o problema
Cache de web é medido em dois eixos que brigam entre si: eficiência (miss ratio) e throughput. Trinta anos de literatura otimizaram o primeiro. ARC, 2Q, SLRU e MQ coordenam várias filas LRU; LHD, LRB, CACHEUS e GLCache colocam machine learning na escolha da vítima. Cada década acrescentou uma camada de complexidade — e quase nenhuma dessas ideias chegou à produção.
O que roda em produção hoje é FIFO e LRU: ATS, Varnish, Nginx, Redis, groupcache. Os autores listam por que. Algoritmo complexo é difícil de depurar — eles acharam dois bugs diferentes na implementação de LIRS de dois simuladores usados em trabalhos anteriores. Consome mais metadata por objeto, e metadata come o espaço que era para dado: o CACHEUS precisa de 3,3 vezes o do LRU, num workload em que muitos objetos têm dezenas de bytes. Tem parâmetro para ajustar por workload. E alonga a seção crítica, o que derruba throughput justamente quando a CPU passou de 100 cores. O LRU estrito, apesar de simples, sofre do mesmo mal por outro motivo: cada hit move o objeto para a cabeça da lista, e mover exige lock no caminho de leitura.
a ideia
FIFO-Reinsertion — o mesmo algoritmo que também se chama CLOCK ou Second Chance — existe desde os anos 1960. Uma fila, um bit visited por objeto. Na hora de despejar, olha-se o objeto da cauda: se foi visitado, zera o bit e reinsere na cabeça; se não, despeja.
SIEVE muda uma coisa só: o objeto que sobreviveu fica onde está. Quem anda é o ponteiro, o hand, que caminha da cauda para a cabeça e para no primeiro objeto com bit zero.
A consequência não é óbvia. Os sobreviventes se acumulam atrás do hand, então ele atravessa depressa a região dos objetos velhos e populares e passa a maior parte do tempo perto da cabeça, onde estão os recém-inseridos. Objeto novo é examinado quase imediatamente depois de entrar; objeto velho que continua sendo pedido quase nunca é examinado. A fila se particiona sozinha entre novos e velhos, sem que ninguém tenha configurado o tamanho de uma fila de admissão. Daí o nome: uma peneira que vai sifting os impopulares para fora.
como funciona
hit: x.visited = 1
miss (cache cheio):
o = hand ou tail, se hand for NULL
while o.visited == 1:
o.visited = 0
o = o.prev # não move o objeto
if o == NULL: o = tail
hand = o.prev
descarta o
insere x na cabeça, x.visited = 0Vale notar o que não está aí: nenhuma operação de lista no hit, nenhum contador, nenhum timestamp, nenhum ghost queue. São 4 linhas para o hit e 9 para o evict no simulador dos autores, contra 64 e 108 do ARC. Metadata: 17 bytes por objeto, um bit a mais que o LRU. Parâmetros: zero.
A análise formaliza a intuição da peneira. Para dois objetos retidos consecutivos, o mais próximo da cabeça tem “inter-examination time” menor; e todo objeto retido tem inter-arrival time menor ou igual ao inter-examination time do objeto da cauda. Esse número é a malha da peneira, e ela se ajusta sozinha: se poucos objetos sobreviveram numa rodada, a rodada seguinte demora mais para chegar ali e a malha alarga.
Medindo com perf stat em workload sintético power-law, SIEVE executa até 40% menos instruções por request que LRU e 24% menos que FIFO — parte disso vem do próprio miss ratio menor, que significa menos inserções.
o que isso custou
SIEVE não é scan-resistant, e os autores dizem isso sem rodeio. Em workloads de block cache, onde scans são comuns, o miss ratio às vezes fica acima do LRU: o scan empurra objetos populares para fora e, sem ghost cache, o algoritmo não tem como reconhecê-los quando voltam.
Com cache pequeno — 0,1% do footprint do trace — TwoQ e LHD passam à frente. O objeto novo é examinado antes de ter chance de mostrar popularidade. TwoQ escapa disso porque reserva 25% fixos do espaço para objetos novos, exatamente o tipo de parâmetro que SIEVE não tem.
Mudança de população também dói. Num workload construído colando dois Zipfians com objetos diferentes, o pico de miss ratio de SIEVE é maior que o de LRU e ARC, porque o hand precisa voltar até a cauda antes de conseguir despejar os objetos velhos que ficaram obsoletos de uma vez. E, em byte miss ratio, o LRB vence nos tamanhos de cache de 1% e 2% dos traces Wiki; SIEVE só ganha nos tamanhos maiores.
Por fim, a comparação principal de eficiência ignora tamanho de objeto, sob a justificativa de que caches slab-based despejam entre objetos de tamanho parecido. O byte miss ratio é tratado à parte.
onde isso aparece hoje
SIEVE não é só um algoritmo, é um primitivo — a proposta explícita do paper. Trocar o LRU dentro de algoritmos existentes por SIEVE melhora todos eles: LeCaR-SIEVE reduz o miss ratio do LeCaR em 4,5% na média, ARC-SIEVE reduz o do ARC em 3,7% (até 62,5%) e fica como o melhor de todos os avaliados nos dois tamanhos de cache. Quando os três candidatos simples recebem um oráculo de Belady, SIEVE-Belady tem o menor miss ratio em 97% e 94% dos traces — o candidato que SIEVE oferece é melhor que o que FIFO ou LRU ofereceriam.
O trabalho vem de uma linhagem: lazy promotion e quick demotion, formulados no HotOS’23 pelo mesmo grupo, e S3-FIFO, do SOSP’23, que aparece aqui como comparação. SIEVE é a coisa mais simples que os autores encontraram que faz as duas.
A adoção veio junto com o paper: implementações em Cachelib, groupcache, mnemonist, lru-dict e lru-rs — no máximo 21 linhas em cada uma —, mais o código e os traces abertos em github.com/cacheMon/NSDI24-SIEVE e bibliotecas por linguagem em sievecache.com. Como a ordem de inserção é preservada, caches particionados por TTL, como o Segcache, conseguem varrer objetos expirados sem procedimento separado.