Анатомия файловых систем Linux для флэш-носителей

Разновидности и архитектуры

Вы, скорее всего, слышали о некоторых файловых системах для флэш-носителей, например о JFFS (Journaling Flash File System, журналируемая файловая система для флэш-носителей) или YAFFS (Yet Another Flash File System, альтернативная файловая система для флэш-носителей). Но знаете ли вы, для чего эти системы были придуманы? Данная статья рассказывает о тех из них, которые поддерживаются Linux®, и о том, каким образом эти системы оптимизируют износ, характерный для флэш-памяти, а также дает обзор фундаментальных особенностей доступных на сегодня файловых систем для флэш.

М. Тим Джонс, инженер-консультант, Emulex

M. Тим Джонс (M. Tim Jones) является архитектором встраиваимого программного обеспечения и автором работ: Программирование Приложений под GNU/Linux, Программирование AI-приложений и Использование BSD-сокетов в различных языках программирования. Он имеет опыт разработки процессоров для геостационарных космических летательных аппаратов, а также разработки архитектуры встраиваемых систем и сетевых протоколов. Сейчас Тим работает инженером-консультантом в корпорации Эмулекс (Emulex Corp.) в г.Лонгмонт, Колорадо.



18.11.2008

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

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

Технологические разновидности флэш-памяти

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

Существуют два основных типа флэш-памяти в зависимости от используемой технологии -- NOR (на основе элемента ИЛИ-НЕ) и NAND (на основе И-НЕ). Сначала появилась NOR-память, для которой характерна высокая скорость чтения и небольшие объемы. Более современная NAND-память поддерживает большие емкости и гораздо более высокую скорость записи и стирания. При этом интерфейс ввода/вывода NAND-памяти намного сложнее.

Устройства флэш-памяти как правило имеют внутреннее деление на разделы, доступ к которым может производиться параллельно (например, стирание одного раздела одновременно с чтением из другого). Разделы в свою очередь делятся на блоки размером обычно 64 или 128 Кб. Более того, встраиваемое ПО может рассматривать эти блоки как состоящие из сегментов определенного размера, например, 512 байт (без учета метаданных).

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

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

Обычно операция стирания для NOR-памяти занимает несколько секунд, а для NAND-памяти - миллисекунды. Допустимое количество операций стирания является ключевой характеристикой флэш-памяти. Каждый блок NOR-памяти возможно стирать до 100000 раз, блок NAND-памяти - до миллиона.


Особенности работы с флэш-памятью

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

Сборка мусора

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

Контроль дефектных блоков

Со временем некоторые блоки флэш-носителя иногда становятся дефектными, а некоторые могут быть дефектными сразу после схода с конвейера. Эти блоки нельзя использовать. Они обычно обнаруживаются после неудачной операции над блоком (например, Стирания) или операции записи, при которой возникает нарушение ECC-кода (Error Correction Code, код исправления ошибки).

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

Оптимизация износа

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

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


Вопросы архитектуры

Итак, мы рассказали о флэш-памяти и трудностях при работе с ней. Теперь посмотрим, какие места занимает флэш-память в общей архитектуре системы (рис. 1). Наверху находится слой виртуальной файловой системы (VFS, virtual file system), предоставляющий высокоуровневый интерфейс для приложений. Ниже идет уровень файловых систем для флэш, которые будут рассмотрены в следующем разделе. Далее располагается FTL-уровень (Flash Translation Layer, уровень флэш-преобразования), который занимается управлением флэш-носителем, включая выделение блоков под данные, преобразование адресов, динамическую оптимизацию износа и сборку мусора. В некоторых устройствах часть функций FTL-уровня может быть реализована аппаратно.

Рисунок 1. Общая архитектура файловых систем флэш-носителей
Общая архитектура файловых систем флэш-носителей

Для взаимодействия с флэш-устройствами в Linux применяется интерфейс устройств на основе технологий памяти (Memory Technology Device, MTD). MTD-интерфейс автоматически распознает разрядность шины флэш-устройств и определяет необходимое число таких устройств для получения шины требуемой разрядности.


Файловые системы для флэш-носителей

В Linux доступно несколько таких файловых систем. В следующих разделах вы узнаете об их архитектуре и преимуществах.

Журналируемая файловая система для флэш-носителей

Журналируемая файловая система для флэш-носителей (Journaling Flash File System, JFFS) является одной из первых систем для флэш в Linux. JFFS, в основе структуры которой лежит журнал, предназначалась для NOR-устройств. Система на тот момент являлась уникальной и разрешала множество проблем флэш-носителей, но имела один существенный недостаток.

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

Рисунок 2. Циклический журнал до и после срабатывания сборщика мусора
Циклический журнал до и после срабатывания сборщика мусора

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

Вторая журналируемая файловая система для флэш-носителей (JFFS2, Journaling Flash File System 2)

Снижая срок службы NOR-носителей из-за своего алгоритма оптимизации износа, система JFFS тем не менее довольно широко применялась. В результате было решено переработать ее алгоритм и отказаться от циклического журнала. Так появилась JFFS2, ориентированная на NAND-память. Эта система демонстрирует более высокую скорость работы и имеет функцию сжатия.

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

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

Рисунок 3. Управление блоками и сборка мусора в JFFS2
Управление блоками и сборка мусора в JFFS2

Альтернативная файловая система для флэш-носителей (YAFFS, Yet Another Flash File System)

YAFFS была разработана для флэш-памяти NAND-типа. Первая реализация системы поддерживает устройства, имеющие размер страницы 512 байт, а более новая -- современные носители с большим размером страницы и более серьезными ограничениями записи.

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

Рисунок 4. Сокращение времени монтирования в YAFFS2 за счет снимков
Сокращение времени монтирования в YAFFS2 за счет снимков

