# Как построить идеальный кэш: алгоритмический баттл Machine Learning Street Talk

Источник: https://www.youtube.com/watch?v=rLOz9naqZMI
Канал: Machine Learning Street Talk
Опубликовано: 01.03.2023

---

В новом выпуске канала **Machine Learning Street Talk** ведущий Тим Скарф устроил необычный технический челлендж для своих гостей — ведущих ученых из Google DeepMind и Mila. В роли интервьюируемого выступил **Петар Величкович** (Petar Veličković), известный исследователь в области графовых нейронных сетей, который в прошлом был успешным участником олимпиад по программированию (ICPC) [0:02]. 

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

## 🧠 Проблема кэширования: три уровня сложности
[[JUMP:0:40]]

Тим Скарф предложил спроектировать класс `Cache`, способный хранить миллионы и даже миллиарды объектов (например, видео с YouTube) [1:19]. Основное требование: метод `get` должен работать за константное время $O(1)$, а метод `set` — максимально быстро [0:40].

Каждый элемент в кэше характеризуется четырьмя параметрами:

1. **Key** (ключ) — строка.
2. **Value** (значение) — объект.
3. **Priority** (приоритет) — число.
4. **Expiration** (время истечения) — системное время [1:49].

Главная сложность заключается в правилах вытеснения (eviction) элементов при переполнении кэша:

*   **Правило А (Срок годности):** Если есть элементы, время жизни которых истекло (expiration < текущего времени), нужно удалить один из них [3:10].
*   **Правило Б (Приоритет и LRU):** Если истекших элементов нет, нужно удалить элемент с самым низким приоритетом. Если таких несколько — удаляется наименее востребованный из них (Least Recently Used, LRU) [3:38].

## 🛠 Построение архитектуры: от хэш-таблиц к кучам
[[JUMP:6:02]]

Петар Величкович начал решение с обеспечения константного времени для метода `get`. Для этого необходима **хэш-таблица** (Hash Table), которая отображает ключи напрямую на значения (или ссылки на узлы в других структурах) [10:28].

Для реализации **Правила А** (удаление истекших элементов) Величкович предложил использовать **очередь с приоритетом** (Priority Queue), реализованную на базе бинарной кучи (Binary Heap) [9:49].

*   Ключом в этой куче выступает время истечения (expiration).
*   При вызове `set` система проверяет корень кучи. Если время в корне меньше текущего, элемент извлекается и удаляется из основной хэш-таблицы [10:15].
*   В случае совпадения времени истечения используется дополнительное сравнение по ключу для детерминированности [13:11].

Однако возникла проблема согласованности данных: если элемент удаляется по правилу приоритета, его нужно быстро найти и удалить и из кучи истечения срока. В стандартной куче удаление из середины занимает линейное время $O(n)$, что недопустимо [11:08].

## ⚖️ Балансировка и Red-Black Trees
[[JUMP:18:02]]

Чтобы добиться логарифмической сложности $O(\log n)$ для удаления элементов из произвольного места, Петар предложил заменить бинарные кучи на **сбалансированные бинарные деревья поиска** (Balanced BST), такие как Красно-черные деревья (Red-Black Trees) [18:28].

Ведущие кратко обсудили принципы работы красно-черных деревьев:

*   Они обеспечивают логарифмическую высоту дерева за счет операций вращения [18:55].
*   Существуют строгие правила раскраски узлов (например, у красного узла не может быть красных детей, а листья всегда черные) [19:23].
*   Петар признался, что, несмотря на знание теории, ему никогда не приходилось реализовывать красно-черное дерево «с нуля» на практике [18:28].

## 🔗 Финальный штрих: Интеграция LRU
[[JUMP:20:32]]

Самым сложным этапом стала интеграция правила Least Recently Used (LRU) внутрь иерархии приоритетов. Величкович предложил структуру, где каждый узел в дереве приоритетов указывает не на один элемент, а на **двусвязный список** (Doubly Linked List) [24:14].

Механика работы:

1.  Все элементы с одинаковым приоритетом находятся в одном списке.
2.  При обращении к элементу через `get`, он перемещается в «голову» своего списка (splice-операция), что занимает $O(1)$ [23:48].
3.  Хэш-таблица при этом должна хранить прямые указатели на узлы в этих двусвязных списках, чтобы обновление позиции происходило мгновенно [24:14].
4.  При необходимости вытеснения по приоритету, система берет узел с минимальным приоритетом из BST и удаляет элемент из «хвоста» его списка [24:00].

## 🚀 Асимптотика и «олимпиадные» хитрости
[[JUMP:24:40]]

Итоговая сложность метода `set` в предложенной архитектуре составила **$O(\log n)$**, где $n$ — количество элементов в кэше [25:08]. Петар отметил, что если количество уникальных приоритетов фиксировано и невелико, можно использовать «корзины» (buckets) и свести сложность к $O(1)$ для операций с приоритетами [27:22].

Для еще более экстремальной оптимизации Величкович упомянул **деревья ван Эмде Боаса** (van Emde Boas trees или vEB-trees), которые позволяют выполнять операции за **$O(\log \log n)$** [11:35]. Однако такие структуры требуют, чтобы ключи были представлены в виде битовых строк ограниченной вселенной [11:49].

В завершение беседы Петар вспомнил, что подобную задачу на проектирование LRU-кэша ему давали на реальном собеседовании в Google в 2015 году [28:14]. Тим Скарф в шутку резюмировал, что с таким решением он бы точно нанял Петара на работу [28:14].