8. LFU кэш

Введение: Когда новизна уступает популярности

В предыдущей главе мы детально разобрали 7. LRU кэш, опирающийся на принцип временной локальности (temporal locality). Если элемент запросили только что, велика вероятность, что к нему обратятся снова. Однако в реальном сетевом трафике распределение нагрузки почти никогда не бывает равномерным. Оно подчиняется степенному закону Парето и распределению Ципфа (Zipf): около 20% популярных ключей генерируют более 80% всех обращений.

В таких условиях у LRU обнаруживается фундаментальная уязвимость к сканирующим запросам (scan resistance problem). Стоит ночному batch-скрипту или поисковому боту пройтись по базе данных с миллионом уникальных идентификаторов, как LRU послушно вымоет из оперативной памяти действительно ценные, горячие данные, заменив их одноразовым мусором.

Алгоритм LFU (Least Frequently Used) решает эту проблему принципиально: он отслеживает не время последнего доступа, а частоту обращений. Когда лимит памяти исчерпан, из кэша вытесняется элемент с наименьшим счётчиком использования. Это делает LFU идеальным выбором для кэширования статических каталогов товаров, конфигурационных метаданных, скомпилированных SQL-планов, сессий долгоживущих API-клиентов и защиты от сканирующих ботов.

Главная инженерная дилемма LFU кроется в алгоритмической цене: как поддерживать упорядоченность по частоте, не превращая каждую операцию Get и Put в O(n log n) или O(n)? Ответ кроется в элегантной композиции структур данных, гарантирующей строгое O(1) для всех базовых операций.

1. Архитектурный фундамент: Двойная маппа и частотные бакеты

Чтобы добиться константного времени O(1) для операций поиска, инкремента и вытеснения, классический алгоритм LFU (предложенный Ketan Shah, Anirban Mitra и Dhruv Matani) организует данные в двухуровневую систему:

1. KeyMap: Хеш-таблица map[K]*node[K, V] (или map[K]*Node[K,V]), обеспечивающая мгновенный доступ к узлу по ключу за O(1).
2. FreqMap: Хеш-таблица списков map[int]*list.List, где ключом выступает целое число — частота обращений, а значением — двусвязный список узлов с данной частотой. Внутри бакета узлы упорядочены по времени обращения (LRU-тайбрейкер): самый свежий узел находится в голове (PushFront), самый старый — в хвосте.
3. minFreq: Целочисленный указатель на текущую минимальную частоту среди всех присутствующих в кэше элементов. Значение minFreq изменяется строго детерминировано.

Рассмотрим поведение системы при операциях чтения и записи:

При Get(key):

• Находим узел в KeyMap. Если ключ отсутствует — возвращаем промах.
• Извлекаем узел из списка FreqMap[node.freq].
• Инкрементируем счётчик частоты: node.freq++.
• Вставляем узел в начало списка нового бакета FreqMap[node.freq].
• Если старый бакет minFreq опустел, инкрементируем minFreq (minFreq++).
• Возвращаем значение узла.

При Put(key, value):

• Если ключ уже существует, обновляем его значение и продвигаем частоту точно так же, как в операции Get.
• Если ключ новый, проверяем текущую ёмкость. Если KeyMap заполнен до предела capacity, находим список FreqMap[minFreq], удаляем из него самый старый хвостовой узел и стираем его из KeyMap. При необходимости вызываем коллбэк onEvict.
• Создаём новый узел со значением freq = 1.
• Помещаем узел в оба хранилища: KeyMap и бакет FreqMap[1].
• Сбрасываем указатель минимума: minFreq = 1.

