DGFS — быстрая файловая система своими руками

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



    Есть мнение, что специализированная read-only файловая система при прочих равных обладает преимуществами перед оной общего назначения т.к:

    1. не обязательно управлять свободным пространством;
    2. не надо тратиться на журналирование;
    3. можно не заботиться о фрагментации и хранить файлы непрерывно;
    4. возможно собрать всю мета-информацию в одном месте и эффективно ее кэшировать;
    5. грех не сжимать мета-информацию, раз уж она оказалась в одной куче.

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

    Задача


    1. 100 млн небольших файлов (по ~8К).
    2. Трехуровневая иерархия — 100 директорий верхнего уровня, в каждой из которых 100 директорий среднего уровня, в каждой из которых 100 директорий нижнего уровня, в каждой из которых 100 файлов.
    3. Оптимизируем время построения и среднее время чтения случайного файла.

    Железо


    В первую очередь, диск: все эксперименты проводятся на выделенном Seagate Barracuda ST31000340NS емкостью 1 Tb.
    Операционная система — Windows XP.
    Процессор: AMD Athlon II X3 445 3 Ггц.
    Память: 4 Гб.

    Характеристики диска


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



    На представленном графике отображены гистограммы времен чтений с диска в произвольных позициях. По оси абсцисс отложена длительность позиционирования и чтения. По оси ординат — число попаданий в корзину шириной в 0.1 msec.

    Обращения к диску производились штатным образом:

    • открытие через CreateFile("\\\\.\\PhysicalDrive1"...);
    • позиционирование через SetFilePointer;
    • и чтение посредством ReadFile.

    Производилось несколько серий замеров, по 10000 в каждой серии. Каждая серия отмечена своим цветом:

    • all — позиционирование идет по всему диску;
    • ½ — только по его младшей половине и т.д.



    А здесь показаны мат. ожидания и ошибки из предыдущего графика, ось абсцисс в логарифмической шкале, например, 1/16 соответствует 4 (1/2**4).

    Какие выводы можно сделать?

    1. В худшем случае (случайный поиск) матожидание одного чтения составляет 13 msec. То есть больше 80 случайных чтений в секунду с этого диска сделать нельзя.
    2. На 1/256 мы впервые видим попадания в кэш.
    3. На 1/1024 в кэш начинает попадать ощутимое количество чтений ~1%.
    4. Больше ничем 1/256 от 1/1024 не отличается, прогон головок уже слишком мал, мы видим только их разгон и (в основном) успокоение.
    5. У нас есть возможность масштабирования, то есть допустимо проводить эксперименты на частично заполненном диске и довольно уверенно экстраполировать результаты.

    NTFS


    Попробуем создать файл размером с диск и получить временные характеристики работы с ним. Для этого создадим файл соизмеримого с файловой системой размера и будем читать его в случайных местах штатными _fseeki64/fread.



    На графике аналогичные представленным ранее гистограммы. А две из них, помеченные как (disc), взяты из предыдущего графика. Парные же им гистограммы, помеченные как (file), получены на основании замеров файловых чтений. Что можно отметить:

    1. Времена близки.
    2. Хотя файл составляет 90% от файловой системы (9хЕ11 байт), чтение из него на полном размере в среднем почти на миллисекунду медленнее.
    3. Дисковый кэш для файла работает лучше, чем для диска.
    4. Появились хвосты в ~6 msec, если худшее время для полного чтения было около 24 msec, то теперь тянется почти до 30. Аналогично и для 1/256. Видимо, метаданные выпали из кэша и их приходится дополнительно читать.
    5. Но в целом чтение из большого файла работает очень похоже на работу с голым диском и в некоторых случаях может ее заменить или эмулировать. Это делает честь NTFS, т.к. например, структура ext2/ext3 требует для файла минимум 4-байтного числа на каждый 4-Kb блок данных:



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

    NTFS с иерархией


    Вспомним уже про нашу тестовую задачу и попробуем решить ее в лоб — средствами файловой системы. Тут же выясняется, что:

    1. Это занимает довольно много времени, на создание одной ветки из миллиона файлов уходит около получаса с тенденцией к постепенному замедлению по мере заполнения диска в соответствии с нашим первым графиком.
    2. Создание всех 100 млн. файлов, следовательно, заняло бы 50+ часов.
    3. Поэтому мы сделаем замеры на 7 млн файлов (~1/16) и отмасштабируемся к полной задаче.
    4. Попытка провести замеры в условиях, более приближенных к боевым, привела к тому, что на 12-м миллионе файлов рухнула NTFS с примерно такой же диагностикой, что получила главная героиня в фильме “Смерть ей к лицу”: — “Вообще-то, раздробленный шейный позвонок, это очень, ОЧЕНЬ плохой признак!”

    Для начала рассмотрим гистограмму в миллисекундах:



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

    • Две серии -— 7 млн как 1/16 задачи и 1 млн для калибровки.
    • В серии 10000 измерений, в корзине 0.5 msec.
    • Общее время 1/16 теста — 7’13’’ то есть матожидание — 43 msec.
    • Общее время 1/100 теста — 5’20’’ то есть матожидание — 32 msec.


    А теперь взглянем на то же в единицах условных seek’ов:



    • Что 1/16, что 1/100, слишком велики, чтобы их сколь-нибудь эффективно кэшировать. А файлы наши слишком малы для фрагментации.
    • Поэтому 1 seek мы должны заплатить за чтение собственно данных. Все остальное — внутренние дела файловой системы.
    • Максимумы приходятся на 3.5 (для 1/100) и 4 (для 1/16) seek’а.
    • А матожидания вообще на 4...5.
    • То есть, чтобы добраться до информации о том, где хранится файл, файловой системе (NTFS) приходится делать 3-4 чтения. А иногда и больше 10.
    • В случае полной задачи, надо полагать, ситуация не улучшится.


    Прототип


    Построим прототип нашей read-only файловой системы:

    1. Состоит он из двух файлов — данных и метаданных.
    2. Файл данных — просто записанные подряд все файлы.
    3. Файл метаданных — В-дерево с ключом — идентификатор файла. Значение — адрес в файле данных и его размер.
    4. Под идентификатором файла понимается закодированный путь к нему. Вспомним, что наши данные расположены в трехуровневой системе директорий, где каждый уровень кодируется числом от 0 до 100, аналогично и сам файл. Вся эта структура упаковывается в целое число.
    5. Дерево записано в виде 4К страниц, применяется примитивное сжатие.
    6. Для того, чтобы избежать фрагментации, указанные файлы приходится создавать в разных файловых системах.
    7. Просто дописывать данные в конец файла (данных) оказывается неэффективно. Чем больше файл, тем дороже обходится файловой системе (NTFS, WinXP) его расширение. Чтобы избежать этой нелинейности, приходится предварительно создать файл нужного размера (900 Гб).
    8. Занимает это предварительное создание больше 2 часов, всё это время уходит на заполнение этого файла нулями, видимо, из соображений безопасности.
    9. Столько же времени занимает и заполнение этого файла данными.
    10. Построение индекса занимает около 2 минут.
    11. Напомним, всего 100 млн файлов, каждый размером около 8К.
    12. Файл индекса занимает 521 Мб. Или ~5 байт на файл. Или ~5 бит на килобайт данных.
    13. Был также опробован вариант индекса с более сложным сжатием (кодами Хаффмана). Занимает этот индекс 325 Мб. Или 3 бита на килобайт данных.

    Далее представлены гистограммы времен, полученные на этих данных:



    • «alone» — под этой меткой идет файл данных, расположенный отдельно от индексного файла, на другом физическом диске;
    • «ogether» — и файл данных и индекс расположены в пределах одной файловой системы на одном физическом диске;
    • «index only» — осуществляется только поиск информации о файле в индексе без чтения собственно данных;
    • «with compr. index» — то же, что и «together», но со сжатым индексом;
    • «compr. index only» — то же, что и «index only», но со сжатым индексом;
    • всего 10000 чтений, шаг гистограммы 0.1 msec.

    Выводы:



    1. Качество сжатия индекса почти не влияет на скорость работы. На разжатие страниц тратится процессорное время, но зато лучше работает кэш страниц.
    2. Чтение индекса выглядит как одно чтение из файла соответствующего размера (см. первый график). Так как 512 Мб — это 1/2000 диска, среднее время seek’а должно быть около 6.5 msec, плюс надбавка за то, что мы читаем из файла, а не напрямую с диска. Судя по всему, это оно и есть. Дерево индекса трех-уровневое, верхние два уровня очень быстро оказываются в кэше, а нижний уровень страниц кэшировать бессмысленно. В результате, любой поиск в дереве вырождается в единственное чтение листовой страницы.
    3. Если файл данных и индексный файл расположены на одном физическом диске, общее время поиска равно двум случайным seek’ам на полное расстояние. Один на чтение данных и один на переход к индексному файлу, который расположен либо в самом начале, либо в самом конце диска.
    4. Если же файлы разнесены по разным устройствам, мы имеем один полный seek на чтение данных и один короткий на поиск в индексе. Учитывая, что индексный файл относительно невелик, напрашивается естественное решение — если нам нужно хранилище в несколько (десятков) терабайт, надо готовить выделенный диск под индекс (SSD) и несколько дисков под данные. Это может быть оформлено как JBOD и внешне выглядеть как обычная файловая система.
    5. Эта схема обладает важной особенностью — гарантированным временем ответа, чего трудно добиться в обычных файловых системах, например, для использования в системах реального времени.

    Здесь самое время спросить — ну хорошо, мы разобрали очень специальный случай регулярно устроенной файловой системы (три уровня с фиксированными именами). А как быть с обычными данными, с обычными путями и названиями?

    Ответ такой — принципиально ничего не изменится. По-прежнему будет один основной индекс. Но устроен он будет немного по-другому.

    Выше идентификатором файла (ключом индекса) был закодированный путь к нему. Так и будет, ключ — строковый полный путь к файлу. Всё остальное в значении — размер, положение, владелец, группа, права…

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

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

    Но ведь пути файлов занимают кучу места? Да, но файлы в одной директории имеют общий префикс, который можно хранить только один раз. Общий суффикс тоже частое явление. Чтобы понять объем данных, которые надо хранить, был проделан ряд экспериментов с путями файловой системы, которые показали, что они с помощью bzip2 (BWT+suffix sort + huffman), сжимаются в среднем в 10 раз. Таким образом, остается 5-6 байт на файл.

    Суммарно можно рассчитывать на 10-16 байт на файл, или ~2 байта на килобайт данных, (если средний файл 8К). На терабайтный файл надо 2 гигабайта индекса, обычный 64-гигабайтный SSD-диск, следовательно, способен обслужить 32 терабайта данных.

    Аналоги


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

    Примерным аналогом можно считать использование СУБД для хранения данных. В самом деле: храним содержимое файлов как BLOB’ы, а метаданные, как атрибуты таблицы. Просто и изящно. СУБД сама заботится о том, как поэффективнее расположить файлы в доступном ей дисковом пространстве. Сама создает и поддерживает все нужные индексы. Плюс приятный бонус — мы можем менять наши данные без ограничений.
    Однако:

    • В конечном счете, СУБД всё равно обращается к диску, напрямую или через файловую систему. А это таит опасность, стоит недоглядеть и — бац! время работы замедлилось в разы. Но, допустим, у нас идеальная СУБД, с которой этого не произойдёт.
    • СУБД не сможет сжать префиксы столь же эффективно просто в силу того, что не рассчитана на read-only режим.
    • То же самое можно сказать и про метаданные — в СУБД они будут занимать гораздо больше места.
    • Больше места — больше чтений с диска — медленней работа.
    • Использование хэш-кодов от пути файла не решает проблемы т.к. соответствие пути хэш-коду всё равно надо где-то хранить просто для того, чтобы обеспечить возможность просмотра содержимого директории. Выльется всё в то, что придется воспроизвести структуру файловой системы средствами СУБД.
    • Файлы размером больше страницы будут принудительно разбиты СУБД на части, и произвольный доступ к ним будет осуществляться в лучшем случае за логарифмическое от размера файла время.
    • Если мы можем просто разместить все метаданные на выделенном SSD диске, в случае СУБД сделать это будет намного сложнее.
    • Про гарантированное время отклика можно забыть.

    Транзакционность


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

    Итого


    Итак, представлен прототип read-only файловой системы, который прост, гибок, решает тестовую задачу и при этом:

    • демонстрирует максимально возможную на отведенном для него железе производительность;
    • его архитектура не накладывает объективных ограничений на объем данных;
    • дает понять, что следует делать, чтобы получить файловую систему общего назначения, а не заточенную под конкретную задачу поделку
    • дает понять, в какую сторону стоит двигаться для того, чтобы сделать нашу файловую систему инкрементально изменяемой.
    2ГИС 195,33
    Карта города и справочник предприятий
    Поделиться публикацией
    Комментарии 33
      +3
      Все же хотелось увидеть сравнение с другими single file virtual filesystem. Как говорится, не squashfs единым. Есть еще whefs, libgsf и т.д.
        0
        согласен, но не всё сразу
        +3
        Вот что бывает когда BigData пытаются запихнуть в бытовое решение. Это как борцу тяжеловесу влезть в пачку балерины…
          +3
          Понятие BigData оно отчасти психологическое, я сам определяю что можно решить с помощью кавалерии, а когда нужна тяжелая артиллерия.
            0
            То что вы приводите — это уже скорее массовая ковровая бомбежка кассетными бомбами.
              0
              Не понял аллегории. Бомба то одна. И не ядерная.
                0
                Файлов зато много.
                  +1
                  Если что — я вас не минусовал, меня и самого некисло слили недавно. :-)
            0
            А для обычного пользователя под Win 7 можно что-то сделать? На одном из дисков 400 тысяч мелких файлов в 70 Gb. Когда туда лезешь — система заметно подтормаживает. Индексацию выключил. Можно поставить на этот диск свою файловую систему так, чтобы OS её понимала?
              +1
              что-то вроде Solid File System
                0
                Как вариант можно сделать отдельный раздел для этой кучи файлов. Если к папке доступ не постоянный это чуток решает проблему. (Но когда туда нырнёте тормоза будут практически такие же.)

                Если раздел создать нет возможности\желания можно создать образ диска и монтировать его.

                Если это у вас выкаченный сайт, можно скомпилировать в один chm.

                  0
                  Если честно, то это выкачаная флибуста после небольшой чистки «под себя». Книги одним словом. Про них особо не вспоминаешь, но вот когда вспоминаешь, так это именно после того, что тормозить начало. И мысли, что места вся эта мелочь занимает кучу просто так.
                  0
                  Попробуйте PrimoCache. Она, хоть и бета, но помогает — хотя, конечно, от размеров и расположения файлов многое зависит.

                  Там в настройке есть две фичи, которые вас порадуют:

                  1. Можно указать, что вы хотите видеть ровный поток данных на запись, даже если готовы подождать указываемое время: скажем, ставите 5 (а может — и 60) секунд, и много меньше переживаете, что пиковая работа с множеством файлов поставит на попа всю систему — за 60 секунд все планируемые изменения имеют шанс записаться и с меньшим напрягом I/O.
                  2. Можно под кеш выделить отдельный раздел либо диск, которые будут очищены и уйдут только под эту задачу. Это, конечно, не кеши ZFS :), но кой-какая польза вам будем: 60 или 120 Гб SSD отлично справится с задачей (и, наверняка, объемом) кеширования, и вам не придется перекраивать всю ФС.

                  Я бы на вашем месте попробовал. По поводу что прога платная: она давно платная и давно бета, так вот на их форуме раз в сколько-то дней выкладывают ключик на следующие 90 дней работы (вроде как чтобы бета-тестеры не платили за лицензии) — не забывайте только их вводить. Как только ключик кончает действие, так кеш отключается, и работаете по старинке, без него, т.е. ничего не разваливается.

                  Сам, кстати, использую именно первую из упомянутых фич, чтобы сделать равномерным поток записи на SSD и тем уменьшить wear-out. Пока доволен :)

                  P.S. www.romexsoftware.com/en-us/primo-cache/
                    0
                    Спасибо. Надо будет глянуть.
                      0
                      Простите… А у вас все эти файлы в одном каталоге лежат, или по немного объектов в немногих каталогах, но с большой вложенностью?

                      Просто если у вас NTFS (а чему бы там еще быть?), то при небольшом количестве записей в каталоге они сохранятся прямо в записи в MFT (small indexes), при большем числе — будет организовано нерезидентное хранение каталога (large indexes), что нагрузит I/O. Если Вы храните ваши файлы по многу на том же диске, что и всю систему, тормоза прямо просятся.

                      Я бы на вашем месте, наверное, выделил бы под хранение отдельный раздел (раз объем известен, логично откромсать от основного диска нужное кол-во гогов (не забудьте накинуть хотя бы процентов 30, чтобы NTFS эффективно работала с файлами), отформатировать в NTFS, и туда уже переложить книги. А, если есть возможность, под такие дела купить SSD на 120 Гб, и радоваться ))
                        0
                        Файлы на отдельном физическом диске. И к ним обращаешься редко. Смысла SSD им давать нет. Просто архив в свете того, что из Сети начали пропадать то одно, то другое. Но совсем их забекапить и отложить в сторонку тоже не хочется. Иногда заглядываю за книгой или цитатой.

                        Думал, что есть нечто для такого случая специфическое. Но по видимому возня не стоит времени и сил.
                  0
                  Для того, чтобы избежать фрагментации, указанные файлы приходится создавать в разных файловых системах.

                  Почему? Индекс же можно записывать на ФС после предварительной подготовки основного файла.
                    0
                    Речь шла о замерах и необходимости исключить случайное влияние. А так да.
                    +3
                    Это делает честь NTFS, т.к. например, структура ext2/ext3 требует для файла минимум 4-байтного числа на каждый 4-Kb блок данных:
                    То есть, надо дополнительно тратить по байту на каждый килобайт данных, на терабайт выходит гигабайт, а закэшировать гигабайт не так то просто. Впрочем, в ext4 такой проблемы, по-видимому, нет, или она замаскирована с помощью экстентов.

                    Для справки: в NTFS расположение файла на диске кодируется пофрагментно (каждый непрерывный кусок файла на диске описывается одной структурой). Если файл нефрагментирован, будет одна структура на весь файл, если файл разбит на два куска «первые N кластеров файла расположены в кластерах [A,A+N-1] диска, последние M кластеров — в кластерах [B,B+M-1] диска», то будут две структуры, кодирующие пары (N,A) и (M,B-A) соответственно, и так далее. Кодирование использует переменную длину, отбрасывая ведущие нули или FFки.
                      0
                      Спасибо, как то так и предполагал. С другой стороны, сильно фрагментированыые файлы в такой схеме начнут требовать индексации этих структур.
                    • НЛО прилетело и опубликовало эту надпись здесь
                        0
                        У нас DGFS, но это неофициальное название.
                        • НЛО прилетело и опубликовало эту надпись здесь
                        0
                        Граф сериализуете? :)
                          0
                          Дерево :)
                            0
                            А не пробовали mem mapped файл?
                              0
                              Всё что касается памяти ограничено в размерах.
                              В данной статье скорее делалось сравнение — вот есть 100млн мелких файлов, что нам может предложить штатная
                              файловая система и можно ли сделать это быстрее.
                              Ключевая мысль — пользовательская структура файловой системы это часть данных а не часть архитектуры файловой системы.
                              Дерево — отличный объект, с которым умеют работать в базах данных.
                              Так давайте смотреть на файловую систему как на единое дерево где путь к файлу — ключ, а содержимое файла — значение в едином дереве.
                                0
                                Собственно, почему я заинтересовался. ОС Фантом, над которой я работаю — ОС с персистентной памятью. И мотивация у меня ровно вот такая: стейт современного приложения = граф, и заперсистить его в ФС = всегда война, немцы, потеря времени и здравого смысла. Вместо этого ОС просто гарантирует приложению, что ничего в файл писать не надо, "просто оставь это здесь", оно никуда не денется. Ограничения в размере адресного пространства — это следующий вопрос. В 32 бит они есть, а в 64 уже, считай, не будет. Но — технически это всё реализовано как persistent paging, то есть в традиционных ФС аналог такой техники — memory mapped file. Отсюда мне было бы интересно знать, какая производительность получается, в сравнении с сериализациями графа/дерева в традиционную/оптимизированную ФС, если его положить в mem mapped file. Я полагаю, что характеристические оценки скорости для такого подхода будут оценкой сверху для производительности дисковой подсистемы ОС Фантом.
                                  0
                                  Мemory mapped file — это такой персональный кусочек свопа, ос выделяет сегмент и мапит его виртуальную память на диск. Как клиент будет работать с этой памятью ос не знает и потому действует довольно консервативно. Скорость чтения из него ограничена физическими возможностями диска.

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

                                  В вашем случае клиент не распоряжается политикой распределения виртуального адресного пространства, а система распоряжается, но понятия не имеет как было бы оптимальнее с точки зрения клиента.
                                  Можно подумать лишь о том, как более эффективно использовать дисковый кэш при чтении из свопа.
                                    0
                                    Очевидно. Но, по сути, (как и в процессоре) операции записи нас волнуют примерно никак (степень их отложенности — только вопрос надёжности), а операции чтения мы можем хинтовать — достаточно из параллельной нити трогать данные, которые нам вскорости понадобятся, и пейджинг их подгонит. В этом смысле ничего не меняется по сравнению с "ручной" работой с диском, нет?
                                      0
                                      Отчасти так, но мы не знаем в какой последовательности данные потребуются пользователям. Пользователи зачастую знают, но у них нет средств подсказать системе.
                                      Фактически все сведется к случайному чтению/записи диска и бороться с этим бессмысленно.
                                      Хотя, для SSD дисков проблема не столь катастрофична.

                                      А вообще, ваша персистентная память до боли напоминает работу СУБД:

                                      • ядро — СУБД
                                      • процесс — connection
                                      • страница изменилась — update, делаем копию, заносим в ремап, пишем лог
                                      • ос периодически сохраняет состояние процесса — коммит
                                      • время от времени checkpoint с очисткой лога,
                                      • упали — подняли своп — перечитали лог — сбросили лог
                                        0
                                        Может, дать процессам ручку — чтоб они сами себе коммит делали, когда считают это правильным?
                                        И системе легче и пользователи начнут жить в другой парадигме.
                                          0
                                          Адресное пространство общее. "Коммит" тоже общий. Но, вообще говоря, вместо этого можно иметь вызов "дождаться снапшота". Который может, в частности, приближать его наступление.

                        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                        Самое читаемое