Cache LRU concorrente em Go: singleflight, sharding e benchmarks práticos

Problema real que resolve

Aplicações web, APIs e sistemas distribuídos frequentemente precisam armazenar dados derivados caros em memória para reduzir latência e custos de I/O. Um cache LRU (Least Recently Used) é uma estrutura clássica para manter itens quentes enquanto descarta os menos utilizados. Em sistemas concorrentes escritos em Go, implementar um LRU que seja eficiente, seguro e escalável para dezenas ou centenas de goroutines é mais complexo do que parece.

O problema que tratamos: como implementar um cache LRU que suporte alto throughput de leituras e escritas concorrentes sem se tornar gargalo por mutex global, evitando também o problema de "thundering herd" quando múltiplas goroutines tentam popular o mesmo miss ao mesmo tempo.

Nosso objetivo é explorar alternativas: uma implementação ingênua e simples, uma otimizada usando sharding e outra que combina sharding com singleflight (para evitar chamadas duplicadas a recursos caros). Vamos também medir tudo com benchmarks práticos para ter evidências das decisões.

Este artigo foca em práticas reais: trade-offs entre simplicidade e desempenho, caminhos comuns de erro e como validar em ambiente de desenvolvimento antes de levar para produção.

Por que LRU e não outro algoritmo?

LRU é uma escolha pragmática para caches in-memory quando o padrão de acesso segue alguma localidade temporal. Não é perfeito para todos os padrões (workloads de "scan" massivo podem poluir o cache), mas é simples, previsível e suportado por estruturas eficientes em Go, como container/list. A implementação e otimização do LRU em ambiente concorrente é um problema recorrente.

Requisitos práticos

Definimos requisitos claros: thread-safe, limite de capacidade, operação O(1) para acesso/atualização, baixa contenção com alta concorrência, e evitar recomputação desnecessária (singleflight). Esses requisitos orientam as escolhas técnicas abaixo.

Abordagem ingênua vs abordagem otimizada

A abordagem ingênua é uma implementação LRU com um mutex global que protege um mapa e uma lista dupla ligada. É simples e correta, mas o mutex global se torna gargalo quando centenas de goroutines competem por leitura/escrita.

Alternativa otimizada: sharding (dividir o cache em N shards independentes, cada um com seu mutex) reduz contenção implicitamente. Para misses simultâneos no mesmo item, empregamos singleflight (x/sync/singleflight) para garantir que apenas uma goroutine efetua a computação/IO, e as demais aguardam o resultado.

Vamos discutir trade-offs: sharding melhora throughput mas aumenta complexidade; singleflight evita carga duplicada mas adiciona latência para agrupar solicitações concorrentes. Combinar ambos costuma ser a solução mais prática para caches de aplicação.

Abordagem ingênua (mutex global)

Vantagens: fácil de implementar e raciocinar. Desvantagens: contenção em workloads com alta concorrência, o que degrada latência e throughput.

Abordagem otimizada (sharding + singleflight)

Sharding reduz contenção distribuindo chaves entre shards. Singleflight resolve o problema do "thundering herd". Juntas, essas técnicas alcançam baixos tempos de latência média e escalam com núcleos/threads.

Implementação com código real

Apresentarei três blocos de código: 1) LRU ingênuo com mutex global; 2) LRU sharded com singleflight; 3) exemplo de uso e pequena API CLI para testar. Cada bloco tem contexto antes e explicação após.

LRU ingênuo com mutex global

O código abaixo implementa um LRU básico usando container/list e um mutex para sincronização de todas as operações. Serve como referência e ponto de comparação nos benchmarks.

package lru

import (
	"container/list"
	"sync"
)

// entry represents a cache entry.
type entry struct {
	key   string
	value interface{}
}

// LRUCache é uma implementação simples com mutex global.
type LRUCache struct {
	mu    sync.Mutex
	cap   int
	ll    *list.List
	cache map[string]*list.Element
}

func NewLRU(capacity int) *LRUCache {
	return &LRUCache{
		cap:   capacity,
		ll:    list.New(),
		cache: make(map[string]*list.Element, capacity),
	}
}

func (c *LRUCache) Get(key string) (interface{}, bool) {
	c.mu.Lock()
	defer c.mu.Unlock()
	if ele, ok := c.cache[key]; ok {
		c.ll.MoveToFront(ele)
		return ele.Value.(*entry).value, true
	}
	return nil, false
}

func (c *LRUCache) Put(key string, val interface{}) {
	c.mu.Lock()
	defer c.mu.Unlock()
	if ele, ok := c.cache[key]; ok {
		c.ll.MoveToFront(ele)
		ele.Value.(*entry).value = val
		return
	}
	ent := &entry{key: key, value: val}
	ele := c.ll.PushFront(ent)
	c.cache[key] = ele
	if c.ll.Len() > c.cap {
		back := c.ll.Back()
		if back != nil {
			c.ll.Remove(back)
			delete(c.cache, back.Value.(*entry).key)
		}
	}
}

O que este bloco faz: implementa Get e Put com mutex exclusivo. O custo de contenção aparece quando muitas goroutines chamam Get/Put simultaneamente.

