Tabela de hash distribuída

Tabelas de hash distribuídas ( também conhecidas como DHTs ) são uma classe de sistemas distribuídos descentralizados que dividem a associação de um conjunto de chaves entre os nós participantes e podem encaminhar mensagens com eficiência para o único proprietário de uma chave específica. Cada nó é o análogo de um slot de matriz em uma tabela de hash.

Normalmente, os DHTs são projetados para gerenciar um grande número de nós, mesmo nos casos em que há entradas contínuas ou falhas repentinas de alguns deles. Esse tipo de infraestrutura pode ser usado para implementar serviços mais complexos, como sistemas de arquivos distribuídos , sistemas de compartilhamento de arquivos ponto a ponto , cache cooperativo da Web , multicast , anycast e serviços de nome de domínio .

História

Originalmente, a pesquisa DHT foi parcialmente motivada por sistemas peer-to-peer, como Napster , Gnutella , Freenet , que dependiam ou dependem de recursos distribuídos na Internet para fornecer o aplicativo desejado. Em particular, esses sistemas aproveitaram o aumento da largura de banda e o aumento do espaço no disco rígido para fornecer um sistema de compartilhamento de arquivos.

Esses sistemas diferiam entre si na forma como encontraram os dados contidos por seus respectivos pares. O Napster tinha um índice em um servidor centralizado: cada nó, em sua entrada, enviava uma lista dos arquivos que possuía localmente ao servidor, que realizaria as buscas e indicaria aos solicitantes os nós que guardavam os dados desejados. Esse componente centralizado tornou o sistema vulnerável a ataques. Gnutella e redes similares avançaram para um modelo de inundação; em essência, cada busca era de fato constituída em uma mensagem que era transmitida a todas as outras máquinas da rede. Embora esse método evitasse a possibilidade de um único ponto de ruptura, o mecanismo era muito menos eficiente que o Napster. Finalmente, havia o Freenet, que fornecia um mecanismo totalmente distribuído, mas empregando endereçamento heurístico baseado em chave em que cada arquivo era associado a uma chave, e arquivos com chaves semelhantes tendiam a agrupar-se em conjuntos de nós semelhantes. Portanto, era provável que as solicitações fossem encaminhadas pela rede para esses conjuntos de nós sem ter que visitar muitos pares. No entanto, a Freenet não ofereceu a certeza de encontrar os dados necessários.

As tabelas de hash distribuídas usam um tipo mais estruturado de roteamento baseado em chaves para alcançar tanto a descentralização do Gnutella e do Freenet, quanto a eficiência e confiabilidade nas buscas oferecidas pelo Napster. Uma desvantagem é que, como no Freenet, os DHTs oferecem busca apenas por títulos exatos e não por palavras-chave, embora esse tipo de funcionalidade possa ser colocado em uma camada superior do DHT.

Os primeiros quatro DHTs - CAN , Acorde , Pastelaria e Tapeçaria - foram todos apresentados ao mesmo tempo, em 2001 . Desde então, essa área de pesquisa tem sido bastante ativa. Além dos estudos acadêmicos, a tecnologia DHT foi adotada como componente do BitTorrent , eMule e na Coral Content Distribution Network .

Propriedades

As características do DHT enfatizam as seguintes propriedades:

• Descentralização : os nós formam coletivamente o sistema sem qualquer coordenação central.
• Escalabilidade : o sistema foi projetado para operação eficiente mesmo com centenas de milhões de nós.
• Tolerância a falhas : o sistema deve ser confiável mesmo na presença de nós que entram, saem da rede ou estão sujeitos a mau funcionamento com alta frequência.

A principal técnica utilizada para atingir esses objetivos é constituída pelo fato de que cada nó precisa permanecer em contato com apenas um pequeno número de outros nós da rede - geralmente ... dos outros n participantes (veja abaixo) - dessa forma a rede está sujeita a uma quantidade mínima de trabalho para cada mudança que ocorre no conjunto de nós que a constituem.

Algumas instalações de DHT tentam implementar mecanismos de segurança para impedir nós participantes maliciosos e permitir que os nós permaneçam anônimos, embora isso seja menos comum do que outros sistemas peer-to-peer (especialmente quando se trata de compartilhamento de arquivos).

