2. Кэш структуры

«Кэширование подобно заготовке дров на зиму: в доме будет тепло лишь тогда, когда вовремя выносишь золу и освобождаешь место для свежих поленьев».
— Брайан Керниган

Кэш-структуры: Архитектура, политики вытеснения и механика памяти

In-memory кэш — это не просто примитивная обертка над хэш-таблицей map. Это высоконагруженная, конкурентная система хранения данных с жесткими лимитами по памяти, детерминированной латентностью и гарантированной защитой от утечек ресурсов.

В распределенной бэкенд-инженерии на Go проектирование кэша требует глубокого понимания:

• Как предотвратить шторм запросов к основной базе данных (Cache Stampede / Thundering Herd)?
• Как структура двусвязного списка влияет на промахи процессорного кэша (Pointer Chasing vs Array-backed buffers)?
• Почему удаление ключей из стандартного map в Go не возвращает оперативную память операционной системе (Memory Bloat)?
• Как мягкий лимит памяти GOMEMLIMIT защищает сервис от аварийного завершения по Linux OOM Killer?

flowchart TD
    classDef entry   fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef accent  fill:#1e1b4b,stroke:#818cf8,stroke-width:1px,color:#f8fafc
    classDef warn    fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc

    Req["Запрос: Get(key)"]:::entry --> Lookup{"Поиск ключа в Map"}:::process

    Lookup -- "Cache Hit (Найден)" --> UpdateOrder["Обновление порядка вытеснения<br/>(LRU/LFU инвариант)"]:::accent
    UpdateOrder --> ReturnHit["Возврат значения из RAM"]:::success

    Lookup -- "Cache Miss (Промах)" --> Load["Загрузка из БД / Источника<br/>(Защита через singleflight)"]:::warn
    Load --> CapCheck{"Достигнут ли лимит емкости?"}:::process

    CapCheck -- "Да (Кэш переполнен)" --> Evict["Вытеснение по политике:<br/>Удаление жертвы (Victim)"]:::warn
    CapCheck -- "Нет" --> Insert["Вставка нового значения"]:::process

    Evict --> Insert
    Insert --> ReturnMiss["Возврат свежих данных"]:::success
  

1. Фундаментальная триада архитектуры кэша

Любой промышленный кэш состоит из трех взаимосвязанных подсистем:

1. Индекс (Fast Lookup):
   Обеспечивает доступ к значению по ключу за $O(1)$. В Go это либо встроенный map[K]V, либо открыто-адресованная хэш-таблица.
2. Хранилище значений и метаданных (Storage):
   Полезная нагрузка (payload), метки времени создания, счетчики обращений, TTL (Time-To-Live).
3. Очередь вытеснения (Eviction Policy):
   Детерминированный алгоритм, определяющий, какой именно элемент должен быть уничтожен, когда память кэша исчерпана.

2. Сравнение политик вытеснения (Eviction Policies)

flowchart LR
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef accent  fill:#1e1b4b,stroke:#818cf8,stroke-width:1px,color:#f8fafc
    classDef warn    fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc

    Policies["Политики вытеснения"]:::accent --> LRU["1. LRU (Least Recently Used)<br/>Вытесняет то, к чему дольше не обращались"]:::process
    Policies --> LFU["2. LFU (Least Frequently Used)<br/>Вытесняет наименее популярное"]:::process
    Policies --> FIFO["3. FIFO (First In, First Out)<br/>Простая циклическая очередь"]:::warn
    Policies --> TTL["4. TTL / Expiration<br/>Удаление по истечении таймера"]:::success

    LRU --> LRUImpl["Map + Двусвязный список"]:::process
    LFU --> LFUImpl["Map + Частотные бакеты"]:::process
    FIFO --> FIFOImpl["Кольцевой буфер (Ring Buffer)"]:::warn
    TTL --> TTLImpl["Priority Queue или Time Wheel"]:::success
  

3. Механическая симпатия: Память, кэш-линии и сборщик мусора

1. Проблема Pointer Chasing в двусвязных списках

Классический LRU использует узлы type Node struct { key, val string; prev, next *Node }.
Каждый узел выделяется в куче отдельно. Адреса разбросаны хаотично.
При обходе списка процессор вынужден непрерывно загружать новые несвязанные 64-байтные кэш-линии из DRAM, теряя до 150 тактов на каждый промах кэша.

