Tabela de hash distribuída

a tabela de hash distribuída ( dht ) é um sistema distribuído que fornece um serviço de pesquisa semelhante a uma tabela de hash. Os pares -chave -valor são armazenados em um DHT, e qualquer nó participante pode recuperar com eficiência o valor associado a uma determinada chave. A principal vantagem de um DHT é que os nós podem ser adicionados ou removidos com o mínimo de trabalho em torno das teclas de distribuição. As chaves são identificadores exclusivos que mapeiam para valores específicos , que por sua vez podem ser qualquer coisa, desde endereços, documentos, dados arbitrários. A responsabilidade de manter o mapeamento de chaves para valores é distribuída entre os nós, de tal maneira que uma mudança no conjunto de participantes causa uma quantidade mínima de interrupção. Isso permite que um DHT seja dimensionado para um número extremamente grande de nós e lidar com chegadas contínuas, partidas e falhas.

DHTs formam uma infraestrutura que pode ser usada para criar serviços mais complexos, como Anycast, cache cooperativo da Web, sistemas de arquivos distribuídos, serviços de nomes de domínio, mensagens instantâneas, multicast e também compartilhamento de arquivos ponto a ponto e distribuição de conteúdo sistemas. Redes distribuídas notáveis que usam DHTs incluem o rastreador distribuído da BitTorrent, a rede KAD, a botnet da tempestade, o Tox Instant Messenger, o Freenet, o mecanismo de pesquisa de Yacy e o sistema de arquivos interplanetários.

A pesquisa DHT foi originalmente motivada, em parte, por sistemas ponto a ponto (P2P) como Freenet, Gnutella, Bittorrent e Napster, que aproveitaram os recursos distribuídos pela Internet para fornecer um único aplicativo útil. Em particular, eles aproveitaram o aumento da largura de banda e da capacidade do disco rígido para fornecer um serviço de compartilhamento de arquivos.

Esses sistemas diferiram na maneira como localizaram os dados oferecidos por seus pares. O Napster, o primeiro sistema de entrega de conteúdo P2P em larga escala, exigia um servidor de índice central: cada nó, ao ingressar, enviaria uma lista de arquivos de retenção localmente para o servidor, que executariam pesquisas e refeririam as consultas aos nós que mantinham o Resultados. Esse componente central deixou o sistema vulnerável a ataques e ações judiciais.

Gnutella e redes semelhantes foram transferidas para um modelo de inundação de consulta - em essência, cada pesquisa resultaria em uma mensagem transmitida para todas as máquinas da rede. Enquanto evitava um único ponto de falha, esse método foi significativamente menos eficiente que o Napster. As versões posteriores dos clientes da Gnutella mudaram para um modelo de consulta dinâmica que melhorou bastante a eficiência.

O Freenet é totalmente distribuído, mas emprega um roteamento heurístico baseado em chave no qual cada arquivo está associado a uma chave, e arquivos com teclas semelhantes tendem a se agrupar em um conjunto semelhante de nós. As consultas provavelmente serão encaminhadas pela rede para esse cluster sem precisar visitar muitos colegas. No entanto, o Freenet não garante que os dados sejam encontrados.

As tabelas de hash distribuídas usam um roteamento mais estruturado baseado em chaves para atingir a descentralização de Freenet e Gnutella e a eficiência e os resultados garantidos do Napster. Uma desvantagem é que, como o Freenet, o DHTS suporta diretamente a pesquisa de correspondência exata, em vez da pesquisa de palavras-chave, embora o algoritmo de roteamento de Freenet possa ser generalizado para qualquer tipo de chave em que uma operação de proximidade possa ser definida.

Em 2001, quatro sistemas - podem, acorde, pastelaria e tapeçaria - relacionaram o DHTS como um tópico de pesquisa popular. Um projeto chamado infraestrutura para sistemas resilientes à Internet (IRIS) foi financiado por uma doação de US $ 12 milhões da Fundação Nacional de Ciências dos Estados Unidos em 2002. Os pesquisadores incluíram Sylvia Ratnasamy, Ion Stoica, Hari Balakrishnan e Scott Shenker. Fora da academia, a tecnologia DHT foi adotada como um componente do BitTorrent e em projetos do planetLab, como a rede de distribuição de conteúdo de corais.

DHTS enfatiza caracteristicamente as seguintes propriedades:

• Autonomia e descentralização: Os nós formam coletivamente o sistema sem qualquer coordenação central.
• Tolerância de falhas: O sistema deve ser confiável (em algum sentido) mesmo com nós ingressando continuamente, saindo e falhando.
• Escalabilidade: O sistema deve funcionar de forma eficiente, mesmo com milhares ou milhões de nós.