flowchart TD
    Req["Запрос Get(key)"] --> Find{"Ключ в KeyMap?"}
    Find -->|"Нет"| Miss["Cache Miss<br/>(вернуть false)"]
    Find -->|"Да"| Extract["Извлечь узел из списка<br/>FreqMap[node.freq]"]
    Extract --> Inc["Инкремент node.freq++"]
    Inc --> Insert["Вставить узел в голову<br/>FreqMap[node.freq]"]
    Insert --> Check{"Бакет minFreq<br/>стал пустым?"}
    Check -->|"Да"| Up["Инкремент: minFreq++"]
    Check -->|"Нет"| Ret["Вернуть значение V"]
    Up --> Ret

    classDef default fill:#0f172a,stroke:#334155,color:#f8fafc
    classDef decision fill:#1e293b,stroke:#818cf8,color:#f8fafc
    classDef accent fill:#1e293b,stroke:#38bdf8,color:#38bdf8
    classDef success fill:#1e293b,stroke:#10b981,color:#10b981
    classDef warning fill:#1e293b,stroke:#f59e0b,color:#f59e0b

    class Find,Check decision
    class Extract,Inc,Insert accent
    class Up,Ret success
    class Miss warning
  

Такая архитектура гарантирует, что поиск, перепривязка частоты и вытеснение выполняются за константное время без перемещения массивов в памяти.

2. Production-реализация на Go 1.21+

Ниже представлена потокобезопасная обобщённая (generics) реализация LFU-кэша с использованием стандартной библиотеки Go (container/list), поддержкой таймстампов CreatedAt и настраиваемым хуком вытеснения onEvict.

package lfu

import (
    "container/list"
    "fmt"
    "sync"
    "time"
)

// node хранит данные ключа, значение и метаинформацию для LFU-алгоритма
type node[K comparable, V any] struct {
    Key       K
    Value     V
    Freq      int
    CreatedAt time.Time
    listElem  *list.Element // указатель на элемент внутри частотного списка
}

// Cache реализует LFU-кэш с амортизированной сложностью O(1) для всех операций
type Cache[K comparable, V any] struct {
    mu       sync.RWMutex
    capacity int
    keyMap   map[K]*node[K, V]
    freqMap  map[int]*list.List
    minFreq  int
    onEvict  func(K, V)
}

// New создаёт LFU кэш заданной емкости
func New[K comparable, V any](capacity int, onEvict func(K, V)) (*Cache[K, V], error) {
    if capacity <= 0 {
        return nil, fmt.Errorf("lfu: capacity must be positive")
    }
    return &Cache[K, V]{
        capacity: capacity,
        keyMap:   make(map[K]*node[K, V], capacity),
        freqMap:  make(map[int]*list.List),
        minFreq:  1,
        onEvict:  onEvict,
    }, nil
}

// Get возвращает значение и инкрементирует частоту обращения к ключу
func (c *Cache[K, V]) Get(key K) (V, bool) {
    c.mu.RLock()
    n, ok := c.keyMap[key]
    c.mu.RUnlock()
    if !ok {
        var zero V
        return zero, false
    }

    c.mu.Lock()
    c.moveNodeToNextFreq(n)
    val := n.Value
    c.mu.Unlock()
    return val, true
}

// Put добавляет или обновляет элемент в кэше
func (c *Cache[K, V]) Put(key K, value V) bool {
    c.mu.Lock()
    defer c.mu.Unlock()

    if n, ok := c.keyMap[key]; ok {
        n.Value = value
        c.moveNodeToNextFreq(n)
        return false
    }

    if len(c.keyMap) >= c.capacity {
        c.evict()
    }

    newNode := &node[K, V]{
        Key:       key,
        Value:     value,
        Freq:      1,
        CreatedAt: time.Now(),
    }
    c.addToList(newNode)
    c.keyMap[key] = newNode
    c.minFreq = 1
    return true
}

// moveNodeToNextFreq перемещает узел в бакет freq + 1
func (c *Cache[K, V]) moveNodeToNextFreq(n *node[K, V]) {
    c.removeFromList(n)
    n.Freq++
    c.addToList(n)

    // Если старый бакет стал пустым и это был minFreq, увеличиваем minFreq
    if freqList, ok := c.freqMap[n.Freq-1]; ok && freqList.Len() == 0 {
        delete(c.freqMap, n.Freq-1)
        if c.minFreq == n.Freq-1 {
            c.minFreq = n.Freq
        }
    }
}

