Desenvolvimento
Análise Mais Realista
O trabalho [16] mostra que uma rede volátil pode funcionar num estado "quase estável" se a rotina de estabilização é executada com certa frequência. Nesse caso, os lookups são rápidos e corretos
Operações Dinâmicas e Falhas
Saída Voluntária de um Nó
O nó que sai pode comunicar seu sucessor e seu predecessor e distribuir suas chaves de forma controlada.
Falhas e Replicação
Mesmo em caso de falha, o tempo para encontrar um sucessor é O(log N)
De qualquer modo, há uma alta probabilidade de um lookup encontrar o nó certo ou um muito próximo dele em caso de falha
Para utilizar esta nova tabela, os pseudo-códigos apresentados precisam ser pouco modificados
O valor r é escolhido estatisticamente (qual a chance de uma falha simultânea que queremos). r = U(log N)
Chord mantém também uma lista de tamanho r contendo todos os r sucessores de um nó n. Para haver falha, todos o r sucessores de n devem falhar simultaneamente.
Em caso de falha, a informação sobre um sucessor pode ser inválida (ver exemplo considerando a Figura 4)
Impacto da Chegada de Nós Sobre as Buscas
Só haveria problema se um grande número de nós fosse inserido entre 2 outros de uma vez.
Se N cresce, após a estabilização o acréscimo de N não muda os passos de lookup (a Finger Table tem no máximo m entradas)
Correção: 1 de 3 casos
3 - As chave estão imprecisas porque ainda não migraram para o servidor correto: um lookup pode falhar. O lookup pode ser repetido após algum tempo pela camada de software que usa o Chord. A espera é curta.
2 - Finger Table desatualizada: um lookup ainda é correto, mas mais lento
1 - Informação razoavelmente atualizada: um lookup encontra corretamente o sucessor
Chegada de Nós e Estabilidade
A operação do protocolo leva a formação de um círculo lógico - o Chord Ring
Exemplo página 23, abaixo da Figura 6
Pseudo-código na Figura 6
Protocolo de estabilização - cada nó executa periodicamente para atualizar as Finger Tables e informações sobre o sucessor
Localização escalável da Chave
O número de nós que devem ser contactados para encontrar um sucessor com a Chave buscada numa rede de N nós é O(log N)
Pseudo-código na Figura 5
Mesmo a Finger Table não tem informação para determinar todos os nós, mas apenas um número O(log N)
Cada nó mantém pouca informação na Finger Table
A i-ésima entrada contém a identidade do primeiro nó s sucessor de n por pelo menos 2**(i-1) no Chrod Ring - s = sucessor(n+2**(i-1)) - explicação completa no texto, exemplo na Fig. 4(a)
Cada nó n mantém uma tabela de roteamento com até m entradas - finger table
m - número de bits do identificador de chaves/nós
Não importante para a correção - cada Nó precisa saber apenas seu sucessor
Apresenta informação adicional de roteamento
Localização simples da Chave
Número de mensagens é linear
Pseudo-código na Fig. 3(a)
Queries são repassadas pelo anel até chegarem ao Nó certo ou falharem
Um Nó só precisa saber seu sucessor
Buscas no Chord Ring precisam de pouco estado por Nó
Relacionar Chaves com Nós
Quando um Nó X deixa a rede, suas Chaves são repassadas a sucessor(X)
Quando um Nó X entra na rede, algumas Chaves mantidas por sucessor(X) são repassadas a X
Círculo de IDs = Chord Ring
Este Nó é o sucessor de K - sucessor(K)
A Chave K é relacionada ao 1o. Nó cujo ID seja igual ou maior que K
Ordena IDs no "Círculo de IDs" módulo 2**m (fig. 2)
m deve ser grande o suficiente para não ocorrer colisões
ID Key = Hash(Key)
ID Node = Hash(End. IP)
Cada Nó/Chave possui um identificador de m-bits produzido com SHA-1
Protocolo
Um Nó não precisa saber sobre todos os outros - escalabilidade
Quando um Nó entra ou sai da rede, só O(1/N) das Chaves são movidas - mínimo para manter a rede balanceada
Alta probabilidade de carga balanceada pela função hash
Hash consistente [12] [14]
Mapeia Chaves para os Nós que as mantém
Cálculo distribuído rápido de função hash
Produto
Chord facilita funções da aplicação
Outras: caching, nomes user-friendly, etc.
Replicação: a aplicação mantém informação sob 2 Chaves Chord derivadas de identificadores dos níveis de aplicação dos dados
Autenticação: a aplicação mantém informações com uma chave Chord derivada de um hash criptografado dos dados
P. ex. a aplicação pode mover objetos para novos hosts quando um novo Nó entra na rede
2 - Chord informa a aplicação sobre alteração do conjunto de chaves que o Nó está mantendo
1 - função lookup(Key) devolve End. IP do Host que mantém Key
2 formas de interação:
Chord é uma biblioteca lincada na aplicação que usa o protocolo
Aplicações
CAN
Um Nó contém O9d) estados - custo O(d.N**(1/d))
Tabela hash distribuída (mapeia chaves para valores)
Espaço de coordenadas cartesianas de d-dimensões
Oceanstore / Plaxton
Subtopic
Uma query não viaja mais que a distância do Nó onde a Chave está
Distribuição de chaves balanceada
Query viaja por log(No. saltos)
GLOBE
Objetos divididos por vários servidores Root físicos (hash)
Trabalha com altas cargas no nó raiz lógico
Usa ponteiros para caches como atalhos
Informações sobre os objetos ficam nas folhas
Árvore estática da Internet
Organiza a Internet como uma hierarquia de domínios
Administrativos
Topológicos
Geográficos
Mapeia ID de objetos para localização de objetos
Serviço de localização em WAN
Archival Intermemory [4]
Mapeia endereços lógicos para as máquinas que mantém objetos
Árvore de busca montada offline
Ohaha [20]
Possui as fraquezas do Freenet
Consulta informações de roteamento como Freenet
Função hash mapeia documentos para os nós que os mantém
Freenet [5] [6]
Previne danos/exclusão de objetos
Garantia de anonimato
Lookup ocorre em cópias mantidas em cache
Objetos não são responsabilidade dos seus servidores
Adapta-se automaticamente a mudanças na rede
Simétrico (cada nó é balanceado com os outros)
Sistema descentralizado
DNS baseado em Chord
Também encontra objetos não ligados a máquinas específicas
Não impõem padrões de nomenclatura
Mantém informação de roteamento correta automaticamente
Servidores não são necessários
Chave ~ hash(Host name) [7]
DNS
Lookup: nomes de hosts são Chaves; Endereços IP são valores
Especializado em encontrar nomes de hosts e serviços
Nomes de hosts devem refletir limites administrativos
Gerência manual da informação de roteamento
Usa servidores Root
Chord Protocol
CFS
Chord localiza os blocos
Arquivos armazenados numa rede P2P
Chord File System
Implementação
Mapeia Nós num espaço undimensional virtual
Algoritmo de roteamento similar ao Grid [15]
Armazena e acha valores no Nó mapeado pela Chave
Dabek [9]
Hashing
[12]
Carga balanceada
Chaves associadas a Nós
Lookup
Busca correta e robusta mesmo se a informação de roteamento esteja parcialmente incorreta
O(log N) mensagens
Cada nó se comunica com outros
Roteamento
Algoritmo Dinâmico: a rede se altera com frequência
Tabela de roteamento distribuída
Cada Nó possui informações sobre poucos Nós - O(log N)
Inicialiazação
Total de Chaves / No. de Nós (N)
Características
Flexibilidade de nomes - não há restrições
Disponibilidade - novos Nós e falhas são ajustados automaticamente
Custo de busca O(log N) - barato para redes grandes
Totalmente distribuído
Balanceamento de carga natural
Requisitos
Pelo menos 1 informação de roteamento correta
Desempenho
As alterações da rede dificultam manter dados atualizados, mesmo sobre O(log N) nós!
Degrada quando a informação de roteamento está desatualizada
Nó
Chaves mapeadas para valores
Armazena dados (objetos)
Operação
Não faz hierarquias por classes de objetos
Resultado definido: sucesso ou falha
Lookup em tempo previsível
Sem anonimato
Valor: Endereço, Documento, Dado
Saída: Nó que mantém K
Função Hash: mapeia K para um valor
Entrada: uma Chave K
Objetivo
Nós entram e deixam a rede frequentemente - o tratamento é simples
Busca de dados distribuídos pelos N nós da rede
Escalável
Simples
