Explicação básica simples de uma tabela de hash distribuída (DHT)

Alguém poderia dar uma explicação sobre como um DHT funciona?

Nada muito pesado, apenas o básico.

Ok, eles são fundamentalmente uma ideia bastante simples. Um DHT fornece uma interface semelhante a um dicionário, mas os nós são distribuídos pela rede. O truque com as DHTs é que o nó que armazena uma chave específica é encontrado com hash nessa chave; portanto, seus depósitos de tabelas de hash agora são nós independentes em uma rede.

Isso oferece muita tolerância a falhas e confiabilidade, e possivelmente algum benefício no desempenho, mas também gera muitas dores de cabeça. Por exemplo, o que acontece quando um nó sai da rede, com falha ou não? E como você redistribui as chaves quando um nó se une para que a carga seja aproximadamente equilibrada. Pense bem, como você distribui as chaves igualmente? E quando um nó se une, como você evita repetir tudo? Lembre-se de que você precisaria fazer isso em uma tabela de hash normal se aumentar o número de buckets.

Um exemplo de DHT que resolve alguns desses problemas é um anel lógico de n nós, cada um assumindo a responsabilidade por 1 / n do espaço de chaves. Depois de adicionar um nó à rede, ele encontra um local no anel para ficar entre dois outros nós e assume a responsabilidade por algumas das chaves em seus nós irmãos. A beleza dessa abordagem é que nenhum dos outros nós no anel é afetado; somente os dois nós irmãos precisam redistribuir as chaves.

Por exemplo, digamos que em um anel de três nós, o primeiro nó tenha as chaves 0-10, o segundo 11-20 e o terceiro 21-30. Se um quarto nó aparecer e se inserir entre os nós 3 e 0 (lembre-se, eles estão em um anel), ele poderá se responsabilizar por, digamos, metade do espaço de chaves de 3, então agora ele lida com 26-30 e o nó 3 lida com 21 -25.

Existem muitas outras estruturas de sobreposição como essa que usam o roteamento baseado em conteúdo para encontrar o nó certo no qual armazenar uma chave. A localização de uma chave em um anel exige a busca em volta do anel, um nó por vez (a menos que você mantenha uma tabela de consulta local, problemática em um DHT de milhares de nós), que é o roteamento de O (n) -hop. Outras estruturas - incluindo anéis aumentados - garantem o roteamento de O (log n) e algumas reivindicam o roteamento de O (1) ao custo de mais manutenção.

Leia a página da Wikipédia e, se você realmente quiser conhecer um pouco mais, confira esta página do curso em Harvard, que possui uma lista de leitura bastante abrangente.

As DHTs fornecem ao usuário o mesmo tipo de interface que uma hashtable normal (procure um valor por chave), mas os dados são distribuídos por um número arbitrário de nós conectados. A Wikipedia tem uma boa introdução básica que eu estaria regurgitando se escrever mais -

http://en.wikipedia.org/wiki/Distributed_hash_table

Eu gostaria de acrescentar à resposta útil de HenryR, pois eu tinha apenas uma visão do hash consistente. Uma pesquisa de hash normal / ingênua é uma função de duas variáveis, uma das quais é o número de buckets. A beleza do hash consistente é que eliminamos o número de buckets "n" da equação.

No hash ingênuo, a primeira variável é a chave do objeto a ser armazenado na tabela. Vamos chamar a tecla "x". A segunda variável é o número de buckets, "n". Portanto, para determinar em qual balde / máquina o objeto está armazenado, é necessário calcular: hash (x) mod (n). Portanto, quando você altera o número de buckets, também altera o endereço no qual quase todos os objetos são armazenados.

Compare isso ao hash consistente. Vamos definir "R" como o intervalo de uma função hash. R é apenas uma constante. No hash consistente, o endereço de um objeto está localizado no hash (x) / R. Como nossa pesquisa não é mais uma função do número de buckets, terminamos com menos remapeamento quando alteramos o número de buckets.

http://michaelnielsen.org/blog/consistent-hashing/