Простой FTL для флешек

FTL — Flash Translation Layer — «драйвер», представляющий флеш-память в виде обычного блочного устройства. Служит для ускорения записи и/или выравнивания износа (wear leveling).

SSD содержат «умный» FTL; USB-флешки и карты памяти содержат «тупой» FTL. Засчёт «тупости» последнего случайная запись сводится к полной перезаписи отдельных Erase Unit’ов, и поэтому происходит ОЧЕНЬ медленно — обычно 2-3 операции в секунду.

Идея: реализовать простой FTL, пригодный к использованию поверх «тупого» флешечного, в виде драйвера на уровне ОС (модуля Linux). Назвать, например, SFTL. Смысл в том, чтобы не тащить лог-структурированность на уровень файловой системы, как это делается сейчас в JFFS2/UBIFS/LogFS/NILFS/F2FS, а, аналогично SSD’шкам, реализовать это в виде отдельного уровня, по сути, превращающего любую файловую систему в лог-структурированную, и кардинального ускоряющего случайную запись.

Плюсы такой идеи:

• Реализация становится сильно проще засчёт отсутствия необходимости писать код и утилиты ФС. А то, блин, ни для одной (!!!) из выше перечисленных ФС, в том числе и для наиболее свежей F2FS, например, нет fsck!
• Поверх транслированного устройства можно использовать любую обычную файловую систему.
• В принципе, с небольшими изменениями можно использовать почти одну и ту же реализацию для MTD и для USB-флешек.
• Если захочется, можно относительно несложно реализовать снимки ФС, аналогично LVM’ской реализации — патчи в код ФС, позволяющие приостановить запись и в заданный момент времени получить консистентное состояние записанных данных и метаданных, в коде ядра уже есть.

Минусы идеи:

• В некотором смысле, это «велосипедик» — частично повторяет, например, функционал самсунговской F2FS. Частично повторяет и функционал других лог-структурированных ФС, но их можно не рассматривать — они сделаны исключительно под MTD и на блочных девайсах не работают.
• Хранение карт отображения ниже уровня ФС приводит к дополнительным накладным расходам — тратится часть места на устройстве и используется дополнительная оперативная память. Частично это решается большим размером блока, но большой размер блока ведёт к большим накладным расходам на хранение мелких файлов и не поддерживается почти ни одной Linux ФС.
• Очень желательно реализовать TRIM и очень желательно, чтобы ФС, гоняемая поверх SFTL, его поддерживала. Хотя это, возможно, и не проблема вовсе — многие ФС в Linux, в том числе ext4, xfs и даже VFAT, его поддерживают, а что ещё нужно джентльмену?
• Сложнее реализовать прозрачное сжатие — оно требует, чтобы ФС понимала, сколько на устройстве реально осталось свободного места. В принципе, чтобы ФС это умела, её можно запатчить, и тогда реализовать.

Типичная скорость работы флешек

Детальное описание внутреннего устройства флешек и карточек памяти есть здесь: https://wiki.linaro.org/WorkingGroups/KernelArchived/Projects/FlashCardSurvey

• Скорость случайного чтения любыми блоками идентична скорости последовательного чтения. То есть, случайное чтение быстрое.
• Последовательная запись блоками по <WRITE UNIT> Кб или большими примерно в 2 раза медленнее чтения такими же блоками. Типичный WRITE UNIT = 32 Кб.
• Последовательная запись блоками, меньшими <WRITE UNIT> примерно в 4 раза медленнее чтения такими же блоками.
• Erase Unit составляет обычно 1/2/4 Мб, а может составлять и больше. Естественно, команды ERASE у USB-флешек нет, но размер блока стирания легко определить, варьируя размер блока при случайной записи.
• Скорость случайной записи очень низка и, независимо от размера блока, составляет обычно 2-3 операции записи в секунду, так как в реальности почти каждая операция ведёт к перезаписи целого Erase Unit’а. При размере блока в 512 байт скорость случайной записи составит всего лишь 1-2 килобайта в секунду!
• Наилучшая скорость чтения/последовательной записи достигается при размере блока ≥ <WRITE UNIT>. Скорость чтения (любого — последовательного, случайного) блоками размера <WRITE UNIT> составляет обычно мегабайты в секунду — 6-12 Мб/с.

