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

177

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

Nada muito pesado, apenas o básico.

Gustavo Carreno
fonte

Respostas:

237

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.

HenryR
fonte
23
+1 boa resposta. O que você quer dizer no terceiro parágrafo ("Um exemplo de DHT que aborda alguns desses problemas é um anel lógico de n nós") é Hashing Consistente. É um tópico realmente interessante, usado no Apache Cassandra, um banco de dados distribuído criado pelo Facebook. Link para o artigo (vale a pena lê-lo): cs.cornell.edu/projects/ladis2009/papers/lakshman-ladis2009.pdf
santiagobasulto
5
Um protocolo de pesquisa baseada em anel que é muito fácil de entender é Chord: pdos.csail.mit.edu/papers/chord:sigcomm01
ThomasWeiss
Você pode explicar como o valor-chave é armazenado em um nó? Será alguma forma de tabela de hash ou um banco de dados ?.
Criador de varinhas
@ HenryR, não é "anel de nó" simplesmente uma estrutura de árvore?
Pacerier
A Uni de Illinois ensina o protocolo acorde a cada semestre, como parte de sua classe de sistemas distribuídos, se alguém quiser mais material de leitura - courses.engr.illinois.edu/ece428/sp2018/lectures.html
Siddhartha
11

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

Peter
fonte
7

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/

thebiggestlebowski
fonte
1
Você ainda precisaria modificar de qualquer maneira, não é? Digamos que você tenha 3 servidores. hash(x)/Rfornece 34500. Você ainda precisa fazer 34500% 3 .
Pacerier
Seu post no blog não é claro, você deve listar o instantâneo passo a passo de um exemplo de trabalho em que os nós são adicionados e removidos, juntamente com as linhas que são adicionadas e removidas.
Pacerier 3/11