13 521
правка
Изменения
м
→Запись
* Вместо того, чтобы записывать сегмент целиком, может оказаться лучше оставить в нём немного места и переместить туда близкие по возрасту данные, извлечённые из частично свободного сегмента — то есть, сделать дефрагментацию в процессе записи.
Таким образом, при выборе кластера для записи блока мы имеем два критерия качества: (основной) число свободных блоков и (дополнительный) близость среднего возраста к центру выбранной для записи блока группы K-средних. Остаётся вопрос — как Комбинировать их комбинироватьнужно примерно так — если считать, что разница в возрасте блоков в сегменте потенциально может привести к тому, что к моменту, когда мы будем его перезаписывать, более старые блоки (ранее перезаписанные меньшее число раз), вероятно, ещё не будут перезаписаны, а более новые уже будут. То есть можно считать, что «цена» записи в частично занятый сегмент больше на число блоков, относящихся к более старой возрастной группе, чем записываемый. Можно этот показатель ещё домножить на некий варьируемый коэффициент.
Следует отметить, что наш индекс со временем тоже становится фрагментированным, и из-за TRIM его фрагментация может вовсе не соответствовать фрагментации самого устройства с данными.
А уже в дополнение к вышеописанному алгоритму можно добавить и фоновый сборщик мусора, хотя бы с жадной стратегией.
При записи блока:
# Обновление классификации:
#* Если блок был уже записан ранее — вычитаем его возраст из суммы возрастов его группы, и уменьшаем число блоков в ней на 1.
#* Увеличиваем возраст блока на 1.
#* Если есть пустые группы и возраст не равен в точности среднему возрасту ни одной из непустых групп, относим блок к первой пустой группе.
#* Если пустых групп нет — выбираем группу, средний возраст которой наиболее близок к возрасту блока. Если таких несколько — выбираем группу с максимальным возрастом.
#* Обновляем центр выбранной группы, то есть добавляем новый возраст к сумме возрастов и увеличиваем число блоков в группе на 1.
# Выбираем сегмент для записи:
#* Если для выбранной группы уже есть открытый сегмент — пишем в него.
#* Если нет — ищем сегмент, в котором минимально (число_занятых_блоков + коэффициент_возраста*число_занятых_блоков_более_старых_групп) и пишем в него.
# В момент, когда после записи в сегменте остаётся меньше, чем (коэффициент_дефрагментации*число_изначально_занятых_блоков_сегмента), разрешается сделать дефрагментацию на лету и переместить в текущий сегмент какие-нибудь блоки, например, блоки из сегментов, имеющих максимальный разброс возрастов.
=== TRIM ===