Структура хранения

• SFTL использует кластеры по 4096 байт (8 физических секторов).
• Виртуальные адреса кластеров отображаются на физические, кластер может находиться в любом месте флешки.
• Данные отображения каждого кластера содержат его виртуальный адрес, номер версии, магическое число (magic) и контрольную сумму, что вместе составляет 16 байт. При перезаписи кластера старая версия не удаляется — просто записывается новая с увеличенным на 1 номером версии.
• Карты отображения перемешиваются с данными. Информация об отображении 1 кластера занимает 16 байт, следовательно, в 1 сектор (512 байт) входит информация об N=32 кластерах. Совокупность 32 кластеров с данными и 1 индексного сектора называется сегментом.
• Вся флешка состоит из сегментов. То есть, на ней чередуются последовательности по 128 кб данных и 512 байт «индекса». Следовательно, индекс занимает 1/256 всей памяти, что составляет 4 Мб на 1 Гб.

Алгоритм работы

Монтирование

При монтировании с диска читается весь индекс, то есть каждый 257-ой сектор, и все карты (физический кластер -> виртуальный кластер; виртуальный кластер -> {физический кластер, версия}) сохраняются в оперативной памяти. Произвольное чтение с флеш-памяти, будь то FTL’нутая USB-флешка или голый MTD (Memory Type Device), быстрое, следовательно, монтирование тоже происходит быстро. Минус в том, что индекс нужно держать в оперативной памяти, а занимает он примерно 3 мб на каждый 1 гб данных, что составляет уже 192 мб на 64-гигабайтную флешку — довольно много. То есть, применение ограничивается размером потребляемой оперативной памяти — всё как в SSD.

Для больших устройств можно увеличить размер кластера, скажем, до 64 кб — тогда индекс будет занимать в 16 раз меньше — всего 12 мб на 64 гб флешку. При этом, однако, потребуется ФС с таким же размером блока, а в Linux, кроме VFAT, подобных, по сути, нет — есть только ext4 с bigalloc’ом, который до сих пор глючит. Хотя, в принципе, для флешек FAT вполне подходит.

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

Чтение

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

Запись

При записи новой версии кластер, содержащий предыдущую, не очищается, а просто помечается как свободный. Даже при следующем монтировании он будет считаться свободным, так как содержит старую версию блока.

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

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

(2) Решить относительно легко. Тупейший вариант — это, не обращая внимания на фрагментацию, всегда писать в первый доступный свободный кластер. Производительность записи при этом будет падать приблизительно на количество пропущенных при записи (занятых) кластеров внутри каждого Erase Unit’а. То есть цена пропуска кластера примерно равна цене его записи, так как большую часть времени записи занимает стирание.

Более сложный вариант решения: зарезервировать N-1 сегментов и следить, чтобы кроме зарезервированных всегда был как минимум один свободный сегмент. При записи, когда число свободных сегментов будет становится равным N-1, искать и дефрагментировать ближайшие частично свободные сегменты. Резерв нужен для того, чтобы даже в худшем случае дефрагментация удалась. Худший случай — это сборка свободного сегмента из N сегментов, в каждом из которых свободен только 1 кластер — чтобы вместить данные из этих N сегментов, очевидно, нужен N-1 свободный. Цена перемещения данных равна времени их чтения + записи.

С (1) — проблемой фрагментации в целом, общей для всех лог-структурированных ФС — ситуация посложнее. Методы борьбы с ней, в принципе, придуманы. F2FS, например, (а) использует фоновый сборщик мусора (б) пытается разделять запись «холодные», «средние» и «горячие» блоки и (в) пытается чуть умнее обычного выбирать кластер при сборке мусора.