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

Материал из YourcmcWiki
Перейти к: навигация, поиск
м (Идея)
м (Запись)
 
(не показаны 4 промежуточные версии этого же участника)
Строка 8: Строка 8:
  
 
Плюсы такой идеи:
 
Плюсы такой идеи:
* Главный плюс — реализация ПРОСТА. Засчёт отсутствия необходимости писать код и утилиты ФС. А то, блин, '''ни для одной''' (!!!) из вышеперечисленных ФС, в том числе и для наиболее свежей F2FS, например, нет fsck! Типа они все такие лог-структурированные и сбое-устойчивые. Хотя для F2FS обещают, что fsck когда-то будет.
+
* Главный плюс — реализация относительно проста засчёт отсутствия необходимости писать код и утилиты ФС. А то, блин, из всех вышеперечисленных ФС fsck только недавно появился для наиболее свежей F2FS.
 
* Поверх транслированного устройства можно использовать любую обычную файловую систему. Или даже не файловую систему, а, например, raw tablespace для СУБД. Хотя это может потребовать дополнительных фич — например, барьеров.
 
* Поверх транслированного устройства можно использовать любую обычную файловую систему. Или даже не файловую систему, а, например, raw tablespace для СУБД. Хотя это может потребовать дополнительных фич — например, барьеров.
 
* В принципе, с небольшими изменениями можно использовать почти одну и ту же реализацию FTL для MTD и для USB-флешек.
 
* В принципе, с небольшими изменениями можно использовать почти одну и ту же реализацию FTL для MTD и для USB-флешек.
Строка 14: Строка 14:
  
 
Минусы идеи:
 
Минусы идеи:
* Главный минус — дублирование кода аллокатора блоков между FTL и файловой системой, и двойной объём работы. Ведь карты распределения блоков УЖЕ есть у файловой системы в виде информации о том, какие блоки каким файлам принадлежат, а при наличии FTL карты дублируются, что приводит к лишним накладным расходам — и месту на устройстве, и занятой оперативной памяти, и лишней работе, которую должен делать процессор. То есть, в общем, все эти накладные расходы всегда есть и в SSD’шках — но там они выполняются на отдельном процессоре и работе основной системы не мешают.
+
* Главный минус — дублирование кода аллокатора блоков между FTL и файловой системой, ведь карты распределения блоков УЖЕ есть у файловой системы в виде информации о том, какие блоки каким файлам принадлежат. Это ведёт к следующим проблемам:
 +
** Двойной расход занятого места на устройстве и в оперативной памяти.
 +
** Двойной объём работы, выполняемый процессором. В общем, эти накладные расходы всегда есть и в SSD’шках — но там они выполняются на отдельном процессоре и работе основной системы не мешают.
 +
** Худшая статистика — для FTL доступна только статистика на уровне блоков, в то время, как файловая система располагает статистикой на уровне файлов, каталогов и т. п. и потенциально может лучше прогнозировать правильное размещение блоков.
 
* Это, в некотором смысле, «велосипедик», частично повторяющий, например, функционал самсунговской F2FS. Частично повторяет и функционал других лог-структурированных ФС, но их можно не рассматривать — они сделаны исключительно под MTD и на блочных девайсах не работают.
 
* Это, в некотором смысле, «велосипедик», частично повторяющий, например, функционал самсунговской F2FS. Частично повторяет и функционал других лог-структурированных ФС, но их можно не рассматривать — они сделаны исключительно под MTD и на блочных девайсах не работают.
 
* Аналогично SSD, очень желательно реализовать TRIM и очень желательно, чтобы ФС, гоняемая поверх SFTL, его поддерживала. Хотя это, возможно, и не проблема вовсе — многие ФС в Linux, в том числе ext4, xfs и даже VFAT, его поддерживают, а что ещё нужно джентльмену?
 
* Аналогично SSD, очень желательно реализовать TRIM и очень желательно, чтобы ФС, гоняемая поверх SFTL, его поддерживала. Хотя это, возможно, и не проблема вовсе — многие ФС в Linux, в том числе ext4, xfs и даже VFAT, его поддерживают, а что ещё нужно джентльмену?
Строка 29: Строка 32:
 
* Наилучшая скорость и чтения, и последовательной записи достигается при размере блока &ge; <WRITE UNIT>. Скорость чтения (любого — последовательного, случайного) блоками размера <WRITE UNIT> составляет обычно мегабайты в секунду — 6-12 Мб/с.
 
* Наилучшая скорость и чтения, и последовательной записи достигается при размере блока &ge; <WRITE UNIT>. Скорость чтения (любого — последовательного, случайного) блоками размера <WRITE UNIT> составляет обычно мегабайты в секунду — 6-12 Мб/с.
  
Отличия флешек от MTD с точки зрения нашего FTL:
+
Отличия флешек от MTD с точки зрения FTL:
 
* На MTD можно с одинаковой скоростью писать в любой стёртый сектор (что, разумеется, удобнее). На флешках так делать нельзя, а можно держать лишь максимум LIMIT (~6) активных регионов.
 
* На MTD можно с одинаковой скоростью писать в любой стёртый сектор (что, разумеется, удобнее). На флешках так делать нельзя, а можно держать лишь максимум LIMIT (~6) активных регионов.
 
* Зато при записи на флешки можно не обращать внимания на Erase Unit’ы — этим занимается её внутренний FTL. Если конкретно:
 
* Зато при записи на флешки можно не обращать внимания на Erase Unit’ы — этим занимается её внутренний FTL. Если конкретно:
** Можно очищать блоки мелкими порциями, в то время, как на MTD нужно очищать и стирать Erase Unit целиком. Размер сегмента, не кратный размеру Erase Unit (как у нас — 128.5 Кб), использовать при этом можно — просто потребуется при очистке затрагивать ещё и пограничные сегменты.
+
** Можно очищать блоки мелкими порциями, в то время, как на MTD нужно очищать и стирать Erase Unit целиком. Размер сегмента, не кратный размеру Erase Unit (как в прошлых идеях — 128.5 Кб), использовать при этом можно — просто потребуется при очистке затрагивать ещё и пограничные сегменты.
 
** Можно не делать динамического Wear-Leveling’а (то есть WL перезаписываемых данных) на уровне блоков стирания — флешечный FTL делает это сам. Однако, флешки обычно не двигают статические данные, поэтому может потребоваться Static Wear Leveling. Кроме того, отдельные кластеры внутри всех блоков стирания должны записываться равномерно — нельзя, например, всегда записывать 1-ый сектор каждого Erase Unit’а в 10 раз чаще остальных.
 
** Можно не делать динамического Wear-Leveling’а (то есть WL перезаписываемых данных) на уровне блоков стирания — флешечный FTL делает это сам. Однако, флешки обычно не двигают статические данные, поэтому может потребоваться Static Wear Leveling. Кроме того, отдельные кластеры внутри всех блоков стирания должны записываться равномерно — нельзя, например, всегда записывать 1-ый сектор каждого Erase Unit’а в 10 раз чаще остальных.
  
Строка 39: Строка 42:
 
* Предлагается использовать кластеры по 4096 байт (8 физических секторов).
 
* Предлагается использовать кластеры по 4096 байт (8 физических секторов).
 
* Виртуальные адреса кластеров отображать на физические. Кластер может находиться в любом месте флешки.
 
* Виртуальные адреса кластеров отображать на физические. Кластер может находиться в любом месте флешки.
* Данные отображения каждого кластера содержат его виртуальный адрес, номер версии, магическое число (magic) и контрольную сумму, что вместе составляет 16 байт. При перезаписи кластера старая версия не удаляется — просто записывается новая с увеличенным на 1 номером версии.
+
* Данные отображения каждого кластера содержат его физический адрес, виртуальный адрес и номер версии, что вместе составляет 12 байт и лимитирует объём устройства 2^44 байт, то есть 16 Тб. При перезаписи кластера старая версия не удаляется — просто записывается новая с увеличенным на 1 номером версии; кроме того, номер версии позволяет понять, в каких секторах лежат «горячие» данные, а в каких «холодные». В одном 512-байтном блоке помещаются карты для 42 кластеров + контрольная сумма. Таким образом, карты всех блоков занимают примерно 3/1024 ёмкости диска.
* Карты отображения перемешиваются с данными. Информация об отображении 1 кластера занимает 16 байт, следовательно, в 1 сектор (512 байт) входит информация об N=32 кластерах. Совокупность 32 кластеров с данными и 1 индексного сектора называется сегментом.
+
* В самом начале диска находится суперблок; далее сохраняются карты отображения, с округлением занятого пространства вверх до размера Erase Unit’а. Благодаря наличию динамического WL внутри флешки частая перезапись этих первых Erase Unit’ов пугать нас не должна.
* Вся флешка состоит из сегментов. То есть, на ней чередуются последовательности по 128 кб данных и 512 байт «индекса». Следовательно, индекс занимает 1/256 всей памяти, что составляет 4 Мб на 1 Гб.
+
* Карты записываются последовательно, данные также записываются последовательно.
 +
* Если будет нужен статический WL — нужно также хранить количество стираний каждого Erase Unit’а.
  
 
== Алгоритм работы ==
 
== Алгоритм работы ==
Строка 47: Строка 51:
 
=== Монтирование ===
 
=== Монтирование ===
  
При монтировании с диска читается весь индекс, то есть каждый 257-ой сектор, и все карты (физический кластер -> виртуальный кластер; виртуальный кластер -> {физический кластер, версия}) сохраняются в оперативной памяти. Произвольное чтение с флеш-памяти, будь то FTL’нутая USB-флешка или голый MTD (Memory Type Device), быстрое, следовательно, монтирование тоже происходит быстро. Минус в том, что индекс нужно держать в оперативной памяти, а занимает он примерно 3 мб на каждый 1 гб данных, что составляет уже 192 мб на 64-гигабайтную флешку — довольно много. То есть, применение ограничивается размером потребляемой оперативной памяти — всё как в SSD.
+
При монтировании все карты читаются с диска и сохраняются в оперативной памяти (физический кластер -> виртуальный кластер; виртуальный кластер -> {физический кластер, версия}). Карт не очень много, значит, монтирование происходит довольно быстро. Минус в том, что вся эта петрушка занимает в памяти те же 3/1024 объёма диска, что составляет уже 192 мб на 64-гигабайтную флешку — довольно много. То есть, применение ограничивается размером потребляемой оперативной памяти… всё как в SSD.
  
