Cloudflare - In-Memory KV Store com TTL

Dados da empresa e da vaga

Empresa: Cloudflare, Inc.
Sede: São Francisco, Califórnia, EUA (com polos em Londres, Lisboa, Austin, Cingapura e contratação remota global)
Perfil da vaga: Systems Engineer (Edge Infrastructure / Distributed Storage em Go)
Modelo de trabalho: Remoto internacional
Faixa salarial estimada da vaga:
- Sênior nos EUA: $170.000 a $210.000 (Base) / $250.000 a $340.000 USD/ano (Total Comp com ações na NYSE: NET)
- Sênior Internacional Remoto (LATAM/Europa): $80.000 a $125.000 USD/ano
Stack principal do time: Go, Rust, C, Linux Kernel / eBPF, TCP/UDP, HTTP/3, Docker, Prometheus

Contexto do desafio técnico

A Cloudflare opera uma das maiores redes de borda (Edge) do planeta, sendo responsável por acelerar e proteger dezenas de milhões de propriedades web. Seus engenheiros de sistemas trabalham diretamente na camada de rede e armazenamento distribuído de baixa latência (como o Cloudflare KV e Workers).

Em testes práticos para engenheiros Go de sistemas, a Cloudflare costuma aplicar desafios voltados para estruturas de dados em memória de alta performance, protocolos de rede puros e concorrência sem bloqueio global.

O desafio clássico consiste em construir um In-Memory Key-Value Store Concorrente com Suporte a TTL e Expiração Amostrada, simulando o comportamento central de sistemas como Redis e Memcached, acompanhado de uma interface HTTP ou TCP de acesso rápido.

Requisitos funcionais e comportamentais

Operações fundamentais da loja de chaves:
- Set(key string, value []byte, ttl time.Duration): Armazena o valor associado à chave com um prazo de expiração opcional. Se ttl == 0, a chave vive indefinidamente.
- Get(key string) ([]byte, bool): Retorna o valor associado à chave. Se a chave não existir ou já tiver expirado, retorna nil, false.
- Delete(key string): Remove imediatamente a chave do armazenamento.
Estratégia de Expiração Híbrida (Passiva + Ativa):
- Expiração Passiva (Lazy Expiration): Quando uma chave é solicitada no Get(), o sistema verifica se seu prazo de validade expirou. Se sim, remove a chave naquele instante e retorna não encontrada.
- Expiração Ativa Periódica (Active Janitor / Sampling): Se chaves forem gravadas com TTL curto e nunca mais forem lidas por nenhum cliente, elas continuariam ocupando memória indefinidamente apenas com a estratégia passiva. O candidato deve implementar uma rotina concorrente que acorda periodicamente (ex.: a cada 100ms), sorteia uma amostra aleatória de chaves com TTL e remove aquelas que já prescreveram.
Particionamento de Travas (Lock Sharding / Striping):
- A grande armadilha do teste: Proteger o mapa inteiro com um único sync.RWMutex cria um gargalo severo em servidores com 16, 32 ou 64 núcleos de CPU, degradando a vazão.
- O candidato de nível sênior deve particionar o armazenamento interno em $N$ fatias independentes (shards, ex.: 32 ou 64 buckets), onde cada bucket possui seu próprio mapa e seu próprio mutex. A chave é roteada para o bucket correspondente por uma função hash rápida (como FNV-1a).

Exemplo de arquitetura particionada em Go

package kvstore

import (
	"context"
	"hash/fnv"
	"sync"
	"time"
)

type item struct {
	value     []byte
	expiresAt int64 // timestamp em nanossegundos (0 se eterno)
}

func (i *item) isExpired(now int64) bool {
	if i.expiresAt == 0 {
		return false
	}
	return now > i.expiresAt
}

type shard struct {
	mu    sync.RWMutex
	items map[string]*item
}

type ShardedStore struct {
	shardCount uint32
	shards     []*shard
}

func NewShardedStore(ctx context.Context, shardCount uint32, cleanupInterval time.Duration) *ShardedStore {
	store := &ShardedStore{
		shardCount: shardCount,
		shards:     make([]*shard, shardCount),
	}

	for i := uint32(0); i < shardCount; i++ {
		store.shards[i] = &shard{
			items: make(map[string]*item),
		}
	}

	go store.startActiveJanitor(ctx, cleanupInterval)

	return store
}

func (s *ShardedStore) getShard(key string) *shard {
	h := fnv.New32a()
	h.Write([]byte(key))
	idx := h.Sum32() % s.shardCount
	return s.shards[idx]
}

func (s *ShardedStore) Set(key string, val []byte, ttl time.Duration) {
	var expiresAt int64
	if ttl > 0 {
		expiresAt = time.Now().Add(ttl).UnixNano()
	}

	shard := s.getShard(key)
	shard.mu.Lock()
	shard.items[key] = &item{
		value:     val,
		expiresAt: expiresAt,
	}
	shard.mu.Unlock()
}

func (s *ShardedStore) Get(key string) ([]byte, bool) {
	shard := s.getShard(key)
	now := time.Now().UnixNano()

	shard.mu.RLock()
	it, exists := shard.items[key]
	shard.mu.RUnlock()

	if !exists {
		return nil, false
	}

	// Expiração Passiva (Lazy)
	if it.isExpired(now) {
		shard.mu.Lock()
		// Double check sob trava de escrita
		if it, exists = shard.items[key]; exists && it.isExpired(now) {
			delete(shard.items, key)
			exists = false
		}
		shard.mu.Unlock()

		if !exists {
			return nil, false
		}
	}

	return it.value, true
}

func (s *ShardedStore) startActiveJanitor(ctx context.Context, interval time.Duration) {
	ticker := time.NewTicker(interval)
	defer ticker.Stop()

	for {
		select {
		case <-ctx.Done():
			return
		case <-ticker.C:
			s.cleanExpiredSample()
		}
	}
}

func (s *ShardedStore) cleanExpiredSample() {
	now := time.Now().UnixNano()

	// Varrer cada shard de forma rápida
	for _, shard := range s.shards {
		shard.mu.Lock()
		count := 0
		for k, it := range shard.items {
			if it.isExpired(now) {
				delete(shard.items, k)
			}
			count++
			if count > 50 { // Amostragem máxima por ciclo para não travar o shard
				break
			}
		}
		shard.mu.Unlock()
	}
}

O que os avaliadores da Cloudflare analisam no teste

Escalabilidade concorrente: Testam o armazenamento simulando centenas de leituras simultâneas (goroutines) enquanto escritas acontecem. Com Lock Sharding, a contenção de mutexes cai drasticamente.
Uso de inteiros para timestamps: Usar int64 (em nanossegundos) em vez de instâncias de time.Time dentro da struct reduz o tamanho em memória de cada nó de cache e acelera a comparação numérica no laço de expiração.
Ausência de alocações transitórias: Evitar converter string para []byte repetidamente para não disparar cópias no Heap.
Respeito ao ciclo de vida: Garantir que o encerramento da aplicação tramite o fechamento correto de canais e interrupção do ticker via defer ticker.Stop().

Neste texto