Шардированный LRU-кэш¶

Зачем¶

Один map[string]V + один Mutex = одна общая блокировка. При тысячах горутин все они дерутся за этот один lock — throughput резко падает.

Решение — шардирование: разделяем ключи по hash(key) % N на N независимых шардов. Каждый шард — свой map + свой lock. Конкуренция падает в N раз.

Это типовой паттерн в продакшене: concurrent-map, ristretto, bigcache, шардированные таблицы в БД, Redis Cluster.

Структура¶

type ShardedLRU[K comparable, V any] struct {
    shards   []*shard[K, V]
    shardCnt uint64   // степень двойки для дешёвой маски
    hash     func(K) uint64
}

type shard[K comparable, V any] struct {
    mu       sync.RWMutex
    capacity int
    items    map[K]*list.Element
    order    *list.List   // container/list для LRU
}

Базовый API¶

func New[K comparable, V any](shards int, capPerShard int, hash func(K) uint64) *ShardedLRU[K, V]

func (c *ShardedLRU[K, V]) Get(k K) (V, bool)
func (c *ShardedLRU[K, V]) Set(k K, v V)
func (c *ShardedLRU[K, V]) Delete(k K)
func (c *ShardedLRU[K, V]) Len() int

Шардирование¶

Степень двойки + битовая маска быстрее, чем %:

func (c *ShardedLRU[K, V]) shardOf(k K) *shard[K, V] {
    return c.shards[c.hash(k)&(c.shardCnt-1)]
}

LRU через container/list¶

type entry[K, V any] struct {
    key K
    val V
}

func (s *shard[K, V]) get(k K) (V, bool) {
    s.mu.Lock()
    defer s.mu.Unlock()
    if el, ok := s.items[k]; ok {
        s.order.MoveToFront(el)
        return el.Value.(*entry[K, V]).val, true
    }
    var zero V
    return zero, false
}

func (s *shard[K, V]) set(k K, v V) {
    s.mu.Lock()
    defer s.mu.Unlock()
    if el, ok := s.items[k]; ok {
        s.order.MoveToFront(el)
        el.Value.(*entry[K, V]).val = v
        return
    }
    el := s.order.PushFront(&entry[K, V]{key: k, val: v})
    s.items[k] = el
    if s.order.Len() > s.capacity {
        oldest := s.order.Back()
        s.order.Remove(oldest)
        delete(s.items, oldest.Value.(*entry[K, V]).key)
    }
}

Замечание про RWMutex: для классического LRU у Get тоже есть запись (move to front), поэтому RWMutex даёт мало. Если хочешь «чистый Read без блокировки записи» — реализуй s3-fifo или sieve, где Read не модифицирует структуру.

Бенчмарк¶

func BenchmarkLRU(b *testing.B) {
    cache := simpleLRU.New[string, int](10000)
    benchCache(b, cache)
}

func BenchmarkShardedLRU(b *testing.B) {
    cache := New[string, int](64, 10000/64, fnvHash)
    benchCache(b, cache)
}

func benchCache(b *testing.B, c interface {
    Get(string) (int, bool)
    Set(string, int)
}) {
    b.RunParallel(func(pb *testing.PB) {
        for pb.Next() {
            k := randKey()
            if _, ok := c.Get(k); !ok {
                c.Set(k, 1)
            }
        }
    })
}

Запуск:

go test -bench=. -cpu=1,4,8,16 ./...

Типичные результаты (средние, AMD Ryzen 9):

concurrency	LRU+Mutex	ShardedLRU 64	speedup
1	220 ns/op	240 ns/op	-10%
4	1100 ns/op	280 ns/op	x4
8	2400 ns/op	290 ns/op	x8
16	5300 ns/op	320 ns/op	x16

Видно: на single-thread шардирование чуть медленнее (overhead на хеш), но на concurrency скейлится почти линейно.

Что говорить на собесе¶

«У одного mutex'а есть hard cap по throughput — все горутины серiализуются».
«Шардирование уменьшает contention пропорционально числу шардов».
«N выбираем степенью двойки — позволяет заменить % на &».
«Для горячих ключей (zipf) шардирование не помогает — добавляем per-key sharding (hash(key+v))».

Что прокачать дальше¶

ristretto — admission control + sampled LFU.
bigcache — массивы байт, no GC overhead для больших.
sieve — простой single-bit замена LRU без overhead.