o problema
Cache tem duas religiões. LRU aposta em recência e é ótimo quando o workload segue o modelo de stack depth distribution; é barato, é O(1) e responde rápido a mudança. Mas não enxerga frequência: uma varredura sequencial de uma tabela inteira empurra para fora todas as páginas quentes, e nenhuma delas será usada de novo. LFU aposta em frequência e é ótimo sob o modelo de referência independente, mas exige fila de prioridade, custa logarítmico no tamanho do cache e acumula páginas velhas com contador alto que ninguém mais pede.
Nos anos anteriores a 2003, a área tentou costurar as duas coisas: FBR, LRU-2, 2Q, LIRS, LRFU. Todos funcionam. Todos vêm com knob. E o paper mostra que o knob é o problema: no trace P12, o parâmetro CIP do LRU-2 com cache de 1.024 páginas dá 4,07% de hit ratio no melhor ajuste e 0,87% no pior; com 524.288 páginas, o ajuste que era o pior vira o melhor (63,15% contra 60,82%). Um valor bom para um cache é ruim para outro tamanho do mesmo cache, no mesmo trace. Os autores do 2Q admitiram que a fórmula deles para o parâmetro exige estimar a miss rate de antemão e “é de pouca utilidade prática”. Some a isso o custo: no trace de uma workstation, LRU e ARC ficam entre 12 e 17 segundos de book-keeping, LRU-2 dobra isso e LRFU chega a 554 segundos.
a ideia
Em vez de escolher entre recência e frequência, mantenha duas listas LRU — uma de páginas vistas uma vez recentemente, outra de páginas vistas pelo menos duas vezes — e trate a fronteira entre elas como a única decisão. O cache tem c páginas; o catálogo lembra 2c. As páginas que saíram do cache continuam no catálogo como fantasmas, sem dado, só metadado.
Fantasma serve para uma coisa: reclamar. Se chega uma requisição para uma página que está no fantasma da lista de recência, isso é prova de que a parte de recência estava curta demais, e o alvo cresce. Se o hit é no fantasma da lista de frequência, o alvo encolhe. O algoritmo investe na lista que está performando melhor, e o tamanho do passo depende de quão desequilibradas as duas listas de fantasma estão: quanto menor a lista que acertou, maior o ajuste. O efeito acumulado é um passeio aleatório do parâmetro, guiado pelo próprio workload.
como funciona
# T1/T2 no cache (c páginas); B1/B2 são fantasmas (só metadado, mais c)
# p = tamanho-alvo de T1, começa em 0
on request(x):
if x in T1 or x in T2: # hit
move x -> MRU(T2)
elif x in B1: # miss: recência estava curta
p = min(c, p + max(1, |B2|/|B1|))
replace(x); move x -> MRU(T2)
elif x in B2: # miss: frequência estava curta
p = max(0, p - max(1, |B1|/|B2|))
replace(x); move x -> MRU(T2)
else: # página nunca vista
poda L1/L2 para caber em 2c; replace(x)
insere x -> MRU(T1)
replace(x):
if T1 não vazio and (|T1| > p or (x in B2 and |T1| == p)):
LRU(T1) -> MRU(B1) # sai do cache, fica o fantasma
else:
LRU(T2) -> MRU(B2)Duas listas encadeadas, um inteiro, nenhuma fila de prioridade, nenhum contador de frequência para reescalar periodicamente. Custo constante por requisição, no pior caso — não na média.
o que isso custou
O catálogo dobra. Para cachear c páginas você mantém metadado de 2c, e isso é espaço que o LRU não gasta.
O modelo é estreito de propósito: demand paging, páginas de tamanho uniforme, sem prefetch, e a única métrica é hit ratio. Não há noção de miss caro e miss barato, nem de objeto de tamanho variável — nas medições de overhead os autores assumem explicitamente que um miss não custa nada além de um hit, para isolar o book-keeping.
Adaptar sem parar tem preço. Em workload estável existe um p quase ótimo, e o ARC nunca fica parado nele: oscila em volta. No trace P8 isso custa 27,51% contra 28,92% da política de fração fixa com o melhor p offline. O ganho aparece quando o workload muda de regime: no P4, onde o alvo percorre toda a faixa entre 0 e o tamanho do cache, o ARC online faz 11,24% e a melhor fração fixa offline faz 9,11%.
A universalidade é empírica, não provada — os autores tomam o termo emprestado da compressão de dados e o sustentam com traces, não com teorema. E a distância para o ótimo offline continua enorme: no OLTP com 1.000 páginas, ARC faz 38,93% e o MIN de Belady, que enxerga o futuro, faz 53,61%. A variante com histórico extra, ARC(x), perde a garantia de tempo constante no pior caso por causa da poda; os autores medem só a versão sem ela. A regra de desempate quando a lista está exatamente no alvo eles próprios chamam de arbitrária.
onde isso aparece hoje
A dupla lista-fantasma mais knob que se ajusta sozinho virou vocabulário: hoje se fala em ghost list sem citar a fonte. O cache de leitura do ZFS se chama ARC por causa deste paper.
A linhagem seguiu por dois caminhos opostos. Um insiste que a adaptação pode ser mais esperta e aprendida de dados, como em Cold-RL, que troca o escalar por uma política treinada com reinforcement learning offline. O outro desconfia da complexidade toda: SIEVE volta a uma lista só e argumenta que, para cache web, simplicidade rende mais que adaptatividade. A hipótese de página de tamanho uniforme, que aqui é premissa declarada, é justamente o que Segcache precisa demolir para lidar com objetos pequenos e heterogêneos. E o eixo espaço-versus-desempenho que o catálogo dobrado exemplifica é o que a conjectura RUM depois formalizou como escolha inescapável de projeto.