В эпоху облачных вычислений широко распространены распределенные системы хранения. Но вы когда-нибудь задумывались о том, как они хранят данные внутри? Ответ явно неоднороден, но позвольте мне рассказать вам о том приключении, которое у нас было при разработке того, как самое быстрое и самое масштабируемое устройство резервного копирования с дедупликацией в мире собиралось это сделать.

Почему естественный, первый выбор стал помехой

Когда мы начали создавать устройство резервного копирования NEC HydraStor как 9LivesData еще в 2003 году, очевидным выбором для хранения данных на дисках было использование ext3 - самого популярного Linux файловая система в то время. Однако наша последующая борьба за обеспечение максимальной производительности и использования хранилища доказала, что этот подход неоптимален. Оказалось, что стандартная файловая система POSIX может быть не лучшим выбором, поскольку она предоставляет множество ненужных функций, но не дает нам некоторых функций, которые мы действительно хотели. Несколько примеров:

  • Было действительно сложно точно сказать, сколько данных ext3 еще может принять, поэтому защита от нехватки места стала сложной. Что ж, statfs может сказать нам, сколько блоков еще доступно, но знаете что? Они также будут использоваться для непрямых блокировок. Таким образом, одноблочное добавление может занимать от 1 до 4 блоков на устройстве, в зависимости от того, к какому файлу мы добавляем. Не говоря уже об изменении размера учетной директории при создании или удалении файлов. Удачи в отслеживании!
  • ext3, как и любая файловая система, устойчивая к сбоям питания, использовала внутренний журнал. Однако в NEC HydraStor мы выполняли транзакции на нескольких дисках / разделах, поэтому в любом случае нам нужен был собственный журнал более высокого уровня. Это привело к так называемому двойному ведению журнала: каждый пользователь, выполняющий запись, создавал запись об обновлении метаданных в нашем журнале, затем при фактической записи ext3 повторно регистрировал ее
    , и только после этого обновление было окончательно записано в целевое местоположение. Да, можно сказать, обновления метаданных небольшие, но перезапись даже одного блока размером 4 КиБ здесь и там на вращающемся диске вызывает серьезные задержки и падение пропускной способности, поскольку головка диска должна много перемещаться.
  • Мы не могли сказать пользователю, что его данные были постоянными, сразу после возврата вызова записи. Даже открытие файла с флагом O_DIRECT не гарантирует этого. Чтобы быть уверенным, нам пришлось либо использовать флаг O_SYNC, либо вызывать fsync после каждой записи. Но это увеличило бы задержку. Жаль, что мы не могли просто сказать пользователю «ОК» после того, как файловая система занесла в журнал обновления метаданных и сбросила данные, не дожидаясь применения журнала. Однако ни один API не позволил нам его пропустить.
  • Обычно мы писали большие файлы (несколько мегабайт), поэтому забота ext3 о маленьких файлах нам мешала. Нам не нужно было разделить раздел на группы размещения 128 МиБ, чтобы обеспечить параллельное размещение множества крошечных файлов. Вместо этого мы предпочли бы хранить все данные ближе к началу диска, так как это было размещено на внешнем крае пластин жесткого диска, на котором было ок. Линейная скорость в 2 раза выше, чем на другом конце.
  • Когда какая-либо файловая система переполнялась, было сложно избежать ее быстрого старения. А в случае загрузки HydraStor почти полных дисков фрагментация ext3 резко возросла.

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

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

Наконец, мы решили столкнуться с нашей судьбой и раздвинуть границы производительности и управляемости HydraStor, следуя наиболее многообещающему подходу: заменив ext3 на наш собственный уровень файловой системы, IMULA (полученный из оптимизации для неизменяемого большие файлы). Следите за обновлениями, чтобы узнать, как это произошло.

Как началась наша экспедиция

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

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

Как бы вы к этому подошли? Обратите внимание, что типичная рабочая нагрузка HydraStor состоит в основном из:

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

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

