o problema
- Um site fica popular de uma hora para outra e recebe muito mais requests do que foi provisionado para atender. O paper cita casos concretos: o site do JPL depois que o cometa Shoemaker-Levy 9 bateu em Júpiter, um site da IBM durante o Deep Blue contra Kasparov, sites políticos na noite da eleição. A máquina fica swamped — não só para de responder como congestiona a rede em volta, derrubando vizinhos que não tinham nada com aquilo.
As respostas da época tinham cada uma seu jeito de falhar. O proxy cache compartilhado vive um dilema: quanto mais gente divide o mesmo cache, maior o ganho, e maior a chance de o próprio cache afundar. Malpani et al. fazem um grupo de caches funcionar como um só, consultando os outros por IP Multicast quando dá miss — o número de mensagens cresce até virar problema. O Harvest Cache, de Chankhunthod et al., monta uma árvore de caches, mas é a mesma árvore para todas as páginas: a raiz recebe pelo menos um request por página distinta pedida na árvore inteira. Plaxton e Rajaraman balanceiam com hash e hierarquias de conjuntos virtuais, só que usam o swamping como gatilho de replicação — o que faz sentido num sistema paralelo síncrono, onde a máquina afogada apenas descarta mensagens, e não faz sentido nenhum na internet, onde ela cai e ainda irrita o dono.
Por baixo de tudo isso há um problema mais fundo. Hash comum só funciona se todo mundo concordar sobre quais buckets existem. Na internet as máquinas entram e saem, e a notícia disso se espalha devagar; dois clientes têm visões diferentes do mundo ao mesmo tempo. Com um hash convencional, isso é catastrófico: mudar o tamanho do range joga fora todo o cache de todo mundo.
a ideia
Duas ferramentas. A primeira, random trees: uma árvore d-ária diferente por página, com os nós atribuídos a caches por hash, e o browser escolhendo um caminho folha→raiz aleatório. Isso preserva o coalescing da árvore do Harvest sem que nenhuma máquina seja raiz de muita coisa.
A segunda é o consistent hashing, e o movimento central é mudar a assinatura da função. Em vez de hashear para um conjunto fixo de buckets, a função recebe a visão como argumento: f: 2^B × I → B. Não existe “o mapeamento”; existe uma família de mapeamentos, um por visão, construída de modo que visões parecidas produzam mapeamentos parecidos. Em vez de fatiar o mundo em p pedaços recalculados do zero a cada mudança, cada bucket ganha posições fixas num círculo e cada item vai para a posição mais próxima. Tirar um bucket redistribui só o que era dele.
como funciona
Duas funções aleatórias: rB joga buckets no intervalo unitário e rI joga itens. fV(i) é o bucket b da visão V que minimiza |rB(b) − rI(i)|. Cada bucket não entra uma vez, mas Θ(log C) vezes — as réplicas, sem as quais o intervalo fica irregular e o balanceamento não vale. Independência log C-way nas funções basta; não é preciso aleatoriedade plena.
O paper formaliza quatro propriedades: balance (cada bucket leva O(1/|V|) dos itens), monotonicity, spread (quantos buckets distintos recebem o mesmo item somando todas as visões) e load (quantos itens distintos alguém acha que pertencem a um bucket). Com V visões contendo cada uma ao menos C/t buckets, spread e load ficam em O(t log C) com alta probabilidade.
Há uma caracterização elegante: toda função monótona equivale a associar a cada item uma permutação dos buckets e devolver o primeiro elemento da permutação que está na visão. Monotonicidade e permutação são a mesma coisa vista de dois ângulos.
Na implementação, uma árvore binária balanceada guarda a correspondência segmento→bucket, com C log C intervalos e lookup em O(log C). O truque para chegar a O(1) esperado é picar o intervalo em ~C log C segmentos de tamanho 1/2^x e manter uma árvore por segmento: achar o segmento é O(1), e cada um tem O(1) pontos em média. Inserir ou remover um bucket sai em O(log C) esperado, com a bisseção dos segmentos amortizada ao longo das inserções.
o que isso custou
A árvore multiplica a latência pela profundidade: 2 log_d C saltos. Os autores argumentam que o pipeline (um cache repassa bytes antes de receber a página inteira) e um d grande tornam isso pequeno para páginas grandes, mas admitem que o protocolo aumenta o atraso de páginas pequenas.
As garantias são probabilísticas e dependem de um adversário fraco por hipótese: ele escolhe quais páginas são pedidas, mas não vê os bits aleatórios do protocolo e não adapta os pedidos às latências que observa.
O modelo de latência é uma ultramétrica — clusters hierárquicos, tudo dentro de uma universidade equidistante. Ainda assim não basta: é preciso restringir os casos degenerados exigindo que em nenhum cluster a razão entre caches e browsers caia abaixo de 1/λ. Sem essa restrição, os próprios autores mostram que dá para forçar o afogamento de um cache cercado de browsers.
Páginas são supostas imutáveis. Falhas de servidor ficam de fora, delegadas ao algoritmo de dispersão de Rabin. E detecção de falha não é tratada: o paper trata só de tolerância, mandando t requests em paralelo, porque na internet não receber resposta rápida não é evidência de que a máquina caiu.
O buraco maior é o tempo. A análise temporal é a análise estática de um lote aplicada a uma janela curta o bastante para que nada seja despejado do cache. Os autores dizem com todas as letras que não sabem como modelar tempo na internet e deixam isso aberto, junto com a pergunta de qual é o tradeoff possível entre spread e load e se existe construção determinística com os mesmos limites. Uma consequência prática cai do modelo: aumentar q (o número de requests antes de um cache guardar a página) só piora a taxa suportada, o que sugere fixar q = 2.
onde isso aparece hoje
Sobreviveu a metade do hash; as árvores aleatórias por página ficaram no papel. Leighton e Lewin, dois dos autores, fundaram a Akamai pouco depois, e o problema atacado aqui — servir conteúdo popular sem afogar a origem — virou uma indústria.
Na década seguinte o consistent hashing virou o alicerce das DHTs: Chord é literalmente o esquema do anel transformado em serviço de lookup roteado, e Kademlia troca a distância no círculo pela métrica XOR mantendo a mesma ideia de “o nó mais próximo da chave”. Do lado dos bancos, Dynamo particiona por consistent hashing e usa nós virtuais — as réplicas Θ(log C) daqui, com outro nome e com a função extra de acomodar máquinas de capacidades diferentes — e Cassandra herda o anel inteiro. Qualquer cliente de memcached ou sharding de cache que você abrir hoje tem um anel dentro.