middle

Какие политики вытеснения (eviction) существуют?

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

Аналогия из жизни: политика вытеснения — как правила уборки книжной полки, когда она заполнена. LRU убирает книгу, которую дольше всего не открывали. LFU убирает ту, которую открывали реже всего за всё время. FIFO убирает ту, что стоит дольше всего.

Основные алгоритмы

Политика	Алгоритм	Плюсы	Минусы
LRU (Least Recently Used)	Удаляет давно не использованный	Простой, хороший hit rate	Не учитывает частоту
LFU (Least Frequently Used)	Удаляет редко используемый	Учитывает популярность	Залипание старых популярных элементов
FIFO (First In First Out)	Удаляет самый старый	Очень простой	Не учитывает паттерн доступа
Random	Удаляет случайный	Простой, O(1)	Может удалить горячий элемент
W-TinyLFU (Caffeine)	LFU с окном + фильтром	Лучший hit rate	Сложная реализация

LRU (используется в Redis, LinkedHashMap)

Пример

// Java: LRU-кэш на LinkedHashMap
Map<String, String> lruCache = new LinkedHashMap<>(100, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
        return size() > 100; // удалять при превышении 100 элементов
    }
};

Redis eviction policies

Пример

# redis.conf
maxmemory 256mb
maxmemory-policy allkeys-lru   # LRU среди всех ключей

Политика Redis	Описание
`noeviction`	Ошибка при нехватке памяти (по умолчанию)
`allkeys-lru`	LRU среди всех ключей
`volatile-lru`	LRU среди ключей с TTL
`allkeys-lfu`	LFU среди всех ключей (Redis 4.0+)
`volatile-lfu`	LFU среди ключей с TTL
`allkeys-random`	Случайный среди всех
`volatile-ttl`	Удалять ключи с ближайшим истечением TTL

W-TinyLFU (Caffeine)

Caffeine использует Window TinyLFU — гибрид LRU и LFU с Bloom-фильтром для отслеживания частоты. Обеспечивает near-optimal hit rate с минимальными затратами памяти.

Пример

Caffeine.newBuilder()
    .maximumSize(10_000)  // при превышении — W-TinyLFU решает, что удалить
    .build();

Ключевые принципы

LRU — хорош для большинства случаев; используется в Redis (allkeys-lru)
W-TinyLFU (Caffeine) — лучший hit rate среди in-process кэшей; рекомендуется для L1
Redis allkeys-lru — рекомендуемая политика для кэша; noeviction — для persistent storage
volatile-* политики работают только с ключами, у которых установлен TTL

Частые ошибки

Redis noeviction для кэша — при заполнении памяти Redis начнёт отдавать ошибки вместо вытеснения
LFU без decay — старые популярные ключи залипают навсегда; Redis LFU использует логарифмический decay
Не установить maxmemory в Redis — Redis будет расти до OOM kill ОС

Как используется в 2026

Redis: allkeys-lru или allkeys-lfu — стандартная конфигурация для кэша
Caffeine: W-TinyLFU по умолчанию — лучший in-process алгоритм
Мониторинг eviction rate — если высокий, нужно увеличить maximumSize или maxmemory

На собеседовании: интервьюер ожидает знание LRU, LFU и W-TinyLFU, а также умение выбрать правильную политику Redis. Частая ошибка — не знать, что noeviction стоит по умолчанию в Redis и не подходит для кэша.

#eviction #lfu #caching #lru #redis #w-tinylfu