Log-структурированные файловые системы — каждому SSD

Валерия Аврора (Valerie Aurora, formerly Henson)
Перевод Алексея Федорчука, версия 2, причёсанная
Оригинал, 18 октября 2009

От переводчика. Эту статью следует рассматривать как введение в тему файловых систем для твердотельных накопителей любого рода. Она написана ещё до широкого распространения SSD-накопителей, но в преддверии его, и потому сохраняет актуальность.

Введение

Когда речь заходит о log-структурированной файловой системе, большинство разработчиков устройств хранения сразу вспомнит классическую работу Остерхаута (Ousterhout) и Розенблюма (Rosenblum) The Design and Implementation of a Log-structured File System — и почти двух десятилетиях последующих попыток решить неприятную проблему очистки сегмента (см. ниже), за ней последовавших.

Разработчики Linux могли бы подумать о JFFS2, NILFS или LogFS, трёх из нескольких современных log-структурированных файловых систем, специализированных для использования на твердотельных устройствах (SSD). Мало кто, однако, вспомнит о прошивках SSD, хотя flash translation layer (FTL) в современных полнофункциональных SSD в ряде важных аспектов сходен с log-структурированной файловой системой. Экстраполяция исследований log-структурированных файловых систем позволяет нам определить, как получить для SSD максимальную производительность. В частности, полная поддержка команд TRIM, на уровне как SSD, так и файловой системы, будет иметь ключевое значение для поддержания долгосрочной пиковой производительности большинства SSD.

Что такое log-структурированная файловая система?

Log-структурированные файловые системы, как ни странно, произошли от обычных журналируемых файловых систем (logging или journaling file systems). Журналируемая файловая система является нормальной системой write-in-place в стиле ext2 или FFS, отличаясь только наличием журнала записи операций. Далее, в остальной части документа, будет использоваться термин журналируемая файловая система, чтобы избежать путаницы между «логируемыми» и «log-структурированными» файловыми системами).

Журналируемая файловая система хранит на диске состояние файловой системы путём последовательного занесения итога каждой операции записи в журнал (хранящийся в энергонезависимой памяти), прежде чем записать изменения в место их постоянного хранения в файловой системе. Эти или записи журнала содержат достаточно информации, чтобы повторить всю процедуру, если прямая запись в файловую систему прерывается, например, при сбое системы. Эта операция называется восстановлением по журналу. Так что, в общем, все изменения в файловой системе записываются на диск дважды: один раз в журнал, и второй — по месту постоянной дислокации.

Примерно в 1988 году Джон К. Остерхаут (John K. Ousterhout) сотоварищи поняли, что вторую запись можно пропустить полностью, если обращаться ко всей файловой системе как к одному огромному журналу. Вместо того чтобы записывать изменения в журнал, а затем переписывать их по месту постоянного хранения на диске, можно просто один раз дописать данные в конец журнала, где они и останутся. Запись изменений существующих файлов и инодов выполняется copy-on-write — пространство, занятое старой версией, помечается как свободное, а новая версия дописывается в конец занятого пространства. Концептуально, поиск текущего состояния файловой системы — воспроизведение журнала от начала до конца. На практике, log-структурированная файловая система периодически записывает на диске точки проверки (checkpoints): они сохраняют состояние файловой системы на момент их записи, не требуя обращения к журналу. Любые изменения в файловой системе после очередноой точки проверки выделяют путём воспроизведения относительно небольшого количества записей в журнале, следующих за ней.

Одним из интересных преимуществ устройства log-структурированной файловой системы (LFS) является то, что большинство операций записи в файловую систему являются последовательными. Раздел, описывающий мотивацию для Sprite LFS, созданную почти 20 лет назад, показывает, как мало изменилось в мире устройств хранения:

За последнее десятилетие скорость процессоров резко возросла, в то время как время доступа к диску уменьшается медленно. Эта тенденция, вероятно, сохранится и в будущем, и это станет тормозом для всё большего и большего числа приложений.
[…]
Log-структурированные файловые системы основаны на предположении, что файлы кэшируются в оперативной памяти и, что с увеличением объёма памяти кэш будет всё более эффективно удовлетворять запросы на чтение. В результате в дисковом трафике будут преобладать операции записи.

