Uma tabela de hash distribuída (ou DHT para Tabela de hash distribuída ) é uma tecnologia que permite o estabelecimento de uma tabela de hash em um sistema distribuído . Uma tabela hash é uma estrutura de dados do tipo chave → valor . Cada dado é associado a uma chave e é distribuído pela rede . As tabelas de hash permitem distribuir o armazenamento de dados por todos os nós da rede, sendo cada nó responsável por uma parte dos dados. As tabelas de hash distribuídas fornecem um algoritmo para localizar o nó responsável pelos dados e seu valor da chave.
Os protocolos Chord , P2P CAN , Tapestry , Pastry , Kademlia configuram tabelas de hash distribuídas. Tabelas hash distribuídas são usadas em sistemas de compartilhamento de dados ponto a ponto (como BitTorrent , IPFS , etc.), mas também em software operando de maneira descentralizada, como o mecanismo de busca distribuído YaCy ou em roteamento. I2P .
Suponha que um grande número de usuários (5 milhões) tenha lançado seu software de compartilhamento de arquivos ponto a ponto (P2P) em seus computadores. Todos compartilham seus arquivos (áudio, imagens, vídeo, multimídia, etc. ). Um usuário (Luc) possui, por exemplo, o álbum (fictício) " 42 mon amour ".
Suponha que outro usuário (Peter) queira baixar este álbum. Como o software P2P dele pode encontrar o computador de Luc? O software de Pierre poderia perguntar aos 5 milhões de computadores se por acaso eles têm este álbum. O software de Luc então responderia: "Eu o tenho e posso começar a transferi-lo." "No entanto, seria muito longo e muito pesado no consumo de recursos perguntar aos 5 milhões de computadores se eles têm este álbum, porque haveria constantemente milhões de perguntas como" Estou procurando por este álbum, o como você? ", Resultando em milhões de respostas:" Não, desculpe! "
Um grande diretório arquivando os nomes dos arquivos compartilhados por todos os usuários resolveria a questão: bastaria perguntar a este "grande diretório" (a tabela hash ) do álbum de música 42 meu amor para obter a resposta: "Está disponível. no computador de Luc. (e o de Mathieu, Paul, etc. ) ”. Era assim que funcionava a primeira geração de redes P2P. Um servidor central serviu como um “grande diretório” (exemplos: Napster , Audiogalaxy , Edonkey , Kazaa ). Essa solução é cada vez menos usada por causa de sua fragilidade; na verdade, se o servidor central não estiver mais disponível, nenhuma pesquisa poderá ser realizada nos arquivos compartilhados da rede, falamos então de um único ponto de falha .
A tabela hash distribuída, portanto, fornece, em relação às técnicas anteriores, independência vis-à-vis um servidor central, distribuindo-o aos vários nós.
Por exemplo, o usuário Jean-Claude será responsável por todos os arquivos que começam com A, Toto será responsável por todos os arquivos que começam com B, etc. Quando um novo usuário se conecta à rede, a primeira coisa que o software faz é anunciar quais arquivos podem ser compartilhados. Se ele for dono do filme Big Buck Bunny , por exemplo , ele dirá ao usuário Toto (que é o responsável pelos arquivos que começam com B): “Eu tenho o filme Big Buck Bunny. Se as pessoas quiserem, está disponível na minha casa ”. As pesquisas, portanto, tornam-se muito rápidas. Se estivermos procurando por Big Buck Bunny, perguntaremos diretamente ao responsável pela letra "B".
A realidade é um pouco mais complexa: uma pessoa não deve se responsabilizar pelas palavras que começam com "B", pois se desligar o computador parte da lista telefônica se perderá. Portanto, é necessário introduzir uma certa redundância no diretório e, portanto, vários computadores são simultaneamente responsáveis pelas mesmas listas. Além disso, como existem centenas de milhões de arquivos compartilhados, o princípio de divisão do diretório não se baseia nas letras do alfabeto, mas em uma tabela hash das palavras dos títulos dos arquivos.
Por fim, nem todo computador precisa conhecer todos os computadores que arquivam palavras. Ele normalmente conhece cerca de cem computadores. Se o usuário pesquisar Big Buck Bunny e não conhecer o computador que arquiva os arquivos começando com B, então:
Muitos softwares de compartilhamento de dados usam um DHT para descentralizar parte da informação, por exemplo, Ares Galaxy , também, muitos clientes recentes para o protocolo BitTorrent como Azureus , Bitcomet , Deluge , I2pSnark , KTorrent , Transmission ou mesmo µTorrent usam um DHT para fazer é possível encontrar pares sem usar um rastreador .
O primeiro cliente BitTorrent a usar DHT foi Azureus, seguido pelo cliente BitTorrent oficial que criou uma versão diferente. A versão oficial do cliente foi então chamada de Mainline DHT. A maioria dos clientes agora oferece suporte à versão Mainline DHT.
Alguns softwares de mensagens instantâneas usam DHT para descentralizar parte das informações, por exemplo Jami ou Tox .