Saltar para o conteúdo

Distributed hash table

Origem: Wikipédia, a enciclopédia livre.

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

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.

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|]) 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).

Operações Providas

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.

Exemplos

Protocolos e implementações de DHT

Applicações usando DHTs

Obtida de "https://pt.wikipedia.org/w/index.php?title=Distributed_hash_table&oldid=14638559"