Для больших устройств можно увеличить размер кластера, скажем, до 64 кб — тогда индекс будет занимать в 16 раз меньше — всего 12 мб на 64 гб флешку. При этом, однако, потребуется ФС с таким же размером блока, а в Linux, кроме VFAT, подобных, по сути, нет — есть только ext4 с bigalloc’ом, который до сих пор глючит. Хотя, в принципе, для флешек и FAT вполне подходит.
+
Для больших устройств теоретически можно увеличить размер кластера, скажем, до 64 кб — тогда индекс будет занимать в 16 раз меньше — всего 12 мб на 64 гб флешку. При этом, однако, потребуется ФС с таким же размером блока, а в Linux, кроме VFAT, подобных, по сути, нет — есть только ext4 с bigalloc’ом, который до сих пор глючит. Хотя, в принципе, для флешек и FAT вполне подходит.
  
 
Второй и сильно более сложный вариант снижения потребления памяти — поддерживать карту виртуальных кластеров в специально отведённом наборе ''виртуальных'' же кластеров (то есть, например, в начале ''виртуального'' диска), а в оперативной памяти сохранять только карты этих «индексных» кластеров. Остальные карты читать по требованию, кэшируя заданное их число в оперативной памяти. Засчёт высокой скорости случайного чтения значительного снижения производительности чтения при этом, теоретически, быть не должно. Минусом, однако, является то, что опять-таки теоретически, в наихудшем случае, из-за необходимости при перезаписи каждого кластера ещё и сбрасывать на диск обновлённую карту, скорость записи может упасть в 3 раза. Это если перезапись каждого кластера приведёт к перезаписи части карт (хранимых такими же кластерами), а перезапись части карт приведёт к перезаписи карт для карт (опять-таки хранимых такими же кластерами). Сия проблема типична для лог-структурированных ФС и называется «wandering tree update».
 
Второй и сильно более сложный вариант снижения потребления памяти — поддерживать карту виртуальных кластеров в специально отведённом наборе ''виртуальных'' же кластеров (то есть, например, в начале ''виртуального'' диска), а в оперативной памяти сохранять только карты этих «индексных» кластеров. Остальные карты читать по требованию, кэшируя заданное их число в оперативной памяти. Засчёт высокой скорости случайного чтения значительного снижения производительности чтения при этом, теоретически, быть не должно. Минусом, однако, является то, что опять-таки теоретически, в наихудшем случае, из-за необходимости при перезаписи каждого кластера ещё и сбрасывать на диск обновлённую карту, скорость записи может упасть в 3 раза. Это если перезапись каждого кластера приведёт к перезаписи части карт (хранимых такими же кластерами), а перезапись части карт приведёт к перезаписи карт для карт (опять-таки хранимых такими же кластерами). Сия проблема типична для лог-структурированных ФС и называется «wandering tree update».
Строка 55: Строка 59:
 
=== Чтение ===
 
=== Чтение ===
  
Чтение простое — нужно просто определять реальное положение каждого считываемого кластера и читать соответствующие блоки с нижележащего устройства. Либо, если кластер ещё не сопоставлен реальному, возвращать нули.
+
Чтение простое — нужно просто определять реальное положение каждого считываемого кластера и читать соответствующие блоки с нижележащего устройства. Если кластер TRIM’нут или ещё не сопоставлен реальному, возвращать нули.
  
 
=== Запись ===
 
=== Запись ===
Строка 61: Строка 65:
 
При записи новой версии кластер, содержащий предыдущую, не очищается, а просто помечается как свободный. Даже при следующем монтировании он будет считаться свободным, так как содержит старую версию блока.
 
При записи новой версии кластер, содержащий предыдущую, не очищается, а просто помечается как свободный. Даже при следующем монтировании он будет считаться свободным, так как содержит старую версию блока.
  
Центральная идея всего SFTL — превращение случайной записи в последовательную. Условно говоря, драйвер должен использовать флешку как кольцевой буфер, всё время записывая новые версии кластеров в следующий свободный сегмент, и после конца снова переходя в начало флешки. То есть, в идеале запись должна происходить в связное свободное место. Со временем это, очевидно, приводит к фрагментации свободного пространства — следовательно, появляются две проблемы:
+
Центральная идея любого FTL — превращение случайной записи в более-менее последовательную, всё время записывая новые версии кластеров в следующий свободный Erase Unit. Со временем это, очевидно, приводит к фрагментации свободного пространства внутри Erase Unit’ов — следовательно, запись из последовательной может снова превратиться в случайную.
# Запись из последовательной может снова превратиться в случайную.
+
# В какой-то момент может оказаться, что сегментов, свободных целиком, нет вообще, хотя свободного места при этом вполне хватает.
+
  
