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

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

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

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

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

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

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

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

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

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

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

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

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

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

Об авторе

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