Sieve é mais simples que LRU
Um novo algoritmo de expulsão de cache chamado SIEVE é apresentado como uma alternativa mais simples e de melhor desempenho ao clássico LRU, especialmente em cargas de trabalho modernas de web e semelhantes a CDN. Os comentadores analisam de perto seu comportamento real, complexidade, casos-limite (como resistência a scans) e desempenho amortizado, frequentemente contrastando benchmarks acadêmicos com restrições do mundo real como concorrência, localidade de cache de CPU e padrões de acesso adversariais. O estilo de blog carregado de marketing e uma animação inicialmente incorreta recebem críticas, mas a pesquisa subjacente, as implementações de código aberto e os esclarecimentos dos autores levam muitos a ver SIEVE como uma adição promissora, porém dependente da carga de trabalho, ao conjunto de ferramentas de projeto de cache.
Estilo de escrita & comunicação
- Muitos leitores não gostam do tom exagerado e “de marketing” do blog (por exemplo, “superstar”, “turbo boost”), descrevendo-o como desagradável e parecido com ChatGPT.
- Outros são mais tolerantes, vendo isso como divulgação para não especialistas ou como produto da cultura atual de “vender sua pesquisa”.
- Os autores afirmam que o post foi “polido” pelo ChatGPT, aceitam as críticas e se comprometem a reescrevê-lo em um estilo mais direto.
Compreensão do algoritmo & correção
- Comentadores relacionam SIEVE ao clássico CLOCK/NRU: uma fila circular (ou lista), um ponteiro “hand” e uma flag de visitado de 1 bit significando “tocado desde a última passagem do hand”.
- Em um miss, o hand avança, limpando bits de visitado até encontrar uma entrada não visitada para expulsar.
- Várias pessoas acharam a prosa e a animação confusas. Uma inconsistência na animação (não limpar um bit de visitado) foi identificada; os autores a atualizaram.
Desempenho e adequação à carga de trabalho
- Relata-se que o SIEVE (segundo o paper e gráficos adicionais) supera baselines fortes (por exemplo, LRU, TinyLFU) em muitos traços web e em alguns traços de I/O de bloco multi-tenant, mas não em todas as cargas de trabalho.
- É explicitamente reconhecido que ele não é resistente a scans e pode degenerar para um comportamento parecido com MRU em alguns padrões.
- Uma afirmação de métrica (“melhor em ~45% dos traços”) levou a perguntas sobre os outros 55%; o contraponto é que esses 55% são compartilhados por muitos algoritmos concorrentes.
Escolhas de design, complexidade & implementação
- O custo de expulsão no pior caso é O(N), mas comentadores argumentam que é O(1) amortizado porque cada varredura limpa bits de visitado que precisam ser redefinidos um a um.
- Implementações discutidas: listas ligadas versus arrays/ring buffers versus dicionários ordenados; listas circulares para evitar verificações de null; designs log-estruturados/baseados em segmentos como o Segcache.
- Converter uma biblioteca LRU existente para SIEVE exigiu poucas mudanças de código, o que alguns veem como evidência de simplicidade de implementação.
Críticas, alternativas & preocupações adversariais
- Um longo subthread argumenta que inserir novos itens sempre em uma “head” fixa enquanto o hand percorre um anel conceitual penaliza injustamente itens dependendo da posição do hand; outros respondem que justiça para itens individuais é irrelevante se a taxa de acerto melhora.
- Alguns sugerem variantes: inserir na posição do hand, manter um deslocamento fixo entre inserção e hand, adicionar aleatoriedade ou esquemas multigeracionais.
- Há uma discussão mais ampla de que qualquer política determinística tem cargas de trabalho adversariais, e caches em produção frequentemente injetam aleatoriedade, amostragem ou políticas híbridas para evitar padrões de negação de serviço.