Uma técnica-chave usada para atingir esses objetivos é que qualquer nó precisa coordenar com apenas alguns outros nós no sistema < /span>-Mais comumente, o (log n ) dos participantes n (veja abaixo) - para que apenas uma quantidade limitada de trabalho precisa ser feita para cada alteração na associação.

Alguns projetos de DHT procuram ser seguros contra participantes maliciosos e permitir que os participantes permaneçam anônimos, embora isso seja menos comum do que em muitos outros sistemas ponto a ponto (especialmente o compartilhamento de arquivos); Veja P2P anônimo.

A estrutura de um DHT pode ser decomposta em vários componentes principais. A fundação é um espaço abstrato, como o conjunto de cordas de 160 bits. Um esquema de particionamento de chaves divide a propriedade desse espaço de chave entre os nós participantes. Uma rede de sobreposição conecta os nós, permitindo que eles encontrem o proprietário de qualquer chave no espaço de chave.

Depois que esses componentes estão em vigor, um uso típico do DHT para armazenamento e recuperação pode prosseguir da seguinte maneira. Suponha que o espaço de chave seja o conjunto de cordas de 160 bits. Para indexar um arquivo com dado nome do arquivo e dados no dht, O hash sha-1 de nome do arquivo é gerado, produzindo uma chave de 160 bits k e uma mensagem put ( k, dados ) é enviado a qualquer nó que participe do DHT. A mensagem é encaminhada do nó para o nó através da rede de sobreposição até atingir o nó único responsável pelo chave k , conforme especificado pelo espaço de chaves partição. Esse nó então armazena a chave e os dados. Qualquer outro cliente pode recuperar o conteúdo do arquivo por novamente hashing nome do arquivo para produzir k e pedindo a qualquer nó DHT para encontrar os dados associados a k com uma mensagem get ( k ) . A mensagem será novamente roteada através da sobreposição para o nó responsável por k , que responderá com o armazenado dados .

Os componentes de particionamento de chaves e sobreposição são descritos abaixo com o objetivo de capturar as principais idéias comuns à maioria dos DHTs; Muitos designs diferem nos detalhes.

A maioria dos DHTs usa alguma variante de hash consistente ou hastes de renda para mapear as teclas para nós. Os dois algoritmos parecem ter sido elaborados de forma independente e simultaneamente para resolver o problema da tabela de hash distribuídos.

Tanto o hash consistente quanto o hash de renda têm a propriedade essencial de que a remoção ou a adição de um nó altera apenas o conjunto de chaves pertencentes aos nós com IDs adjacentes e deixa todos os outros nós não afetados. Contraste isso com uma tabela de hash tradicional na qual a adição ou remoção de um balde faz com que quase todo o espaço de chave seja remapeado. Como qualquer alteração na propriedade normalmente corresponde ao movimento intensivo em largura de banda de objetos armazenados no DHT de um nó para outro, é necessário minimizar essa reorganização para suportar com eficiência altas taxas de rotatividade (chegada e falha do nó).

A hashing consistente emprega uma função $(k_{1},k_{2})}$ que define uma noção abstrata da distância entre as chaves $Não. k_{1}}$ e $Não. k_{2}}$, que não está relacionado com a distância geográfica ou latência de rede. Cada nó é atribuído uma única chave chamada sua identificador (ID). Um nó com identificação ${\displaystyle i_{x}}$ possui todas as chaves $Não. k_{m}}$ para os quais ${\displaystyle i_{x}}$ é o ID mais próximo, medido de acordo com $(k_{m},i_{x})}$.

Por exemplo, o Chord DHT usa hashing consistente, que trata nós como pontos em um círculo, e $(k_{1},k_{2})}$ é a distância que viaja no sentido horário ao redor do círculo de $Não. k_{1}}$ para $Não. k_{2}}$. Assim, o espaço-chave circular é dividido em segmentos contíguos cujos pontos finais são os identificadores de nó. Se $Não. i_{1}}$ e $Não. i_{2}}$ são duas IDs adjacentes, com uma distância no sentido horário mais curta $Não. i_{1}}$ para $Não. i_{2}}$, então o nó com ID $Não. i_{2}}$ possui todas as chaves que caem entre $Não. i_{1}}$ e $Não. i_{2}}$.

