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.
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:
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.
Algumas propriedades enfatizadas são:
Para prover essas características, uma técnica usada é fazer com que cada nó coordene apenas uma quantidade pequena de outros nós (tipicamente ) 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).
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.
Uma DHT precisa prover somente uma operação, o . Tal operação busca o nó responsável pela chave . 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:
Qualquer outro cliente com interesse no arquivo armazenado procederia da seguinte forma:
A maioria das DHTs usam algum variante de hash consistente para mapear chaves para os nós. Essa técnica emprega uma função a qual define uma noção abstrata de distância entre as chaves e 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 é dono de todas as chaves para as quais é o ID mais próximo, medido de acordo com .
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).
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 , o nó ou é dono da chave ou tem um link para um nó perto de 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 usando o seguinte algoritmo guloso: em cada passo, encaminhe a mensagem para o vizinho cujo ID seja o mais próximo de . Quando não houver tal vizinho, chegou-se ao nó mais próximo, o qual é o dono da chave 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 como o número de nós na DHT e usando notação Grande-O, são:
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 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.
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. Estes algoritmos são usados por aplicações para fazer multicast superposto, busca por faixa ou coletar estatísticas.
As implementações de DHT diferem, entre outras coisas, na estrutura de dados que usam para prover lookups em . 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 .
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.
Entre as diferenças mais notáveis nas DHT no mundo real estão as seguintes:
This article uses material from the Wikipedia Português article Distributed hash table, which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0"); additional terms may apply (view authors). Conteúdo disponibilizado nos termos da CC BY-SA 4.0, salvo indicação em contrário. Images, videos and audio are available under their respective licenses.
®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki Português (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.