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