Em hashing de encontro, também chamado de maior peso aleatório (HRW) hashing, todos os clientes usam a mesma função hash $(em inglês)}$ (escolhido antes do tempo) para associar uma chave a um dos n servidores disponíveis. Cada cliente tem a mesma lista de identificadores (S₁, S₂, S_n ?, um para cada servidor. Dada uma chave k, um cliente computa n pesos de hash O quê?₁ = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = h(S₁, k), O quê?₂ = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = h(S₂, k),..., O quê?_n = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = h(S_n, k). O cliente associa essa chave com o servidor correspondente ao mais alto peso hash para essa chave. Um servidor com ID ${\displaystyle S_{x}}$ possui todas as chaves $Não. k_{m}}$ para o qual o peso de hash $(S_{x},k_{m})}$ é maior do que o peso hash de qualquer outro nó para essa chave.

O hash de preservação da localidade garante que chaves semelhantes sejam atribuídas a objetos semelhantes. Isso pode permitir uma execução mais eficiente das consultas de alcance; no entanto, em contraste com o uso de hash consistente, não há mais garantia de que as chaves (e, portanto, a carga) sejam uniformemente distribuídas aleatoriamente sobre o espaço chave e os pares participantes. Os protocolos DHT, como autoconfiança e o Oscar, abordam esses problemas. A autocontrante decompa as teclas de objeto de IDs de pares e teclas de classificação ao longo do anel com uma abordagem estatística baseada no paradigma de inteligência do enxame. A classificação garante que as teclas semelhantes sejam armazenadas pelos nós vizinhos e que os procedimentos de descoberta, incluindo consultas de alcance, possam ser realizados no tempo logarítmico. O Oscar constrói uma rede de mundo pequeno navegável com base na amostragem aleatória de caminhada, também garantindo tempo de pesquisa logarítmica.

Cada nó mantém um conjunto de links para outros nós (seus vizinhos ou tabela de roteamento). Juntos, esses links formam a rede de sobreposição. Um nó escolhe seus vizinhos de acordo com uma certa estrutura, chamada de topologia da rede.

Todas as topologias de DHT compartilham alguma variante da propriedade mais essencial: para qualquer chave k , cada nó tem um idi do nó Isso possui k ou tem um link para um nó cujo nó ID está mais próximo de k , em termos da distância da chave definida acima. É então fácil rotear uma mensagem para o proprietário de qualquer chave k usando o seguinte algoritmo ganancioso (que não é necessariamente globalmente ideal ): Em cada etapa, encaminhe a mensagem para o vizinho cujo ID é mais próximo de k . Quando não existe um vizinho, devemos ter chegado ao nó mais próximo, que é o proprietário de k , conforme definido acima. Às vezes, esse estilo de roteamento é chamado de roteamento baseado em chaves.

Além da correção básica de roteamento, duas restrições importantes na topologia são garantir que o número máximo de saltos em qualquer rota (comprimento da rota) seja baixo, para que os pedidos sejam concluídos rapidamente; e que o número máximo de vizinhos de qualquer nó (grau de nó máximo) é baixo, de modo que a sobrecarga de manutenção não é excessiva. Obviamente, ter rotas mais curtas requer maior grau máximo. Algumas opções comuns para o máximo grau e o comprimento da rota são as seguintes, onde n é o número de nós no DHT, usando o Big O notação:

Max. grau	Comprimento máximo da rota	Usado em	Nota
$Não.$	$(n)}$		Maiores comprimentos de pesquisa, com provavelmente muito mais lento vezes de pesquisa
$Não.$	$O(\log n)}$	Koorde (com grau constante)	Mais complexo para implementar, mas o tempo de pesquisa aceitável pode ser encontrado com um número fixo de conexões
$O(\log n)}$	$O(\log n)}$	Choro. Kademlia Pasta Tapeçaria	O mais comum, mas não ideal (grau / comprimento de rota). Chord é a versão mais básica, com Kademlia parecendo a variante mais popular otimizada (deve ter melhorado a pesquisa média)
$O(\log n)}$	${\displaystyle O(\log n/\log(\log n)}$	Koorde (com ótima aparência)	Mais complexo para implementar, mas os lookups podem ser mais rápidos (ter um pior caso limitado)
$O({\sqrt {n}})}$	$Não.$		A pior necessidade de armazenamento local, com muita comunicação após qualquer nó conecta ou desliga

A escolha mais comum, $O(\log n)}$ comprimento do curso/grau, não é ideal em termos de grau/rote tradeoff comprimento, mas tais topologias normalmente permitem mais flexibilidade na escolha dos vizinhos. Muitos DHTs usam essa flexibilidade para escolher vizinhos que estão próximos em termos de latência na rede física subjacente. Em geral, todos os DHTs constroem topologias de rede de pequeno mundo navegáveis, que negociam o comprimento da rota vs. grau de rede.

