Информатика · объяснение и практика

LFU: частота обращений и правило разрешения равенства

LFU на короткой трассе: счётчики обращений, частота против недавности и явное правило для одинаковых частот.

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Структуры данных · Учебная карта

В маршруте Случайность, численные оценки и целостность · 10 тем

Главная мысль

LFU вытесняет наименее часто использованный элемент среди находящихся в кэше. Для точной трассы нужно определить начальный счётчик, учитывается ли загрузка и как разрешается равенство. Частота и время последнего обращения могут выбирать разных кандидатов.

Определим правила до первого запроса

Возьмём кэш вместимостью два элемента. При загрузке счётчик равен единице, при попадании увеличивается на единицу. Если минимальные счётчики одинаковы, удаляем более давно использованный элемент. После вытеснения история данного элемента забывается; новая загрузка начинает счёт заново. Это конкретный вариант LFU, а не универсальная договорённость всех реализаций.

Для запросов А, А, А, Б получаем А с частотой 3 и Б с частотой 1. Б использован позже, но реже. При новом В правило LFU удалит Б. LRU в тот же момент удалил бы А, потому что его последнее использование старее. Нельзя подменять один критерий другим из-за общего слова «популярность».

Проверим равенство и возвращение

Начнём заново и выполним А, Б, А, Б. Частоты равны двум, а последним использован Б. При запросе В удаляется А по нашему дополнительному правилу давности. Если правило равенства было бы случайным или по времени загрузки, задача имела бы другое продолжение.

После удаления А запрос А загружает его с частотой 1. Старое значение 2 не возвращается: мы явно выбрали учёт только текущего пребывания. Реальная система может сохранять более длинную историю, но тогда обязана описать её размер и старение. Без этого внешне одинаковые запросы могут давать несравнимые состояния.

Пример

Кэш 2; А,Б,А,Б: А(2),Б(2), Б новее. Новый В вытесняет А.

Частота определяет набор кандидатов, а правило равенства выбирает из него одного. Обе стадии нужны для однозначного ответа.

Зачем частотам бывает нужно старение

Элемент, очень востребованный вчера, способен долго сохранять большой счётчик, хотя текущей программе больше не нужен. Нагрузка меняется, поэтому простая пожизненная сумма обращений может защищать устаревшие предпочтения. Периодическое старение или ограниченное окно — возможные изменения политики, которые следует называть отдельно.

Частота обращений также не гарантирует актуальность содержимого. Часто используемое значение после изменения источника может требовать инвалидизации. В учебном разборе полезно держать три колонки: счётчик, последнее обращение и решение о вытеснении. Они показывают, какой именно факт использован, и не смешивают производительность с проверкой свежести данных.

От чтения к действию

А теперь — вы

В полном кэше LFU находятся А(3 обращения), Б(1), В(1). При равных частотах вытесняют наименее недавно использованный; общий порядок от старого к новому А, Б, В. Кого вытеснит новый Г?

Частые вопросы

LFU всегда лучше LRU?

Нет. Результат зависит от нагрузки, вместимости и правил старения. На одной трассе преимущества не доказывают универсальное превосходство.

Что делать при одинаковых частотах?

Нужно заранее задать дополнительное правило. Само название LFU не определяет единственный вариант равенства.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться