lab08 — LRU-кэш¶

LRU-кэш (Least Recently Used) — кэш фиксированной ёмкости, который при переполнении вытесняет наименее недавно использованный элемент. Это самая ходовая политика вытеснения в проде: ею (в той или иной форме) пользуются Redis, Memcached, кэши страниц БД и CDN. Лаборатория собирает кэш из двух уже знакомых структур — хеш-таблицы из lab05 (быстрый доступ по ключу) и двусвязного списка в духе lab02 (порядок использования) — и показывает, как их связка даёт get и put за O(1).

В отличие от lab05, сама хеш-таблица здесь не предмет изучения, поэтому в роли хранилища key -> узел используется встроенный dict. Предмет лабы — порядок использования и вытеснение, и вот его двусвязный список реализован руками.

Зачем именно две структуры¶

LRU-кэшу нужны одновременно две вещи, и ни одна структура не даёт обе за O(1):

быстро найти значение по ключу — это умеет хеш-таблица (dict), O(1);
быстро понять, какой элемент использовался дольше всех, и быстро «освежить» только что использованный — это умеет упорядоченный список, но поиск в нём по ключу — O(n).

Решение — держать обе структуры и связать их: dict отображает key -> узел, а узлы выстроены в двусвязный список по порядку использования. Тогда:

get(key): dict за O(1) находит узел, список за O(1) переносит его в «голову» (most recently used);
вытеснение: «хвост» списка — это всегда least recently used, удалить его — O(1).

Почему список именно двусвязный¶

Ключевая операция — вырезать произвольный узел из середины (когда к нему обратились) и перевесить в голову. В односвязном списке, чтобы вырезать узел, нужен его предшественник, а его поиск — O(n). В двусвязном у каждого узла есть ссылка prev, поэтому вырезание — чистая O(1): достаточно перецепить четыре ссылки соседей.

class Node:
    def __init__(self, key=None, value=None):
        self.key = key      # ключ нужен прямо в узле:
        self.value = value  # при вытеснении хвоста надо знать, что удалить из dict
        self.prev = None
        self.next = None

key хранится в самом узле не случайно: когда мы вытесняем «хвост», мы держим в руках узел, но из dict его надо удалить по ключу — поэтому ключ обязан быть доступен из узла.

Часовые узлы (sentinels)¶

Чтобы не писать проверки if node.prev is None на каждой вставке/удалении с краёв, список обрамлён двумя часовыми (sentinel) узлами-пустышками: _head и _tail. Реальные узлы всегда лежат строго между ними:

_head <-> [MRU] <-> ... <-> [LRU] <-> _tail

Сразу за _head — самый свежий элемент (MRU), перед _tail — кандидат на вытеснение (LRU). У любого реального узла гарантированно есть и prev, и next, поэтому весь код перецепления ссылок — без ветвлений на None.

Операции списка: всё за O(1)¶

def _remove(self, node):
    node.prev.next = node.next   # сосед слева смотрит вправо мимо node
    node.next.prev = node.prev   # сосед справа смотрит влево мимо node

def _add_front(self, node):
    node.prev = self._head
    node.next = self._head.next
    self._head.next.prev = node
    self._head.next = node

def _move_to_front(self, node):  # «освежить» использованный узел
    self._remove(node)
    self._add_front(node)

get и put¶

def get(self, key, default=None):
    node = self._store.get(key)
    if node is None:
        return default
    self._move_to_front(node)    # обращение = использование -> в голову
    return node.value

def put(self, key, value):
    node = self._store.get(key)
    if node is not None:         # ключ уже есть — обновляем и освежаем
        node.value = value
        self._move_to_front(node)
        return
    new_node = Node(key, value)  # новый ключ — в dict и в голову списка
    self._store[key] = new_node
    self._add_front(new_node)
    if len(self._store) > self._capacity:
        self._evict()            # переполнение — выкидываем LRU (хвост)

def _evict(self):
    lru = self._tail.prev        # перед часовым хвостом — наименее недавний
    self._remove(lru)
    del self._store[lru.key]     # вот зачем ключ хранится в узле

Главная идея политики LRU: вытесняется не самый старый по вставке, а наименее недавно использованный. Любое обращение (get, а также put с обновлением) переводит ключ в голову и отодвигает момент его вытеснения. Поэтому «горячие» ключи, к которым обращаются часто, в кэше задерживаются, а «холодные» — выпадают первыми.

Разбор последовательности (capacity = 2)¶

Операция	Состояние MRU → LRU	Комментарий
`put(1)`	`[1]`
`put(2)`	`[2, 1]`	2 свежее
`get(1)` → `1`	`[1, 2]`	1 освежён, стал MRU
`put(3)`	`[3, 1]`	переполнение → вытеснен 2 (LRU)
`get(2)` → промах	`[3, 1]`	2 уже вытеснен
`put(4)`	`[4, 3]`	вытеснен 1

Обратите внимание: если бы get(1) не было, при put(3) вытеснился бы 1. Само обращение к ключу спасло его от вытеснения — это и есть суть LRU.

Сложность¶

Операция	Сложность	Почему
`get`	O(1)	поиск в `dict` + перецепление ссылок
`put`	O(1)	поиск/вставка в `dict` + работа со списком
вытеснение `_evict`	O(1)	хвост известен сразу (перед `_tail`)
`keys_mru_to_lru` / печать	O(n)	проход по всему списку

Память — O(capacity): по одному узлу и записи в dict на каждый хранимый ключ.

Где это в проде¶

LRU и его родственники — это буквально то, как устроено вытеснение в инфраструктуре, которую эксплуатирует SRE:

Redis / Memcached. При достижении лимита памяти Redis применяет политику вытеснения (maxmemory-policy): allkeys-lru / volatile-lru — приближённый LRU (Redis не держит точный список ради экономии памяти, а сэмплирует кандидатов), есть и allkeys-lfu (по частоте). Memcached использует LRU по слабам (slab classes). Понимание LRU объясняет, почему именно эти ключи выживают, а эти выпадают, и почему «горячие» данные остаются в кэше.
Кэш CDN (edge). Узлы CDN хранят популярный контент близко к пользователю, вытесняя редко запрашиваемые объекты — те же MRU/LRU, только объекты — это файлы и ответы.
Кэш страниц БД (buffer pool). PostgreSQL (clock-sweep, родственник LRU), MySQL/InnoDB (LRU-список buffer pool), страничный кэш ОС — все держат «горячие» страницы в RAM и вытесняют холодные, чтобы избегать дорогих чтений с диска.

Почему кэш «промахивается» и зачем правильный размер. Промах (cache miss) — это запрос ключа, которого в кэше уже нет: его либо никогда не клали, либо вытеснили под давлением ёмкости. Если кэш мал относительно рабочего множества (working set) запросов, полезные данные вытесняются раньше, чем к ним обратятся снова — растёт доля промахов (miss rate), и каждый промах оборачивается дорогим походом в БД/на диск/по сети. Слишком большой кэш — это зря потраченная дорогая RAM и риск, что вытеснение/обслуживание самого кэша начнёт стоить дороже выгоды. Поэтому подбор capacity (а на практике — maxmemory, размер buffer pool, объём edge-хранилища) под реальный working set — это прямая работа по производительности: цель — держать hit rate высоким при разумном расходе памяти. Патологический случай — cache thrashing: рабочее множество чуть больше кэша, и при последовательном переборе ключей LRU вытесняет ровно тот элемент, который понадобится следующим, давая почти 100% промахов.

Меню¶

menu создаёт LRU-кэш небольшой ёмкости и в цикле читает выбор:

Пункт	Действие
1	`put` — добавить/обновить пару `ключ=значение` (ключ освежается)
2	`get` — получить значение по ключу (обращение освежает ключ)
3	`peek` — подсмотреть значение, не меняя порядок использования
4	Напечатать кэш в порядке MRU → LRU
5	Демонстрация вытеснения (`demo_eviction`)
6	Пересоздать кэш с новой ёмкостью
0	Выход

Пункт 5 (demo_eviction) — наглядный ответ на вопрос «кого вытеснит LRU»: на кэше ёмкости 2 видно, как get освежает ключ и меняет жертву вытеснения, а пункт 3 (peek) показывает обратное — чтение без освежения порядка не спасает ключ от вытеснения.