Решение High-Performance систем (Array-backed LRU):
Все узлы размещаются в едином непрерывном срезе nodes := make([]Node, capacity). Ссылки prev и next становятся не указателями, а целочисленными индексами int32 в срезе.
Это обеспечивает идеальную локальность данных (Spatial Locality) и позволяет аппаратному префетчеру процессора работать на полной скорости шины памяти.

2. Ловушка delete() в Go map: Memory Bloat

Когда вы удаляете ключ из стандартного map с помощью функции delete(c.items, key), рантайм Go не возвращает память операционной системе. Он лишь помечает слот в бакете как пустой.
Если кэш непрерывно вставляет и удаляет миллионы ключей, размер карты в памяти (RSS процесса) никогда не уменьшится!

// Паттерн периодического компактирования карты (Rebuild)
func (c *Cache) CompactIfNecessary() {
    if len(c.items) < c.maxCapacity/4 {
        newMap := make(map[string]*Item, len(c.items))
        for k, v := range c.items {
            newMap[k] = v
        }
        c.items = newMap // Старая раздутая карта будет утилизирована GC
    }
}

4. Паттерны надежности: Борьба со штормом запросов (Cache Stampede)

В высоконагруженном API сброс популярного ключа (например, главной страницы каталога) приводит к тому, что тысячи параллельных горутин одновременно получают Cache Miss и синхронно обрушиваются с тяжелыми запросами на базу данных. Это явление называют Cache Stampede или Thundering Herd.

Защита через пакет golang.org/x/sync/singleflight

Паттерн Singleflight подавляет дублирующие параллельные вызовы, объединяя их в один единственный запрос к источнику:

package cache

import (
    "sync"
    "golang.org/x/sync/singleflight"
)

type RobustCache struct {
    mu    sync.RWMutex
    items map[string]string
    group singleflight.Group
}

// GetOrFetch возвращает значение из кэша либо вызывает fetcher строго один раз
func (c *RobustCache) GetOrFetch(key string, fetcher func() (string, error)) (string, error) {
    // 1. Быстрый путь: проверка в кэше под RLock
    c.mu.RLock()
    val, ok := c.items[key]
    c.mu.RUnlock()
    if ok {
        return val, nil
    }

    // 2. Защита от Cache Stampede: только 1 горутина идет в БД, остальные ждут ее результат
    v, err, _ := c.group.Do(key, func() (any, error) {
        data, fetchErr := fetcher()
        if fetchErr != nil {
            return nil, fetchErr
        }

        c.mu.Lock()
        c.items[key] = data
        c.mu.Unlock()
        return data, nil
    })

    if err != nil {
        return "", err
    }
    return v.(string), nil
}

5. Граничные случаи и ловушки продакшена

1. Утечки горутин при использовании time.After:
   Никогда не очищайте TTL-кэш конструкцией select { case <-time.After(ttl): } внутри цикла запросов! Функция time.After выделяет новый таймер в рантайме, который не освобождается до истечения времени. При миллионе запросов сервис падает по OOM.
   Используйте единую фоновую горутину-уборщик с time.NewTicker(interval).
2. Pointer Aliasing:
   Если кэш хранит изменяемые структуры по указателю map[string]*User, возврат *User клиенту позволяет клиенту изменить внутреннее состояние кэша без мьютекса. Всегда возвращайте глубокую копию либо сериализованный срез []byte.
3. Ограничение RSS через debug.SetMemoryLimit (GOMEMLIMIT):
   В Go 1.19+ мягкий лимит памяти позволяет сборщику мусора агрессивно очищать неиспользуемые блоки кэша до того, как контейнер в Kubernetes будет убит OOMKilled.

Вопросы для собеседования

Резюме

• Кэш строится на союзе быстрого индекса (map), хранилища и политики вытеснения (Eviction Policy).
• LRU эффективен для большинства сценариев; LFU защищает долгоживущие популярные ключи; FIFO минимизирует оверхед синхронизации.
• delete() в Go map не освобождает выделенную память; для долгоживущих кэшей требуется периодическое пересоздание карты или использование открытой адресации.
• Паттерн singleflight.Group — индустриальный стандарт защиты базы данных от шторма запросов (Cache Stampede).

В следующей лекции мы детально разберем практическую реализацию классического кэша: 3. LRU Cache, где с нуля построим потокобезопасный двусвязный список с dummy-узлами и протестируем его поведение под высокой нагрузкой.