o problema
Cache in-memory guarda objeto pequeno. Nos quatro maiores clusters de produção do Twitter, o tamanho médio de chave mais valor é 230, 55, 294 e 72 bytes. Memcached carrega 56 bytes de metadados junto de cada objeto: dois ponteiros de LRU, um ponteiro de hash, tempo de acesso, tempo de expiração, tamanho e o valor de cas. Num cache de objetos de 45 bytes, o contêiner pesa mais que a carga. E a linha de pesquisa que atacava miss ratio ia no sentido contrário: LHD, Hyperbolic, pRedis e mPart tomam decisões melhores de despejo justamente adicionando mais metadado por objeto.
O segundo desperdício é o objeto expirado. TTL é onipresente em cache — no Twitter, todo workload usa TTL, de um minuto a um mês, para limitar inconsistência, forçar recomputação periódica, implementar rate limiter e cumprir regras de privacidade. Só que nenhuma técnica existente remove tudo que expirou por preço razoável: deleção no acesso e checagem da cauda da LRU são baratas e incompletas; scan completo do cache é completo e caro; a amostragem aleatória do Redis é as duas coisas ruins ao mesmo tempo, com acesso aleatório à memória e um percentual residual de expirados que o operador tem que aceitar. Some a isso fragmentação: quem usa malloc sofre fragmentação externa, quem usa slab sofre fragmentação interna e calcificação de slab, com migração que às vezes derruba o processo.
a ideia
Trocar a unidade de gerência. Em vez de administrar objeto por objeto, Segcache administra segmentos: logs de tamanho fixo, 1 MB por padrão, nos quais objetos são só appendados. A diferença em relação ao slab do Memcached é o critério de agrupamento — segmento agrupa por TTL aproximado, não por tamanho. Como os segmentos de um mesmo TTL ficam encadeados em ordem de criação, eles ficam automaticamente em ordem de expiração. Expirar vira olhar a cabeça da corrente.
Da mesma decisão sai a economia de metadado, que os autores chamam de “object sharing economy”: se todos os objetos de um segmento nascem juntos e morrem juntos, tempo de criação, TTL e reference counter podem morar no header do segmento. E se o ciclo de vida é gerido em bloco, ninguém precisa de ponteiro de LRU por objeto.
como funciona
O espectro de TTLs é cortado em 1.024 buckets, divididos em quatro grupos; de um grupo para o próximo, a largura cresce por um fator de 16, o que cobre de segundos a um mês sem perder resolução na ponta baixa. O TTL é arredondado para baixo — objeto pode expirar cedo, nunca tarde. Achar o bucket custa algumas operações bitwise; a escrita faz append no segmento da cauda da corrente.
A hash table usa bulk chaining: cada bucket ocupa 64 bytes, uma linha de cache da CPU, dividida em oito slots. O primeiro guarda informação do bucket (spinlock de 8 bits, contador de uso de 8, timestamp do último acesso de 16, cas de 32), seis guardam objetos, e o oitavo guarda um objeto ou o ponteiro para o próximo bucket. Cada slot de objeto tem 24 bits de segment id, 20 de offset, 8 de frequência e 12 de tag. Com isso o ponteiro de hash por objeto some. Sobram, no objeto, 8 bits de tamanho de chave, 24 de tamanho de valor e 8 de flag: 5 bytes, 91% menos que Memcached.
A expiração é uma thread de fundo que lê o header do primeiro segmento de cada bucket não vazio; se expirou, libera o segmento inteiro e desce a corrente até achar um que não expirou. O despejo mescla N segmentos consecutivos do mesmo bucket em um só, numa passada, retendo cerca de 1/N dos bytes de cada, com ranking por frequência sobre tamanho e limiar dinâmico reajustado a cada décimo de segmento. A frequência vem do ASFC, um contador de um byte: incremento determinístico até 16, depois probabilístico no estilo Morris, e no máximo um incremento por segundo — o que absorve rajada. Objeto retido tem a frequência zerada na mescla, o que dá efeito parecido com janela sem introduzir parâmetro novo.
O modelo de threads cai fora dos pontos de contenção clássicos: cada thread escreve nos seus segmentos ativos, a leitura não pega lock exceto para incrementar frequência, e só a remoção de segmento da corrente entra em seção crítica. Resultado: 22-60% menos memória que os melhores designs comparados, até 40% mais throughput que Memcached numa thread, e cerca de 8× o throughput do Memcached com 24 threads (70 MQPS contra 9).
o que isso custou
A economia é paga em aproximação. O segmento inteiro expira pelo objeto mais velho, então parte dos objetos morre antes do TTL nominal; os autores medem impacto desprezível no miss ratio das traces do Twitter, mas é uma medição, não uma garantia. O cas compartilhado por bucket de hash cria falso data race entre chaves diferentes — a defesa é estatística: tráfego de cas é ordens de magnitude menor que leitura e escrita, e o cliente re-tenta.
Despejo por segmento pode jogar fora objeto popular. A mescla mitiga, e os próprios autores dizem que as heurísticas de seleção e mescla podem não ser ótimas em alguns casos e merecem mais exploração. Não há admission control, decisão justificada por one-hit-wonder abaixo de 5% em cache in-memory; para CDN, com até 30%, o desenho não serve. E o conjunto todo só vale para cache: aproximar tempo e compartilhar cas e reference counter é inaceitável num key-value store durável, onde o dado é fonte da verdade.
A avaliação também tem buracos declarados. PCache não suporta multithread e ficou fora do teste de escalabilidade; r-LHD e r-Hyperbolic também, porque os autores não acharam jeito simples de dar a eles um locking melhor que o do Memcached; o Memcached com scan travou em deadlock acima de oito threads. Todas as traces vêm de uma empresa só.
onde isso aparece hoje
Segcache é módulo de storage do Pelikan, o framework de cache do Twitter, e está aberto. O argumento central — que expiração e metadado rendem mais que refinar o algoritmo de despejo — ficou como contraponto útil a uma literatura que continua atacando o despejo, seja com simplicidade, como o SIEVE, publicado três anos depois por um grupo que inclui os mesmos autores, seja com aprendizado de máquina, como o Cold-RL no NGINX. A distinção entre cache e store que o paper insiste em fazer também explica por que técnicas de compactação de sistemas log-structured, como as do RocksDB, não se transportam: a taxa de escrita de um cache em produção é alta demais para elas.