F2FS (Flash-Friendly File System)

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 17:17, 25 мая 2016.
F2FS
Полное название Flash-Friendly File System
Содержимое каталога Многоуровневая хэш таблица
Limits
Макс. размер тома 16 тебибайт
Макс. размер файла 3,94 тебибайт
Макс. количество файлов зависит от размера тома
Макс. длина имени файла 255 байт
Features
Даты зарегистрирован modification (mtime), metadata change (ctime), access (atime)
Дата резолюции 1 нс
Признаки POSIX, расширенные атрибуты
Разрешения файловой системы POSIX, ACL
Прозрачное сжатие No
Транспорантное шифрование No
Другие
Операционная система Linux

F2FS[1] (англ. Flash-Friendly File System) – файловая система, ориентированная на использование на флеш-памяти, в том числе оптимизирована для использования с SSD-накопителями, картами памяти (eMMC/SD) и встроенных в различные потребительские устройства флеш-чипов. Автором является Ким Хэ Гык (Kim Jaegeuk, Hangul: 김재극) из корпорации «Samsung». Исходный код F2FS был открыт компанией в октябре 2012, после чего доработан инженерами «Samsung» с учётом замечаний сообщества. Параллельно развивается пакет f2fs-tools, содержащий набор утилит для обслуживания разделов F2FS (mkfs.f2fs, fsck.f2fs). F2FS разработана специально с учётом специфики флеш-памяти и учитывает такие особенности, как неизменное время доступа и ограниченный ресурс количества циклов перезаписи данных.

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 можно выделить :

  • Хранение структур данных организовано в форме журнала, а при обновлении информации используется механизм копирования при записи (Copy-On-Write, COW), при котором при изменении данные не перезаписываются, но сохраняются в новом месте. Метод работы F2FS позволит существенно продлить жизнь флеш-накопителей, поскольку файловая система учитывает внутреннюю геометрию расположения чипов в носителе и работу контроллера. Для снижения износа флеш-накопителя данные по возможности распределяются равномерно, сводя к минимуму повторную запись в одни и те же блоки. С этой целью используется алгоритм последовательного заполнения накопителя, при котором новые данные всегда записываются только в области, следующие после ранее записанных данных, без оглядки на возможную фрагментацию. После достижения конца главы запись начинается с начала, занимая, по возможности, освобождённые блоки. Для исключения конфликтов с логикой контроллера накопителя, в F2FS учитывается специфика работы прослойки FTL (Flash Translation Layer), выполняющего на многих накопителях подобную задачу по равномерному заполнению.
  • Для обеспечения целостности используется модель с фиксацией точек и возможностью отката изменений (roll-back) в случае возникновения проблем.
  • Для адаптации F2FS к различным видам флеш-накопителей, отличающихся своими характеристиками в зависимости от внутренней геометрии и схемы управления, предусмотрен широкий спектр параметров для управления структурой распределения данных в разделе и предоставлена возможность выбора различных алгоритмов очистки и выделения блоков.
  • Раздел F2FS формируется из сегментов размером 2 Мб, сегменты группируются в секции, которые в свою очередь объединяются в зоны.
  • В процессе разработки F2FS учтены проблемы предыдущих специализированных файловых систем на основе структур в форме журнала и приложены все усилия для устранения известных недостатков, таких как большое потребление памяти и высокие накладные расходы при выполнении операций очистки.
  • Файловая система F2FS защищена от «эффекта снежного кома», проявляющегося при использовании Wandering-деревьев: в ситуации, когда вместо перезаписи создаются новые элементы (меняется номер блока), для деревьев, в которых родительский узел ссылается на дочерние узлы, изменение узла приводит к перестройке всех вышележащих узлов.
  • Для ускорения выполнения операций в процессе работы индексы c информацией о распределении данных хранятся в оперативной памяти.
  • Для выполнения операций сборки мусора реализован специальный сборщик, выполняющийся в фоне в моменты простоя системы.
  • В F2FS поддерживается как традиционная для UNIX схема разграничения доступа, так и такие расширенные механизмы, как xattr и POSIX ACL.

Поддержка файловой системы F2FS включена в ядро Linux начиная с 3.8.

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

