A principal pesquisa deste artigo é o código de algoritmo consistente.
O algoritmo consistente de hash foi proposto pelo MIT em 1997 (ver 0). O objetivo do design era resolver o problema do Hotpot na Internet, e sua intenção original era muito semelhante à CARP. O hash consistente corrige o problema causado pelo algoritmo simples de hash usado pela CARP, para que o DHT possa ser realmente aplicado em ambientes P2P.
O hash consistente propõe quatro condições de adaptação que o algoritmo de hash deve atender em um ambiente de cache em mudança dinamicamente:
Balanço significa que o resultado do hash pode ser distribuído a todos os caches o máximo possível, para que todo o espaço do cache possa ser utilizado. Muitos algoritmos de hash podem atender a essa condição.
A monotonidade refere -se a se algum conteúdo foi despachado para o cache correspondente através do hash e novos caches são adicionados ao sistema. O resultado do hash deve garantir que o conteúdo alocado original possa ser mapeado para o novo cache sem ser mapeado para outros buffers na coleção antiga de cache.
Algoritmos simples de hash geralmente não podem atender aos requisitos de monotonicidade, como o hash linear mais simples:
X → Ax + B mod (P)
Na fórmula acima, P representa o tamanho de todos os caches. Não é difícil ver que, quando o tamanho do cache mudar (de P1 para P2), todos os resultados originais do hash mudarão, não atendem assim aos requisitos da monotonicidade.
Alterações nos resultados do hash significam que, quando o espaço do cache muda, todos os relacionamentos de mapeamento precisam ser atualizados no sistema. Nos sistemas P2P, as alterações de cache são equivalentes à união de pares ou saída do sistema. Essa situação ocorre com frequência nos sistemas P2P, que trarão uma enorme carga de computação e transmissão. A monotonidade exige que o algoritmo de hash possa evitar essa situação.
Em um ambiente distribuído, o terminal pode não ver todos os caches, mas só pode ver alguns deles. Quando um terminal deseja mapear o conteúdo do cache através do processo de hash, uma vez que a faixa de cache vista por diferentes terminais pode ser diferente, o resultado do hash é inconsistente. O resultado final é que o mesmo conteúdo é mapeado em diferentes áreas de cache por diferentes terminais. Obviamente, essa situação deve ser evitada porque faz com que o mesmo conteúdo seja armazenado em buffers diferentes, reduzindo a eficiência do armazenamento do sistema. A definição de dispersão é a gravidade da situação acima. Um bom algoritmo de hash deve ser capaz de evitar inconsistências o máximo possível, ou seja, para minimizar a dispersão.
O problema de carga está realmente analisando o problema da descentralização de outra perspectiva. Como terminais diferentes podem mapear o mesmo conteúdo para buffers diferentes, para um buffer específico, ele também pode ser mapeado para conteúdo diferente por diferentes usuários. Como a dispersão, essa situação deve ser evitada; portanto, um bom algoritmo de hash deve ser capaz de minimizar a carga do buffer.
Na superfície, o hash consistente está visando o problema de buffer distribuído, mas se você pensa em buffer como um par em um sistema P2P e o conteúdo mapeado como vários recursos compartilhados (dados, arquivos, fluxos de mídia etc.), você descobrirá que os dois estão realmente descrevendo o mesmo problema.
No algoritmo consistente de hash, cada nó (correspondente ao par no sistema P2P) possui um ID atribuído aleatoriamente. Ao mapear o conteúdo para um nó, uma operação de hash consistente é executada usando a palavra -chave do conteúdo e o ID do nó e obtém o valor -chave. O hash consistente exige que o valor da chave e o ID do nó estejam no mesmo intervalo de valor. O valor mais simples da chave e o ID podem ser unidimensionais, como um conjunto de números inteiros de 0000 a 9999.
Ao armazenar conteúdo com base no valor da chave, o conteúdo é armazenado no nó com o ID mais próximo do seu valor -chave. Por exemplo, se o valor da chave for 1001, existem nós com IDS 1000, 1010, 1100 no sistema, e o conteúdo será mapeado para 1000 nós.
Para construir as rotas necessárias para a consulta, o hash de consistência exige que cada nó armazene as informações de localização (endereço IP) do nó de uplink (o valor do ID é maior que o menor entre seus próprios nós) e o nó downlink (o valor de identificação é menor que o maior entre seus próprios nós). Quando um nó precisa encontrar conteúdo, ele pode decidir iniciar uma solicitação de consulta ao nó Uplink ou Downlink com base no valor da chave do conteúdo. Se um nó que receber a solicitação de consulta descobrir que ele possui o destino solicitado, ele poderá retornar diretamente a confirmação ao nó que inicia a solicitação de consulta; Se descobrir que não pertence ao seu próprio escopo, pode encaminhar a solicitação ao seu nó Uplink/Downlink.
Para manter as informações de roteamento acima mencionadas, quando um nó ingressar/sair do sistema, os nós adjacentes devem atualizar as informações de roteamento em tempo hábil. Isso exige que os nós não apenas armazenem informações de localização do nó downlink diretamente conectadas, mas também conheçam as informações indiretas do nó downlink em uma determinada profundidade (n-hop) e mantenha dinamicamente a lista de nós. Quando um nó sair do sistema, seu nó uplink tenta se conectar diretamente ao nó de downlink mais próximo. Depois que a conexão for bem -sucedida, ele obterá a lista de nós do downlink do novo nó downlink e atualizará sua própria lista de nós. Da mesma forma, quando um novo nó é adicionado ao sistema, primeiro encontre o nó downlink de acordo com seu próprio ID e obtenha a lista de nó do downlink e peça ao nó Uplink para modificar sua lista de nós downlink, restaurando assim o relacionamento de roteamento.
discutir
O hash consistente resolve basicamente o problema mais crítico em um ambiente P2P - como distribuir armazenamento e roteamento em uma topologia de rede dinâmica. Cada nó precisa apenas manter as informações de um pequeno número de nós vizinhos e, quando o nó se unir ao sistema, apenas um pequeno número de nós relevantes participa da manutenção da topologia. Tudo isso torna o hash consistente o primeiro algoritmo prático DHT.
No entanto, o algoritmo de roteamento de hash consistente ainda tem deficiências. Durante o processo de consulta, a mensagem de consulta deve passar pela etapa O (n) (o (n) indica uma relação proporcional com n e n representa o número total de nós no sistema) antes que ele possa atingir o nó da consulta. Não é difícil imaginar que, quando o sistema é muito grande, o número de nós pode exceder um milhão, e essa eficiência de consulta é obviamente difícil de atender às necessidades de uso. De outra perspectiva, mesmo que o usuário possa tolerar longos atrasos, a grande quantidade de mensagens geradas durante o processo de consulta trará carga desnecessária para a rede.
package herotrix;import java.util.Collection;import java.util.SortedMap;import java.util.TreeMap;public class ConsistentHash<T> {// hash algorithm private final HashFunction hashFunction;//number of virtual nodes private final int numberOfReplicas;private final SortedMap<Integer, T> circle = new TreeMap<Integer, T> (); public consistirhash (hashfunção de hashfunction, int numberOfreplicas, coleta <t> nós) {this.hashfunction = hashfunction; this.NumberOfReplicas = númerofreplicas; para (nó t: nós) {add (nó);}} public void add (t node) {for (int i = 0; i <númerofreplicas; i ++) {círculo.put (hashfunction.hash (node.toString ()+i), node);}}} Void Remow (t) (t) (node) (node) (node ode (node.ToString ()+i), node);}}} Void Remover (t) i ++) {circ.Remove (hashfunction.hash (node.tostring ()+i));}} // algoritmo de chave public t get (chave do objeto) {if (circcing.isEmpty ()) {return null;} // calcular esse valor hash hash = não hashfunction.hash (key); if (! circ.containsKey (hash)) {classedMap <Integer, t> tailmap = círculo.tailmap (hash); hash = tailmap.isempty ()? Circle.FirstKey (): Tailmap.FirstKey ();} Return circ.get (hash);}}O exposto acima é o conteúdo inteiro deste artigo sobre o algoritmo consistente do idioma Java Notas de aprendizado (exemplos de código). Espero que seja útil para todos. Amigos interessados podem continuar se referindo a outros tópicos relacionados neste site. Se houver alguma falha, deixe uma mensagem para apontá -la. Obrigado amigos pelo seu apoio para este site!