Sistemas Distribuı́dos: Conceitos e Projeto
Arquiteturas Ponto a Ponto
Francisco José da Silva e Silva
Laboratório de Sistemas Distribuı́dos (LSD)
Departamento de Informática / UFMA
http://www.lsd.deinf.ufma.br
6 de junho de 2013
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
1 / 36
Agenda
1
Arquiteturas Ponto a Ponto Estruturadas
2
Arquiteturas Ponto a Ponto Não Estruturadas
3
Arquiteturas Hı́bridas
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
2 / 36
Arquiteturas Ponto a Ponto Estruturadas
Arquiteturas Ponto a Ponto Estruturadas
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
3 / 36
Arquiteturas Ponto a Ponto Estruturadas
Introdução
Redes ponto-a-ponto (PEER-TO-PEER / P2P) são sistemas
distribuı́dos constituı́dos por processos cuja interação é simétrica:
cada processo agirá como um cliente e um servidor ao mesmo tempo;
Redes P2P são distribuı́das por natureza, não possuindo nenhuma
estrutura hierárquica ou controle centralizado;
Seus componentes são organizados em uma rede de sobreposição
(overlay network), isto é, uma rede na qual os nós são formados pelos
processos e os enclaces representam os canais de comunicação
possı́veis (usualmente realizados como conexões TCP);
Redes P2P permitem o compartilhamento de recursos entre os
participantes e suas implementações tentam prover uma vasta gama
de propriedades: seleção de nós próximos, armazenamento
redundante, localização eficiente de itens de dados, confiança e
autenticação, tornar anônimo, etc. . .
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
4 / 36
Arquiteturas Ponto a Ponto Estruturadas
Arquitetura Abstrata de uma Rede de Sobreposição P2P
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
5 / 36
Arquiteturas Ponto a Ponto Estruturadas
Classes de Redes P2P
1
Estruturada
A topologia da rede de sobreposição é controlada;
Conteúdo é depositado não em nós aleatórios mas em localizações
especı́ficas, o que tornará eventuais consultas mais eficientes;
2
Não estruturada
A construção da rede de sobreposição é baseado em algoritmos
aleatórios. Cada nó manterá uma lista de vizinhos mas esta lista é
construı́da de modo aleatório;
Da mesma maneira, os dados são depositados aleatoriamente nos nós.
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
6 / 36
Arquiteturas Ponto a Ponto Estruturadas
Redes P2P Estruturadas
Usualmente utiliza uma tabela hash distribuı́da (Distributed Hash
Table - DHT) para organizar os nós;
Os itens de dados recebem uma chave aleatória, como um
identificador de 128 ou 160 bits de um grande espaço de
identificadores;
Da mesma forma, os nós também recebem um número aleatório do
mesmo espaço de identificadores;
O sistema deve implementar um esquema determinı́stico que mapeie
exclusivamente a chave de um item de dado para o identificador de
um nó;
A rede P2P permite o armazenamento e recuperação escaláveis de
pares {chave,valor} através da rede de sobreposição.
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
7 / 36
Arquiteturas Ponto a Ponto Estruturadas
Interface de Rede P2P Estruturada Baseada em DHT
Figura: As operações put e get são utilizadas para armazenar e recuperar o valor
correspondente à chave, o que envolve o roteamento de requisições ao nó
correspondente à chave
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
8 / 36
Arquiteturas Ponto a Ponto Estruturadas
Sistema Chord
No sistema Chord os nós estão logicamente organizados em um anel
de tal modo que um item de dado com chave k seja mapeado para o
nó que tenha o menor identificador id > k;
Este nó é denominado sucessor da chave k e denotado por succ(k).
Actual node
15
14
0
1
{13,14,15}
{0,1}
2
3
13
{2,3,4}
12 {8,9,10,11,12}
Associated
data keys
11
10
Francisco Silva (UFMA/LSD)
5
{5,6,7}
9
8
4
6
7
SD: Conceitos e Projeto
6 de junho de 2013
9 / 36
Arquiteturas Ponto a Ponto Estruturadas
Sistema Chord
Uma função hash atribui a nós e chaves de dados um identificador de
m bits;
O identificador de um nó é escolhido através do valor hash de seu
endereço IP, enquanto o identificador de uma chave é produzido
através do valor hash de seu dado;
m é usualmente 128 ou 160, dependendo da função hash utilizada;
A questão central é como resolver com eficiência uma chave k para o
endereço de succ(k);
Uma abordagem óbvia é deixar que cada nó p monitore o sucessor
succ(p + 1) bem como seu predecessor pred(p);
Neste caso, sempre que p recebe uma requisição para resolver k ele
repassa a requisição para um de seus dois vizinhos, a menos que
pred(p) < k 6 p, quando p deve retornar seu próprio endereço;
Esta abordagem, no entanto, não é escalável...
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
10 / 36
Arquiteturas Ponto a Ponto Estruturadas
Sistema Chord: Tabela de Derivação
Cada nó mantém uma tabela de derivação (finger table) de no
máximo m entradas, denotando-se a tabela do nó p por FTp ;
FTp = succ(p + 2i −1 )
Ou seja, a i-ésima entrada aponta para o primeiro nó que sucede p
por, no mı́nimo, 2i −1 ;
Portanto, a distância do atalho em relação ao nó p aumenta
exponencialmente à medida que o ı́ndice na tabela de derivação
cresce;
Para consultar uma chave k, o nó p repassará a requisição a q com
ı́ndice j na tabela de derivação onde:
q = FTp [j] 6 k 6 FTp [j + 1], ignorando-se a aritmética modular por
clareza.
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
11 / 36
Arquiteturas Ponto a Ponto Estruturadas
Exemplo de Resolução de Chave no Sistema Chorus
Considere a resolução de k = 26 a partir do nó 1, conforme figura
constante no próximo slide;
O nó 1 verificará se k é maior que FT1 [5], o que significa que a
requisição será repassada para o nó 18 = FT1 [5];
Por sua vez, o nó 18 selecionará o nó 20, já que
FT18 [2] < k 6 FT18 [3];
Por fim a requisição é repassada do nó 20 para o nó 21 e deste para o
nó 28, que é responsável por k = 26;
Neste ponto o endereço do nó 28 é repassado para o nó 1 e a chave
foi resolvida;
Pode-se mostrar que uma consulta exigirá O(log (N)), onde N é o
número de nós no sistema.
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
12 / 36
Arquiteturas Ponto a Ponto Estruturadas
Exemplo de Resolução de Chave no Sistema Chorus
1
2
3
4
5
Actual node
30
1
2
3
4
5
31
0
1
4
6
25
7
8
24
23
28
28
28
1
9
Francisco Silva (UFMA/LSD)
11
11
14
18
28
10
21
11
20
1
2
3
4
5
1
2
3
4
5
9
Resolve k = 26
from node 1
22
1
2
3
4
5
2
5
Resolve k = 12
from node 28
26
+
su
9
9
9
14
20
1
2
3
4
5
3
28
27
i-1 )
p
(
cc
i
2
29
1
1
1
4
14
4 Finger table
4
9
9
18
21
28
28
28
4
12
13
19
18
1
2
3
4
5
17
16
15
1
2
3
4
5
14
14
18
20
28
14
20
20
28
28
4
SD: Conceitos e Projeto
1
2
3
4
5
18
18
18
28
1
6 de junho de 2013
13 / 36
Arquiteturas Ponto a Ponto Estruturadas
Gerenciamento de Nós no Chorus
Para se juntar ao sistema, o nó p contata um nó arbitrário e requisita
uma consulta para succ(p + 1);
O próprio nó p pode se inserir no anel. Para manter o mapeamento
consistente, certas chaves atribuı́das previamente ao sucessor de p
devem ser reatribuı́das a ele (p);
De forma semelhante, quando um nó p deixa o sistema, todas as
chaves a ele previamente atribuı́das devem ser repassadas a seu
sucessor;
Perceba que os nós devem monitorar seu predecessor.
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
14 / 36
Arquiteturas Ponto a Ponto Estruturadas
Mantendo Tabelas de Derivação Atualizadas
O mais importante para todo nó q é que FTq [1] esteja correta, já que
esta entrada se refere ao próximo nó do anel;
Para isso, cada nó q executa periodicamente um procedimento que
contata succ(q + 1) e requisita que ele retorne pred(succ(q + 1));
Se q = pred(succ(q + 1)), q sabe que suas informações são
consistentes com as de seu sucessor;
Caso o sucessor de q tenha atualizado seu predecessor, um novo nó p
entrou no sistema, com q < p 6 succ(q + 1), de modo que q ajustará
FTq [1] para p;
Ele também verificará se p registrou q como seu predecessor;
De forma semelhante, para atualizar a tabela de derivação, q precisa
simplesmente achar o sucessor para k = q + 2i −1 para cada entrada i ;
Isso pode ser feito pela emissão de uma requisição para resolver
succ(k);
Em Chord, tais requisições são emitidas periodicamente.
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
15 / 36
Arquiteturas Ponto a Ponto Estruturadas
Mantendo Tabelas de Derivação Atualizadas
Cada nó q verifica periodicamente se seu predecessor está vivo;
Se ele tiver falhado, q ajustará pred(q) para “desconhecido”;
Por outro lado, quando q estiver atualizando seu enlace para o
próximo nó no anel e descobrir que o predecessor de succ(q + 1) foi
ajustado para “desconhecido”, ele simplesmente avisará succ(q + 1)
que suspeita que ele é o predecessor;
Estes procedimentos garantem que um sistema Chord seja
normalmente consistente, talvez com exceção de alguns nós.
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
16 / 36
Arquiteturas Ponto a Ponto Estruturadas
Rede CAN
A rede de conteúdo endereçável (Content Addressable Netowrk CAN) utiliza um espaço de coordenadas cartesianas de d dimensões
que é particionado entre os nós do sistema;
Todo item de dados em CAN será atribuı́do a um único ponto desse
espaço, tornando claro qual nó responsável por ele;
Para armazenar um par {k, v }, a chave k é deterministicamente
mapeada para um ponto p no espaço de coordenadas através de uma
função hash;
Cada nó mantêm uma tabela de roteamento que guarda o endereço
IP e as coordenadas de cada um de seus vizinhos no espaço;
Utilizando as coordenadas dos vizinhos, um nó roteia mensagens em
direção ao seu destino encaminhando-as ao vizinho mais próximo das
coordenadas de seu destino.
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
17 / 36
Arquiteturas Ponto a Ponto Estruturadas
Mapeamento de Itens de Dados para Nós em CAN
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
18 / 36
Arquiteturas Ponto a Ponto Estruturadas
Exemplo de Roteamento de Mensagem em CAN
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
19 / 36
Arquiteturas Ponto a Ponto Estruturadas
Gerenciamento de Nós em CAN
Quando um nó p deseja se juntar a um sistema CAN, ele escolhe um
ponto arbitrário do espaço de coordenadas e pesquisa o nó q em cuja
região o ponto cai;
O nó q, então, subdivide sua região em duas metades, designando
uma delas a p;
p descobre seus vizinhos peguntando a q;
Os itens de dados pelos quais p é agora responsável devem ser
transferidos do nó q.
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
20 / 36
Arquiteturas Ponto a Ponto Estruturadas
Adição de Nó em CAN
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
21 / 36
Arquiteturas Ponto a Ponto Estruturadas
Saı́da de Nó em CAN
Considere que o nó cuja coordenada é (0,6; 0,7) deixa o sistema;
Sua região será designada a um dos seus vizinhos, por exemplo o nó
(0,9; 0,9);
Como o nó (0,9; 0,9) não pode simplesmente fundi-la e obter um
retângulo, ele cuidará da região e informará isso aos vizinhos;
Um processo de fundo é iniciado periodicamente para promover uma
repartição simétrica do espaço inteiro.
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
22 / 36
Arquiteturas Ponto a Ponto Estruturadas
Melhorias em CAN
Pode-se manter múltiplos espaços de coordenadas independentes no
sistema, atribuindo-se a cada nó uma zona diferente em cada espaço,
denominado uma realidade;
O conteúdo da tabela hash pode ser replicado em cada realidade
aumentando-se a disponibilidade dos dados;
Uma outra alternativa seria utilizar k funções hash diferentes para
mapear uma chave a k pontos diferentes do espaço de coordenadas.
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
23 / 36
Arquiteturas Ponto a Ponto Estruturadas
Considerações Sobre Redes P2P Estruturadas
Sistemas DHT possem uma sólida base teórica que garante que toda
chave pode ser encontrada;
No entanto, para cada salto na rede de sobreposição, nós roteam a
mensagem ao próximo nó que pode estar distante considerando-se a
rede IP subjacente;
Sistema DHT também assumem que todos os nós participam de
forma equitativa no armazenamento e localização de informação. Isto
pode resultar em gargalos em nós com pouca capacidade.
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
24 / 36
Arquiteturas Ponto a Ponto Estruturadas
Exploração de Proximidade na Rede
Pode-se fazer com que um sistema DHT fique ciente da rede subjacente
das seguintes formas:
Designando-se identificadores de modo tal que dois nós próximos
tenham identificadores que também estejam próximos um do outro;
O mapeamento pode expor falhas correlacionadas: nós de uma rede
corporativa terão identificadores dentro de um mesmo intervalo e, caso
a rede fique inalcançável, teremos uma lacuna na distribuição uniforme
de identificadores;
Na abordagem de roteamento por proximidade, cada nó mantém uma
lista de alternativas para repassar a requisição.
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
25 / 36
Arquiteturas Ponto a Ponto Não Estruturadas
Arquiteturas Ponto a Ponto Não
Estruturadas
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
26 / 36
Arquiteturas Ponto a Ponto Não Estruturadas
Introdução
Redes P2P não estruturadas utilizam algoritmos aleatórios para
construir uma rede de sobreposição;
Da mesma forma, itens de dados são depositados aleatoriamente em
nós;
Consequentemente, quando um nó precisa localizar um item de dado
especı́fico, ele deve inundar a rede com uma consulta de busca;
Uma consulta a um item de dado para os quais o sistema não
mantenha uma grande quantidade de réplicas deve ser enviada para
uma grande quantidade de nós, o que é ineficiente.
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
27 / 36
Arquiteturas Ponto a Ponto Não Estruturadas
Gnutella
Gnutella (pronuncia-se newtella) é um protocolo descentralizado para
redes P2P largamente utilizado;
O sistema não possui diretório centralizado nem controle preciso
sobre a topologia da rede ou depósito de arquivos;
O protocolo de consulta é baseado em uma inundação de vizinhos
com um certo raio;
Esta abordagem é bastante resiliente a nós entrando e saindo com
frequência do sistema;
No entanto, gera-se problemas de escalabilidade e cargas inesperadas
de tráfego na rede.
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
28 / 36
Arquiteturas Ponto a Ponto Não Estruturadas
Entrada de Nós em Gnutella
Um novo nó inicialmente se conecta a um nó conhecido pertencente à
lista http://gnutellahosts.com, que normalmente estão sempre
disponı́veis;
Uma vez conectado à rede, os nós enviam mensagens para interagir
entre si;
Estas mensagens podem ser enviadas por broadcast (enviada a todos
os nós com os quais o emissor possua um conexão TCP aberta) ou
por propagação retroativa (enviada a uma conexão especı́fica no
caminho inverso de uma mensagem inicial);
Cada mensagem possui um identificador gerado aleatoriamente, bem
como campos TTL e “nós atravessados”.
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
29 / 36
Arquiteturas Ponto a Ponto Não Estruturadas
Mensagens Gnutella
De gerenciamento de grupo
Um nó ao entrar na rede inicia o broadcast de uma mensagem PING
para anunciar sua presença;
A mensagem é enviada aos vizinhos que iniciam uma mensagem PONG
de propagação retroativa informando seu endereço IP, quantidade e
tamanho dos seus itens de dados.
De consulta
Uma mensagem QUERY carrega a string de busca utilizada por cada
nó receptor para procurar pesquisar no nome de seus arquivos
armazenados;
Realiza-se uma propagação retroativa de uma mensagem QUERY
RESPONSE contendo a informação necessária para se realizar o
download do arquivo.
De transferência de arquivo
Dowloads de arquivos são realizados diretamente entre
dois nós utilizando-se mensagens GET e PUSH.
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
30 / 36
Arquiteturas Ponto a Ponto Não Estruturadas
Superpares (superpeers)
À medida que uma rede não estruturada cresce, pode-se tornar difı́cil
a localização de itens de dados já que não há um modo determinı́stico
para se rotear a mensagem;
Muitos sistemas mantêm nós especiais que armazenam um ı́ndice de
itens de dados, denominados superpares;
Superpares são organizados em uma rede P2P, o que resulta em uma
organização hierárquica.
Regular peer
Superpeer
Superpeer
network
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
31 / 36
Arquiteturas Hı́bridas
Arquiteturas Hı́bridas
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
32 / 36
Arquiteturas Hı́bridas
Introdução
Em arquiteturas hı́bridas, usualmente um nó se junta ao sistema
através de um esquema cliente-servidor tradicional e tão logo isso
ocorra ele pode usar um esquema descentralizado para colaboração;
Um exemplo clássico é o Napster, que em 1999 foi pioneiro na ideia
de se utilizar um modelo P2P para o compartilhamento de arquivos;
Ele possuı́a uma facilidade centralizada de pesquisa a arquivos que era
baseado em listas providas pelos nós;
O download dos arquivos era realizado diretamente pelos nós;
No entanto, um decisão judicial de um processo gerado pela
Recording Industry Association of America (RIAA) forçou o Napster a
desligar o seu serviço de compartilhamento de música digital.
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
33 / 36
Arquiteturas Hı́bridas
BitTorrent
BitTorrent é um sistema P2P para transferência de arquivos;
Sua ideia básica é que quando um usuário final estiver procurando um
arquivo, ele transfira porções do mesmo de outros usuários até que
possam ser montadas em conjunto, resultando no arquivo completo;
Seu protocolo é projetado para desencorajar caroneiros (free-riders):
Um arquivo só pode ser transferido quando o cliente que o estiver
transferindo estiver transferindo o conteúdo a mais alguém;
Nós que disponibilizem uma alta velocidade para upload poderão,
provavelmente, realizar download à uma velocidade alta;
A taxa de download de um nó será reduzida caso a velocidade de
upload tiver sido limitada.
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
34 / 36
Arquiteturas Hı́bridas
Funcionamento BitTorrent
Para obter um arquivo, um usuário precisa acessar um diretório
global, que é apenas um de alguns sites Web conhecidos;
O diretório contém referências a arquivos .torrent;
Arquivos .torrent contém as informações necessárias para transferir
um arquivo especı́fico;
Em particular, ele referencia um rastreador que mantém uma
contabilidade dos nós ativos que têm porções do arquivo requisitado;
Um nó ativo é aquele que está transferindo outro arquivo no
momento em questão;
Tão logo o nó tenha identificado de onde as porções do arquivo
podem ser transferidas, ele se torana ativo. Neste ponto, ele será
forçado a auxiliar outros.
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
35 / 36
Arquiteturas Hı́bridas
Arquitetura do BitTorrent
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
36 / 36