LRU-кэш

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

← Хеш-таблица | Clock-Sweep →

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

И вот таблица заполнена, а приходит 1001-й элемент. Места нет. Один из старых элементов придётся выбросить, чтобы освободить ячейку, — это и называется вытеснением. Вопрос только в том, какой именно: выброшенный по ошибке элемент скоро запросят снова, и его придётся доставать из медленного источника заново. Значит, нужно правило выбора жертвы — политика вытеснения.

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

LRU-кэш — таблица «ключ → значение» с ограниченной ёмкостью и автоматическим вытеснением. Две операции:

Операция	Что делает	Сложность
`get(key)`	вернуть значение по ключу	O(1)
`put(key, value)`	записать значение по ключу	O(1)

get(key) возвращает значение и помечает элемент «свежим» (к нему только что обратились); если ключа нет — возвращает «ничего» (в коде ниже — nil). put(key, value) записывает значение и тоже делает элемент свежим, а если после этого размер превысил ёмкость — выбрасывает самый старый.

Что происходит при обращениях

Вместимость — 2 элемента. Внутри скобок — порядок от свежего (слева) к старому (справа):

put("a", 1) -> [a]
put("b", 2) -> [b, a]
get("a")    -> [a, b]        a снова свежий, b сместился к старому концу
put("c", 3) -> [c, a]        b выброшен: он был самым старым
get("b")    -> nil           b в кэше больше нет

Каждое обращение двигает элемент к свежему концу. Выбрасывается всегда тот, кто оказался на старом конце, — он дольше всех не использовался.

Почему одной структуры мало

Чтобы поддержать обе операции за O(1), нужно делать две разные вещи быстро: находить элемент по ключу и переупорядочивать элементы по свежести.

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

Ни одна структура не закрывает обе операции. Решение — держать обе и связать их: хеш-таблица отвечает за поиск, список — за порядок.

Как связаны две структуры

Хеш-таблица: ключ -> узел списка

Список (двусвязный): голова (свежий) <-> ... <-> хвост (старый)

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

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

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

Реализация

Узел — это значение, ключ и две ссылки на соседей по списку: prev (в сторону свежего конца) и next (в сторону старого):

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

get и put опираются на две вспомогательные операции со списком: вырвать узел из его текущего места и вставить узел в голову. Обе сводятся к переписыванию ссылок у соседей:

  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, и узел выпадает из цепочки. Узел на хвосте: новым хвостом становится предыдущий. Единственный узел (он и голова, и хвост): обе ссылки кэша обнуляются. Когда обновляется один конец, второй тоже может потребовать обновления, — поэтому в add_to_head есть ветка @tail = node для пустого списка.

В get голова не удаляется зря: ранний возврат на node == @head пропускает уже свежий узел. При вытеснении убирается всегда хвост. Ветка @head = node.next в remove_node нужна не для текущих операций, а чтобы метод оставался полным, если позже добавить удаление произвольного ключа.

Почему порядок удаления критичен

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

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

@tail.key нужно прочитать, пока @tail ещё указывает на жертву. Прогон: хвост — узел b. Сначала @hash.delete(b.key) убирает запись b из хеш-таблицы. Затем remove_node сдвигает @tail на соседа b. Если поменять строки местами, remove_node сдвинет @tail первым, и delete сотрёт из хеш-таблицы запись живого соседа, а b так и останется висеть в таблице, ссылаясь на узел вне списка.

Стоимость операций

Операция	Время	Из чего складывается
`get`	O(1)	поиск в хеш-таблице O(1) + перестановка узла O(1)
`put`	O(1)	поиск в хеш-таблице O(1) + перестановка узла O(1)

Когда лучше считать частоту: LFU

LRU судит о будущем по времени последнего обращения. Это удачно, когда то, что нужно сейчас, постоянно меняется: недавнее обращение — хороший признак, что элемент пригодится снова. Но бывает иначе: данные чётко делятся на «горячие» (нужны постоянно) и «холодные» (почти никогда), и это деление устойчиво во времени. Тогда лучший признак — не «когда обращались в последний раз», а «как часто обращались всего».

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

У счётчика есть обратная сторона. Элемент, который один раз был очень популярен, накапливает огромный счёт и потом застревает в кэше, даже когда стал не нужен, — это называют засорением кэша (cache pollution):

T=0..100: к элементу A обратились 1000 раз -> счётчик A = 1000
T=101:    A больше никому не нужен
T=102:    приходит новый элемент B       -> счётчик B = 1
T=103:    места нет, надо кого-то выбросить

LFU выбросит B (счётчик 1), а бесполезный A оставит (счётчик 1000).

Высокий накопленный счёт держит старого фаворита в кэше и вытесняет свежие элементы, которые могли бы пригодиться. Поэтому при устойчивом делении на горячее и холодное выигрывает LFU, а при подвижном — LRU.

Цена согласованности при многих потоках

По сложности LRU безупречен, но у него есть скрытая цена. Каждое обращение переставляет узел в голову списка, а это четыре записи в ссылки:

node.prev.next = node.next
node.next.prev = node.prev
head.prev = node
node.next = head

Пока программа однопоточная, проблемы нет: записи идут одна за другой. Но если к кэшу одновременно обращается несколько потоков (независимых линий исполнения внутри программы), эти четыре записи у разных потоков могут перемешаться, и список окажется в полусобранном состоянии — ссылки укажут не туда, цепочка порвётся. Чтобы этого не случилось, перестановку выполняют под блокировкой: пропускают внутрь только один поток за раз, остальные ждут.

Поток 1: хочет переставить элемент A -> ждёт блокировку
Поток 2: хочет переставить элемент B -> ждёт блокировку
...
1000 потоков ждут одну блокировку -> очередь, упирающаяся в один замок

В однопоточной программе это ничего не стоит. Но кэш внутри сервера базы данных, к которому тысячи запросов идут параллельно, превращается в узкое место: даже простое чтение требует перестроить список, а значит — встать в очередь за блокировкой. Здесь и проявляется граница LRU как инструмента: его аккуратный порядок «свежий ← → старый» приходится защищать на каждом, даже читающем, обращении.

Clock-Sweep обходит эту цену, отказываясь от точного порядка: вместо перестановки списка он лишь помечает обращённый элемент дешёвым атомарным инкрементом (неделимым увеличением счётчика, которое не требует блокировки).

См. также

Eviction policies в кэшировании — выбор между LRU и LFU на уровне архитектуры
Redis eviction — реализация LRU/LFU в Redis

← Хеш-таблица | Clock-Sweep →

CS Notes

Explorer

lru-cache