O comprimento máximo da rota está intimamente relacionado ao diâmetro: o número máximo de saltos em qualquer caminho mais curto entre nós. Claramente, o pior da rede da rede é pelo menos tão grande quanto seu diâmetro; portanto, os DHTs são limitados pela troca de grau/diâmetro que é fundamental na teoria dos gráficos. O comprimento da rota pode ser maior que o diâmetro, pois o algoritmo de roteamento ganancioso pode não encontrar caminhos mais curtos.

Além do roteamento, existem muitos algoritmos que exploram a estrutura da rede de sobreposição para enviar uma mensagem a todos os nós ou um subconjunto de nós, em um DHT. Esses algoritmos são usados por aplicativos para sobrepor multicast, consultas de alcance ou para coletar estatísticas. Dois sistemas baseados nessa abordagem são Structella, que implementa inundações e caminhadas aleatórias em uma sobreposição de massa e DQ-DHT, que implementa um algoritmo de pesquisa dinâmico de consulta em uma rede de acordes.

Devido à descentralização, tolerância a falhas e escalabilidade dos DHTs, eles são inerentemente mais resistentes contra um invasor hostil do que um sistema centralizado.

Sistemas abertos para armazenamento de dados distribuídos robustos contra atacantes hostis maciços são viáveis.

Um sistema DHT que é cuidadosamente projetado para ter tolerância de falhas bizantinas pode se defender contra uma fraqueza de segurança, conhecida como ataque Sybil, que afeta a maioria dos projetos atuais de DHT. Whanau é um DHT projetado para ser resistente a ataques de Sybil.

Petar Maymounkov, um dos autores originais de Kademlia, propôs uma maneira de contornar a fraqueza ao ataque de Sybil incorporando relacionamentos de confiança social no design do sistema. O novo sistema, o codinome Tonika ou também conhecido por seu nome de domínio como 5TTT, é baseado em um design de algoritmo conhecido como " roteamento elétrico " e em co-autoria com o matemático Jonathan Kelner. A Maymounkov já realizou um esforço abrangente de implementação desse novo sistema. No entanto, pesquisas sobre defesas eficazes contra ataques de Sybil geralmente são consideradas uma questão em aberto, e uma grande variedade de defesas em potencial é proposta todos os anos nas principais conferências de pesquisa de segurança.

As diferenças mais notáveis encontradas em instâncias práticas de implementações de DHT incluem pelo menos o seguinte:

• O espaço de endereço é um parâmetro de DHT. Vários DHTs do mundo real usam espaço chave de 128 bits ou 160 bits.
• Alguns DHTs do mundo real usam funções hash além de SHA-1.
• No mundo real a chave k pode ser um hash de um arquivo conteúdo em vez de um hash de um arquivo Nome para fornecer armazenamento com endereço de conteúdo, de modo que a renomeação do arquivo não impede que os usuários o encontrem.
• Alguns DHTs também podem publicar objetos de diferentes tipos. Por exemplo, chave k poderia ser o nó ID e dados associados podem descrever como entrar em contato com este nó. Isso permite informações de publicação de presença e frequentemente usadas em aplicações IM, etc. No caso mais simples, ID é apenas um número aleatório que é usado diretamente como chave k (então em um DHT de 160 bits ID será um número de 160 bits, geralmente escolhido aleatoriamente). Em alguns DHTs, a publicação de IDs de nós também é usada para otimizar as operações de DHT.
• A redundância pode ser adicionada para melhorar a confiabilidade. O (k, dados) par chave pode ser armazenado em mais de um nó correspondente à chave. Normalmente, em vez de selecionar apenas um nó, os algoritmos DHT do mundo real selecionam Eu... nós adequados, com Eu... sendo um parâmetro específico de implementação do DHT. Em alguns projetos DHT, nós concordam em lidar com uma certa faixa de espaço-chave, cujo tamanho pode ser escolhido dinamicamente, em vez de codificado.
• Alguns avançaram DHTs como Kademlia realizar pesquisas iterativas através do DHT primeiro, a fim de selecionar um conjunto de nós adequados e enviar put(k, dados) mensagens apenas para aqueles nós, assim reduzindo drasticamente o tráfego inútil, uma vez que as mensagens publicadas são enviadas apenas para nós que parecem adequados para armazenar a chave k; e os olhares iterativos cobrem apenas um pequeno conjunto de nós em vez de todo o DHT, reduzindo o encaminhamento inútil. Em tais DHTs, encaminhamento de put(k, dados) mensagens só podem ocorrer como parte de um algoritmo de auto-cura: se um nó alvo receber um put(k, dados) mensagem, mas acredita que k está fora de seu alcance tratado e um nó mais próximo (em termos de espaço-chave DHT) é conhecido, a mensagem é encaminhada para esse nó. Caso contrário, os dados são indexados localmente. Isso leva a um comportamento DHT um tanto deequilíbrio. Naturalmente, tal algoritmo requer nós para publicar seus dados de presença no DHT para que as pesquisas iterativas possam ser realizadas.
• Como na maioria das máquinas que enviam mensagens é muito mais caro do que acessos de tabela hash locais, faz sentido empacotar muitas mensagens relativas a um nó particular em um único lote. Assumindo que cada nó tem um lote local que consiste no máximo b) operações, o procedimento de compensação é o seguinte. Cada nó primeiro classifica seu lote local pelo identificador do nó responsável pela operação. Usando o tipo do balde, isso pode ser feito em O(b + n), onde n é o número de nós no DHT. Quando há várias operações que abordam a mesma chave dentro de um lote, o lote é condensado antes de ser enviado. Por exemplo, várias pesquisas da mesma chave podem ser reduzidas a um ou vários incrementos podem ser reduzidos a uma única operação de adição. Esta redução pode ser implementada com a ajuda de uma mesa de hash local temporária. Finalmente, as operações são enviadas para os respectivos nós.