Вообще забить на фрагментацию и всегда писать в первый доступный свободный кластер — не решение. Производительность записи при этом будет падать приблизительно на количество пропущенных при записи (занятых) кластеров внутри каждого Erase Unit’а. То есть цена пропуска кластера примерно равна цене его записи, так как большую часть времени записи занимает именно стирание.
+
Цена пропуска сектора ''внутри'' одного Erase Unit’а примерно равна цене его записи. Так как если бы мы его записали, то с одного стирания (занимающего большую часть времени) мы бы «сняли» на единицу больше записанных секторов. ''Целые'' Erase Unit’ы при этом можно пропускать вполне свободно (какой из них «открыть» следующим — флешке пофигу). То есть, «цена» записи в частично занятый сегмент такая же, как и на «голом» MTD — там занятые секторы нужно сначала куда-то переместить, и это занимает такое же время.
  
Проблема, на самом деле, общая для всех лог-структурированных ФС. Решают её по-разному. В первую очередь почти во всех реализациях есть фоновый процесс — «сборщик мусора», и есть различные стратегии сборки мусора: жадная (очистка наиболее легко очищаемого сегмента), по возрасту (очистка наиболее старых сегментов), на основе оценки стоимости (cost-based — совмещает лёгкость очистки и возраст).
+
Проблема очистки, на самом деле, общая для всех лог-структурированных устройств («cleaning overhead»). Выхода два:
 +
* Скидывать работу по очистке блоков на свободное время путём добавления сборщика мусора. Объём работы (Write Amplification) это не уменьшает (может даже увеличивать), но распределяет её во времени. Типичные стратегии сборки мусора: жадная (очистка наиболее легко очищаемого сегмента), по возрасту (очистка наиболее старых сегментов), на основе оценки стоимости (cost-based — совмещает лёгкость очистки и возраст).
 +
* Пытаться магическим образом предсказать, какие данные ''будут'' перезаписаны, а какие ''не будут''. Например, пытаться при записи разделять «холодные» и «горячие» данные. Ибо теоретически, чем лучше они разделены, тем больше вероятность того, что в сегменте все блоки будут устаревать вместе &rArr; его будет проще очищать.
  
Вторая идея — пытаться при записи разделять «холодные» и «горячие» данные. Идея в том, что теоретически, чем лучше они разделены, тем больше вероятность того, что в сегменте все блоки будут устаревать вместе &rArr; его будет проще очищать.
+
Голый MTD с точки зрения данного алгоритма отличается от флешки тем, что перед началом записи занятые блоки нужно куда-то переместить, а сегмент — стереть. Но зато при перемещении мы можем без лишних затрат бороться с фрагментацией, группируя блоки по возрасту (так как операция «открытия» блока не занимает времени и писать можно в любой стёртый сектор). А если, например, флешку записать целиком, а потом много раз перезаписывать каждый второй сектор — мы получим 50 % свободного места в каждом сегменте, и ничего не сможем с этим поделать без лишних затрат времени ''перед началом записи''. Конкретно, если перемещать сектора — в самом худшем случае мы можем затратить вплоть до (N-1) стираний, где N — число секторов в сегменте. Чтобы подобным образом бороться с фрагментацией на флешке — перемещать блоки из частично занятых секторов нужно перед окончанием записи в сегмент — в тот момент, когда в записываемом сегменте остаётся нужный объём пространства. Но в худшем случае это ограничивает перемещение числом свободных секторов в записываемом сегменте.
  
А что делать с фрагментацией нам? А нам нужно:
+
Итого, что же делать с фрагментацией нам?
  
Во-первых, обеспечить возможность очистки сегмента в худшем случае, то есть, даже если осталось всего лишь N сегментов, в каждом из которых свободен всего 1 кластер. Для этого N-1 сегмент должен быть зарезервирован.
+
Ответ — выбирать сегмент на основе оценки стоимости и возраста данных. Идея простая — стоимость очистки блока, в который мы будем писать, в точности равна числу занятых в нём секторов, следовально, для записи надо выбирать максимально свободный сегмент (в идеале — совсем свободный). Однако:
 +
* Вместо того, чтобы бросаться перезаписывать сегмент, может оказаться лучше немного подождать, и оставшиеся блоки в нём «протухнут» сами (и мы сможем записать аж целый сегмент). При этом мы проигрываем разницу в числе свободных секторов сейчас, но выигрываем число секторов, которые «протухнут» сами, потом. Откуда следует, что делать такую оптимизацию имеет смысл только для блоков, которые в ближайшее время с большой вероятностью будут перезаписаны.
 +
* Вместо того, чтобы писать блок в произвольный выбранный сегмент, лучше группировать его вместе с блоками, близкими к нему по возрасту. Для этого вместо одного «активного сегмента» таковых помнить нужно несколько (<= лимиту числа открытых на запись блоков на флешке минус один, необходимый под индекс). В качестве каждого активного сегмента нужно выбирать либо любой пустой, либо ближайший по среднему возрасту сохранённых в нём логических блоков к центру группы, построенному с помощью K-средних.
 +
* Вместо того, чтобы записывать сегмент целиком, может оказаться лучше оставить в нём немного места и переместить туда близкие по возрасту данные, извлечённые из частично свободного сегмента — то есть, сделать дефрагментацию в процессе записи.
  