Estrutura

Um DHT é construído em torno de um keyspace abstrato , como um conjunto de strings de 160 bits . A associação do keyspace é dividida entre os nós participantes de acordo com um esquema de particionamento bem definido. A rede de sobreposição conecta os nós, permitindo que eles encontrem o proprietário de uma determinada chave no keyspace.

Com essas posições, a operação típica de um DHT para armazenar e depois recuperar um dado pode acontecer da seguinte maneira. Suponha que o keyspace seja um conjunto de strings de 160 bits. Para armazenar um arquivo caracterizado pelo nome do arquivo e parâmetros de dados no DHT, o hash SHA1 do nome do arquivo é calculado primeiro , produzindo assim uma chave k de 160 bits . Depois disso, uma mensagem put (k, data) pode ser enviada para qualquer nó na rede DHT. A mensagem é encaminhada de nó para nó através da rede overlay até chegar ao único nó que é responsável pela chave k de acordo com as regras de particionamento de keyspace, onde o par (k, dados) é armazenado. Qualquer outro cliente pode então recuperar o conteúdo do arquivo calculando por sua vez o hash do nome do arquivo para obter k e pedir a qualquer nó na rede DHT para encontrar os dados associados a k por meio de uma mensagem get (k) . A mensagem será então encaminhada através do overlay para o nó responsável por k , que responderá com uma cópia dos dados armazenados.

Cada um desses componentes é descrito abaixo para estabelecer os princípios básicos comuns à maioria dos DHTs; alguns mecanismos podem diferir em detalhes.

Particionamento de keyspace

Muitos DHTs usam alguma variante de hash consistente para mapear chaves para nós. Essa técnica emprega uma função que define a noção abstrata de distância entre a chave e a chave . A cada nó é atribuída uma chave que é chamada de identificador (ID). Todas as chaves para as quais i é o ID mais próximo pertencem a um nó com ID i , medido por . $\ delta (k_ {1}, k_ {2})$$k_1$$k_2$$\delta$

Exemplo . O algoritmo Chord considera as teclas como pontos em um círculo, e é a distância percorrida (sentido horário) no círculo entre e . Portanto, o keyspace circular é dividido em segmentos contíguos cujos terminais são os identificadores de nó. Se e são dois IDs adjacentes, então o nó com ID possui todas as chaves que estão entre e . $\ delta (k_ {1}, k_ {2})$$k_1$$k_2$$eu_ {1}$$eu_ {2}$$eu_ {2}$$eu_ {1}$$eu_ {2}$

O hash consistente tem a característica fundamental de que a remoção ou adição de um nó modifica apenas o conjunto de chaves pertencentes aos nós com IDs adjacentes, sem envolver todos os outros nós. Isso é diferente de uma tabela de hash tradicional , na qual a adição ou remoção de um bucket causa um remapeamento de quase todo o keyspace. Uma vez que cada mudança no conjunto de chaves pelo qual um nó é responsável normalmente corresponde a um intenso (em termos de largura de banda) movimento nó a nó de objetos armazenados no DHT, uma minimização desses movimentos de reorganização é necessária para lidar com eficiência com pares que têm um comportamento muito dinâmico (grande número de entradas, saídas ou mau funcionamento).

Rede de sobreposição

Cada nó mantém um conjunto de links para os outros nós (seus vizinhos ). Juntos, esses nós formam a rede overlay, e são organizados de forma estruturada, dando forma à topologia da rede .

Todas as topologias DPT compartilham alguma variante da propriedade mais essencial: para cada chave k , ou o nó possui k ou tem um link para um nó mais próximo de k em termos de distância no keyspace, conforme definido acima. Nesse ponto, é fácil encaminhar uma mensagem para o proprietário de qualquer chave k usando o seguinte algoritmo guloso : em cada etapa subsequente, ele encaminha a mensagem para o vizinho cujo ID está mais próximo de k . Quando não há vizinho com essas características, então chegamos ao nó realmente mais próximo, que deve ser o dono de k conforme definido acima. Esse tipo de roteamento às vezes é chamado de roteamento baseado em chave .

