Simples explicação básica de uma tabela hash distribuída (DHT)
https://stackoverflow.com/questions/144360
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Qualquer um poderia dar uma explicação sobre a forma como a DHT obras?
Nada muito pesado, apenas o básico.
Solução
Ok, eles são fundamentalmente uma idéia muito simples. A DHT dá-lhe uma interface como dicionários, mas os nós são distribuídos em toda a rede. O truque com DHTs é que o nó que recebe para armazenar uma chave particular é encontrado por hashing essa chave, assim, em efeito os seus baldes de hash-table são nós agora independentes em uma rede.
Isto dá um monte de tolerância a falhas e confiabilidade, e possivelmente algum benefício de desempenho, mas também levanta uma série de dores de cabeça. Por exemplo, o que acontece quando um nó sai da rede, ao não ou de outra forma? E como você redistribuir chaves quando um nó se junta para que a carga é mais ou menos equilibrada. Venha para pensar sobre isso, como você distribuir uniformemente as chaves de qualquer maneira? E quando um nó se junta, como você evitar rehashing tudo? (Lembre-se que você tem que fazer isso em uma tabela hash normal, se você aumentar o número de baldes).
Um exemplo DHT que aborda alguns desses problemas é um anel lógico de n nós, cada responsabilidade tomada para 1 / n do keyspace. Uma vez que você adicionar um nó à rede, ele encontra um lugar no anel sentar-se entre dois outros nós, e assume a responsabilidade por algumas das chaves em seus nós irmãos. A beleza deste abordagem é que nenhum dos outros nós no anel são afectadas; apenas os dois nós irmãos têm de redistribuir chaves.
Por exemplo, digamos que em um anel de três nó do primeiro nó possui teclas 0-10, a segunda 11-20 eo terceiro 21-30. Se uma quarta nó vem e insere-se entre os nós 3 e 0 (lembre-se, eles estão em um anel), pode assumir a responsabilidade por exemplo metade do keyspace 3 de, então agora ele lida com 26-30 e nó 3 aborda a 21 -25.
Existem muitas outras estruturas de sobreposição como esta que o uso de conteúdo baseado em roteamento para encontrar o nó direito em que para armazenar uma chave. Localizando uma chave em um anel requer a procura em volta do um nó anel de cada vez (a menos que você mantenha uma tabela look-up local, problemático em uma DHT de milhares de nós), que é O (n) -hop roteamento. Outras estruturas - incluindo anéis aumentada - garantia de O (N log N) -Hop encaminhamento, e alguns reivindicação a O (1) -Hop encaminhamento à custa de mais manutenção.
Leia a página da Wikipedia, e se você realmente quer saber em um pouco de profundidade, confira este coursepage em Harvard, que tem uma lista de leitura bastante abrangente.
Outras dicas
DHT fornecer o mesmo tipo de interface para o utilizador como uma tabela de dispersão normal (veja-se por um valor de chave), mas os dados são distribuídos ao longo de um número arbitrário de nós conectados. Wikipedia tem uma boa introdução básica que eu iria ser essencialmente regurgitar se eu escrever mais -
Eu gostaria de adicionar em resposta útil de HenryR como eu só tinha uma visão sobre hashing consistente. Uma pesquisa de hash normais / ingénuo é uma função de duas variáveis, uma das quais é o número de baldes. A beleza de hashing consistente é que nós eliminamos o número de baldes "n", a partir da equação.
Em hashing ingênuo, 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 baldes, "n". Assim, para determinar qual o balde / máquina objecto é armazenado em, tem de calcular: hash de modificação (x) (n). Portanto, quando você alterar o número de baldes, você também alterar o endereço em que quase todos os objetos são armazenados.
Compare isso com hashing consistente. Vamos definir "R" como o intervalo de uma função hash. R é apenas alguma constante. Em hashing consistente, o endereço de um objecto está localizado na de hash (x) / R. Desde a nossa pesquisa não é mais uma função do número de baldes, acabamos com menos remapeamento quando mudamos o número de baldes.
Confira este artigo Wikipedia Ou este powerpoint slides
confira Dynamo, da Amazon, explica um romance implementação DHT simples, mas com base em círculo hashing consistente.
