Постоянство: деревья данных хранятся как деревья каталогов

Question

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

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

Answer 1

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

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

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

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

Answer 2

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

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

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

Answer 3

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

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

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

Answer 4

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