// evict удаляет наименее часто используемый элемент
func (c *Cache[K, V]) evict() {
    freqList, ok := c.freqMap[c.minFreq]
    if !ok || freqList.Len() == 0 {
        return
    }

    oldest := freqList.Back()
    if oldest == nil {
        return
    }

    n := oldest.Value.(*node[K, V])
    freqList.Remove(oldest)
    if freqList.Len() == 0 {
        delete(c.freqMap, c.minFreq)
    }

    delete(c.keyMap, n.Key)
    if c.onEvict != nil {
        c.onEvict(n.Key, n.Value)
    }
}

// addToList добавляет узел в начало списка его частоты
func (c *Cache[K, V]) addToList(n *node[K, V]) {
    if _, ok := c.freqMap[n.Freq]; !ok {
        c.freqMap[n.Freq] = list.New()
    }
    n.listElem = c.freqMap[n.Freq].PushFront(n)
}

// removeFromList удаляет узел из текущего списка
func (c *Cache[K, V]) removeFromList(n *node[K, V]) {
    if n.listElem != nil {
        c.freqMap[n.Freq].Remove(n.listElem)
        n.listElem = nil
    }
}

Ключевые инженерные решения в этой реализации:

• LRU-тайбрейкер внутри бакета: Метод PushFront добавляет элемент в начало, а evict удаляет с хвоста (freqList.Back()). При равной частоте вытесняется узел, к которому дольше всего не обращались.
• Оптимизация minFreq: Мы не сканируем freqMap в поисках минимального ключа. Минимальная частота либо сбрасывается в 1 при создании нового элемента, либо инкрементируется на 1, когда бакет minFreq становится абсолютно пустым. Это фундаментальный инвариант O(1).
• Двухфазная блокировка в Get: RLock позволяет быстро отсеять отсутствующие ключи без эксклюзивной блокировки, а Lock активируется только при подтверждённом попадании для продвижения узла по частотной сетке.

3. Mechanical Sympathy: Указательная паутина и GC

С точки зрения архитектуры современного процессора и рантайма Go, LFU является одной из самых «дорогих» структур данных:

• Pointer Chasing и промахи кэша процессора: При вызове moveNodeToNextFreq процессор вынужден выполнить цепочку нелокальных чтений памяти: прочитать поле n.listElem $\to$ разыменовать указатели next/prev (или prev/next) для исключения элемента из списка $\to$ найти запись в хеш-таблице freqMap[freq] $\to$ разыменовать заголовок нового списка freqMap[freq].list $\to$ модифицировать next/prev нового соседа. Каждое разыменование указателя — потенциальный Cache Miss. В кэше на 500 000 элементов узлы хаотично разбросаны по виртуальной памяти, и аппаратный префетчер процессора (Hardware Prefetcher) оказывается бессилен.
• Давление на Garbage Collector: Каждый элемент порождает минимум 3–4 указателя в управляемой куче. При активном потоке операций evict и Put аллокатор рантайма работает под предельной нагрузкой, а GC тратит драгоценные процессорные циклы на трассировку огромного графа объектов. В сервисах с десятками гигабайт памяти суммарные задержки Stop-The-World (STW) могут достигать неприемлемых величин.
• Escape Analysis: Экземпляры newNode и list.Element гарантированно покидают стек (escape to heap). Компилятор не может аллоцировать их на стеке функции, поскольку они сохраняются в глобальных хеш-таблицах и передаются в методы list.PushFront.

Инженерная оптимизация для Low-Latency:
Вместо стандартного container/list в высокопроизводительных сервисах используют плоские массивы индексов, аналогично подходу в 4. Disjoint set union DSU, Union Find. Узлы хранятся в непрерывном срезе []node, а связи next[] и prev[] представляются целочисленными срезами []int. Все манипуляции производятся с 32-битными индексами вместо 64-битных указателей. Это сокращает объём памяти на 40%, обеспечивает отличную пространственную локальность (Spatial Locality) и сводит работу GC к сканированию одного непрерывного буфера.