Сжатые файловые системы только для чтения

Иногда во встраиваемых системах нет нужды модифицировать данные файловой системы, так как достаточно только чтения. Для этих случаев в Linux предусмотрено несколько файловых систем только для чтения, среди которых наиболее популярные -- это cramfs и SquashFS.

Cramfs

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

В cramfs метаданные хранятся в несжатом виде, а сами данные организованы в виде страниц, каждая их которых сжимается по алгоритму zlib, что дает возможность произвольного доступа к страницам.

Потренироваться в работе с cramfs можно при помощи утилиты mkcramfs и loop-устройства.

SquashFS

Для флэш-носителей в Linux также применяется SquashFS -- еще одна сжатая файловая система только для чтения. Часто ее можно встретить на многих LiveCD-дистрибутивах Linux. В SquashFS используется как сжатие zlib, так и более быстрый и эффективный алгоритм LZMA (от англ. Lempel-Ziv-Markov chain Algorithm).

Как и с cramfs, cо SquashFS можно легко познакомиться посредством mksquashfs и loop-устройства.


Идем вперед

Мир open source не стоит на месте, ПО развивается, и, конечно, ведется разработка новых файловых систем для флэш-носителей. Одна из таких система, LogFS, воплотила многие новейшие идеи и весьма интересна. Например, в LogFS древовидная структура флэш-носителя хранится в самой флэш-памяти, поэтому эта система монтируется так же быстро, как и традиционные файловые системы типа ext2. Для сборки мусора используются алгоритмы блуждающего дерева (разновидность B+-дерева). LogFS примечательна прежде всего тем, что она отлично масштабируется и поддерживает флэш-устройства очень большого объема.

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

Ресурсы

Научиться

  • Оригинал статьи (EN)
  • Прочтите на страницах Википедии о флэш-памяти и ознакомьтесь со списком файловых систем, включающем файловые системы для жестких дисков, распределенные файловые системы и файловые системы специального назначения (в том числе файловые системы для твердотельных накопителей).
  • Узнайте больше о сравнении флэш-памяти NAND- и NOR-типа (EN).
  • Статья Тима "Анатомия файловой системы Linux" (developerWorks, октябрь 2007 г.) знакомит с виртуальной файловой системой (VFS, Virtual File System), ее архитектурой и основными структурами данных. Также статья объясняет общее устройство файловых систем и демонстрирует, каким образом Linux одновременно поддерживает множество файловых систем.
  • Прочитайте эту статью (EN, PDF) и узнайте об отличиях в управлении флэш-памятью в старой JFFS и новой JFFS2.
  • Сравните YAFFS (EN) с другими популярными файловыми системами для флэш-носителей.
  • Новейшие файловые системы LogFS (EN) и UbiFS (EN) преодолевают многие трудности, присущие используемым сегодня файловым системам для флэш-носителей.
  • MTD (Memory Technology Device) (EN) является общей подсистемой для работы с устройствами на основе памяти, в том числе флэш. MTD предоставляет унифицированный интерфейс между низкоуровневыми драйверами устройств и более высоким уровнем файловых систем.
  • Cramfs и SquashFS (EN) -- это сжатые файловые системы Linux только для чтения, которые были созданы для встраиваемых устройств с дефицитом памяти. Однако сегодня SquashFS можно встретить во многих LiveCD-дистрибутивах Linux. Существует файловая система UnionFS (EN), применяемая в некоторых LiveCD, которая поддерживает так называемое объединенное монтирование, при котором несколько файловых систем накладываются друг на друга. SquashFS обладает среди аналогов более эффективным сжатием и лучшей производительностью за счет алгоритма LZMA, и для нее доступны патчи (EN).
  • Читайте все статьи Тима из серии Анатомия... (EN) на developerWorks.
  • Читайте все статьи Тима о Linux (EN) на developerWorks.
  • Найдите множество ресурсов для Linux-разработчиков в разделе Linux developerWorks и посмотрите список самых популярных статей и учебных материалов по Linux (EN).
  • Взгляните на советы и руководства по Linux на developerWorks.
  • Будьте в курсе технических событий и web-вещаний (EN) developerWorks.

Получить продукты и технологии

  • Закажите SEK для Linux (EN) -- набор из двух DVD-дисков с новейшими ознакомительными версиями ПО от IBM: DB2®, Lotus®, Rational®, Tivoli® и WebSphere®.
  • Разработайте ваш следующий Linux-проект с помощью пробного ПО от IBM (EN).

Обсудить

Комментарии

developerWorks: Войти

Обязательные поля отмечены звездочкой (*).


Нужен IBM ID?
Забыли Ваш IBM ID?


Забыли Ваш пароль?
Изменить пароль

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Профиль создается, когда вы первый раз заходите в developerWorks. Информация в вашем профиле (имя, страна / регион, название компании) отображается для всех пользователей и будет сопровождать любой опубликованный вами контент пока вы специально не укажите скрыть название вашей компании. Вы можете обновить ваш IBM аккаунт в любое время.

Вся введенная информация защищена.

Выберите имя, которое будет отображаться на экране



При первом входе в developerWorks для Вас будет создан профиль и Вам нужно будет выбрать Отображаемое имя. Оно будет выводиться рядом с контентом, опубликованным Вами в developerWorks.

Отображаемое имя должно иметь длину от 3 символов до 31 символа. Ваше Имя в системе должно быть уникальным. В качестве имени по соображениям приватности нельзя использовать контактный e-mail.

Обязательные поля отмечены звездочкой (*).

(Отображаемое имя должно иметь длину от 3 символов до 31 символа.)

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Вся введенная информация защищена.


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Linux
ArticleID=352435
ArticleTitle=Анатомия файловых систем Linux для флэш-носителей
publish-date=11182008