Что такое LRU-кэш — и почему кэш без лимита превращается в утечку памяти

Ты сделал быстрый кэш. Обычный объект: ключ — адрес запроса, значение — ответ.

const cache = {};

async function getUser(id) {
  if (cache[id]) return cache[id];
  const user = await fetch(`/api/users/${id}`).then(r => r.json());
  cache[id] = user;
  return user;
}

Неделю всё летает. А потом сервер падает с «out of memory». Смотри, в чём подвох: этот кэш только растёт. Каждый новый id остаётся в памяти навсегда. Кэш без лимита — это не ускорение, а очень медленная утечка памяти.

Нужен лимит. А с лимитом встаёт вопрос: когда место кончилось, что выкинуть? Вот на него и отвечает LRU.

Что такое LRU простыми словами

LRU — Least Recently Used, «давно не использованный». Правило одно: когда кэш полон, выкидываем ту запись, к которой дольше всех не обращались.

Представь полку ровно на пять книг. Взял книгу почитать — поставил её обратно в левый край. Новую книгу тоже ставишь слева. Места нет — с правого края падает самая запылённая. На полке всегда пять книг, которые ты трогал последними.

Это и есть весь алгоритм. Тонкость в одном слове: использование. Чтение записи двигает её в «свежие», а не только запись.

Как это работает

Кэшу нужно две операции, обе быстрые:

1. Достать по ключу — и пометить запись как свежую.
2. Положить новую запись — и, если места нет, выкинуть самую старую.

Классическая реализация — хеш-таблица плюс двусвязный список. Таблица находит запись мгновенно, список хранит порядок «от свежих к старым». Обе операции работают за постоянное время, сколько бы записей ни было.

В JavaScript есть хитрость попроще. Map помнит порядок вставки. Значит, первый ключ в Map — самый старый. А чтобы освежить запись, её удаляют и вставляют заново — она уезжает в конец.

class LRU {
  constructor(limit) {
    this.limit = limit;
    this.map = new Map();
  }
  get(key) {
    if (!this.map.has(key)) return undefined;
    const value = this.map.get(key);
    this.map.delete(key);      // вынули
    this.map.set(key, value);  // и поставили в конец — теперь свежая
    return value;
  }
  set(key, value) {
    this.map.delete(key);
    this.map.set(key, value);
    if (this.map.size > this.limit) {
      const oldest = this.map.keys().next().value;
      this.map.delete(oldest);  // самая давняя — первая в Map
    }
  }
}

Проверь руками, лимит 2: set(a), set(b), get(a), set(c). Кого выкинет? Не a — её только что читали. Выкинет b. Это главный момент: обычная очередь «первым пришёл — первым ушёл» выкинула бы a.

Зачем это тебе

• Память под контролем. Кэш больше не растёт бесконечно. Ты сам решаешь: 500 записей — и точка.
• Горячее остаётся. Популярные записи читают постоянно, и они не стареют. Редкие уходят сами.
• Ноль настройки. Не нужно гадать, сколько хранить каждую запись. Порядок обращений решает за тебя.

Где LRU слаб. Один большой проход по редким данным — отчёт, экспорт, бот-краулер — вытесняет всё горячее. Полку завалили книгами, которые больше никто не откроет. Против этого придумали LFU (выкидывать редко используемое) и гибриды.

Ещё LRU не отвечает на вопрос свежести. Запись может быть «горячей», но устаревшей. Поэтому LRU обычно ставят вместе со сроком жизни записи. Подробнее про сроки и инвалидацию — в статье про кэширование. А что бывает, когда горячая запись протухает у всех разом, — в разборе cache stampede.

Где ты его встретишь

• Redis. При maxmemory-policy allkeys-lru он вытесняет давно не тронутые ключи. Но LRU там приблизительный: Redis берёт 5 случайных ключей (maxmemory-samples, по умолчанию 5) и выкидывает самый старый из них. Точный LRU на миллионах ключей стоил бы слишком много памяти.
• Пакет lru-cache в npm. Его используют в куче инструментов Node.js. Умеет и лимит по количеству, и срок жизни.
• Кэш процессора и страниц памяти в операционной системе — там LRU и его приближения работают десятилетиями.
• Кэш ответов ИИ. Если ты кэшируешь ответы модели, LRU с лимитом спасает от счёта за память.

Чем LRU отличается от очереди с приоритетом?

Очередь отдаёт элемент с наименьшим приоритетом, который ты задал сам. LRU приоритет не спрашивает — его задаёт время последнего обращения. Подробно про очереди — в статье про priority queue.

Какой лимит ставить?

Начни с объёма, который не жалко держать в памяти, и смотри на долю попаданий. Если попаданий уже 90% и рост лимита их почти не меняет — лимит найден.

Можно ли просто удалять старые записи по таймеру?

Можно, это TTL. Но он не ограничивает размер: за час может прийти миллион новых ключей. Надёжнее держать оба правила сразу — лимит по количеству и срок жизни.