Настойчивость:Деревья данных, хранящиеся в виде Деревьев каталогов

Question

Мне было интересно узнать о практичности хранения древовидной структуры в памяти в виде дерева каталогов для целей сохранения.В моем случае целевой файловой системой будет ZFS, и как только структура будет создана, к ней будут нечасто обращаться несколько процессов.

Насколько эффективно использование дерева каталогов в качестве механизма сохранения для деревьев данных?

Answer 1

Чтобы читать и писать свое дерево, вы будете вызывать файловую систему несколько раз для каждого узла. Это намного дороже, чем любой здравомыслящий код, который вы можете придумать для обхода образа памяти.

Разумный ли это подход зависит от того, каким будет ваш шаблон использования. Если при типичном вызове вашего кода вы ожидаете прочитать всю древовидную структуру, поработайте над этим, а затем запишите его полностью - вам лучше собрать его в один файл. Однако, если вы ожидаете читать / работать с / мутировать только нескольких узлов, без чтения в большей части дерева, разница в производительности между обходом структуры каталогов и выполнением нескольких операций поиска / чтения для обхода дерево, хранящееся в одном файле, будет намного меньше, и вполне возможно, стоит сделать первое для простоты / ясности / избежания повторного изобретения колес. Более того, если несколько процессов делают это одновременно, блокировка узлов и поддеревьев становится намного проще с подходом на основе каталогов.

Помните, что для некоторых обычно используемых файловых систем время открытия записи в каталоге зависит от общего количества записей в каталоге.

РЕДАКТИРОВАТЬ: я делал подобные вещи с ext3 для CGI-интерфейса сайта; не изобретая колесо, мы сделали прототип более быстрым и простым в обслуживании, масштабирование операций чтения / записи / блокировки довольно хорошо, , но очень частые изменения - порядка сотен в секунду - самой структуры каталогов плохо работали на реальном хранилище ; в конце я реструктурировал вещи так, чтобы разделы дерева каталогов, к которым очень часто добавлялись / удалялись записи каталогов, оказались на томе tmpfs - для меня этот набор состояний можно (дорого) восстановить из того, что хранится в менее энергозависимом хранилище после перезагрузки. У меня мало опыта работы с ZFS, и я не знаю предполагаемый шаблон использования, поэтому не знаю, будет ли это проблемой для вас. Если бы я сейчас делал это для очень интенсивно используемого сайта, я бы, вероятно, вместо этого свернул свою собственную библиотеку именованных блокировок.

Answer 2

Большинство файловых систем оптимизированы для доступа к открытому файлу, поэтому открытие / закрытие файла занимает значительное время. Если каждый лист вашего дерева маленький, чтение / запись всей структуры займет много раз дольше, чем необходимо.

Кроме того, большинство файловых систем имеют минимальный блок выделения, обычно около 2-8 КБ. если ваши листья будут намного меньше, вы потеряете много места.

Короче говоря, чем меньше ваши листья, тем хуже идея.

Answer 3

Если я правильно понимаю, вы говорите о построении древовидной структуры, которая дала бы представление вашей файловой системы в коде, поэтому я подозреваю, что в начале, когда вы читаете в древовидной структуре, у вас возникнут дополнительные затраты, но последующие поиски и обходы дерева, вероятно, будут быстрее, чем попадание на диск каждый раз.

Answer 4

Возможные проблемы:

• Это может привести к неэффективному использованию дискового пространства (во многих файловых системах каталог является файлом и как таковой занимает целый блок на диске ...)
• Чтение / запись будет медленным, потому что вы совершаете много обращений к файловой системе
• Файловая система может / будет налагать ограничения на длину имени каждого элемента и / или символов, которые вы можете использовать для имен
• Другим процессам будет легко повредить ваши данные и / или потребуются значительные затраты на блокировку
• При использовании твердотельных `дисков" это может привести к большему количеству операций записи, чем при использовании других методов, и сократить срок службы носителя

Итог:возможно, оно того не стоит.