backend · intermediate · 4d
LRU-кэш
Собери LRU-кэш с вытеснением за O(1) на связке хешмапы и двусвязного списка — та самая задача, которая показывает, почему вытеснение из кэша сложнее, чем кажется.
Результат
Класс LRUCache<K,V> с O(1) get, put, has и size, реализованный на хешмапе и двусвязном списке, с корректным LRU-вытеснением, обновлением давности при чтении и опциональным TTL — доказано acceptance-сьютом.
Этапы
0/6 · 0%- 01Наивная реализация: Map с O(n)-вытеснением
Прежде чем браться за оптимальную структуру, реализуй рабочий кэш на обычном Map<K,V>, чтобы сначала зафиксировать контракт корректности. При переполнении ёмкости обходи мап в поиске наиболее давно использованной записи, отслеживая порядок вставки/доступа в параллельном массиве или сравнивая метки времени. Это O(n) на вытеснение — недопустимо на масштабе, — но это заставит тебя написать тестовый жгут, определить интерфейс (get, put, has, size) и точно зафиксировать контракт вытеснения: засчитывается ли put по существующему ключу как использование? засчитывается ли get по отсутствующему ключу? вообще считается ли чтение использованием? Разберись с каждым граничным случаем в тестах до оптимизации. Неверный порядок вытеснения здесь молча просочится в каждый следующий этап.
Критерии готовности- get/put/has/size работают корректно, а вытеснение удаляет действительно наиболее давно использованный ключ (и чтения, и записи обновляют давность).
- Тестовая последовательность из не менее шести операций доказывает корректный порядок вытеснения, а put по существующему ключу обновляет значение, не увеличивая ёмкость.
Самопроверка
Пройди по порядку вытеснения после put(A), put(B), put(C) при capacity=2, затем get(A): senior-ревьюер проверяет, что на следующем put вытесняется B (а не A), и что твой O(n)-скан правильно упорядочен по времени доступа, а не вставки.
- 02Хешмапа + двусвязный список: O(1) везде
Замени O(n)-скан каноническим сочетанием структур данных: Map<K, Node<K,V>> для O(1)-поиска и двусвязный список для O(1)-упорядочения. Голова списка — конец с наиболее недавно использованным элементом; хвост — с наиболее давно использованным, который и вытесняется. Каждый get и put перемещает затронутый узел в голову — это операция с постоянным временем, если узел хранит прямые указатели prev/next. Классический приём — сторожевые узлы на обоих концах (фиктивная голова и фиктивный хвост), чтобы не было граничных случаев с null-указателями при вставках и удалениях на границах. С сторожевыми узлами вставка-в-голову и удаление-из-хвоста — двустрочные операции без условных переходов — именно это структурное прозрение и делает их O(1). Убедись, что мап и список всегда синхронизированы: каждый map.set имеет парный list.insertAtHead, каждый map.delete имеет парный list.remove.
Критерии готовности- get, put и вытеснение выполняются за O(1) без итерации по списку или мапу — подтверждено чтением кода, а не тестом на время.
- Сторожевые узлы используются, чтобы вставка-в-голову и удаление-из-хвоста были безусловными, а map.size === list.length — инвариант, который можно утверждать в любой точке.
Самопроверка
Покажи код сращивания для перемещения узла в голову: senior-ревьюер проверяет, что это четыре присваивания указателей без специальных случаев для пустого списка или списка из одного элемента, и что сторожевые узлы это обеспечивают.
- 03Давность при чтении: get() обновляет давность, put() по существующему ключу тоже
Этот этап — про точность семантики давности. Есть два независимых правила: (1) успешный get(k) обязан перемещать узел в голову списка (самый недавно использованный конец), чтобы горячий читаемый ключ никогда не вытеснялся; (2) put(k, v) по существующему ключу обязан обновить значение И переместить узел в голову БЕЗ увеличения size, потому что число записей не меняется. Вместе оба правила означают, что элемент может быть защищён от вытеснения только за счёт чтений — это именно то свойство, которое нужно read-heavy кэшу для часто запрашиваемых объектов. Частая ошибка — забыть правило (2) и оставить повторно вставленный существующий ключ на его старой позиции в списке: значение обновляется, но для порядка вытеснения запись устаревает. Докажи оба правила явными тестовыми последовательностями.
Критерии готовности- Тестовая последовательность доказывает, что ключ, доступ к которому был через get(), переживает нетронутый ключ того же возраста при превышении ёмкости.
- put по существующему ключу обновляет значение и перемещает в голову, но cache.size остаётся прежним — доказано утверждением после put.
Самопроверка
Проследи состояние связного списка после: put(A,1) put(B,2) get(A) put(C,3) при capacity=2. Senior-ревьюер проверяет, что третий put вытесняет B, а не A, и что после список упорядочен как [C, A].
- 04Политика вытеснения: граничные случаи, capacity=1, инвариант size
Укрепи логику вытеснения против случаев, ломающих наивные реализации. Capacity=1 — особенно острый граничный случай: любой put нового ключа обязан вытеснить единственную существующую запись, даже если она только что была прочитана. Capacity=0 нужно обработать (хотя это вырожденный случай — каждый put — немедленное вытеснение, каждый get — промах). Когда put вызывается с ключом, уже стоящим в голове LRU-списка (позиция наиболее недавно использованного), код сращивания не должен портить список, пытаясь переместить узел, уже стоящий на нужном месте — путь no-op для этого случая обязателен. Также проверяй инвариант size во всех операциях: size должен равняться числу живых ключей, никогда не превышать capacity и не считать сторожевые узлы. Тонкая ловушка — паттерн delete-then-reinsert: delete(k) с последующим put(k,v) обязан создавать новый узел со свежей давностью, а не воскрешать висячий указатель.
Критерии готовности- capacity=1 корректно вытесняет при каждом put нового ключа, а get возвращает undefined сразу после вытеснения.
- Повторный put по ключу на позиции MRU (уже в голове) не портит список, а size остаётся стабильным — доказано проверкой всех результатов get после.
Самопроверка
Покажи, что происходит при вызове put(K,V) по ключу, стоящему сейчас в позиции головы — обрабатывает ли твой код сращивания случай 'node.prev === sentinel.head', или он портит указатели next/prev? Senior-ревьюер хочет увидеть явный no-op-guard.
- 05TTL-вариант: истечение по времени без фоновых таймеров
Расширь кэш опциональным per-entry TTL (время жизни). Вызов get(k) по просроченной записи обязан возвращать undefined и удалять запись, как будто её никогда не было — это ленивое истечение при доступе, а не проактивная очистка. Никогда не используй setTimeout на запись: это утечка памяти, пропорциональная числу записей, она мешает сборщику мусора утилизировать вытесненные узлы и срабатывает даже после того, как запись вытеснена давлением ёмкости. Вместо этого записывай метку истечения на узел в момент put и проверяй её в момент get. Хитрый инвариант: просроченная-но-ещё-не-тронутая запись всё ещё занимает слот в счётчике ёмкости, потому что ленивое истечение чистит только при касании. Если нужна проактивная очистка, реализуй O(1)-амортизированную выборку, итерируясь с хвоста LRU (записи с наибольшей вероятностью устаревания), чтобы выборка оставалась эффективной. Инъектируемые часы здесь обязательны — тесты не могут спать.
Критерии готовности- get(k) по просроченной записи возвращает undefined, удаляет запись (has(k) равно false) и не обновляет LRU-давность.
- setTimeout и setInterval не используются — истечение чисто ленивое (проверяется при доступе) с инъектируемыми часами, и юнит-тест подтверждает истечение без sleep.
Самопроверка
Если TTL-запись сидит в кэше и к ней никогда не обращаются, она всё равно занимает слот ёмкости. Senior-ревьюер спрашивает: когда она очищается, и есть ли сценарий, когда кэш заполняется просроченными-но-непрочитанными записями, из-за чего корректные новые put отклоняются? Покажи, как твой дизайн это предотвращает или явно это принимает.
- 06Инструментация hit rate: хиты, промахи, вытеснения и реальная цена cache pollution
Кэш без инструментации — чёрный ящик: невозможно понять, помогает он или вредит. Добавь лёгкие счётчики: хиты (get вернул живое значение), промахи (get вернул undefined — будь то отсутствующий ключ или истёкший TTL), вытеснения (запись удалена из-за ёмкости) и истечения (TTL-истечение сработало при доступе). Выставляй метод stats(), возвращающий все четыре. Senior-прозрение здесь: высокий hit rate сам по себе вводит в заблуждение: если кэш достаточно велик, чтобы вместить всё, hit rate — 100%, но ты несёшь устаревшую или неиспользуемую память. Отношение eviction rate к put rate говорит, правильно ли размерен кэш (очень высокий eviction rate = кэш меньше рабочего набора). Отношение expiration rate к eviction rate говорит, не слишком ли короткий TTL (большинство записей истекают до вытеснения). Имея числа, рассуждай об оптимальной ёмкости для заданного паттерна доступа — для Zipf-распределённого паттерна (верхние 20% ключей получают 80% запросов) кэш размером 20% от пространства ключей достигает почти пикового hit rate при доле памяти от кэширования всего.
Критерии готовности- stats() возвращает { hits, misses, evictions, expirations } — все нули при конструировании, и каждый счётчик увеличивается ровно один раз на квалифицирующее событие.
- Ты можешь объяснить в одном абзаце, почему кэш с 95% hit rate может быть всё равно избыточно большим — используя eviction rate как подтверждающее свидетельство.
Самопроверка
Кэш имеет hit rate 90%, eviction rate близкий к нулю и expiration rate близкий к нулю. Senior-ревьюер спрашивает: этот кэш хорошо размерен, недостаточно или избыточно? Что изменится, если уменьшить ёмкость вдвое — и как твой stats() скажет тебе, ухудшило ли это производительность?
Стартер
- README.md
- src/cache.ts
- test/cache.test.ts
Распакуй, реализуй заглушки, затем гоняй тесты, пока не позеленеют: bun test
Рубрика
| Джуниор | Миддл | Сеньор | |
|---|---|---|---|
| O(1)-операции и структура | Map с параллельным массивом порядка или метками времени даёт корректное вытеснение, но сканирует O(n) на каждый put сверх ёмкости. | Хешмапа + двусвязный список со сторожевыми узлами делает get, put и вытеснение O(1); map.size === list.length — инвариант, поддерживаемый во всех операциях. | Код сращивания обрабатывает случай «уже в голове» без повреждающих ветвей, capacity=1 и capacity=0 явно обработаны, и ты можешь объяснить, почему сторожевые узлы устраняют все null-pointer-условия в вставке-в-голову и удалении-из-хвоста. |
| Корректность давности и вытеснения | Вытеснение удаляет запись, вставленную раньше всех (FIFO), а не ту, к которой дольше всего не обращались — чтения не обновляют давность. | И get(), и put() по существующему ключу перемещают узел в голову MRU; put нового ключа вытесняет с хвоста LRU; size не увеличивается при обновлении значения. | Ты можешь проследить состояние списка через чередующуюся последовательность get и put и предсказать точный порядок вытеснения; случай (c) сьюта — ключ, спасённый get, переживающий нетронутый ключ того же возраста — проходит не случайно, а потому что сращивание корректно проводится. |
| Память, TTL и hit rate на масштабе | У кэша нет TTL и счётчиков; невозможно сказать, помогает ли он, без добавления внешнего логирования. | Ленивое TTL-истечение при доступе с инъектируемыми часами (без setTimeout), и stats() выставляет счётчики hit/miss/eviction/expiration, чтобы можно было считать hit rate без внешних инструментов. | Ты можешь судить по отношению eviction rate к put rate, правильно ли размерен кэш для рабочего набора, объяснить, почему близкий к нулю eviction rate при высоком hit rate говорит об избыточном кэше, и сформулировать режим отказа cache pollution, когда последовательный скан вытесняет все горячие записи в чистой LRU-политике. |
Эталонный разбор (спойлер)
Почему одной хешмапы недостаточно для O(1)-вытеснения: хешмапа даёт O(1)-поиск и O(1)-удаление по ключу, но чтобы вытеснить LRU-запись, сначала нужно её найти — а это без обхода всех ключей или отдельной упорядоченной структуры невозможно. Двусвязный список — минимальная упорядоченная структура, поддерживающая O(1)-вставку в голову и O(1)-удаление из хвоста, так что вместе они дают O(1) для всего. Любая другая упорядоченная структура (куча, сбалансированное дерево) сделала бы вытеснение O(log n).
Почему сторожевые узлы устраняют граничные ветви: без сторожевых узлов вставка-в-голову должна проверять «пуст ли список?», а удаление-из-хвоста — «это последний узел?» — оба добавляют условные ветви, которые легко сделать неправильными под конкурентной нагрузкой. Фиктивные голова и хвост означают, что head.next — всегда MRU-узел (или tail, если пусто), а tail.prev — всегда LRU-узел (или head, если пусто) — никаких null-проверок, никаких специальных случаев, четыре безусловных присваивания указателей на сращивание.
Ленивое vs проактивное истечение TTL: ленивое истечение (проверка при доступе) — O(1) на операцию, но оставляет просроченные записи занимающими слоты ёмкости до касания. Проактивное истечение (фоновая выборка) держит кэш плотнее, но вводит фоновый таймер или проход выборки O(просроченных-за-выборку). Компромисс — амортизированная выборка: при каждом put вытеснять не более k просроченных записей с LRU-хвоста — записи там старейшие и наиболее вероятно просроченные — так что стоимость истечения ограничена O(k) на операцию без фонового потока.
Cache pollution при последовательных сканированиях: чистый LRU вытесняет глобально наиболее давно использованную запись. Полный последовательный скан N ключей в кэше ёмкостью N заменяет каждую горячую запись записями сканирования, к которым больше никогда не обратятся — hit rate падает до нуля на время скана, затем медленно восстанавливается при повторном прогреве горячих записей. Алгоритмы 2Q и LIRS решают это, держа испытательную очередь для записей первого доступа: запись сканирования принимается, но не продвигается в горячую очередь до второго обращения, так что трафик одноразового скана не вытесняет горячие записи.
Что на самом деле говорит hit rate: hit rate близкий к 100% не всегда хорош — если рабочий набор меньше ёмкости кэша, ты никогда ничего не вытесняешь и каждый запрос попадает в кэш, но ты тратишь память впустую. Полезные сигналы — hit rate в соотношении с eviction rate: высокий hit rate с близким к нулю eviction rate означает избыточный кэш; высокий hit rate с высоким eviction rate означает, что кэш хорошо соответствует рабочему набору. Для Zipf-распределённых паттернов доступа кэш размером 20–30% от пространства ключей захватывает 80–90% трафика — именно поэтому продакшн-кэши размерены значительно ниже полного датасета.
Сделай по-сеньорски
- Докажи амортизированное O(1) для TTL-выборки, ограничив число удалений с хвоста на каждый put: реализуй выборку как «вытеснять не более k просроченных записей с хвоста на put» и покажи, что при k=1 амортизированная стоимость на операцию всё ещё O(1), а просроченные записи очищаются в течение O(capacity) последующих put.
- Добавь эвристику настройки ёмкости: выставь метод resize(newCapacity), который сливает LRU-записи до тех пор, пока size ≤ newCapacity за O(вытесненных) время, и проверь, что все инварианты сохраняются после живого изменения размера под конкурентными чтениями.
- Реализуй вариант Two-Queue (2Q) или LIRS, устойчивый к cache pollution от последовательных сканирований: один полный скан из N ключей в кэше ёмкостью N вытеснит все горячие записи в чистом LRU, но 2Q принимает записи скана в испытательную очередь и продвигает их только при втором доступе — сравни разницу в hit rate при смешанной нагрузке из горячих ключей и сканирования.
- Расширь stats() временным рядом hit rate в секунду и сканированием, выявляющим top-K самых горячих ключей с момента последнего сброса — используй min-кучу размером K над Map<K, hitCount>, чтобы скан был O(N log K) — и обоснуй, когда учёт O(N log K) оправдан по сравнению с простым наблюдением за глобальным hit rate.