Но подождите, почему мы все ещё говорим о диске? Накопители SSD полностью изменили эксплуатационные характеристики устройств хранения! Диски мертвы! Да здравствует флэшка!

Удивительно, но, когда речь заходит о SSD, log-структурированные файловые системы оказываются более актуальными, чем когда-либо. Основной принцип log-структурированной файловой системы — «дешёвое» чтение и «дорогая» запись (с точки зрения ресурсов), — это категорически верно и для ячеек флэш-памяти SSD на основе NAND .(Далее в этой статье термин «флэш» относится к флэш-памяти на основе NAND вообще, а термин SSD — к флэш-устройствам NAND с выравниванием износа и сбором для записи с flash translation layer). Флэшка может считывать данные небольшими порциями — в несколько сот байтов, — но записывать должна большими непрерывными блоками, порядка десятков тысяч или сотен тысяч байт. Запись на флэшку делается в два шага. Сначала весь блок очищается с установкой неких значений для всех бит (обычно 1, вопреки интуиции). Затем отдельные биты в блоке возвращаются обратно в 0, пока вы не получите желаемый блок.

Log-структурированные файловые системы оказываются очень подходящими для флэшек. Одна из особенностей log-структурированного дизайна — то, что в журнал записываются большие непрерывные куски, называемые «сегментами», размером порядка нескольких мегабайт. Чтобы сократить накладные расходы на изменение метаданных и получить лучшую производительность, записи в журнале собираются и записываются последовательно в полностью свободные сегменты. Большинство сегментов в каждый момент времени частично заняты и частично свободны, так что прежде чем записывать в такой сегмент, нужно собрать в нём данные и переместить в другой. Когда файловая система нуждается в свободных сегментах, она сначала очищает существующие частично занятые сегменты, перемещая все находящиеся на нём данные на другой свободный сегмент — в основном это «сборка мусора» (garbage-collects). После этого файловая система может выполнить одну большую потоковую запись в свободный сегмент. Такая система сегментов и их очистки — именно то, что необходимо для эффективной записи на флэш-устройство, с учётом необходимости удаления больших непрерывных блоков с флэшки перед записью на неё.

Совпадение между log-структурированными файловыми системами и флэшками очевидно, когда вы смотрите на файловые системы, написанные для «голых» флэшек — то есть, для устройств без контроллеров выравнивания износа или сбора для записи. Файловые системы, которые должны управлять стиранием блоков и другими деталями «железа» флэшки, почти всегда имеют log-структурированный дизайн. Наиболее используемой из таких файловых систем для Linux является JFFS2, применяемая во многих встроенных устройствах, таких как билетные автоматы и развлекательные системы в самолётах. Не раз я, сев в самолёт, видела сообщения об ошибках флэшки JFFS2 в развлекательных системах на спинках кресел. (К сожалению, для многих тысяч людей логотип Tux теперь будет, вероятно, ассоциироваться с невозможностью смотреть телевизор при дальних на перелётах).

Для SSD, предстающих как блочные устройства дискового стиля — это ныне большинство накопителей потребительского класса — операционки используют обычную файловую систему для обмена с SSD посредством интерфейса блочных устройств (то есть, прочитать блок #37 в этот буфер, записать этот буфер в блок #42, и т.д.). Тем не менее, эта система содержит логический эквивалент log-структурированной файловой системы, которая просто скрыта внутри SSD. Прошивке, которая реализует выравнивание износа, сбор для записи, и любые другие подобные функции, приходится решать те же проблемы, что и log-структурированной файловой системе.

Большинство производителей SSD отказываются раскрывать какие-либо подробности их внутренней прошивки, но мы можем быть уверены, что она имеет много общего с log-структурированной файловой системой. Во-первых, единственный эффективный способ реализации случайной записи в буфер и записи из буфера является их совместная запись в единый блок стирания. Это требует очистки стираемого блока, перемещения всех задействованных блоков в другую область накопителя, и поддержание соответствия между логическим расположением блоков и их физическим расположением — именно того, что делает log-структурированная файловая система. Во-вторых, когда мы действительно из научных публикаций узнаём детали устройства SSD, оно выглядит как log-структурированная файловая система. В-третьих, когда мы смотрим на тестирование долгосрочной производительности SSD, мы видим ту же картину её снижения с течением времени, что и в log-структурированных файловых системах. Подробнее мы поговорим об этом в следующем разделе.

Производительность log-структурированных файловых систем

Log-структурированные файловые системы сегодня являются «родными» для флэш-накопителей, хотя в 1990 году казалось, что они имеют большой потенциал и как дисковые файловые системы. Однако, как всем известно, мы не используем log-структурированные файловые системы на дисках в ноутбуках и серверах. Почему?

Коротко говоря, log-структурированные файловые системы показывают относительно хорошую производительность, пока очистка сегментов — перемещение реальных данных из сегмента для его повторного использования — в основном может выполняться в фоновом режиме, когда файловая система не была занята «реальной» работой. Первая (после основополагающей) большая статья об LFS [PDF] показала, что производительность LFS деградирует до 40% относительно расчётного идеала при реальных значениях занятости диска, соотношении памяти и дискового пространства и трафика файловой системы. Короче говоря, в стационарном состоянии файловая система тратит значительное количество времени обращения к диску на очистку сегментов — перемещение старых данных из сегмента перед его использованием для новых записей. Эта проблема очистки сегментов было предметом активных исследований в течении десяти лет, но ни одно из решений не смогло превзойти файловые системы write-in-place при практическом использовании диска. Это можно сравнить с «уборкой мусора» при управлении памятью; когда память используется мало и с латентностью всё в порядке, удобство garbage collection перевешивает требования к производительности. Но при высокой степени использования диска — уже при 50% — затраты на очистку и периодические простои в ожидании освобождения пространства становятся проблемой.

В первой статье об LFS было показано, что ключ к хорошей производительности log-структурированных файловых систем в том, что пустые сегменты должны создаваться примерно так же быстро, как и использоваться. Скорость записи в файловую систему ограничивается скоростью очистки сегментов. Худший случай наступает тогда, когда файловая система заполнена на X%, и каждый сегмент также заполнен на X%. Производство одной операции очистки сегмента требует сбора данных по формуле:

N = ceiling(1/(1-X))

сегментов и записи старых данных N-1 из этих сегментов. При использовании диска на 80%, получаем:

N = ceiling(1/(1 - .80)) = 1/.20 = 5

сегментов для очистки. Если размер сегмента составляет 1 МБ, мы должны были бы прочитать

5 * 800KB = 4MB

найденных данных и записать последовательно 4 МБ, прежде чем мы могли бы записать 1 МБ новых данных. (Примечание для педантов: Я использую МБ и КБ в степени 10, а не 2).

Напротив, лучший случай — это файловая система с двумя типами сегментов, полностью заполненными и совершенно пустыми. Лучший шаблон — такой, при котором изменяются все метаданные и данные в одном сегменте, так что когда записаны новые версии, старые версии удаляются, и весь сегмент снова становится пустым. Реальность лежит где-то между этими двумя случаями. Цель log-структурированной файловой системы — в создании бимодального распределения использования сегмента: большинство сегментов должны быть или сильно заполненными, или почти пустыми, при этом заполненные сегменты имеют тенденцию не изменяться. Оказывается, что достичь этого трудно.

К SSD предъявляется дополнительное требование — обеспечить выравнивание износа. Даже в лучшем случае, когда много сегментов заполнено на 100%, и изменения данных в них не записываются, SSD все равно должны иногда перемещать эти сегменты, потому что расширение записи происходит поверх каждого доступного блок флэш-памяти. Это в некоторых случаях добавляет дополнительное перемещение сегмента и делает достижение хорошей производительности даже сложнее, чем в log-структурированных файловых системах на обычных дисках.

Впрок ли урок?

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

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

Одно из самых больших упущений для оптимизации с помощью уроков, полученных от log-структурированных файловых систем, является медленное внедрение поддержки TRIM для SSD. TRIM — это команда для блочного устройства, информирующая его о том, что определенный диапазон блоков больше не используется файловой системой — в основном вызовом free() для блоков. Как уже говорилось ранее, наилучшая производительность достигается, когда пустые сегменты создаются как побочный эффект текущей записи. В качестве простого примера, представьте себе, что сегмент содержит только один индексный дескриптор файла, а всё остальное — данные файла. Если следующая порция для записи в файловую систему перезаписывает все данные файла (и индексный дескриптор в качестве побочного эффекта), этот сегмент становится полностью свободным, и файловая система не должна реально перемещать какие-либо данные перед его повторным использованием. Эквивалентное действие для SSD — это запись в блок, который уже был перезаписан ранее. Внутренне SSD знает, что старая копия этого блока сейчас свободна, и блок может использоваться без копирования его данных в другое место.

Но log-структурированные файловые системы имеют явное преимущество по сравнению с до-TRIM’овыми SSD, а такими были почти все коммерчески доступные SSD на сентябрь 2009 (ныне практически все они TRIM поддерживают — А.Ф.). Log-структурированная файловая система знает, когда область данных на диске стала свободной, даже если она не перезаписывалась. Рассмотрим случай с удалением односегментного файла: весь сегмент освобожден, но никакой перезаписи не было. Log-структурированная файловая система знает, что это произошло, и теперь имеет свободный сегмент для работы. Все же SSD видят несколько маленьких записей для других блоков на диске. Они по прежнему считают, что блоки, использовавшиеся ныне удаленным файлом, всё ещё содержат данные, используемые файловой системой, и нужно продолжать перемещение этих данных. Так как каждый блок устройства был записан по крайней мере один раз, SSD обречены на худший случай в отношении производительности, в котором и запасные блоки, и данные должны быть перемещены каждый раз, когда новый блок вовлекается в использование.

Как мы уже видели, ключ к хорошей производительности log-структурированной файловой системы — наличие свободных или почти свободных сегментов. SSD без поддержки TRIM не знает о многих свободных сегментах, что вызывает огромный недостаток производительности, поэтому то, что SSD поставляются без функции TRIM, просто шокирует. Я думаю, что SSD изначально тестировались на производительность только с файловыми системами write-in-place (кхе, кхе, NTFS) и при низкой степени их использования (скажем, 70% или меньше).

К сожалению, TRIM в его нынешнем виде и спроектирован, и реализован очень плохо: команды TRIM не тэгированы и SSD тратит несколько сотен миллисекунд для выполнения команды TRIM. Разработчики ядра обсуждают, как именно реализовать поддержку TRIM, на Linux Plumbers Conference, на Linux Storage and File System Workshop, и в списках рассылки: какова удельная производительность каждой операции TRIM, как они должны дробиться, как часто выполняться, и хорошо ли забыть или пропустить команды TRIM. На мой взгляд, состояние использован/свободен для блока на устройстве, поддерживающем TRIM, должно отслеживаться так же тщательно, как и страницы памяти. Реализация файловой системы может принимать форму явно синхронных вызовов alloc()/free(), либо асинхронной «сборки мусора» (во время проверки файловой системы или выполнения очистки), но мы не должны допускать утечки используемых блоков по всем тем же причинам, что и утечки памяти. Кроме того, в идеальном мире, TRIM будет переработан или заменен командой, которая будет полнофункциональной, хорошо продуманной первоклассной составляющей спецификации ATA, а не хаком существующей ситуации.

Конечно, всё это умозрительные рассуждения при отсутствии деталей реализации от производителей SSD. Возможно, некоторые программисты прошивок SSD придумали совершенно новые алгоритмы для ремаппинга и сбора для записи, которые не похожи на все log-структурированные файловые системы, и характеристики производительности и оптимизации, которые мы видели до сих, просто кажутся совпадающими с log-структурированными файловыми системами. Тем не менее, до сих пор кажется, что исправление SSD по способу, поддерживаемому log-структурированной файловой системой, способствовало бы получению высокой производительности. Полная поддержка TRIM как SSD, так и файловыми системами будет иметь ключевое значение для высокой производительности в долговременной перспективе.