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ídos, 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 (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 há 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 $\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.

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:

encontra-se o hash SHA1 do nome do arquivo, produzindo a chave k de 160 bits;
envia-se uma mensagem $lookup(k)$ é enviada para qualquer nó participante da DHT;
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;
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:

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

Particionamento do espaço de chaves

A maioria das DHTs usam algum variante de hash consistente para mapear chaves para os nós. Essa técnica emprega uma função $\delta (k_{1},k_{2})$ a qual define uma noção abstrata de distância entre as chaves $k_{1}$ e $k_{2}$ e que não está relacionada a distância geográfica ou latência da rede. A cada nó possui uma chave chamada identificador (ID). Um nó com um ID $i$ é dono de todas as chaves para as quais $i$ é o ID mais próximo, medido de acordo com $\delta$ .

A noção de função de distância ataca dois problemas: mapear chaves de modo a balancear a carga entre os nós e redirecionar um lookup por uma chave para um peer mais próximo do peer responsável. Vários esquemas diferentes são empregados como, por exemplo, o Chord que usa a diferença matemática entre as chaves; o Pastry e o Tapestry usam o o número de bits em comum nas duas chaves e, por fim, o Kademlia que usa OU exclusivo (XOR) da lógica binária.

Hashs consistentes têm a propriedade essencial de modificar somente os nós com IDs adjacentes na ocorrência de adição ou remoção de um nó, não afetando nenhum dos nós restantes no sistema, em oposição a uma tabela hash tradicional na qual uma adição ou remoção de um bucket implica remapear quase todo o espaço de chaves. Dado o fato de que qualquer mudança na posse de chaves tipicamente corresponde a uma operação bandwidth-intensive de objetos armazenados na DHT de um nó para outro, minimizar essa reorganização é necessário para suportar eficientemente altas taxas de entrada e saída de nós (churn).

Rede superposta

Cada nó mantem um conjunto de links para outros nós (seus vizinhos ou sua tabela de roteamento). Juntos, esses links formam uma rede superposta. Um nó escolhe seu vizinho de acordo com a topologia de rede.

Todas as topologias de DHT possuem uma variante da seguinte propriedade: para cada chave $k$ , o nó ou é dono da chave $k$ ou tem um link para um nó perto de $k$ em termos de distância do espaço de chaves definido acima. Dessa forma, é fácil rotear uma mensagem para o dono de qualquer chave $k$ usando o seguinte algoritmo guloso: em cada passo, encaminhe a mensagem para o vizinho cujo ID seja o mais próximo de $k$ . Quando não houver tal vizinho, chegou-se ao nó mais próximo, o qual é o dono da chave $k$ como definido mais acima. Este estilo de roteamento é chamado de roteamento baseado em chave.

Além da corretude do roteamento básico, duas outras importantes restrições são: garantir que o número máximo de saltos em cada roteamento é baixo, de forma que requisições completem rapidamente; e que o número máximo de vizinhos em qualquer nó ([grau (teoria dos grafos)|grau] máximo de um nó) é baixo, tal que o custo de manutenção não seja alto. Naturalmente, ter rotas menores implica maiores graus máximos. Escolhas comuns para o grau máximo e comprimento da rota, considerando $n$ como o número de nós na DHT e usando notação Grande-O, são:

Grau $O(1)$ , rota de comprimento $O(\log n)$
Grau $O(\log n)$ , rota de comprimento $O(\log n/\log \log n)$
Grau $O(\log n)$ , rota de comprimento $O(\log n)$
Grau $O(n^{1/2})$ , rota de comprimento $O(1)$

A terceira escolha é a mais comum, apesar de que não é ótima em termos do dilema grau/comprimento da rota, uma vez que tais topologias tipicamente permitem mais flexibilidade na escolha de vizinhos. Muitas DHTs usam essa flexibilidade para escolher vizinhos mais próximos em termos de latência na rede física.

O comprimento máximo da rota está intimamente ligado ao diâmetro da rede: o número máximo de saltos em qualquer dos caminhos mais curtos entre dois nós. Como o comprimento das rotas na rede é no mínimo o diâmetro, DHTs são limitadas pelo dilema grau/comprimento da rota ^[1] o que é fundamental na teoria dos grafos. O tamanho da rota pode ser maior que o diâmetro dado que o algoritmo guloso pode não encontrar algum dos caminhos mais curtos.^[2]

Algoritmos para redes superpostas

Além do roteamento, existem muitos outros algoritmos que exploram a estrutura das redes superpostas para enviar mensagens para todos os nós, ou um subconjunto deles, numa DHT.^[3] Estes algoritmos são usados por aplicações para fazer multicast superposto, busca por faixa ou coletar estatísticas.

Roteamento em uma dimensão

As implementações de DHT diferem, entre outras coisas, na estrutura de dados que usam para prover lookups em $O(\log n)$ . O Chord, por exemplo, usa uma estrutura similar a uma skiplist. Referências para alguns dos nós são mantidas tal que um nó está na metade da distância, outro a um quarto, e assim por diante seguindo as potências de 2. Dessa forma o nó que recebe uma requisição, a repassa para o nó com ID mais alto e menor que a chave. Um novo nó entra no sistema fazendo um lookup de seu ID (pode ser escolhido aleatoriamente no espaço de chaves), ao encontrar o nó responsável pelo seu ID, atualiza o sucessor dele e o predecessor do antigo sucessor dele para apontarem para o novo nó. Dessa forma o nó passa a fazer parte da rede. De maneira diferente, Kademlia, Pastry e Tapestry usam uma estrutura parecida de trie. Viceroy, outra implementação de DHT, usa uma estrutura de borboleta. Uma variação recente do Chord usa grados de ''de Bruijn'', que requer somente que cada nó conheça outros dois, porém continua mantendo o lookup em $O(\log n)$ .

Roteamento em múltiplas dimensões

Por outro lado, o CAN, por exemplo, usa um espaço cartesiano d-dimensional. O espaço é particionado em hiper-retângulos chamados de zona e cada nó fica responsável pelas chaves pertencentes a uma zona. Quanto a tabela de roteamento, cada nó possui referências para os seus vizinhos no plano cartesiano. Para um novo nó fazer parte da DHT, ele escolhe aleatoriamente um ponto no espaço e usa o lookup para saber qual o nó responsável por ele, eles particionam a zona e o nó se anuncia para que os vizinhos atualizem suas tabelas de roteamento.

DHTs no mundo real e suas diferenças e melhorias sobre o modelo básico

Entre as diferenças mais notáveis nas DHT no mundo real estão as seguintes:

O espaço de endereços é um parâmetro da DHT. Algumas DHTs usam um espaço de chaves de 128 bits ou 160 bits.
Algumas DHTs usam outras funções hash que não SHA1.
No mundo real a chave $k$ pode ser um hash do conteúdo do arquivo ao invés do nome do arquivo, de modo que renomear o arquivo não o impeça de ser encontrado.
Algumas DHTs podem também publicar objetos de diferentes tipos. Por exemplo, chaves $k$ podem ser o $ID$ do nó e informações adicionais podem descrever como entrar em contato com esse nó. Isso permite publicação de informações de presença, muito usadas por aplicações de comunicador instantâneo, por exemplo.
Uma chave $k$ pode ser armazenada em mais de um nó correspondente a essa chave para aumentar a confiabilidade em termos de redundância. Normalmente, ao invés de selecionar somente um nó, algoritmos de DHTs selecionam $i$ nós adequados, onde $i$ é um parâmetro específico da implementação considerada. Em tais projetos de DHT, nós concordam em como manipular uma certa faixa do espaço de chaves, o que muitas vezes é escolhido dinamicamente, ao invés de hard-coded.

Problemas

Tolerância a falhas é previsto apenas para casos singulares.
Poucas implementações levam em conta a proximidade entre os nós para determinar a tabela de roteamento.
Nós maliciosos podem inserir falhas no roteamento.
Caso não exista um mecanismo de autenticação, por exemplo, ataques Sybil podem aumentar bastante a latência da rede fazendo com que os nós maliciosos fiquem se juntando e saindo da rede numa frequência muito alta tal que a DHT execute mais operações com a manutenção da topologia do que com sua finalidade original.
As buscas são do tipo chave-valor exatas. Buscas por faixa de valores podem ser construídas sob a DHT, mas não com um desempenho ótimo.

Exemplos

Protocolos e implementações de DHT

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

Aplicaçõ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.
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

Referências

↑ «The (Degree,Diameter) Problem for Graphs». Consultado em 20 de março de 2009. Arquivado do original em 17 de fevereiro de 2012
↑ Gurmeet Singh Manku, Moni Naor, and Udi Wieder. Know thy Neighbor's Neighbor: the Power of Lookahead in Randomized P2P Networks. Proc. STOC, 2004.
↑ Ali Ghodsi. Distributed k-ary System: Algorithms for Distributed Hash Tables Arquivado em 22 de maio de 2007, no Wayback Machine.. KTH-Royal Institute of Technology, 2006.

Referências gerais

Balakrishnan, Hari and Kaashoek, Frans M. and Karger, David and Morris, Robert and Stoica, Ion (2003). «Looking up data in P2P systems». Communications of the ACM. 46 (7): 43–48. doi:10.1145/606272.606299

[1] «The (Degree,Diameter) Problem for Graphs». Consultado em 20 de março de 2009. Arquivado do original em 17 de fevereiro de 2012

[2] Gurmeet Singh Manku, Moni Naor, and Udi Wieder. Know thy Neighbor's Neighbor: the Power of Lookahead in Randomized P2P Networks. Proc. STOC, 2004.

[3] Ali Ghodsi. Distributed k-ary System: Algorithms for Distributed Hash Tables Arquivado em 22 de maio de 2007, no Wayback Machine.. KTH-Royal Institute of Technology, 2006.

[1]

[2]

[3]