Во-вторых, можно тоже пытаться разделять сектора по частоте их перезаписи. Очень простым способом — с помощью K-средних разбить всю флешку на K «регионов», и стараться писать сектора с соответствующим количеством перезаписи в соответствующий регион. K нужно выбирать меньшим или равным лимиту открытых на запись блоков во флешке.
+
Таким образом, при выборе кластера для записи блока мы имеем два критерия качества: (основной) число свободных блоков и (дополнительный) близость среднего возраста к центру выбранной для записи блока группы K-средних. Комбинировать их нужно примерно так — если считать, что разница в возрасте блоков в сегменте потенциально может привести к тому, что к моменту, когда мы будем его перезаписывать, более старые блоки (ранее перезаписанные меньшее число раз), вероятно, ещё не будут перезаписаны, а более новые уже будут. То есть можно считать, что «цена» записи в частично занятый сегмент больше на число блоков, относящихся к более старой возрастной группе, чем записываемый. Можно этот показатель ещё домножить на некий варьируемый коэффициент.
  
При записи:
+
Следует отметить, что наш индекс со временем тоже становится фрагментированным, и из-за TRIM его фрагментация может вовсе не соответствовать фрагментации самого устройства с данными.
* Выбираем подходящий регион с помощью K-средних.
+
* Если в регионе не окажется свободных сегментов — попытаться найти свободный сегмент в других регионах, начиная с соседнего в сторону более «горячих» сегментов. Идея в том, что раз максимальное количество перезаписей может лишь расти, то больше вероятность того, что в будущем записанный сегмент окажется нужно двигать в «меньшую» сторону. Следовательно, если он изначально будет записан в следующий регион, то в будущем он с большей вероятностью окажется в правильном.
+
* Если свободных сегментов нет ни в родном, ни в соседних регионах — значит, кончилось место и надо переходить к экстренной очистке. Экстренную очистку, опять-таки, пытаемся сначала сделать в «родном» сегменте, а потом в соседних.
+
* Сначала пробуем найти наиболее легко очищаемую последовательность N сегментов и переместить из них данные в последовательность N-1 зарезервированных сегментов. После такой очистки мы получим связный регион, в котором N-1 сегмент станет зарезервированным, а в оставшийся 1 можно будет что-нибудь записать. Очищать пробуем сначала в родном регионе, потом — в соседних.
+
* Если таких последовательностей уже не осталось — значит, места, во-первых, осталось довольно мало (теоретический максимум худшего случая — 1/N, но в среднем — гораздо меньше), а во-вторых, оно сильно фрагментировано. Тогда очистку нужно делать по-другому — брать данные из сегмента, соседнего для свободных зарезервированных, и распределять по отдельным свободным кластерам в разбросанных по всему диску сегментах. Для MTD это вообще быстро, а для флешек это почти ничем не хуже, чем просто случайная запись в те же самые свободные кластеры, но зато даёт всё время поддерживать связную свободную область.
+
  
На MTD можно тоже группировать кластеры с примерно одинаковым возрастом. Но смысла в том, чтобы группировать их '''рядом''', там нет никакого — и более этого, это даже вредно, так как мешает их перемещать в соответствии с требованиями распределения износа, то есть больше изнашивает одни части памяти и меньше — другие.
+
А уже в дополнение к вышеописанному алгоритму можно добавить и фоновый сборщик мусора, хотя бы с жадной стратегией.
  
То есть, для MTD реализация немного меняется. Сегмент делается равным или примерно равным блоку стирания; при записи, если в какой-то сегмент уже начата запись кластеров, соответствующих возрасту нового кластера — кластер пишется в уже открытый сегмент. Если же такой ещё не открыт — для открытия выбирается свободный сегмент, перезаписанный минимальное число раз (Dynamic Wear Leveling). Статический WL в этих условиях осуществляется сборщиком мусора — при большой разности частоты перезаписи сегментов он просто должен выбирать наименее часто перезаписываемый сегмент, и перемещать его данные в другой, свободный, и желательно — наоборот, перезаписанный наибольшее число раз.
+
При записи блока:
 
+
# Обновление классификации:
В-третьих, нужен и фоновый сборщик мусора, хотя бы с жадной стратегией.
+
#* Если блок был уже записан ранее — вычитаем его возраст из суммы возрастов его группы, и уменьшаем число блоков в ней на 1.
 +
#* Увеличиваем возраст блока на 1.
 +
#* Если есть пустые группы и возраст не равен в точности среднему возрасту ни одной из непустых групп, относим блок к первой пустой группе.
 +
#* Если пустых групп нет — выбираем группу, средний возраст которой наиболее близок к возрасту блока. Если таких несколько — выбираем группу с максимальным возрастом.
 +
#* Обновляем центр выбранной группы, то есть добавляем новый возраст к сумме возрастов и увеличиваем число блоков в группе на 1.
 +
# Выбираем сегмент для записи:
 +
#* Если для выбранной группы уже есть открытый сегмент — пишем в него.
 +
#* Если нет — ищем сегмент, в котором минимально (число_занятых_блоков + коэффициент_возраста*число_занятых_блоков_более_старых_групп) и пишем в него.
 +
