o problema
Em 2001 os sistemas peer-to-peer existiam e nenhum sabia achar coisa direito. Napster tinha um índice central: rápido, e um ponto único de falha e de controle — bastava desligar o índice. Gnutella foi para o outro extremo e resolvia busca por broadcast, com custo que cresce com o número de participantes. Freenet roteava consultas atrás de cópias em cache, o que dava um grau de anonimato, mas não garantia encontrar um documento que existe nem colocava limite no custo da busca.
A peça que faltava já existia em teoria: consistent hashing. Ele joga nós e chaves no mesmo espaço de identificadores, atribui cada chave ao nó seguinte no círculo, distribui carga de forma razoavelmente uniforme e, quando alguém entra ou sai, move só uma fração 1/n das chaves — o mínimo necessário. O problema é que o trabalho original supunha que cada nó conhecia quase todos os outros. Tabela de tamanho n por nó não sobrevive a uma rede grande onde as pessoas ligam e desligam a máquina. O Chord ataca exatamente essa lacuna: manter a atribuição do consistent hashing sem que ninguém precise da lista de todo mundo.
a ideia
O protocolo faz uma coisa só: lookup(key) devolve o IP do nó responsável pela chave. Replicação, cache, autenticação, nomes legíveis — nada disso está aqui, é trabalho da aplicação em cima. O espaço de chaves é plano, sem hierarquia administrativa como a do DNS, e a aplicação decide como mapear seus nomes para chaves.
Identificadores de m bits num círculo módulo 2^m. O id de um nó é o SHA-1 do IP; o id de uma chave é o SHA-1 da chave. A chave pertence ao primeiro nó no sentido horário — o sucessor. Cada nó só precisa conhecer seu sucessor imediato, e isso já basta para achar qualquer chave: dá para percorrer o anel inteiro. Também é inaceitável, n saltos. A partir daí o Chord adiciona atalhos a distâncias que dobram, um skip list fechado em círculo, e a busca passa a cortar metade do caminho restante por salto.
A escolha de projeto que interessa é a separação entre as duas coisas. O sucessor garante a resposta certa; os atalhos garantem a resposta rápida. Como consistência de log n ponteiros é difícil de manter numa rede que muda o tempo todo, o protocolo aceita que os atalhos fiquem errados e cuida de perto de um ponteiro só.
como funciona
Cada nó mantém uma finger table com até m entradas: a i-ésima aponta para o sucessor de n + 2^(i-1). A primeira entrada é o próprio sucessor. Numa busca, se a chave não cai entre o nó e seu sucessor, o nó procura na tabela o finger que mais imediatamente precede a chave e repassa a pergunta para lá. Se o alvo está no i-ésimo intervalo, o finger daquele intervalo já está dentro dele, logo a distância cai pelo menos pela metade a cada passo — log n saltos com alta probabilidade. A implementação pode ser iterativa (quem pergunta conduz a busca) ou recursiva (cada nó encaminha); o simulador do paper usa a iterativa.
Para entrar, o nó descobre por fora algum participante, pede a ele seu próprio sucessor, monta a tabela e avisa os nós que passam a ter que apontar para ele: O(log² n) mensagens. Essa versão agressiva não aguenta entradas concorrentes, então o protocolo real troca por estabilização periódica. Cada nó pergunta ao sucessor quem é o predecessor dele; se aparecer alguém no meio, adota esse alguém como novo sucessor e o notifica. Em paralelo, fix_fingers recalcula uma entrada aleatória da tabela por rodada. Duas garantias saem daí: uma consulta que já funcionava nunca deixa de funcionar, e algum tempo depois do último join todos os ponteiros de sucessor estão certos.
Contra falhas, cada nó guarda uma successor-list com seus r sucessores mais próximos. Morreu o sucessor, promove a primeira entrada viva.
o que isso custou
O anel é um espaço artificial e o roteamento ignora a rede física. Plaxton, citado como o parente mais próximo, garante que a consulta nunca viaja mais longe em distância de rede do que o nó que guarda a chave; o Chord não garante nada disso, e troca essa propriedade por simplicidade e por lidar bem com entradas e falhas simultâneas. No protótipo em dez sites, com RTT típico de 60 ms, uma busca com 180 nós gastava cinco trocas de mensagem e mediana de 285 ms.
Balanceamento de carga só fecha com virtual nodes. Sem eles, a carga de um nó pode passar da média por um fator log n, e na simulação sempre havia nós com zero chaves. Com virtual nodes o custo é multiplicar o espaço de finger tables pelo número de réplicas lógicas, e ainda decidir quantas — número que depende do tamanho da rede, que ninguém sabe.
Usar SHA-1 em vez de uma função universal torna o protocolo determinístico e derruba a formulação probabilística: os teoremas passam a valer “sob hipóteses padrão de dificuldade”, não com alta probabilidade. A estabilização não cura partições: um anel quebrado em ciclos disjuntos parece localmente consistente, e os autores admitem não saber se falhas intermitentes conseguem produzir esse estado. Um participante malicioso pode inserir um nó com id logo depois da chave alvo e devolver erro — ataque à disponibilidade que a derivação do id a partir do IP só encarece, não elimina. E lookups durante churn simplesmente falham: o protocolo não repete, quem repete é a camada de cima.
onde isso aparece hoje
Chord é a formalização que fez a DHT virar objeto de estudo, e sua base direta está em Consistent Hashing and Random Trees; a estrutura dos atalhos é a mesma intuição de Skip Lists aplicada a um anel, ideia que Skip Graphs levaria adiante em 2003. Na prática aberta, quem venceu foi Kademlia, no ano seguinte, com métrica XOR e tabelas mais tolerantes a churn — é o que roda no DHT do BitTorrent e no IPFS.
Dentro do datacenter a herança se dividiu: Dynamo e Cassandra ficaram com o anel de consistent hashing e jogaram fora o roteamento em log n, porque numa rede administrada todo nó pode conhecer todo nó e a busca vira um salto só. O que sobrou do Chord ali é a lição de projeto: identificar o invariante mínimo que sustenta a corretude, manter esse com cuidado, e tratar todo o resto como cache que pode envelhecer.