SIEVE, um novo algoritmo de código aberto desenvolvido por cientistas da computação da Emory University, da Carnegie Mellon University e da Pelikan Foundation, simplifica e melhora o gerenciamento de cache da web. Este algoritmo decide efetivamente quais dados serão removidos de um cache, aumentando a eficiência do sistema e reduzindo significativamente a taxa de falhas em comparação com outros algoritmos.
O novo algoritmo de código aberto tem potencial para revolucionar o gerenciamento de tráfego da web em grande escala.
Cientistas da computação desenvolveram um algoritmo altamente eficaz, mas incrivelmente simples, para decidir quais itens descartar de um cache da web para abrir espaço para novos. Conhecido como SIEVE, o novo algoritmo de código aberto tem potencial para transformar o gerenciamento do tráfego da web em grande escala.
SIEVE é um projeto conjunto de cientistas da computação da Emory University, Carnegie Mellon University e da Pelikan Foundation. O artigo da equipe sobre o SIEVE será apresentado no dia 21st Simpósio USENIX sobre Projeto e Implementação de Sistemas em Rede (NSDI) em Santa Clara, Califórnia, em abril.
Uma pré-impressão do artigo já está causando sucesso.
“O SIEVE é cada vez maior do que apenas nós”, diz Yazhuo Zhang, aluno de doutorado da Emory e coautor do artigo. “Já está apresentando um bom desempenho, mas estamos recebendo muitas sugestões boas para torná-lo ainda melhor. Essa é a beleza do mundo do código aberto.”
Zhang compartilha a primeira autoria do artigo com Juncheng (Jason) Yang, que recebeu seu mestrado em ciência da computação na Emory e agora é candidato a doutorado na Carnegie Mellon.
O logotipo da SIEVE, criado por Yazhuo Zhang, retrata objetos mais quentes em tons de vermelho e objetos mais frios em tons de azul. Zhang também projetou um site para o SIEVE, incluindo um gráfico em movimento demonstrando como ele funciona. Crédito: Yazhuo Zhang
“SIEVE é uma melhoria fácil de um algoritmo de remoção de cache testado e comprovado que está em uso há décadas – o que é literalmente como séculos no mundo da computação”, diz Ymir Vigfusson, professor associado do Departamento de Ciência da Computação de Emory.
Vigfusson é co-autor sênior do artigo, junto com Rashmi Vinayak, professora associada do departamento de ciência da computação da Carnegie Mellon. Yao Yue, engenheiro de computação da Fundação Pelikan, também é coautor.
Além de sua velocidade e eficácia, um fator-chave que desperta o interesse no SIEVE é sua simplicidade, que lhe confere escalabilidade.
“Simplicidade é a sofisticação máxima”, diz Vigfusson. “Quanto mais simples forem as peças de um sistema projetado para atender bilhões de pessoas em uma fração de segundo, mais fácil será implementar e manter esse sistema com eficiência.”
Manter ‘objetos quentes’ à mão
Muitas pessoas entendem o valor de reorganizar regularmente seu armário de roupas. Itens que nunca são usados podem ser jogados fora e aqueles que raramente são usados podem ser movidos para o sótão ou algum outro local remoto. Isso deixa os itens mais usados facilmente acessíveis para que possam ser encontrados rapidamente, sem precisar vasculhar.
Um cache é como um armário bem organizado para dados de computador. O cache é preenchido com cópias dos objetos mais populares solicitados pelos usuários, ou “objetos quentes” na terminologia de TI. O cache mantém essa pequena coleção de objetos quentes separadamente do banco de dados principal de uma rede de computadores, que é como um vasto armazém repleto de todas as informações que poderiam ser atendidas pelo sistema.
O armazenamento em cache de objetos ativos permite que um sistema em rede funcione com mais eficiência, respondendo rapidamente às solicitações dos usuários. Um aplicativo da Web pode lidar efetivamente com mais tráfego entrando em um armário prático para pegar a maioria dos objetos que os usuários desejam, em vez de ir até o warehouse e pesquisar cada solicitação em um enorme banco de dados.
“O cache está em toda parte”, diz Zhang. “É importante para todas as empresas, grandes ou pequenas, que utilizam aplicações web. Todo site precisa de um sistema de cache.”
Mesmo assim, o cache é relativamente pouco estudado no campo da ciência da computação.
Como funciona o cache
Embora o cache possa ser considerado um armário bem organizado para um computador, é difícil saber o que deve ser guardado nesse armário quando milhões de pessoas, com necessidades em constante mudança, o utilizam.
A memória rápida do cache é cara para operar, mas é crítica para uma boa experiência dos usuários da web. O objetivo é manter as informações futuras mais úteis no cache. Outros objectos devem ser continuamente peneirados, ou “despejados” na terminologia tecnológica, para dar lugar à variedade variável de objectos quentes.
Algoritmos de remoção de cache determinam quais objetos devem ser descartados e quando fazê-lo.
FIFO, ou “primeiro a entrar, primeiro a sair”, é um algoritmo de despejo clássico desenvolvido na década de 1960. Imagine objetos alinhados em uma esteira transportadora. Os objetos recém-solicitados entram à esquerda e os objetos mais antigos são removidos quando chegam ao final da linha à direita.
No algoritmo LRU, ou “menos usado recentemente”, os objetos também se movem ao longo da linha em direção ao despejo no final. No entanto, se um objeto for solicitado novamente enquanto desce pela correia transportadora, ele será movido de volta para o início da linha.
Existem centenas de variações de algoritmos de despejo, mas eles tendem a assumir maior complexidade para ganhar eficiência. Isso geralmente significa que eles são opacos e exigem muita manutenção, especialmente quando lidam com cargas de trabalho massivas.
“Se um algoritmo é muito complicado, ele tende a ter mais bugs, e todos esses bugs precisam ser corrigidos”, explica Zhang.
Uma ideia simples
Assim como o LRU e alguns outros algoritmos, o SIEVE faz um ajuste simples no esquema FIFO básico.
O SIEVE inicialmente rotula um objeto solicitado como “zero”. Se o objeto for solicitado novamente à medida que desce pela faixa, seu status muda para “um”. Quando um objeto rotulado como “um” chega ao final da linha, ele é automaticamente redefinido para “zero” e despejado.
Um ponteiro, ou “mão em movimento”, também examina os objetos à medida que eles percorrem a linha. O ponteiro começa no final da linha e depois salta para a cabeça, movendo-se num círculo contínuo. Sempre que o ponteiro atinge um objeto rotulado como “zero”, o objeto é removido.
“É importante despejar objetos impopulares o mais rápido possível, e o SIEVE é muito rápido nessa tarefa”, diz Zhang.
Além desse rápido rebaixamento de objetos, o SIEVE consegue manter objetos populares no cache com o mínimo esforço computacional, conhecido como “promoção preguiçosa” na terminologia computacional. Os pesquisadores acreditam que o SIEVE é o algoritmo de remoção de cache mais simples para alcançar efetivamente tanto o rebaixamento rápido quanto a promoção preguiçosa.
Uma taxa de falta mais baixa
O objetivo do armazenamento em cache é atingir uma taxa de falta baixa – a fração de objetos solicitados que devem ser buscados no “armazém”.
Para avaliar o SIEVE, os pesquisadores conduziram experimentos em rastreamentos de cache da web de código aberto do Meta, Wikimedia, X e quatro outros grandes conjuntos de dados. Os resultados mostraram que o SIEVE atinge uma taxa de falta menor do que nove algoritmos de última geração em mais de 45% dos traços. O próximo melhor algoritmo tem uma taxa de falha inferior de apenas 15%.
A facilidade e simplicidade do SIEVE levanta a questão de por que ninguém inventou o método antes. O foco da equipe SIEVE em como os padrões de tráfego da web mudaram nos últimos anos pode ter feito a diferença, teoriza Zhang.
“Por exemplo”, diz ela, “novos itens agora ficam ‘quentes’ rapidamente, mas também desaparecem rapidamente. As pessoas perdem continuamente o interesse pelas coisas porque coisas novas continuam surgindo.”
As cargas de trabalho de cache da Web tendem a seguir o que é conhecido como distribuições Zipfian generalizadas, onde um pequeno subconjunto de objetos é responsável por uma grande proporção de solicitações. O SIEVE pode ter atingido um ponto ideal do Zipfian para as cargas de trabalho atuais.
“É claramente um momento transformador para a nossa compreensão da remoção de cache da web”, diz Vigfusson. “Isso muda uma construção que tem sido usada cegamente por tanto tempo.”
Mesmo uma pequena melhoria num sistema de cache web, acrescenta ele, pode poupar milhões de dólares num grande centro de dados.
Zhang e Yang estão prestes a receber seu doutorado em maio.
“Eles estão fazendo um trabalho incrível”, diz Vigfusson. “É seguro dizer que ambos estão agora entre os especialistas mundiais em remoção de cache da web.”
Reunião: Simpósio USENIX sobre Projeto e Implementação de Sistemas em Rede
A pesquisa foi financiada pela National Science Foundation.
