Простой FTL для флешек — различия между версиями

Версия 01:40, 22 мая 2013

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

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

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

В идеале запись должна происходит в связное свободное место.

Дополнительная идея: сжатие