Distributed Hash Tables.

Para guardar registos de pessoas podemos usar 26 pastas, separando as folhas pela primeira letra do apelido, por exemplo. Isto facilita a tarefa de encontrar um registo porque só precisamos procurar entre os que começam pela mesma letra. Mas isto é pouco eficiente porque há letras muito mais frequentes que outras. Algumas pastas vão ficar mais grossas, dar mais trabalho a percorrer e, porque é mais comum que os apelidos comecem com essas letras, será nessas pastas que vamos encontrar a maior parte dos nomes que tivermos de procurar.

A pesquisa é mais eficiente se distribuirmos melhor os registos. É aqui que entram as funções hash, para fazer batata-palha das regularidades que desequilibram o arquivo. Por exemplo, podemos converter cada letra num número, com o A correspondendo a 1, o B a 2 e assim por diante, somar os valores de todo o nome e calcular o resto da divisão por 26. O número resultante, de 0 a 25, indica em que pasta guardar aquele registo*. Assim a distribuição pelas pastas será mais uniforme, poupando trabalho na pesquisa. É claro que, para nós, fazer estas contas dá mais trabalho que procurar folhas nas pastas. Para o computador já não e, por isso, as tabelas de dispersão (hash tables) servem principalmente para organizar informação digital. Mas, para este post, o que interessa é a ideia.

E uma coisa boa nesta ideia é que a tabela pode ser distribuída. Em vez de uma pessoa ter as pastas todas podemos dá-las a um grupo de pessoas. Cada uma tem um número aleatório de 0 a 25 e guarda as pastas que ficam mais próximas do seu número que do número de qualquer outro participante. Além disso, cada participante sabe o telefone da pessoa com o número mais próximo acima do seu e da pessoa com o número mais próximo abaixo do seu, imaginando que o circulo dá a volta no 25, recomeçando do zero. Assim temos um anel telefónico de várias pessoas, cada uma com o contacto dos seus dois vizinhos.

Para consultar um registo nesta tabela distribuída calculamos o valor do hash do nome. O tal número de 0 a 25. Depois telefonamos a qualquer uma destas pessoas. Essa vê se o valor corresponde a uma das suas pastas. Se corresponder, dá-nos a informação que queremos. Se não corresponder, passa a chamada para o vizinho cujo número estiver mais próximo do hash que lhe demos. Este fará o mesmo até a chamada chegar a quem tem a pasta certa.

Se em vez de pessoas usarmos computadores, ainda melhor. Podemos ter uma função de hash com números maiores. Tipicamente, em vez de 26 valores são números com cinquenta dígitos. Assim cada valor corresponde a uma única entrada na tabela, em vez de uma pasta inteira. O reencaminhamento das mensagens é automático e praticamente instantâneo, pela Internet. Cada computador pode guardar não só os contactos dos seus vizinhos mais próximos mas também vários outros, acelerando a pesquisa. Com informação redundante, tendo vários computadores guardando os mesmos dados, sempre que um desaparece da rede a falha pode ser colmatada pelos vizinhos, trocando os dados necessários para manter toda a tabela disponível. E quando entra um participante novo, procura um cantinho onde se meter e os seus vizinhos dão-lhe uma parte da tabela para guardar.

É isto que está a tramar as editoras de discos e filmes. Quando alguém quer partilhar um ficheiro, o seu programa calcula o hash e gera uma ligação que pode ser publicada em qualquer sítio. Por exemplo, este é o URI ed2k de um ficheiro do filme District 9:

ed2k://|file|District_9_(2009).R5.avi|1474425934|F13EBED7C5C94A19D7872680A20BAD10|/

A primeira parte é o nome do ficheiro, que pouco importa porque o hash é calculado pelo ficheiro em si. Em seguida o tamanho em bytes e, no fim, o hash identificando este ficheiro na rede ed2k. Quem tiver este ficheiro em partilha – com a devida autorização dos detentores de direito e a bênção dos mapinetas, é claro – envia para a rede uma mensagem com o seu endereço e o hash do ficheiro. Esta é reencaminhada até ao computador que, naquele momento, tiver a seu cargo a gama de valores que inclui este hash. É esse computador que vai também receber todos os pedidos de quem quiser o ficheiro, pondo-os assim em contacto com quem o tem.

O Napster morreu quando encerraram os seus servidores, mas com uma DHT a rede deixa de depender de um computador central que registe quem tem quais ficheiros em partilha. Graças aos esforços da indústria discográfica, que motivaram o trabalho gratuito de muitos programadores, agora a RIAA pode fechar os servidores e trackers que quiserem. Já não são necessários.

Para os poucos leitores que tiveram paciência de ler este post até aqui, deixo uma modesta recompensa. Agora quando carregarem no botão Kad do eMule ou repararem no plugin Distributed DB do Vuze já sabem o que é. O que é mais que a grande maioria dos mapinetas que ainda andam a tentar fechar servidores e páginas da Internet, julgando que isso faz alguma coisa às redes de partilha.

* Este é um hash muito pobrezinho, só para explicar a ideia. Se quiserem ver como é um mais a sério, a Wikipedia tem artigos sobre os Secure hash algorithms e os Message digest algorithms, por exemplo.