# В момент, когда после записи в сегменте остаётся меньше, чем (коэффициент_дефрагментации*число_изначально_занятых_блоков_сегмента), разрешается сделать дефрагментацию на лету и переместить в текущий сегмент какие-нибудь блоки, например, блоки из сегментов, имеющих максимальный разброс возрастов.
  
 
=== TRIM ===
 
=== TRIM ===
  
При нашей простейшей структуре хранилища TRIM — некоторая проблема, ибо метаданные жёстко связаны с данными, а при TRIM новую версию метаданных нужно сохранять, не сохраняя сами данные.
+
При TRIM занятого блока в индекс сохраняется запись о его отображении на физический сектор 0.
 
+
Что можно сделать: добавить в структуру информации о кластере флаг trim и сохранять в сегменте пустой trim’нутый кластер с увеличенной версией. Причём, кластеры, содержащие trim’нутые данные, пустыми можно считать не раньше, чем либо trim’нутые данные будут перезаписаны новой версией, либо (!) будут перезаписаны все также находящиеся на диске предыдущие версии этих данных. Чтобы отслеживать второе условие — в оперативной памяти потребуется хранить ещё и счётчик «живых» предыдущих версий каждого блока.
+
 
+
Далее — TRIM легче реализовать, если длина данных блока не считается постоянной — например, если мы также применяем сжатие на уровне блочного устройства. В этом случае сегмент можно делать любого размера, писать в него данные, начиная с начала, и метаданные, начиная с конца. То есть, в последнем 512-байтном блоке сегмента будет содержаться 16-байтный заголовок блока метаданных (самое интересное в котором — это сколько ещё блоков метаданных есть перед этим блоком), и 31 структура метаданных сегментов, с 1-го по 31-ый (тоже по 16 байт = 32 бита номер блока, 32 бита номер версии, 1 бит TRIM, 31 бит размер, 32 бита контрольная сумма). Если при этом в сегменте есть ещё кластеры, то в предпоследнем блоке сегмента хранится информация о кластерах с 32-го по 62-ой; в предпредпоследнем — с 63-го по 93-й, и так далее. TRIM’нутый блок, очевидно, имеет размер 0. Кстати, флаг TRIM можно даже не хранить, а просто считать TRIM’нутым кластер с размером 0; зато, возможно, будет полезно хранить флаг сжатия и давать сохранять несжатые данные.
+
 
+
Тут и приходит осознание — сколько же места потенциально тратится «впустую» в SSD’шках на контроллерах SandForce (у них прозрачное сжатие), и сколько оперативной памяти тратится в SSD’шках в целом…
+
  
 
=== Барьеры / сброс данных на диск ===
 
=== Барьеры / сброс данных на диск ===
Строка 104: Строка 108:
 
Всякая хрень типа СУБД может иногда (при коммите транзакций) требовать гарантированной отправки данных на диск. Если сегмент при этом ещё не заполнился, его нужно записать неполным, а когда заполнится — перезаписать ещё раз. Это гораздо дешевле, чем оставлять фрагментированный сегмент.
 
Всякая хрень типа СУБД может иногда (при коммите транзакций) требовать гарантированной отправки данных на диск. Если сегмент при этом ещё не заполнился, его нужно записать неполным, а когда заполнится — перезаписать ещё раз. Это гораздо дешевле, чем оставлять фрагментированный сегмент.
  
== Locking ==
+
=== Дополнительная идея: сжатие ===
 
+
R/W locking using 1 R/W spinlock and 1 event.
+
 
+
Reading:
+
* Take read lock
+
* Check if requested cluster is mapped into buffer
+
* If yes:
+
** Read from the buffer
+
* If no:
+
** Initiate block read operation
+
* Unlock
+
 
+
Writing:
+
(Start):
+
* Take write lock
+
* Check for free space in buffer
+
* If sufficient:
+
** Write current bio into buffer
+
** Modify translation maps
+
* If insufficient:
+
** (Insufficient) Check flush flag (no need for atomic/etc as already within buffer lock)
+
** If someone is already flushing:
+
*** Unlock
+
*** Wait until flushing ends using an event
+
*** Goto (Start)
+
** If no one is flushing yet:
+
*** Set flush flag
+
*** Remember current bio and initiate (Flush) operation
+
* Unlock
+
 
+
After (Flush) operation ends:
+
* Take write lock (writers are already blocked, this is to block readers)
+
* Clear buffer
+
* If the free sequence pointer can be moved without cleaning:
+
** Move pointer
+
** Perform own remembered write operation
+
** Unset flush flag
+
** Unlock
+
** Wake up waiting writers
+
* If not:
+
** Initiate cleaning process
+
** Unlock
+
 
+
After cleaning operation ends:
+
* Take write lock
+
* Modify translation maps
+
* Move free sequence pointer
+
* If there are no more pending cleaning operations:
+
** Perform own remembered write operation:
+
*** Write current bio into buffer
+
*** Modify translation maps
+
** Unset flush flag
+
** Unlock
+
** Wake up waiting writers
+
* Else:
+
** Initiate next cleaning operation
+
** Unlock
+
 
+
== Дополнительная идея: сжатие ==
+
  
 
== Ссылки ==
 
