CS Notes

lru-cache

5 min read

LRU-кэш

Предпосылки: хеш-таблица (O(1) доступ по ключу), связный список (двусвязный, O(1) удаление/вставка).

Хеш-таблица даёт O(1) доступ по ключу, но не ограничивает количество элементов и не подсказывает, кого удалить при нехватке места. Для кэша с ограниченной ёмкостью нужна политика вытеснения. Простая эвристика: если к элементу давно не обращались, он скорее всего не понадобится. Это политика LRU — Least Recently Used, “наименее недавно использованный”.

LRU-кэш — словарь с ограниченной ёмкостью и автоматическим вытеснением:

ОперацияСигнатураСложность
Получить значениеget(key) → valueO(1)
Записать значениеput(key, value)O(1)

При превышении capacity автоматически вытесняется элемент, к которому дольше всего не обращались.

get(key) возвращает значение и делает элемент “свежим”; если ключа нет — nil. put(key, value) записывает значение, делает элемент “свежим”, а при переполнении вытесняет самый старый.

Пример работы (capacity = 2)

put("a", 1) → [a]
put("b", 2) → [b, a]
get("a")    → [a, b]        a стал свежим
put("c", 3) → [c, a]        b вытеснен (был tail)
get("b")    → nil           b уже нет в кэше

Почему нужны две структуры

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

Структура

HashMap: key → Node

Doubly Linked List: head (свежий) ⇄ ... ⇄ tail (старый)

Узел хранит: key, value, prev, next

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

Реализация (Ruby)

class Node
  attr_accessor :key, :value, :prev, :next
 
  def initialize(key, value)
    @key = key
    @value = value
    @prev = nil
    @next = nil
  end
end
 
class LRUCache
  def initialize(capacity)
    @capacity = capacity
    @hash = {}
    @head = nil  # свежий конец
    @tail = nil  # старый конец
  end
 
  def get(key)
    node = @hash[key]
    return nil unless node
    return node.value if node == @head
 
    remove_node(node)
    add_to_head(node)
    node.value
  end
 
  def put(key, value)
    if @hash.key?(key)
      node = @hash[key]
      node.value = value
      remove_node(node)
      add_to_head(node)
    else
      node = Node.new(key, value)
      @hash[key] = node
      add_to_head(node)
 
      if @hash.size > @capacity
        # Важен порядок! Сначала удаляем из хеша, потом из списка
        @hash.delete(@tail.key)
        remove_node(@tail)
      end
    end
  end
 
  private
 
  def remove_node(node)
    if node.prev
      node.prev.next = node.next
    else
      @head = node.next
    end
 
    if node.next
      node.next.prev = node.prev
    else
      @tail = node.prev
    end
  end
 
  def add_to_head(node)
    node.prev = nil
    node.next = @head
 
    if @head
      @head.prev = node
    else
      @tail = node
    end
 
    @head = node
  end
end

remove_node обрабатывает три случая. В общем (узел в середине): соседи перелинковываются друг на друга — prev.next на next, next.prev на prev. Если узел — tail: предыдущий становится новым tail — та же проблема инвалидации двух указателей на одну структуру, что и в связном списке. Если узел единственный (он и head, и tail): оба обнуляются.

В get удаление head не происходит — ранний возврат на node == @head. При вытеснении удаляется всегда tail. Ветка @head = node.next нужна для полноты remove_node как универсального метода (например, при добавлении delete(key) в расширенном API).

add_to_head вставляет узел в начало, делая его “свежим”. Проверка @tail = node при пустом списке — симметричная задача: если head обновился, tail может потребовать обновления.

Критичный баг с порядком операций

При вытеснении нужно удалить tail из хеш-таблицы и из списка. Порядок этих двух действий критичен: remove_node(@tail) обновляет @tail на предпоследний узел — после этого @tail.key указывает уже не на вытесняемый элемент.

# НЕПРАВИЛЬНО:
remove_node(@tail)         # @tail обновляется на предпоследний!
@hash.delete(@tail.key)    # удаляем ключ НОВОГО tail!
 
# ПРАВИЛЬНО:
@hash.delete(@tail.key)    # сначала берём ключ старого tail
remove_node(@tail)         # потом удаляем узел

Сложность

ОперацияВремяПочему
getO(1)Хеш O(1) + манипуляции O(1)
putO(1)Хеш O(1) + манипуляции O(1)

Альтернатива: LFU

LRU хорошо работает, когда паттерн доступа меняется: недавнее обращение — хороший предиктор будущего. Но что если паттерн стабилен и есть чёткое разделение на “горячие” и “холодные” данные? Тогда частота обращений — лучший сигнал, чем время последнего.

LFU (Least Frequently Used) вытесняет элемент с наименьшим количеством обращений за всё время. LRU смотрит на время последнего обращения, LFU — на частоту.

Проблема LFU — cache pollution (загрязнение кэша):

T=0-100: страница A читается 1000 раз, count=1000
T=101:   страница A больше никому не нужна
T=102:   страница B нужна, count=1
T=103:   нужно вытеснить кого-то

LFU выберет B (count=1), хотя A уже бесполезна.

Элемент, популярный в прошлом, “застревает” в кэше из-за высокого счётчика. Он вытесняет новые элементы, которые могли бы быть полезны.

При стабильном паттерне доступа LFU лучше LRU. При меняющемся — наоборот.

Проблема: contention в многопоточной среде

LRU работает идеально по сложности, но при каждом обращении нужно переместить элемент в начало списка. Это 4 записи в указатели:

  1. node.prev.next = node.next
  2. node.next.prev = node.prev
  3. head.prev = node
  4. node.next = head

Эти изменения должны быть согласованы — иначе список развалится. На практике это означает блокировку, пускающую только один поток за раз. Альтернатива — более сложные реализации без блокировок.

Поток 1: хочет переместить элемент A → ждёт блокировку
Поток 2: хочет переместить элемент B → ждёт блокировку
...
1000 потоков ждут одну блокировку → bottleneck

В однопоточной программе это не проблема. Но сервер базы данных с тысячами параллельных запросов к кэшу — это постоянное ожидание на блокировке. Clock-Sweep решает эту проблему, заменяя манипуляции со списком атомарным инкрементом.

См. также

Graph View

Backlinks