Lock-free структуры данных на практике

Проблема: mutex как узкое место

Когда несколько горутин одновременно обращаются к общей структуре данных, классическое решение — sync.Mutex или sync.RWMutex. Это работает, но создаёт две фундаментальные проблемы:

1. Contention (конкуренция за блокировку). Если 100 горутин одновременно пытаются прочитать один кэш, они выстраиваются в очередь. Даже RWMutex с его read-locks не спасает, когда на запись приходит каждая десятая операция.

2. Системные вызовы. Когда мьютекс занят, Go паркует горутину через runtime. Парковка-распарковка — это системный вызов, который стоит сотни наносекунд. Для системы, где вся операция чтения занимает 0.35 ns, это катастрофа.

Идея: linked list в массиве

Классический linked list в Go — это map или указатели на структуры в куче. Оба варианта создают нагрузку на GC. Мы используем другой подход: массив фиксированного размера с индексами вместо указателей.

Вместо того чтобы хранить указатель на следующий элемент (*Entry), мы храним индекс в массиве (uint32). Это даёт три преимущества:

• Ноль аллокаций — массив выделяется один раз
• Кэш-френдли — все элементы лежат в одном непрерывном блоке памяти
• Компактно — 4 байта на указатель вместо 8 на 64-битной системе

Анатомия шарда

Вот как выглядит реальный шард кэша верификации в MEMORIA:

type verifyCacheEntry struct {
    key   uint64   // Хэш сообщения
    value bool     // Результат верификации
    next  uint32   // Индекс следующего элемента (0xFFFFFFFF = конец)
    _     [4]byte  // Padding для выравнивания до 24 байт
}

type verifyCacheShard struct {
    arena    [256]verifyCacheEntry  // Предвыделенный массив
    freeList uint32                 // Голова списка свободных слотов
    head     [256]uint32            // Головы 256 бакетов
    mutex    sync.RWMutex           // Только для редких записей
    count    uint32                 // Текущее количество элементов
}Go

Разберём каждое поле:

arena [256]verifyCacheEntry

Массив из 256 записей. Каждая запись — ровно 24 байта. Весь шард занимает 6 KB в памяти. Это предвыделяется при старте приложения и никогда не освобождается.

freeList uint32

Индекс первого свободного слота. Это односвязный список: каждый свободный элемент хранит в поле next индекс следующего свободного элемента. Специальное значение 0xFFFFFFFF означает «конец списка».

head [256]uint32

Массив из 256 голов бакетов. Это хэш-таблица с цепочками (chaining). Ключ хэшируется в диапазон 0-255, и мы получаем индекс бакета. Все коллизии разрешаются через linked list.

O(1) аллокация через free list

Вот как выглядит аллокация нового элемента:

//go:nosplit
func (vc *verifyCacheShard) alloc() (*verifyCacheEntry, uint32) {
    if vc.freeList == 0xFFFFFFFF || vc.freeList >= uint32(len(vc.arena)) {
        return nil, 0  // Кэш переполнен
    }
    
    idx := vc.freeList
    vc.freeList = vc.arena[idx].next
    vc.arena[idx].next = 0xFFFFFFFF
    vc.count++
    
    return &vc.arena[idx], idx
}Go

Что происходит:

1. Проверяем, что free list не пуст
2. Берём первый свободный индекс
3. Сдвигаем голову free list на следующий свободный элемент
4. Помечаем взятый элемент как «конец списка» (0xFFFFFFFF)
5. Увеличиваем счётчик

Вся операция — 5 присваиваний. Никаких системных вызовов, никаких аллокаций в куче. Бенчмарки показывают 4.5 наносекунды на операцию.

Освобождение элемента симметрично:

func (vc *verifyCacheShard) free(idx uint32) {
    vc.arena[idx].next = vc.freeList
    vc.freeList = idx
    vc.count--
}Go

Два присваивания. O(1). Всегда.

Хэширование и бакеты

Поиск элемента в кэше использует хэш-таблицу с цепочками:

func (vc *verifyCacheShard) Get(key uint64) bool {
    bucket := key & 255  // Быстрый modulo через bitwise AND
    
    entryIdx := vc.head[bucket]
    for entryIdx != 0xFFFFFFFF && entryIdx < uint32(len(vc.arena)) {
        entry := &vc.arena[entryIdx]
        if entry.key == key {
            return entry.value
        }
        entryIdx = entry.next
    }
    return false
}Go

Обратите внимание на key & 255. Это оптимизация: вместо операции деления key % 256 мы используем побитовое AND. Поскольку 256 — это степень двойки (2^8), младшие 8 бит числа и есть остаток от деления на 256. Это работает в ~10 раз быстрее, чем деление на современных CPU.

Вставка работает аналогично, но добавляет элемент в начало цепочки:

//go:nosplit
func (vc *verifyCacheShard) Set(key uint64, value bool) bool {
    bucket := key & 255
    
    // Сначала ищем, нет ли уже такого ключа
    entryIdx := vc.head[bucket]
    for entryIdx != 0xFFFFFFFF && entryIdx < uint32(len(vc.arena)) {
        entry := &vc.arena[entryIdx]
        if entry.key == key {
            entry.value = value  // Обновляем существующий
            return true
        }
        entryIdx = entry.next
    }
    
    // Ключа нет — аллоцируем новый
    newEntry, idx := vc.alloc()
    if newEntry == nil {
        return false  // Кэш переполнен
    }
    
    newEntry.key = key
    newEntry.value = value
    newEntry.next = vc.head[bucket]  // Вставляем в начало цепочки
    vc.head[bucket] = idx
    
    return true
}Go