• Apache Cassandra
• BATON Sobreposição
• Mainline DHT – padrão DHT usado por BitTorrent (baseado em Kademlia, conforme fornecido por Khashmir)
• Rede endereçável de conteúdo (CAN)
• Choro.
• Koorde
• Kademlia
• Pasta
• P-Grid
• Riak
• ScyllaDB
• Tapeçaria
• TomP2P
• Voldemort

• BTDigg: motor de busca BitTorrent DHT
• Código: web caching
• Freenet: uma rede anônima resistente à censura
• GlusterFS: um sistema de arquivos distribuído usado para virtualização de armazenamento
• GNUnet: Rede de distribuição como Freenet incluindo uma implementação DHT
• I2P: Uma rede de peer-to-peer anônima de código aberto
• I2P-Bote: e-mail anônimo seguro sem servidor
• IPFS: Um protocolo de distribuição de hipermedia com endereço de conteúdo, peer-to-peer
• JXTA: plataforma P2P de código aberto
• LBRY: Um protocolo de compartilhamento de conteúdo baseado em blockchain que usa um sistema DHT influenciado por Kademlia para distribuição de conteúdo
• Oracle Coherence: uma rede de dados em memória construída sobre uma implementação Java DHT
• Perfect Dark: uma aplicação de compartilhamento de arquivos peer-to-peer do Japão
• Retroshare: uma rede de amigos
• Jami: uma plataforma de comunicação de voz, vídeo e chat com preservação de privacidade, baseada em um DHT semelhante à Kademlia
• Tox: um sistema de mensagens instantâneas destinado a funcionar como um substituto do Skype
• Twister: uma plataforma de microblogging peer-to-peer
• YaCy: um motor de busca distribuído

• Couchbase Server: um sistema de armazenamento de objetos distribuídos persistente, replicado e agrupado compatível com protocolo memcached.
• Memcached: um sistema de cache de objetos de memória distribuído de alto desempenho.
• Árvore de hash prefix: consulta sofisticada sobre DHTs.
• Árvore de Merkle: árvore com cada nó não folha rotulado com a hash dos rótulos de seus nós filhos.
• A maioria das lojas de dados distribuídas empregam alguma forma de DHT para pesquisa.
• Os gráficos de deslocamento são uma estrutura de dados eficiente para a implementação de DHTs.

• Tabelas de Hash distribuídas, Parte 1 por Brandon Wiley.
• Página de Carles Pairot na pesquisa DHT e P2P
• kademlia.scs.cs.nyu.edu Arquivo.org instantâneos de kademlia.scs.cs.nyu.edu
• Eng-Keong Lua; Crowcroft, Jon; Pias, Marcelo; Sharma, Ravi; Lim, Steve (2005). «IEEE Survey on overlay network schemes» (em inglês). CiteSeerX 10.1.1.197: cobrindo redes de sobreposição descentralizadas não estruturadas e estruturadas, incluindo DHTs (Chord, Pastry, Tapestry e outros).
• Principal DHT Medição no Departamento de Ciência da Computação, Universidade de Helsínquia, Finlândia.