== Ссылки ==

Текущая версия на 15:07, 20 января 2014

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

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

Идея

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

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

  • Главный плюс — реализация относительно проста засчёт отсутствия необходимости писать код и утилиты ФС. А то, блин, из всех вышеперечисленных ФС fsck только недавно появился для наиболее свежей F2FS.
  • Поверх транслированного устройства можно использовать любую обычную файловую систему. Или даже не файловую систему, а, например, raw tablespace для СУБД. Хотя это может потребовать дополнительных фич — например, барьеров.
  • В принципе, с небольшими изменениями можно использовать почти одну и ту же реализацию FTL для MTD и для USB-флешек.
  • Если захочется, можно относительно несложно реализовать снимки ФС, аналогично LVM’ской реализации — патчи в код ФС, позволяющие приостановить запись и в заданный момент времени получить консистентное состояние записанных данных и метаданных, в коде ядра уже есть.

Минусы идеи:

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

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

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

Отличия флешек от MTD с точки зрения FTL:

  • На MTD можно с одинаковой скоростью писать в любой стёртый сектор (что, разумеется, удобнее). На флешках так делать нельзя, а можно держать лишь максимум LIMIT (~6) активных регионов.
  • Зато при записи на флешки можно не обращать внимания на Erase Unit’ы — этим занимается её внутренний FTL. Если конкретно:
    • Можно очищать блоки мелкими порциями, в то время, как на MTD нужно очищать и стирать Erase Unit целиком. Размер сегмента, не кратный размеру Erase Unit (как в прошлых идеях — 128.5 Кб), использовать при этом можно — просто потребуется при очистке затрагивать ещё и пограничные сегменты.
    • Можно не делать динамического Wear-Leveling’а (то есть WL перезаписываемых данных) на уровне блоков стирания — флешечный FTL делает это сам. Однако, флешки обычно не двигают статические данные, поэтому может потребоваться Static Wear Leveling. Кроме того, отдельные кластеры внутри всех блоков стирания должны записываться равномерно — нельзя, например, всегда записывать 1-ый сектор каждого Erase Unit’а в 10 раз чаще остальных.

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

  • Предлагается использовать кластеры по 4096 байт (8 физических секторов).
  • Виртуальные адреса кластеров отображать на физические. Кластер может находиться в любом месте флешки.
  • Данные отображения каждого кластера содержат его физический адрес, виртуальный адрес и номер версии, что вместе составляет 12 байт и лимитирует объём устройства 2^44 байт, то есть 16 Тб. При перезаписи кластера старая версия не удаляется — просто записывается новая с увеличенным на 1 номером версии; кроме того, номер версии позволяет понять, в каких секторах лежат «горячие» данные, а в каких «холодные». В одном 512-байтном блоке помещаются карты для 42 кластеров + контрольная сумма. Таким образом, карты всех блоков занимают примерно 3/1024 ёмкости диска.
  • В самом начале диска находится суперблок; далее сохраняются карты отображения, с округлением занятого пространства вверх до размера Erase Unit’а. Благодаря наличию динамического WL внутри флешки частая перезапись этих первых Erase Unit’ов пугать нас не должна.
  • Карты записываются последовательно, данные также записываются последовательно.
  • Если будет нужен статический WL — нужно также хранить количество стираний каждого Erase Unit’а.

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

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

При монтировании все карты читаются с диска и сохраняются в оперативной памяти (физический кластер -> виртуальный кластер; виртуальный кластер -> {физический кластер, версия}). Карт не очень много, значит, монтирование происходит довольно быстро. Минус в том, что вся эта петрушка занимает в памяти те же 3/1024 объёма диска, что составляет уже 192 мб на 64-гигабайтную флешку — довольно много. То есть, применение ограничивается размером потребляемой оперативной памяти… всё как в SSD.

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

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

Чтение

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

Запись

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

Центральная идея любого FTL — превращение случайной записи в более-менее последовательную, всё время записывая новые версии кластеров в следующий свободный Erase Unit. Со временем это, очевидно, приводит к фрагментации свободного пространства внутри Erase Unit’ов — следовательно, запись из последовательной может снова превратиться в случайную.

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

Проблема очистки, на самом деле, общая для всех лог-структурированных устройств («cleaning overhead»). Выхода два:

  • Скидывать работу по очистке блоков на свободное время путём добавления сборщика мусора. Объём работы (Write Amplification) это не уменьшает (может даже увеличивать), но распределяет её во времени. Типичные стратегии сборки мусора: жадная (очистка наиболее легко очищаемого сегмента), по возрасту (очистка наиболее старых сегментов), на основе оценки стоимости (cost-based — совмещает лёгкость очистки и возраст).
  • Пытаться магическим образом предсказать, какие данные будут перезаписаны, а какие не будут. Например, пытаться при записи разделять «холодные» и «горячие» данные. Ибо теоретически, чем лучше они разделены, тем больше вероятность того, что в сегменте все блоки будут устаревать вместе ⇒ его будет проще очищать.

