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

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

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

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

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

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

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

• SFTL использует кластеры по 4096 байт (8 физических секторов).
• Виртуальные адреса кластеров отображаются на физические, кластер может находиться в любом месте флешки.
• Данные отображения каждого кластера содержат его виртуальный адрес, номер версии, магическое число (magic) и контрольную сумму, что вместе составляет 16 байт. При перезаписи кластера старая версия не удаляется — просто записывается новая с увеличенным на 1 номером версии.
• Карты отображения перемешиваются с данными. Информация об отображении 1 кластера занимает 16 байт, следовательно, в 1 сектор (512 байт) входит информация о 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 вполне подходит.

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

Чтение

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