4. Конкурентность и горизонтальное масштабирование

Одиночный мьютекс sync.RWMutex превращается в узкое горлышко (bottleneck) уже при нагрузке 15–20 тысяч RPS. Конкурирующие горутины блокируются на futex-системных вызовах ядра Linux, вызывая частый контекстный свитч потоков операционной системы (структур M в рантайме Go).

Для масштабирования LFU на многоядерных архитектурах применяются следующие инженерные приёмы:

1. Шардирование (Striping / Sharding) по hash(key) % N:
   Создаётся пул из N независимых LFU-кэшей, каждый из которых защищён собственным мьютексом. Конфликты за блокировку снижаются в N раз. Хотя глобальная точность счётчика minFreq формально дробится на локальные минимумы, на практике при N >= 16 и качественной хеш-функции отклонение в hit rate составляет не более 1–2%.
2. Lock-free чтение с батчингом (Batched Write Buffering):
   Операция чтения Get проверяет ключ через атомарные указатели (atomic.Pointer) или concurrent-карты без захвата эксклюзивного мьютекса. Инкременты частоты и задачи на вытеснение помещаются в неблокирующий кольцевой буфер или буферизованный канал chan. Фоновая горутина вычитывает события пакетами и обновляет бакеты FreqMap за один проход. Это даёт слабую согласованность (eventual consistency), но гарантирует субмикросекундную задержку на чтение.
3. TTL-гибридизация:
   Чистый алгоритм LFU принципиально не очищает неактуальные ключи, если к ним перестали обращаться. Для защиты от утечек памяти запускается периодический воркер, который проверяет метки времени CreatedAt и удаляет элементы по TTL, предотвращая захламление памяти.

5. LFU vs LRU: Выбор под паттерн трафика

В стандартной практике Go-разработки алгоритм LRU остаётся решением по умолчанию благодаря исключительной простоте реализации и минимальному накладным расходам на сборщик мусора. LFU становится безальтернативным выбором, когда доступ к данным строго подчиняется степенному закону и стоимость промаха кэша (обращение к тяжёлой БД или удалённому сервису) крайне высока.

Итог

• LFU кэш незаменим в системах с неравномерным трафиком (распределение Zipf), где ценность объекта определяется накопленной популярностью, а не секундной новизной.
• Архитектурная триада KeyMap + FreqMap + minFreq обеспечивает математически строгое амортизированное O(1) для операций Get, Put и evict.
• В языке Go связка структур из container/list создаёт существенную нагрузку на GC и вызывает деградацию производительности из-за Pointer Chasing. В сверхнагруженных подсистемах предпочтение отдаётся плоским массивам индексов.
• Конкурентная масштабируемость достигается шардированием пространства ключей на N >= 16 независимых бакетов либо разделением путей чтения и записи через каналы chan и батчинг.
• Проблема устаревания данных решается периодическим делением частот пополам (freq = freq / 2) или применением архитектуры W-TinyLFU.

Мы успешно завершили седьмой раздел, посвящённый продвинутым структурам данных: исследованию подверглись деревья отрезков, дерево Фенвика, разреженные таблицы, система непересекающихся множеств DSU, списки с пропусками Skip List, декартово дерево Treap, а также алгоритмы кэширования LRU и LFU.

Теперь мы переходим к фундаментальному разделу алгоритмов: методам упорядочивания данных. Понимание сортировок лежит в основе эффективного построения индексов в базах данных, оптимизации операторов соединения (Merge Join) и тонкого понимания внутреннего устройства рантайма Go. В следующей главе мы начнём с классического алгоритма, демонстрирующего механику перестановок и квадратичную сложность.

1. Bubble sort и его недостатки