Além da correção subjacente desse tipo de roteamento, existem duas restrições principais na topologia para que o número máximo de etapas sucessivas em qualquer caminho (atraso) seja baixo, para que a solicitação seja atendida rapidamente e que o número máximo de vizinhos de cada nó (o grau do nó) é baixo, a fim de manter a sobrecarga de manutenção baixa. Há um trade-off entre esses dois critérios que é fundamental na teoria dos grafos . Algumas escolhas comuns são mostradas abaixo, onde n é o número de nós no DHT:

• Graduação , extensão$O(1)$$O (\ log n)$
• Graduação , extensão$O (\ log n)$$O(\log n/\log\log n)$
• Graduação , extensão$O (\ log n)$$O (\ log n)$
• Graduação , extensão$O (n ^ {{1/2}})$$O(1)$

A terceira escolha é a mais comum, embora não seja a melhor em termos de trade-off grau/atraso, pois esta topologia normalmente permite maior flexibilidade em termos de escolha de vizinhos. Isso é útil, por exemplo, para escolher vizinhos compatíveis com a topologia e ao mesmo tempo semelhantes em termos de latência na rede física subjacente.

Além dos algoritmos de roteamento, existem vários algoritmos que exploram a estrutura da rede overlay de um DHT para enviar uma mensagem a todos os nós, ou a um subconjunto dos nós, do próprio DHT . Esses algoritmos são usados ​​por aplicativos para realizar operações multicast na sobreposição, para realizar consultas de intervalo ou para coletar estatísticas. Dois sistemas baseados nesta abordagem são Structella , que implementa inundação e passeio aleatório na sobreposição de uma rede Pastry, e DQ-DHT, que implementa um algoritmo de consulta dinâmica em uma rede Chord .

Exemplos

Protocolos e implementações DHT

• Acorde
• Kademlia
• ( PT ) Bamboo , em bamboo-dht.org .
• ( PT ) Bunshin , em planet.urv.es .
• ( PT ) CAN (Content Addressable Network)
• ( PT ) Sistema DKS , em dks.sics.se. Recuperado em 8 de maio de 2019 (arquivado do original em 20 de janeiro de 2012) .
• ( PT ) Implementação do JGroups DHT , em jgroups.org .
• Pastelaria , em freepastry.org . _ _
• ( PT ) Tapeçaria e nova implementação chamada Quimera.

Aplicações que empregam DHTs

• BitTorrent : distribuição de arquivos. O BitTorrent opcionalmente usa um DHT como um rastreador distribuído para oferecer um encontro entre clientes que estão baixando um arquivo específico.
• Rede de Distribuição de Conteúdo Coral
• eMule : Compartilhamento de arquivos.
• NEOnet : Compartilhamento de arquivos.
• Overnet : Compartilhamento de arquivos.
• Transmissão : Cliente Bittorent de código aberto .

Artigos

• ( EN ) Hari Balakrishnan, M. Frans Kaashoek, David Karger, Robert Morris e Ion Stoica. Pesquisa de dados em sistemas P2P . Em Comunicações da ACM, fevereiro de 2003.
• ( PT ) Gurmeet Singh Manku. Dipsea: Uma Tabela de Hash Distribuída Modular . Tese de doutorado (Universidade de Stanford), agosto de 2004.
• ( PT ) Moni Naor e Udi Wieder. Novas Arquiteturas para Aplicações P2P: a Abordagem Contínua-Discreta . Proc. SPAA, 2003.

Links externos

• DHT no Torrent Wiki , em torrent.culturaliberap2p.it . Recuperado em 27 de julho de 2010 (arquivado do original em 24 de agosto de 2010) .
• ( PT ) Tabelas de Hash Distribuídas, Parte 1 por Brandon Wiley.
• ( PT ) Distributed Hash Tables liga a página de Carles Pairot sobre pesquisa de DHT e P2P.
• ( PT ) Sloppy Hashing and Self-Organizing Clusters : publicações do projeto Coral Content Distribution Network .
• ( PT ) Projeto IRIS (Infraestrutura para Sistemas de Internet Resilientes)
• ( PT ) Várias publicações DHT Página de El-Ansary sobre pesquisa em DHT.