Голый MTD с точки зрения данного алгоритма отличается от флешки тем, что перед началом записи занятые блоки нужно куда-то переместить, а сегмент — стереть. Но зато при перемещении мы можем без лишних затрат бороться с фрагментацией, группируя блоки по возрасту (так как операция «открытия» блока не занимает времени и писать можно в любой стёртый сектор). А если, например, флешку записать целиком, а потом много раз перезаписывать каждый второй сектор — мы получим 50 % свободного места в каждом сегменте, и ничего не сможем с этим поделать без лишних затрат времени перед началом записи. Конкретно, если перемещать сектора — в самом худшем случае мы можем затратить вплоть до (N-1) стираний, где N — число секторов в сегменте. Чтобы подобным образом бороться с фрагментацией на флешке — перемещать блоки из частично занятых секторов нужно перед окончанием записи в сегмент — в тот момент, когда в записываемом сегменте остаётся нужный объём пространства. Но в худшем случае это ограничивает перемещение числом свободных секторов в записываемом сегменте.

Итого, что же делать с фрагментацией нам?

Ответ — выбирать сегмент на основе оценки стоимости и возраста данных. Идея простая — стоимость очистки блока, в который мы будем писать, в точности равна числу занятых в нём секторов, следовально, для записи надо выбирать максимально свободный сегмент (в идеале — совсем свободный). Однако:

  • Вместо того, чтобы бросаться перезаписывать сегмент, может оказаться лучше немного подождать, и оставшиеся блоки в нём «протухнут» сами (и мы сможем записать аж целый сегмент). При этом мы проигрываем разницу в числе свободных секторов сейчас, но выигрываем число секторов, которые «протухнут» сами, потом. Откуда следует, что делать такую оптимизацию имеет смысл только для блоков, которые в ближайшее время с большой вероятностью будут перезаписаны.
  • Вместо того, чтобы писать блок в произвольный выбранный сегмент, лучше группировать его вместе с блоками, близкими к нему по возрасту. Для этого вместо одного «активного сегмента» таковых помнить нужно несколько (<= лимиту числа открытых на запись блоков на флешке минус один, необходимый под индекс). В качестве каждого активного сегмента нужно выбирать либо любой пустой, либо ближайший по среднему возрасту сохранённых в нём логических блоков к центру группы, построенному с помощью K-средних.
  • Вместо того, чтобы записывать сегмент целиком, может оказаться лучше оставить в нём немного места и переместить туда близкие по возрасту данные, извлечённые из частично свободного сегмента — то есть, сделать дефрагментацию в процессе записи.

Таким образом, при выборе кластера для записи блока мы имеем два критерия качества: (основной) число свободных блоков и (дополнительный) близость среднего возраста к центру выбранной для записи блока группы K-средних. Комбинировать их нужно примерно так — если считать, что разница в возрасте блоков в сегменте потенциально может привести к тому, что к моменту, когда мы будем его перезаписывать, более старые блоки (ранее перезаписанные меньшее число раз), вероятно, ещё не будут перезаписаны, а более новые уже будут. То есть можно считать, что «цена» записи в частично занятый сегмент больше на число блоков, относящихся к более старой возрастной группе, чем записываемый. Можно этот показатель ещё домножить на некий варьируемый коэффициент.

Следует отметить, что наш индекс со временем тоже становится фрагментированным, и из-за TRIM его фрагментация может вовсе не соответствовать фрагментации самого устройства с данными.

А уже в дополнение к вышеописанному алгоритму можно добавить и фоновый сборщик мусора, хотя бы с жадной стратегией.

При записи блока:

  1. Обновление классификации:
    • Если блок был уже записан ранее — вычитаем его возраст из суммы возрастов его группы, и уменьшаем число блоков в ней на 1.
    • Увеличиваем возраст блока на 1.
    • Если есть пустые группы и возраст не равен в точности среднему возрасту ни одной из непустых групп, относим блок к первой пустой группе.
    • Если пустых групп нет — выбираем группу, средний возраст которой наиболее близок к возрасту блока. Если таких несколько — выбираем группу с максимальным возрастом.
    • Обновляем центр выбранной группы, то есть добавляем новый возраст к сумме возрастов и увеличиваем число блоков в группе на 1.
  2. Выбираем сегмент для записи:
    • Если для выбранной группы уже есть открытый сегмент — пишем в него.
    • Если нет — ищем сегмент, в котором минимально (число_занятых_блоков + коэффициент_возраста*число_занятых_блоков_более_старых_групп) и пишем в него.
  3. В момент, когда после записи в сегменте остаётся меньше, чем (коэффициент_дефрагментации*число_изначально_занятых_блоков_сегмента), разрешается сделать дефрагментацию на лету и переместить в текущий сегмент какие-нибудь блоки, например, блоки из сегментов, имеющих максимальный разброс возрастов.

TRIM

При TRIM занятого блока в индекс сохраняется запись о его отображении на физический сектор 0.

Барьеры / сброс данных на диск

Всякая хрень типа СУБД может иногда (при коммите транзакций) требовать гарантированной отправки данных на диск. Если сегмент при этом ещё не заполнился, его нужно записать неполным, а когда заполнится — перезаписать ещё раз. Это гораздо дешевле, чем оставлять фрагментированный сегмент.

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

Ссылки