Шардирование: как победить contention

Даже с lock-free чтением, операции записи требуют мьютекс. Если все 15 миллионов пользователей обращаются к одному кэшу — contention убьёт производительность.

Решение: разделить один большой кэш на 256 независимых шардов:

const SHARD_COUNT = 256
const SHARD_MASK = SHARD_COUNT - 1  // 0xFF

var verifyCaches [SHARD_COUNT]verifyCacheShard

func getShard(key uint64) *verifyCacheShard {
    return &verifyCaches[key & SHARD_MASK]
}Go

Теперь каждый шард обслуживает только 1/256 часть трафика. Вероятность того, что две горутины одновременно захотят один шард, снижается в 256 раз.

Каждый шард имеет свой собственный мьютекс. Это значит, что 256 горутин могут одновременно писать в 256 разных шардов без какой-либо конкуренции.

Три применения в MEMORIA

Один и тот же паттерн используется в трёх разных местах кода:

1. Verify Cache — кэш верификации подписей

Когда клиент отправляет снапшот с подписью BLAKE3, сервер проверяет подпись. Вычисление хэша стоит ~100 ns. Чтобы не делать это повторно для одинаковых снапшотов, результат кешируется:

type verifyCacheEntry struct {
    key   uint64   // xxhash от сообщения
    value bool     // true если подпись валидна
    next  uint32
}

var verifyCaches [256]verifyCacheShardGo

Размер одного шарда: 256 × 24 байта = 6 KB. Всего 256 шардов × 6 KB = 1.5 MB на весь кэш.

2. ReqID Cache — защита от replay-атак

Каждый P2P-перевод имеет уникальный reqID (8 байт). Чтобы злоумышленник не мог отправить один и тот же пакет дважды, мы запоминаем все reqID за последние 10 секунд:

type reqIDCacheEntry struct {
    reqID     [8]byte
    timestamp uint32
    next      uint32
    _         [4]byte
}

var reqIDCaches [256]reqIDCacheShardGo

Функция CheckReplay возвращает true, если reqID новый, и false, если он уже был использован в окне 10 секунд.

3. IP Limiter — защита от DDoS

Чтобы один IP-адрес не мог завалить сервер запросами, мы ограничиваем количество операций с одного IP до 10 в секунду:

type ipLimiterEntry struct {
    ipHash      uint64
    count       uint16
    lastSec     uint32
    lastNewUser uint32
    next        uint32
    _           [4]byte
}

var ipLimiterShards [64]ipLimiterShardGo

Здесь шардов меньше (64 вместо 256), потому что IP-адресов меньше, чем ключей кэша, и каждый элемент больше (32 байта вместо 24).

Бенчмарки

Реальные цифры с Intel Core i7-4790:

BenchmarkArena_Alloc-8          24736123    4.572 ns/op    0 B/op    0 allocs/op
BenchmarkArena_Alloc_Small-8    26194135    4.706 ns/op    0 B/op    0 allocs/op
BenchmarkArena_Alloc_Large-8    25316743    4.842 ns/op    0 B/op    0 allocs/opgo test -bench

Сравним с стандартными структурами Go:

Разница в 10-20 раз по скорости и бесконечность по аллокациям. Но главное — предсказуемость. MEMORIA-кэш всегда работает за 5-10 ns, независимо от нагрузки. sync.Map может деградировать до микросекунд при высокой конкуренции.

Компромиссы

У подхода есть свои ограничения, о которых важно знать:

1. Фиксированный размер

Если кэш переполняется (все 256 слотов в шарде заняты), новые элементы не добавляются. В MEMORIA мы решаем это подбором размера: 256 слотов на шард × 256 шардов = 65 536 записей. При TTL в несколько секунд этого достаточно для миллионов операций.

2. Нет удаления по ключу

Мы не удаляем элементы по ключу — только по истечении TTL или при переполнении. Это упрощает код, но требует, чтобы размер кэша был достаточным.

3. Фрагментация внутри шарда

Со временем free list может фрагментироваться. Но поскольку у нас нет реального «освобождения» памяти (только возврат в free list), это не проблема — просто список свободных слотов становится длиннее.

4. Сложность кода

Работа с индексами вместо указателей, ручное управление free list, padding для выравнивания — всё это увеличивает сложность кода. Одна ошибка может привести к memory corruption. Поэтому в init() есть проверки:

func init() {
    testShard := &ipLimiterShards[0]
    entry, idx := testShard.alloc()
    if entry == nil {
        log.Fatal("alloc failed in init check")
    }
    expectedPtr := uintptr(unsafe.Pointer(&testShard.arena[idx]))
    actualPtr := uintptr(unsafe.Pointer(entry))
    if expectedPtr != actualPtr {
        log.Fatalf("⚠️ Pointer mismatch: idx=%d, expected=%x, got=%x", 
            idx, expectedPtr, actualPtr)
    }
    // Возвращаем элемент обратно
    testShard.arena[idx].next = testShard.freeList
    testShard.freeList = idx
    testShard.count--
}Go

В следующей статье мы разберём, как на базе этих lock-free структур построен бинарный UDP-протокол, который обрабатывает 256 пакетов за один системный вызов.