Distributed hash table

Tabelas hash distribuídas (DHTs) ou ainda tabelas de espalhamento distribuídas são uma classe de sistemas distribuídos descentralizados que provêem um serviço de lookup similar a uma tabela hash: pares (chave, valor) são armazenados na DHT e qualquer nó participante pode eficientemente recuperar o valor associado a uma dada chave. A responsabilidade de manter o mapeamento de chaves para valores é distribuída entre os nós tal que mudanças no conjunto de participantes causem o mínimo de desordem. Isso faz com que as DHTs escalem a um número extremamente grande de nós e gerenciem chegadas, saídas e falhas contínuas dos mesmos.

DHTs formam infra-estruturas que podem ser usadas para construir sistemas mais complexos como sistema de arquivos distribuído, compartilhamento de arquivos peer-to-peer e sistemas de distribuição de conteúdo, web caching cooperativo, multicast, anycast, domain name system, e comunicador instantâneo. Redes distribuídas notáveis que usam DHT incluem o tracker distribuído do BitTorrent, a rede eDonkey, o botnet Storm, YaCy, e a Coral Content Distribution Network.

Histórico

A pesquisa em DHT foi originalmente motivada, em parte, pelos sistemas peer-to-peer como Napster, Gnutella e Freenet, os quais tiraram vantagem de recursos disponíveis na Internet para prover uma única aplicação útil. Em particular, eles tiravam vantagem da crescente capacidade de largura de banda e armazenamento em disco rígido para prover um serviço de compartilhamento de arquivos.

Esses sistemas se diferenciavam em como eles encontravam os dados que seus peers continham:

• O Napster mantinha um banco de dados central mapeando cada chave ao endereço do servidor que continha o arquivo. Durante o join, um novo nó enviava uma lista contendo os arquivos guardados localmente para o servidor. Dessa forma, o servidor recebia requisições dos clientes e as direcionava para os nodos que continham os resultados. Esse componente central deixava o sistema vulnerável a ataques e apresentava problemas de escalabilidade e elasticidade.
• Gnutella e redes similares usavam um modelo de requisições em [[inundação de mensagem|inundação (flooding)]. Essencialmente, cada busca resultava numa mensagem em broadcast para todo as outras máquinas. Apesar de evitar o ponto único de falha, esse método era significantemente menos eficiente que do Napster.
• Finalmente, o Freenet também era completamente distribuído. requisições eram enviadas de nó em nó até o objeto desejado ser encontrado. Arquivos similares tendiam a se acumular num conjunto similar de nós, logo as requisições roteavam pela rede para o conjunto de nós similares responsável sem a necessidade de visitar muitos deles. Devido ao anonimato dos servidores, não é garantido que um dado seria encontrado uma vez que nenhum servidor fica responsável por um arquivo em especial caso ele seja pouco popular na comunidade.

DHT usam um roteamento baseado em chave mais estruturado com a finalidade de conseguir tanto a descentralização do Gnutella e Freenet como a eficiência e garantia de resultados do Napster. Uma desvantagem é que, como o Freenet, DHTs suportavam diretamente buscas exatas somente ao invés de buscas por palavras-chave. Entretanto tal funcionalidade pode ser implementada sobre a DHT.

As primeiras quatro DHTs - CAN, Chord, Pastry e Tapestry - foram introduzidas quase simultaneamente em 2001. Desde então esta área de pesquisa tem estado bastante ativa. Fora da academia, a tecnologia DHT tem sido adotada como um componente do BitTorrent e na Coral Content Distribution Network.

Propriedades

Algumas propriedades enfatizadas são:

• Descentralização: não uma entidade de coordenação central.
• Escalabilidade: o sistema deve estar preparado para funcionar corretamente tanto com milhares de nós como para milhões de nós sem que haja uma queda na qualidade do serviço oferecido.
• Tolerância a falhas: a entrada, saída e falha de peers não deve abalar o sistema, mesmo que essas ocorram frequentemente.

Para prover essas características, uma técnica usada é fazer com que cada nó coordene apenas uma quantidade pequena de outros nós (tipicamente [[Grande-O|$\Theta (\log n)$]) quando comparada com a quantidade total na DHT. Dessa forma é necessário realizar somente uma quantidade limitada de trabalho para cada mudança. \cialmente compartilhamento de arquivos).

Finalmente, DHTs precisam lidar com questões mais tradicionais de sistemas distribuídos como balanceamento de carga, integridade de dados e desempenho (particularmente, assegurando que operações como roteamento e armazenamento e recuperação de dados completem rapidamente).

Estrutura

Há três coisas básicas a se considerar no projeto de uma DHT: o tipo da chave, um esquema de particionamento do espaço de chaves e uma rede superposta. Os requisitos principais de DHTs é que os dados possam ser endereçados por chaves numéricas únicas e que os valores sejam o dado em si (conteúdo de um arquivo, por exemplo) ou um apontador para o local onde o dado se encontra. De acordo com a faixa de valores numéricos da chave, será definido o espaço de chaves. Fundamentalmente tem-se um conjunto de cadeias de caracteres de 160 bits. Um esquema de particionamento do espaço de chaves divide a posse do espaço entre os nós participantes. Uma rede superposta então conecta os nós, permitindo a eles encontrar o dono de uma dada chave no espaço de chaves.

Operações Providas

Uma DHT precisa prover somente uma operação, o $lookup(k)$. Tal operação busca o nó responsável pela chave $k$. Para inserir um novo valor na DHT, realizar-se-ia o lookup e, uma vez com uma referência para o nó responsável, armazenar-se-ia a chave e o valor.

Considerando essa operação, um típico uso de DHT para armazenamento e recuperação procede da seguinte forma, supondo um espaço de chaves com cadeias de caracteres de 160 bits. Para armazenar um arquivo com um certo nome e conteúdo numa DHT:

1. encontra-se o hash SHA1 do nome do arquivo, produzindo a chave k de 160 bits;
2. envia-se uma mensagem $lookup(k)$ é enviada para qualquer nó participante da DHT;
3. a mensagem é encaminhada de nó em nó pela rede superposta até que chegue ao único nó responsável pela chave k de acordo com o particionamento do espaço de chaves;
4. uma vez com uma referência para o nó responsável, armazena-se o conteúdo do arquivo.

Qualquer outro cliente com interesse no arquivo armazenado procederia da seguinte forma:

1. de posse do nome do arquivo, ele calcularia o hash SHA1 do arquivo novamente, produzindo k;
2. enviaria uma mensagem de $lookup(k)$ para qualquer nó da DHT;
3. a mensagem seria encaminhada de modo similar ao caso anterior;
4. uma vez com uma referência para o nó responsável pela chave k, o conteúdo armazenado poderia ser pedido diretamente.

Exemplos

Protocolos e implementações de DHT

• CAN (Content Addressable Network)
• Chord
• Kademlia
• Pastry
• P-Grid
• Tapestry

Applicações usando DHTs

• BitTorrent: Distribuição de arquivos. BitTorrent usa opcionalmente uma DHT como um tracker distribuído para prover um ponto de encontro entre os clientes fazendo download de um arquivo particular (veja Comparação dos clientes de BitTorrent)
• The Circle: Compartilhamento de arquivos e chat
• Codeen: Web caching
• Coral Content Distribution Network: Rede de distribuição de conteúdo
• Dijjer: Rede de distribuição parecida com o Freenet
• eMule: Compartilhamento de arquivos
• FAROO: Mecanismo peer-to-peer de busca na web
• GNUnet: Rede de distribuição parecida com o Freenet com uma implementação de DHT [1]
• JXTA: Plataforma peer-to-peer de código aberto
• LimeWire: Compartilhamento de arquivos; contendo Mojito DHT
• NEOnet: Compartilhamento de arquivos
• Overnet: Compartilhamento de arquivos
• Warez P2P: Compartilhamento de arquivos
• YaCy: Mecanismo distribuído de busca na web