Подобно большинству файловых систем, 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 года при односекундном разрешении.

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

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

Каталоги

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

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

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

F2FS использует отчасти последовательный поиск и отчасти хеширование для обеспечения схемы простой, достаточно эффективной, и тривиально обеспечивающей стабильность адреса telldir(). Много хэш-кода заимствовано из ext3, однако F2FS пропускает per-directory 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 все журналированы в Checkpoint блоке - который всегда записывается в чекпойнте. Таким образом, когда F2FS свободна для некоторой работы, которую она могла бы оставить FTL, она старается быть дружелюбной и выполняет только случайные обновления блока, когда это действительно нужно. Когда F2FS требуются многочисленные случайные обновления блока. она будет выполнять несколько из них одновременно, чтобы хоть немного снизить нагрузку на FTL.

Производительность

Представлены результаты оценки производительности файловых систем EXT4 и NILFS2 в сравнении F2FS, новой файловой системы для Flash-накопителей, разработанной в компании Samsung. Тестирование проводилось как на обычном ПК с CPU Core i5 2500, так и на смартфоне a Galaxy S3 с прошивкой на базе Android 4.0.4. В обоих конфигурация использовалась SD-карта Transcend 16GB class 10;

Производительность F2FS оказалась выше конкурентов в тестах на случайную и последовательную буферизированную запись, запись cо сбросом буферов через fsync и случайное чтение данных. При оценке времени монтирования лидером стала ФС EXT4, F2FS оказалась на втором месте.[3]

buffered write (1GB file)

Desktop PC Galaxy-S 3
sequential (MB/s) random (IOPS) sequential (MB/s) random (IOPS)
EXT4 7.1 1073 6.7 1073
NILFS2 6.8 1462 4.0 1272
F2FS 10.6 2675 6.9 1682

"write + fsync (100MB file)"

Desktop PC Galaxy-S 3
sequential (KB/s) random (IOPS) sequential (KB/s) random (IOPS)
EXT4 511.8 125 383.4 119
NILFS2 545.2 112 356.7 72
F2FS 1057.9 240 772.3 184

"mounting time"

Desktop PC Galaxy-S 3
1st mount after formating (msec) after rebooting (msec) 1st mount after formating (msec) after rebooting (msec)
EXT4 11 20 20 40
NILFS2 920 1013 1680 1630
F2FS 1486 161 2280 1570

"buffered read (1GB file)"

Desktop PC Galaxy-S 3
sequential (MB/s) random (IOPS) sequential (MB/s) random (IOPS)
EXT4 16.4 1568 9.6 1395
NILFS2 16.6 1609 9.6 1440
F2FS 16.8 1643 9.7 1499

Дополнение: отдельно проведено сравнение производительности VFAT и F2FS:

"buffered write (1GB file), 4KByte write"

Desktop PC Galaxy-S 3
sequential (MB/s) random (IOPS) sequential (MB/s) random (IOPS)
EXT4 7.1 1073 6.7 1073
NILFS2 6.8 1462 4.0 1272
F2FS 10.6 2675 6.9 1682
VFAT 7.3 1108 7.3 1075

"write + fsync (100MB file), 4KByte write"

Desktop PC Galaxy-S 3
sequential (MB/s) random (IOPS) sequential (MB/s) random (IOPS)
EXT4 511.8 125 383.4 119
NILFS2 545.2 112 356.7 72
F2FS 1047.9 240 772.3 184
VFAT 356.5 260 474.4 373

"buffered read (1GB file), 4KByte read"

Desktop PC Galaxy-S 3
sequential (MB/s) random (IOPS) sequential (MB/s) random (IOPS)
EXT4 16.4 1568 9.6 1395
NILFS2 16.6 1609 9.6 1440
F2FS 16.8 1643 9.7 1499
VFAT 16.6 1592 9.6 1501

Ссылки

Примечания

  1. Материал из Википедии-F2FS[1]
  2. Материал из электронного ресурса-Разборки с F2FS-Файлы, иноды и индексирование[2]
  3. Материал из электронного ресурса- Новая файловая система F2FS-[3]