Итак, с этим подходом у нас есть две противоречивые цели: большие экстенты и экстенты, близкие к своим предшественникам. Как достичь обоих? Давайте просто воспользуемся несколькими порогами размера, чтобы решить эту проблему. А именно, мы можем сначала найти ближайший экстент размером не менее 1024 блоков. Если это не удается, давайте попробуем 256, затем 32 и один блок в конце.

Но ждать! Мы забыли о важной оптимизации: хранить данные как можно ближе к началу. Итак, давайте добавим дополнительный, первый шаг к этому алгоритму: поиск ближайшего экстента из 1024 блоков в некоторой начальной части диска. Но что должно означать «начальная часть»?

Представьте, что мы переписали все данные в самое начало раздела. Звучит реально, правда? Итак, почему бы не выбрать общую занимаемую площадь в качестве размера «начальной части»? Что ж, это привело бы к проблемам фрагментации почти полных разделов в этой начальной части. Итак, чтобы избежать этого, давайте просто уменьшим это количество до 120% от общего количества занятых блоков.

Следуя этим рассуждениям, мы подготовили алгоритм распределения, который выглядел примерно так:

  • найти ближайший экстент после текущего «указателя распределения» размером не менее 1024 блоков в пределах начальной части диска размером = общее занимаемое пространство * 120%.
  • в случае неудачи попробуйте сделать то же самое для всего раздела.
  • затем найдите ближайший свободный экстент во всем разделе с минимальным размером 256 блоков, затем 32 блока и, наконец, 1 блок.
  • как только вы найдете какой-то экстент, не забудьте обновить указатель выделения до его конца.

Затем пришло время для тестирования. Мы отслеживали пропускную способность нескольких шаблонов записи с помощью этого распределителя и прототипной реализации пользовательских операций. Вот диаграмма, показывающая относительное сравнение IMULA (синий) и ext3 (красный), каждый из которых работает на четырех жестких дисках. Графики масштабируются по горизонтали на тот же промежуток времени и имеют линейный вертикальный масштаб:

Как видите, наш первый подход был в 2–4 раза лучше, чем ext3, и это неплохой результат, не правда ли?

Но фрагментировал ли он пространство с течением времени? Чтобы проверить это, мы смоделировали заполнение диска до 99% емкости, затем удалили случайные 5% блоков данных, снова наполнили их новыми данными до 99%, снова удалили 5% и так далее. Как наша новая блестящая идея могла работать в таком стрессе? Давайте посмотрим:

На этой диаграмме показано, как изменилось распределение количества экстентов на файл за эти 20 циклов удаления и заполнения. После 20 циклов наш алгоритм распределения обычно сохраняет около 4 экстентов на файл. Это составило средний размер экстента 3 МБ. Учитывая тот факт, что этого размера было достаточно, чтобы амортизировать время поиска при доступе к данным, наша первая идея оказалась весьма удачной.

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

Заполнение деталей

Итак, у нас был распределитель блоков, что еще нам нужно было реализовать, чтобы наша «файловая система» работала?

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

Бесплатная карта

В идеале бесплатная карта могла работать только в памяти (мы надеялись на небольшую фрагментацию, не так ли?), Но требование поддержки быстрого обновления на месте с ext3 вынудило нас сохранить размер базового блока на уровне 4 КиБ и быть готовым. для высокой начальной фрагментации. К счастью, эксперименты показали, что наш новый блестящий распределитель с течением времени снизил высокую начальную фрагментацию при использовании стандартной рабочей нагрузки HydraStor. Это была отличная новость, но все же мы должны были быть готовы к устаревшей структуре файлов и должны были написать код, удаляющий метаданные на диск, по крайней мере, временно. Таким образом, даже несмотря на то, что мы могли восстановить всю свободную карту из последовательно читаемой таблицы inode, нам все еще нужен был какой-то «бесплатный файл карты» на диске, по крайней мере, для подкачки.

