Categorieën: Alle - servidores - objetos

door Flavio Braga 14 jaren geleden

699

Artigo-Chord Protocol

Diversos sistemas de gerenciamento de informações e localização de objetos na rede são discutidos, cada um com suas características e vantagens específicas. Alguns, como o DNS, utilizam servidores raiz para fazer a correspondência entre nomes de hosts e endereços IP, destacando a importância da gerência manual de informações de roteamento.

Artigo-Chord Protocol

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

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