13 521
правка
Изменения
м
А голый Минус флешки (в отличие от MTD) в том, что перед началом записи в частично занятый сегмент мы не можем никуда переместить из него данные. Голый MTD с точки зрения данного алгоритма отличается от флешки только тем, что перед началом записи занятые блоки всё-таки нужно стереть и куда-то переместить, а сегмент — стереть. Но зато при перемещении мы можем без лишних затрат бороться с фрагментацией, группируя блоки по возрасту (так как операция «открытия» блока не занимает времени и писать можно в любой стёртый сектор). А если, например, флешку записать целиком, а потом много раз перезаписывать каждый второй сектор — мы получим 50 % свободного места в каждом сегменте, и ничего не сможем с этим поделать без лишних затрат времени ''перед началом записи''. Конкретно, если перемещать сектора — в самом худшем случае мы можем затратить вплоть до (N-1) стираний, где N — число секторов в сегменте. Чтобы подобным образом бороться с фрагментацией на флешке — перемещать блоки из частично занятых секторов нужно перед окончанием записи в сегмент — в тот момент, когда в записываемом сегменте остаётся нужный объём пространства. Но в худшем случае это ограничивает перемещение числом свободных секторов в записываемом сегменте.
→Запись
Центральная идея любого FTL — превращение случайной записи в более-менее последовательную, всё время записывая новые версии кластеров в следующий свободный Erase Unit. Со временем это, очевидно, приводит к фрагментации свободного пространства внутри Erase Unit’ов — следовательно, запись из последовательной может снова превратиться в случайную.
Цена пропуска сектора ''внутри'' одного Erase Unit’а примерно равна цене его записи. Так как если бы мы его записали, то с одного стирания (занимающего большую часть времени) мы бы «сняли» на единицу больше записанных секторов. ''Целые'' Erase Unit’ы при этом можно пропускать вполне свободно (какой из них «открыть» следующим — флешке пофигу). То есть, «цена» записи в частично занятый сегмент такая же, как и на «голом» MTD — там занятые секторы нужно сначала куда-то переместить, и это занимает такое же время.
Проблемаочистки, на самом деле, общая для всех лог-структурированных устройств («cleaning overhead»). Выхода два:
* Скидывать работу по очистке блоков на свободное время путём добавления сборщика мусора. Объём работы (Write Amplification) это не уменьшает (может даже увеличивать), но распределяет её во времени. Типичные стратегии сборки мусора: жадная (очистка наиболее легко очищаемого сегмента), по возрасту (очистка наиболее старых сегментов), на основе оценки стоимости (cost-based — совмещает лёгкость очистки и возраст).
* Пытаться магическим образом предсказать, какие данные ''будут'' перезаписаны, а какие ''не будут''. Например, пытаться при записи разделять «холодные» и «горячие» данные. Ибо теоретически, чем лучше они разделены, тем больше вероятность того, что в сегменте все блоки будут устаревать вместе ⇒ его будет проще очищать.
Таким образом, при выборе кластера для записи блока мы имеем два критерия качества: (основной) число свободных блоков и (дополнительный) близость среднего возраста к центру выбранной для записи блока группы K-средних. Остаётся вопрос — как их комбинировать.
Следует отметить, что наш индекс со временем тоже становится фрагментированным, и из-за TRIM его фрагментация может вовсе не соответствовать фрагментации самого устройства с данными.