Как устроен LRU-кэш и какие ещё бывают политики вытеснения?

LRU (least recently used). Гипотеза — недавно использованное скоро понадобится снова. Реализация за O(1):

• хеш-таблица ключ → узел списка;
• двусвязный список в порядке использования: голова — самый свежий, хвост — самый старый;
• get: найти узел через таблицу, перенести в голову;
• put: если ключ есть — обновить и перенести в голову; если нет — создать узел в голове, а при переполнении удалить хвост (и из таблицы).

Двусвязный — чтобы удалить узел из середины за O(1). В Python — OrderedDict с move_to_end и popitem(last=False), в Java — LinkedHashMap с accessOrder = true и removeEldestEntry.

LFU (least frequently used) — считает обращения, выбрасывает наименее частый. Хорошо держит стабильно популярное, но плохо забывает: вчерашний хит с миллионом обращений сидит в кэше навсегда. Нужны старение счётчиков и O(1)-структура (списки по частотам).

Проблемы LRU:

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

Улучшения:

• SLRU / 2Q — новый ключ попадает в «испытательный» сегмент и переходит в основной, только если к нему обратились снова;
• ARC — адаптивно делит место между «недавними» и «частыми»;
• W-TinyLFU (Caffeine в Java, Ristretto в Go) — маленькое LRU-окно для новых и частотный фильтр на count-min sketch при входе в основную часть: новый ключ вытеснит жертву, только если встречался чаще неё. Близко к оптимальному на реальных нагрузках;
• TTL — отдельно от политики: данные устаревают по времени.

Где важно: локальные кэши в сервисах, буферный кэш базы (в PostgreSQL — clock sweep, приближение LRU со счётчиком использования), page cache ОС, CDN, Redis (allkeys-lru/allkeys-lfu — приближённые: выбирают жертву из случайной выборки ключей, а не держат точный список).

from collections import OrderedDict

class LRU:
    def __init__(self, capacity):
        self.cap, self.data = capacity, OrderedDict()

    def get(self, key):
        if key not in self.data:
            return None
        self.data.move_to_end(key)          # стал самым свежим
        return self.data[key]

    def put(self, key, value):
        self.data[key] = value
        self.data.move_to_end(key)
        if len(self.data) > self.cap:
            self.data.popitem(last=False)   # вытесняем самый старый