Разборки с F2FS

Нейл Браун (Neil Brown)
Перевод Алексея Федорчука. версия 2, причёсанная
Оригинал, 10 октября 2012

От переводчика. Это на сегодняшний день наиболее полное описание файловой системы F2FS. В ней рассматривается именно та её реализация, которая была передана в исходных текстах разработчикам ядра Linux (которые включили её в версию 3.8. Перед прочтением настоятельно рекомендуется ознакомиться с работой Валерии Авроры про log-структурированные файловые системы, иначе кое-что здесь будет не понятно — вне зависимости от степени владения (или не владения) английским.

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

F2FS — это «Дружественная к Флэшкам Файловая система» (flash-friendly file system), новая файловая система для Linux, недавно анонсированная инженерами Samsung. В отличие от jffs2 и LogFS, F2FS ориентирована не на твердотельные накопители как raw-устройства, а на обычные носители типа SSD, eMMC, SD-карты и другие — те, что уже имеют встроенный FTL (Flash Translation Layer). В ответ на то, что «железо» становится умнее, мы должны разрабатывать ещё более умный софт для управления им, то есть «умный в превосходной степени». Похоже на воспитание, не так ли?

F2FS основана на дизайне log-структурированной файловой системы (LFS), что неудивительно, учитывая требования флэш-накопителей. Для тех, кто не знаком с log-структурированным дизайном, перечислю его основные элементы:

  1. Требование копирования при записи (copy-on-write), так что данные всегда записываются в ранее неиспользуемое пространство.
  2. Это свободное пространство выделяется в больших «регионах», доступных для непрерывной записи. Когда число таких «регионов» уменьшается, сохраняющиеся ранее записанные данные собираются из нескольких «регионов» в одну свободную, чем создаётся больше свободных «регионов». Этот процесс называется чисткой (cleaning) и является одним из самых ресурсоёмких при log-структурировании.

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

Особенность F2FS, оправдывающая её название как Дружественной к Флэшкам, — то, что она собирает блоки в отдельные куски, которые будут записаны одновременно и последовательно, что ей сделать легче, чем FTL. Вместо создания одного большого куска для записи, F2FS фактически создаёт до шести параллельно записываемых кусков. Как мы увидим, при этом создаются различные виды блоков с различным сроком существования. Группировка блоков с похожими характеристиками предназначена для облегчения требуемой LFS «сборки мусора» (garbage collection).

«Масштабируемость» является важным качеством — F2FS не всегда записывает непрерывными потоками, но к этому стремится. Некоторые метаданные, а иногда даже некоторые данные, записываются случайными единичными блоками. Это было бы неприемлемо для обычной log-структурированной файловой системой, но F2FS позволяет избежать сложности, делая небольшие обновления при необходимости, оставляя остальную работу FTL.

Прежде чем перейти к подробностям того, как F2FS делает то, что делает, дадим список того, что она не делает.

Так, от файловой системы copy-on-write мы могли бы ожидать «дешёвых» снапшотов, за счёт сохранения старой копии. F2FS не даёт такой возможности, и не способна на это в ее нынешнем виде из-за сохранения метаданных в двух местах, что будет подробно описано позже.

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

Блоки, сегменты, секции и зоны

Подобно большинству файловых систем, F2FS состоит из блоков. Все блоки имеют размер 4 КБ, хотя он неявно связан с размером системной страницы. Так что для архитектур IA64 и PowerPC это вряд ли будет верно. Адресация блоков 32-битная, так что общее количество адресуемых байт в файловой системе не более 2(32+12) байт, или 16 терабайт. Для нынешних объёмов флэш-накопителей это не является существенным ограничением.

Блоки собираются в сегменты, состоящие из 512 блоков — размером 2 МБ. Документация описывает это как умолчание (которое можно изменить), но этот размер довольно глубоко встроен в код. Каждый сегмент содержит резюмирующий блок, содержащий список принадлежности каждого блока в сегменте (файла плюс смещение). Резюме в основном используется при очистке, для определения, какие блоки нуждаются в перемещении и как после этого должны обновляться иноды. В одном резюмирующем блоке могут комфортно размещаться данные для обычных 512 блоков (оставляя немного дополнительного пространства для других целей), так что 2 МБ — естественный размер сегмента. Больше было бы непрактично, меньше — расточительно.

Сегменты собраны в секции. Размер их определяется гибко, но должен быть степенью двойки. Секция соответствует «региону» в терминах log-структурирования. Секция, как правило, заполняется от начала до конца, прежде чем начинается заполнение другой секции. Очистка секции также происходит одновременно. По умолчанию при использовании утилиты mkfs размер 20, или один сегмент на секцию.

F2FS имеет шесть секций, открытых для записи, в каждую из которых в любое время могут записываться различные виды данных. Различные секции позволяют хранить содержимое файлов отдельно от инодов, а также разделять их на «горячие», «теплые» и «холодные» в соответствии с изменяемой эвристикой. Например, каталоги рассматриваются как «горячие», и хранятся отдельно от файлов данных, поскольку они имеют разную «продолжительность жизни». «Холодные» данные, как ожидается, останутся неизменными в течение достаточно долгого времени, так что секции, заполненные «холодными» блоками, скорее всего, не потребуют очистки. Иноды, определённые как «горячие», согласно ожиданиям, будут обновляться ​​в ближайшее время, так что по прошествии короткого времени секция, заполненная «горячими» инодами, будет содержать очень мало «живых» блоков, и, следовательно, легко очищаться.

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

Эти зоны, заполненные секциями сегментов из блоков, составляют «главную область» файловой системы. Существует также «мета-область» файловой системы, которая содержит различные метаданные, такие как уже упомянутые резюмирующие блоки. Эта область не управляется обычными log-структурными линиями и, таким образом, оставляет больше работы для FTL. Она достаточно мала, так что это не создаёт проблем.

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

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

Третий способ — выделение удвоенного объёма на каждый блок в двух различных местах, так что он состоит из двух экземпляров, первичного и вторичного. Из них только один является «живым» в данное время, а «не-живой» просто обновляется после copy-on-write по запросу LFS. Этот подход к метаданным является главным препятствием для создания снапшотов. F2FS журналирует небольшое количество обновлений в этой группе при создании точек проверки (checkpoint), которые могут несколько облегчить задачи FTL.

Файлы, иноды и индексирование

Большинство современных файловых систем используют B-деревья или аналогичные структуры для управления индексами при поиске блоков файла. Для btrfs B-деревья столь важны, что этой структуре данных она обязана своим названием. Для F2FS это не так.

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

В F2FS используется дерево индексов, которое очень напоминает оригинальную файловую систему Unix и её потомков, например ext3. Индексный дескриптор (инод) содержит список адресов начальных блоков файла, некоторые адреса косвенных блоков (которые сами по себе содержат дополнительные адреса), а также некоторых вторичных и третичных косвенных блоков. Если ext3 содержит 12 прямых адресов и по одному на каждый из косвенных адресов, то в F2FS имеется 929 прямых адресов, по два косвенных и дважды косвенных адреса, и один третичный косвенный адрес. Это позволяет адресовать для одного файла почти 4 ТБ, или четверть максимального размера файловой системы.

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

Очевидно, что все это требует немного большего размера инода, чем таковой в ext3. Копирование при записи весьма неудобно для объектов, которые меньше, чем размер блока, так что F2FS резервирует для каждого инода полный блок в 4 КБ, обеспечивая достаточно пространства для индексирования. Здесь остаётся даже место для хранения (базового) имени файла, или одного из его имен, вместе с инодом родительского файла. Это упрощает восстановление недавно созданных файлов во время восстановления после сбоя и уменьшает количество блоков, которые должны быть записаны для такого файла для его сохранности.

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

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

Удивительно, но, кажется, в иноде не нашлось достаточно места для хранения 64-разрядной временной метки, так что вместо запаса в несколько веков на будущее при наносекундном разрешении, обеспечивается только запас до 2038 года при односекундном разрешении. Этот просчёт был отмечен в рассылке LWN http://lwn.net/Articles/519032/ и может быть исправлен в будущих релизах.

Одной из неудобных особенностей любой файловой системы с copy-on-write является то, что всякий раз при записи блока его адрес изменяется, так что его родитель в индексном дереве должен измениться и переместиться, и так далее, вплоть до корня дерева. Журналируемая природа LFS означает, что прокрутка вперёд во время восстановления может восстановить последние изменения в индексации дерева, так что все изменения не должны записываться сразу. Но в конце концов они должны быть записаны, что увеличивает работу при чистке.

Это еще одна область, в которой F2FS использует лежащий в его основе FTL. Среди содержимого «мета-области» имеется NAT (Node Address Table) — таблица адресов узлов. Здесь слово «узел» относится к инодам и косвенно индексируемым блокам, а также к блокам, используемым для хранения расширенных аттрибутов (xattr). Когда адрес инода хранится в каталоге, или индекс блока хранится в иноде или ином индексе блока, это не блок хранимых адресов, а смещение в NAT. Фактический адрес блока хранится в NAT по этому смещению. Это означает, что, когда блок данных записан, мы все еще нуждаемся в обновлении и записи узла, который указывает на это. Но запись этого узла требует только обновления начала NAT. NAT является частью метаданных, он использует два местоположения журнала (которые зависят от FTL для сбора записи), и поэтому не требует дальнейшей индексации.

Каталоги

F2FS на самом деле не предъявляет никаких особых требований к расположению каталогов, за исключением изменения возможно меньшего количество блоков, что в любом случае способствует производительности. Таким образом, мы можем оценить структуру каталогов F2FS в равных условиях с другими файловыми системами. Основная цель заключается в обеспечении быстрого поиска по имени файла, а также в обеспечении стабильности адреса каждого имени, которое может быть представлено с помощью telldir ().

Оригинальная файловая система Unix (когда она стала поддерживать 256-байтные имена файлов) использовала ту же схему каталогов, что и ext2 — последовательный поиск файлов среди всех записей каталога. Это просто и эффективно, но не очень хорошо масштабируется на большие каталоги.

Более современные файловые системы, такие как ext3, XFS, btrfs, использующие различные схемы, включающие B-деревья, иногда индексированные по хэшу имени файла. Одна из проблем с B-деревьями заключается в том, что иногда узлы должны быть разделены, и некоторые записи каталога могут быть перемещены в файл. Это создаёт дополнительные проблемы обеспечения стабильного адреса для telldir () и, вероятно, причиной того, что telldir () часто называют убогим интерфейсом.

F2FS использует отчасти последовательный поиск и отчасти хеширование для обеспечения схемы простой, достаточно эффективной, и тривиально обеспечивающей стабильность адреса telldir (). Много хэш-кода заимствовано из ext3, однако F2FS использует некий seed для директории. Этот seed является тайным случайным числом, которое гарантирует, что хэш-значения, разные в каждом каталоге, не предсказуемы. Использование такого seed обеспечивает защиту от столкновения хешей.

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

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

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

Суперблоки, точки проверки и другие метаданные

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

Собственно fs2fs_super_block, который хранится во втором блоке устройства, содержит только данные read-only. После создания файловой системы он никогда не будет изменяться. В этом суперблоке описывается размер файловой системы, размеры сегментов, разделов и зон, сколько места было выделено на различные части «мета-области», и другие мелкие детали.

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

Ранее мы уже упоминали таблицы адресов узлов (NAT) и область резюме сегмента (SSA), которые также входят в «мета-область» наряду с суперблоком (SB) и точками проверки (CP). Ещё один элемент метаданных называется таблицей информации о сегментах — SIT (Segment Info Table).

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

Когда для NAT или SIT требуются обновления, F2FS не делает их немедленно, но хранит их в памяти до записи следующей точки проверки. Если обновлений относительно немного, то они не записываются в их окончательное «место обитания», но вместо этого журналируются в некоем свободном пространстве в резюме сегмента блоков, которые записываются в это время. Если общее количество обновлений, требуемых для резюме сегмента блоков, достаточно мало, даже если они еще не записаны, то обновления SIT, NAT и SSA журналируются в блоке точки проверки, который всегда записывается в неё. Таким образом, когда F2FS свободна для некоторой работы, которую она могла бы оставить FTL, она старается быть дружелюбной и выполняет только случайные обновления блока, когда это действительно нужно. Когда F2FS требуются многочисленные случайные обновления блока. она будет выполнять несколько из них одновременно, чтобы хоть немного снизить нагрузку на FTL.

Знать, когда завязывать

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

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

Обзаведусь ли ею я?

Файловая система F2FS содержит ряд интересных идей, и ряд направлений для возможного улучшения — и то, и другое привлекательно. Однако предстоит выяснить, будет ли соответствовать реальность обещаниям. Одна из сложностей в том, что параметры F2FS (такие, как размер секции и зоны) должны быть настроены для конкретного устройства флэш-памяти и ее FTL; производители же, как известно, скрывают, как именно их FTL работает. F2FS также требует, чтобы флэш-накопитель имел шесть и более одновременно «открытых» областей записи. Это не может быть проблемой для Samsung, но является таковой для среднего техно-гика — хотя Арнд Бергман (Arnd Bergmann) провёл некоторые исследования, которые могут оказаться полезными. Если же до народа доходят отчеты результатам работы F2FS, не настроенной должным образом для данного устройства хранения, это может быть вредно для проекта в целом.

F2FS включает ряд оптимизаций, направленных на облегчение нагрузки на FTL. Было бы очень полезно выяснить, насколько они фактически приводят к сокращению числа операций записи. Это поможет подтвердить, что оптимизация полезна или, напротив, не требуется. Так, сбор статистики о том, как часто «выстреливают» различные оптимизации, поможет укрепить уверенность в файловой системе.

F2FS кажется, была написана без особого расчёта на распараллеливание рабочих нагрузок. В частности, все представления запросов на запись осуществляется в рамках единого семафора. Так, вероятно, F2FS — это не файловая система для обработки больших объёмов данных на 256-ядерной «рабочей лошадке». Однако она должна прекрасно показывать себя на мобильных устройствах еще немало лет.

И, наконец, требуется ещё много тестов. Некоторые предварительные измерения производительности были опубликованы, но для объективного сравнения действительно нужны и «зрелость» файловой системы, и различные варианты рабочих нагрузок. Надеюсь, кто-то найдёт время на такое тестирование.

Между тем, я бы использовал F2FS? Учитывая, что мой телефон является столь же игрушкой, сколь и рабочим инструментом, подозреваю, что да. Правда, перед этим в первую очередь я хотел бы убедиться в наличии надёжных бэкапов. Но потом… Я, вероятно, всё равно сделаю это.