Depois: funciona bem para baixa concorrência, mas não escala. Use como baseline.

LRU sharded com singleflight

A seguir, uma implementação que cria N shards. Cada shard tem seu próprio LRU e mutex. Para evitar recomputação de misses concorrentes, usamos singleflight para garantir única chamada ao fornecedor (fetch function).

package shardedcache

import (
	"container/list"
	"hash/fnv"
	"sync"
	"time"

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

type shard struct {
	mu    sync.Mutex
	ll    *list.List
	cache map[string]*list.Element
	cap   int
}

type entry struct {
	key   string
	value interface{}
	ts    time.Time
}

// ShardedCache combina shards e singleflight.
type ShardedCache struct {
	shards    []*shard
	shardMask uint32
	group     singleflight.Group
}

func NewShardedCache(shardCount int, shardCap int) *ShardedCache {
	// shardCount must be power of two for mask
	if shardCount <= 0 || (shardCount&(shardCount-1)) != 0 {
		panic("shardCount must be power of two")
	}
	s := make([]*shard, shardCount)
	for i := range s {
		s[i] = &shard{ll: list.New(), cache: make(map[string]*list.Element, shardCap), cap: shardCap}
	}
	return &ShardedCache{shards: s, shardMask: uint32(shardCount - 1)}
}

func (c *ShardedCache) getShard(key string) *shard {
	h := fnv.New32a()
	h.Write([]byte(key))
	idx := h.Sum32() & c.shardMask
	return c.shards[idx]
}

func (c *ShardedCache) GetOrFetch(key string, fetch func() (interface{}, error)) (interface{}, error) {
	// first, try fast path without singleflight
	sh := c.getShard(key)
	sh.mu.Lock()
	if ele, ok := sh.cache[key]; ok {
		sh.ll.MoveToFront(ele)
		val := ele.Value.(*entry).value
		sh.mu.Unlock()
		return val, nil
	}
	sh.mu.Unlock()

	// miss: use singleflight to avoid duplicate fetches
	v, err, _ := c.group.Do(key, func() (interface{}, error) {
		// double-check inside singleflight to avoid race with in-flight Put
		sh2 := c.getShard(key)
		sh2.mu.Lock()
		if ele, ok := sh2.cache[key]; ok {
			sh2.ll.MoveToFront(ele)
			val := ele.Value.(*entry).value
			sh2.mu.Unlock()
			return val, nil
		}
		sh2.mu.Unlock()

		// actual fetch
		val, ferr := fetch()
		if ferr != nil {
			return nil, ferr
		}

		// insert into shard
		sh3 := c.getShard(key)
		sh3.mu.Lock()
		ent := &entry{key: key, value: val, ts: time.Now()}
		ele := sh3.ll.PushFront(ent)
		sh3.cache[key] = ele
		if sh3.ll.Len() > sh3.cap {
			back := sh3.ll.Back()
			if back != nil {
				sh3.ll.Remove(back)
				delete(sh3.cache, back.Value.(*entry).key)
			}
		}
		sh3.mu.Unlock()
		return val, nil
	})
	return v, err
}

O que este bloco faz: combina hashing para selecionar shard, evita bloqueio global e usa singleflight para pedidos concorrentes pela mesma chave. O double-check pattern (verificar antes e dentro do singleflight) reduz desnecessária execução do fetch.

Depois: esta implementação exigirá ajustes (eviction across shards, métricas), mas é um ponto de partida robusto para produção.

Exemplo de uso e pequena CLI de teste

Abaixo um programa que demonstra criação do cache sharded, provê uma função fetch que simula I/O e faz leituras concorrentes para provocar contention e thundering herd controlado.

package main

import (
	"fmt"
	"math/rand"
	"sync"
	"time"

	"example.com/shardedcache"
)

func main() {
	rand.Seed(time.Now().UnixNano())
	c := shardedcache.NewShardedCache(8, 1024)
	fetch := func(key string) func() (interface{}, error) {
		return func() (interface{}, error) {
			// simula latencia de IO
			time.Sleep(10 * time.Millisecond)
			return fmt.Sprintf("val-%s-%d", key, rand.Intn(1000)), nil
		}
	}

	var wg sync.WaitGroup
	for i := 0; i < 100; i++ {
		wg.Add(1)
		go func(id int) {
			defer wg.Done()
			k := "item-" + fmt.Sprint(id%10)
			v, err := c.GetOrFetch(k, fetch(k))
			if err != nil {
				fmt.Println("fetch err:", err)
				return
			}
			fmt.Println("goroutine", id, "got", v)
		}(i)
	}
	wg.Wait()
}

O que acontece: vários workers tentam buscar 10 chaves diferentes com conteúdo simulado. O singleflight garante que, para cada chave, apenas uma simulação de I/O ocorra se houver concorrência.

Testes e validacao

Benchmarks comprovam comportamento. Mostrarei um benchmark comparando a implementação ingênua (mutex global) e a sharded+singleflight. O benchmark precisa simular leituras e writes com diversas taxas de hits.

Benchmark: estrutura do teste

Crie um arquivo _cache_bench_test.go_ com benchmarks para Get e GetOrFetch. O benchmark usa GOMAXPROCS alto e varying parallelism para medir escalabilidade. Métricas importantes: ns/op, MB/s se aplicável, e alocações/op.

Exemplo de benchmark

O código a seguir é um benchmark funcional que compara o LRU com mutex global vs ShardedCache em leituras concorrentes. Coloque em um pacote de testes e execute com go test -bench=.

package bench

import (
	"math/rand"
	"runtime"
	"testing"
	"time"

	"example.com/lru"
	"example.com/shardedcache"
)

func BenchmarkCaches(b *testing.B) {
	runtime.GOMAXPROCS(8)
	keys := make([]string, 1000)
	for i := range keys {
		keys[i] = "k" + string(i)
	}

	b.Run("global_mutex", func(b *testing.B) {
		c := lru.NewLRU(2048)
		for i := 0; i < 1000; i++ {
			c.Put(keys[i%1000], i)
		}
		b.ResetTimer()
		b.RunParallel(func(pb *testing.PB) {
			r := rand.New(rand.NewSource(time.Now().UnixNano()))
			for pb.Next() {
				c.Get(keys[r.Intn(len(keys))])
			}
		})
	})

	b.Run("sharded_singleflight", func(b *testing.B) {
		c := shardedcache.NewShardedCache(16, 256)
		fetch := func() (interface{}, error) { return 42, nil }
		for i := 0; i < 1000; i++ {
			c.GetOrFetch(keys[i%1000], fetch)
		}
		b.ResetTimer()
		b.RunParallel(func(pb *testing.PB) {
			r := rand.New(rand.NewSource(time.Now().UnixNano()))
			for pb.Next() {
				c.GetOrFetch(keys[r.Intn(len(keys))], fetch)
			}
		})
	})
}

Depois: rode go test -bench=. Compare resultados entre as variações, alterando número de shards e capacidade para sentir impacto nas métricas.

Considerações de produção

Ao mover para produção, há pontos práticos cruciais: instrumentação, métricas por shard, monitoramento de latência e taxas de hit/miss. Também é importante entender padrões de acesso da aplicação, pois um cache mal dimensionado pode se tornar ineficiente.

Erros comuns e armadilhas

Listo as armadilhas práticas:

• Subestimar o custo das cópias de objetos armazenados no cache (pessoas armazenam structs grandes por valor).
• Usar mutex global sem avaliar concorrência; causa degradação não linear conforme goroutines aumentam.
• Esquecer de instrumentar shards — sem métricas é difícil diagnosticar hot shards.
• Evitar esquecer de checar a necessidade de keys com alta concorrência: nesses casos, singleflight é essencial.

Regra prática: meça com cargas que refletem a produção. Micro-benchmarks são úteis, mas a distribuição das chaves e padrões de acesso revelam problemas reais.

Detalhe técnico: hashing determinístico que cria hot shards. Não use hash simples quando chaves tem prefixos comuns (por exemplo, usuário:1234/*). Use um hash com bom espalhamento (FNV, xxhash) e escolha shards como potências de dois.

Dicas operacionais

Configure eviction e monitore garbage collection/sequelas de memória. Para caches com TTL, considere manutenção periódica por goroutine de limpeza ou inserir timestamp no entry e checar no Get.

Para workloads com alta taxa de writes, prefira shards maiores ou diminuia o número de shards para reduzir overhead de gerência. Para leitura intensa, aumente shards para distribuir bloqueios.

Conclusao e recomendações práticas

Implementações ingênuas de LRU com mutex global funcionam para baixa concorrência, mas não escalam. Sharding reduz contenção; singleflight evita recomputação redundante. A combinação é comprovadamente eficaz para caches em Go em serviços com goroutines concorrentes.

Recomendações finais:

1. Comece simples: implemente LRU e meça. Use como baseline.
2. Adote sharding quando mutex global mostrar contenção nos benchmarks.
3. Adicione singleflight para evitar thundering herd em misses concorrentes.
4. Instrumente por shard, monitore hit/miss, latência de fetch e GC.
5. Valide com benchmarks que simulam padrões reais de tráfego antes de promover para produção.

Conclusão prática: para a maioria dos serviços Go com 1-3 anos de experiência, a rota mais segura é começar com a versão sharded+singleflight, ajustar número de shards a partir de benchmarks e instrumentação, e manter testes de carga como parte do ciclo de deploy.

Resumo técnico

Sharding transforma um único ponto de contenção em múltiplos pontos menores, aumentando throughput. Singleflight garante que apenas uma operação cara ocorra por chave em miss. Ambos combinados entregam baixo tempo de resposta e melhor uso de recursos.

Passos seguintes

Implemente as versões, rode os benchmarks neste artigo, e depois adicione métricas: latência por operação, hit ratio, e contagem de chamadas ao fetch. Se precisar de persistência entre instâncias, avalie caches distribuídos (Redis, memcached) com políticas LRU e consistência apropriada.