Зная, что нам нужны «страницы» свободной карты, мы разделили диск на «группы». Чтобы сохранить свободный размер файла карты постоянного размера, мы решили сохранить описания групп в виде растровых изображений свободных блоков (как это делают ext3 и некоторые другие файловые системы). Это привело к естественному размеру группы 128 МиБ - так как это размер, соответствующий количеству блоков, покрытых одним блоком битов.

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

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

Каждый кружок внизу представляет максимальный свободный размер экстента в одной группе. Благодаря этому подходу каждый свободный обход карты требовал не более O (log G + g) процессорного времени (где g - размер группы, а G - количество групп) и не более одного ввода / вывода. Операция O (при необходимости получить группу с диска). Обратите внимание, что мы также сделали наши структуры достаточно компактными для памяти, что помогло сохранить как можно больше информации в ОЗУ.

Вот изображение, иллюстрирующее дизайн бесплатной карты:

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

Теперь давайте перейдем к следующему краеугольному камню каждой файловой системы: метаданным файла.

Таблица индексных дескрипторов

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

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

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

Файл таблицы Inode обычно имеет несколько гигабайт на многотерабайтных дисках. Это было довольно много для чтения при запуске, поэтому мы решили сохранить его фактическое содержимое в компактном виде. Мы сделали это, разделив этот файл на сегменты фиксированного размера и сохранив минимальное количество активных сегментов (то есть те, которые мы должны были прочитать при запуске). Обратите внимание, что это разделение не было статичным, как в случае с Free map - каждый индексный дескриптор мог храниться в любом сегменте. Фактически, это могло храниться в нескольких из них в разных версиях. Читая сегменты в правильной последовательности, мы убедились, что самая последняя версия индексного дескриптора считывалась последней. Это была последовательность заполнения корзин данными, которая хранилась в заголовке таблицы индексных дескрипторов. Также обратите внимание, что устаревшие версии inodes, несмотря на то, что они хранятся в некоторых потенциально активных сегментах, не способствовали их заполнению.

Как сделать так, чтобы количество активных сегментов было небольшим? Что ж ... Нам приходилось использовать их повторно, когда это было возможно. Итак, как правило, при сбросе обновлений из журнала мы просто выбираем ведро с наименьшим заполнением и переписываем его содержимое вместе с новыми данными в новое ведро. Чтобы сделать это возможным, нам нужно было только убедиться, что некоторое ведро заполнено не более чем наполовину и что одно активное ведро было пустым. Это, в свою очередь, можно сделать, просто установив желаемое количество активных сегментов на число, способное хранить вдвое больший объем активных данных плюс один. Набор активных сегментов был скорректирован на лету до рассчитанного желаемого числа путем простого выбора между 0, 1 или 2 сегментами, которые должны быть перезаписаны вместе с обновлениями, выгруженными из журнала.

Вот диаграмма, показывающая структуру таблицы Inode. Обратите внимание на дублированный заголовок (для устойчивости к сбоям питания во время обновления одного из них):

Конечно, мы не забыли и о кешировании inodes в памяти. Мы сделали это для двух списков LRU (для чистых и грязных inodes), так что доступ к ним в общем случае был быстрым.

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

Достигнув цели

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

По общему признанию, через несколько лет после того, как мы внедрили IMULA, основные файловые системы, такие как ext4, также улучшили свою производительность, а XFS даже догнала наши результаты. Однако они намного сложнее, и все равно будет довольно сложно настроить их под нашу рабочую нагрузку по сравнению с полностью контролируемыми настройками, которые мы создаем. Не говоря уже о реализации пользовательских функций на уровне файловой системы…

Этот подход также использовался другими системами. Одним из наиболее известных является Ceph, который недавно представил свою новую серверную часть хранилища «BlueStore» в качестве замены устаревшего «FileStore». .

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

Благодарности

IMULA не был бы реализован так хорошо без Марека Допьера, Михала Велницкого, Рафала Вията, Кшиштофа Лихота, Марцина Добжицкого и Витольда Кренцицкого, которые внесли свой вклад в этот проект, не только я. Большое им всем спасибо!

Первоначально опубликовано на 9livesdata.com 2 октября 2018 г.