Sistemas Distribuı́dos: Conceitos e Projeto
Arquiteturas Ponto a Ponto
Francisco José da Silva e Silva
Laboratório de Sistemas Distribuı́dos (LSD)
Departamento de Informá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 Nã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
Introdução
Redes ponto-a-ponto (PEER-TO-PEER / P2P) são sistemas
distribuı́dos constituı́dos por processos cuja interação é simétrica:
cada processo agirá como um cliente e um servidor ao mesmo tempo;
Redes P2P são distribuı́das por natureza, não possuindo nenhuma
estrutura hierárquica ou controle centralizado;
Seus componentes são organizados em uma rede de sobreposição
(overlay network), isto é, uma rede na qual os nós são formados pelos
processos e os enclaces representam os canais de comunicação
possı́veis (usualmente realizados como conexões TCP);
Redes P2P permitem o compartilhamento de recursos entre os
participantes e suas implementações tentam prover uma vasta gama
de propriedades: seleção de nós próximos, armazenamento
redundante, localização eficiente de itens de dados, confiança e
autenticação, tornar anô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 Sobreposiçã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 sobreposição é controlada;
Conteúdo é depositado não em nós aleatórios mas em localizações
especı́ficas, o que tornará eventuais consultas mais eficientes;
2
Não estruturada
A construção da rede de sobreposição é baseado em algoritmos
aleatórios. Cada nó manterá uma lista de vizinhos mas esta lista é
construı́da de modo aleatório;
Da mesma maneira, os dados são depositados aleatoriamente nos nó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 nós;
Os itens de dados recebem uma chave aleatória, como um
identificador de 128 ou 160 bits de um grande espaço de
identificadores;
Da mesma forma, os nós também recebem um número aleatório do
mesmo espaç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 nó;
A rede P2P permite o armazenamento e recuperação escaláveis de
pares {chave,valor} através da rede de sobreposiçã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 operações put e get são utilizadas para armazenar e recuperar o valor
correspondente à chave, o que envolve o roteamento de requisições ao nó
correspondente à 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 nós estão logicamente organizados em um anel
de tal modo que um item de dado com chave k seja mapeado para o
nó que tenha o menor identificador id > k;
Este nó é 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 função hash atribui a nós e chaves de dados um identificador de
m bits;
O identificador de um nó é escolhido através do valor hash de seu
endereço IP, enquanto o identificador de uma chave é produzido
através do valor hash de seu dado;
m é usualmente 128 ou 160, dependendo da função hash utilizada;
A questão central é como resolver com eficiência uma chave k para o
endereço de succ(k);
Uma abordagem óbvia é deixar que cada nó p monitore o sucessor
succ(p + 1) bem como seu predecessor pred(p);
Neste caso, sempre que p recebe uma requisição para resolver k ele
repassa a requisição para um de seus dois vizinhos, a menos que
pred(p) < k 6 p, quando p deve retornar seu próprio endereço;
Esta abordagem, no entanto, não é escalá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 Derivação
Cada nó mantém uma tabela de derivação (finger table) de no
máximo m entradas, denotando-se a tabela do nó p por FTp ;
FTp = succ(p + 2i −1 )
Ou seja, a i-ésima entrada aponta para o primeiro nó que sucede p
por, no mı́nimo, 2i −1 ;
Portanto, a distância do atalho em relação ao nó p aumenta
exponencialmente à medida que o ı́ndice na tabela de derivação
cresce;
Para consultar uma chave k, o nó p repassará a requisição a q com
ı́ndice j na tabela de derivação onde:
q = FTp [j] 6 k 6 FTp [j + 1], ignorando-se a aritmé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 Resolução de Chave no Sistema Chorus
Considere a resolução de k = 26 a partir do nó 1, conforme figura
constante no próximo slide;
O nó 1 verificará se k é maior que FT1 [5], o que significa que a
requisição será repassada para o nó 18 = FT1 [5];
Por sua vez, o nó 18 selecionará o nó 20, já que
FT18 [2] < k 6 FT18 [3];
Por fim a requisição é repassada do nó 20 para o nó 21 e deste para o
nó 28, que é responsável por k = 26;
Neste ponto o endereço do nó 28 é repassado para o nó 1 e a chave
foi resolvida;
Pode-se mostrar que uma consulta exigirá O(log (N)), onde N é o
número de nó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 Resoluçã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 Nós no Chorus
Para se juntar ao sistema, o nó p contata um nó arbitrário e requisita
uma consulta para succ(p + 1);
O próprio nó 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 nó p deixa o sistema, todas as
chaves a ele previamente atribuı́das devem ser repassadas a seu
sucessor;
Perceba que os nó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 Derivação Atualizadas
O mais importante para todo nó q é que FTq [1] esteja correta, já que
esta entrada se refere ao próximo nó do anel;
Para isso, cada nó 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 informações são
consistentes com as de seu sucessor;
Caso o sucessor de q tenha atualizado seu predecessor, um novo nó p
entrou no sistema, com q < p 6 succ(q + 1), de modo que q ajustará
FTq [1] para p;
Ele também verificará se p registrou q como seu predecessor;
De forma semelhante, para atualizar a tabela de derivação, q precisa
simplesmente achar o sucessor para k = q + 2i −1 para cada entrada i ;
Isso pode ser feito pela emissão de uma requisição para resolver
succ(k);
Em Chord, tais requisições sã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 Derivação Atualizadas
Cada nó q verifica periodicamente se seu predecessor está vivo;
Se ele tiver falhado, q ajustará pred(q) para “desconhecido”;
Por outro lado, quando q estiver atualizando seu enlace para o
próximo nó no anel e descobrir que o predecessor de succ(q + 1) foi
ajustado para “desconhecido”, ele simplesmente avisará succ(q + 1)
que suspeita que ele é o predecessor;
Estes procedimentos garantem que um sistema Chord seja
normalmente consistente, talvez com exceção de alguns nó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 conteúdo endereçável (Content Addressable Netowrk CAN) utiliza um espaço de coordenadas cartesianas de d dimensões
que é particionado entre os nós do sistema;
Todo item de dados em CAN será atribuı́do a um único ponto desse
espaço, tornando claro qual nó responsável por ele;
Para armazenar um par {k, v }, a chave k é deterministicamente
mapeada para um ponto p no espaço de coordenadas através de uma
função hash;
Cada nó mantêm uma tabela de roteamento que guarda o endereço
IP e as coordenadas de cada um de seus vizinhos no espaço;
Utilizando as coordenadas dos vizinhos, um nó roteia mensagens em
direção ao seu destino encaminhando-as ao vizinho mais pró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 Nó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 Nós em CAN
Quando um nó p deseja se juntar a um sistema CAN, ele escolhe um
ponto arbitrário do espaço de coordenadas e pesquisa o nó q em cuja
região o ponto cai;
O nó q, então, subdivide sua região em duas metades, designando
uma delas a p;
p descobre seus vizinhos peguntando a q;
Os itens de dados pelos quais p é agora responsável devem ser
transferidos do nó q.
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
20 / 36
Arquiteturas Ponto a Ponto Estruturadas
Adição de Nó 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 Nó em CAN
Considere que o nó cuja coordenada é (0,6; 0,7) deixa o sistema;
Sua região será designada a um dos seus vizinhos, por exemplo o nó
(0,9; 0,9);
Como o nó (0,9; 0,9) não pode simplesmente fundi-la e obter um
retângulo, ele cuidará da região e informará isso aos vizinhos;
Um processo de fundo é iniciado periodicamente para promover uma
repartição simétrica do espaç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 múltiplos espaços de coordenadas independentes no
sistema, atribuindo-se a cada nó uma zona diferente em cada espaço,
denominado uma realidade;
O conteúdo da tabela hash pode ser replicado em cada realidade
aumentando-se a disponibilidade dos dados;
Uma outra alternativa seria utilizar k funções hash diferentes para
mapear uma chave a k pontos diferentes do espaço de coordenadas.
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
23 / 36
Arquiteturas Ponto a Ponto Estruturadas
Considerações Sobre Redes P2P Estruturadas
Sistemas DHT possem uma sólida base teórica que garante que toda
chave pode ser encontrada;
No entanto, para cada salto na rede de sobreposição, nós roteam a
mensagem ao próximo nó que pode estar distante considerando-se a
rede IP subjacente;
Sistema DHT também assumem que todos os nós participam de
forma equitativa no armazenamento e localização de informação. Isto
pode resultar em gargalos em nós com pouca capacidade.
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
24 / 36
Arquiteturas Ponto a Ponto Estruturadas
Exploraçã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 nós próximos
tenham identificadores que também estejam próximos um do outro;
O mapeamento pode expor falhas correlacionadas: nós de uma rede
corporativa terão identificadores dentro de um mesmo intervalo e, caso
a rede fique inalcançável, teremos uma lacuna na distribuição uniforme
de identificadores;
Na abordagem de roteamento por proximidade, cada nó mantém uma
lista de alternativas para repassar a requisição.
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
25 / 36
Arquiteturas Ponto a Ponto Não Estruturadas
Arquiteturas Ponto a Ponto Não
Estruturadas
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
26 / 36
Arquiteturas Ponto a Ponto Não Estruturadas
Introdução
Redes P2P não estruturadas utilizam algoritmos aleatórios para
construir uma rede de sobreposição;
Da mesma forma, itens de dados são depositados aleatoriamente em
nós;
Consequentemente, quando um nó 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 não
mantenha uma grande quantidade de réplicas deve ser enviada para
uma grande quantidade de nós, o que é ineficiente.
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
27 / 36
Arquiteturas Ponto a Ponto Não Estruturadas
Gnutella
Gnutella (pronuncia-se newtella) é um protocolo descentralizado para
redes P2P largamente utilizado;
O sistema não possui diretório centralizado nem controle preciso
sobre a topologia da rede ou depósito de arquivos;
O protocolo de consulta é baseado em uma inundação de vizinhos
com um certo raio;
Esta abordagem é bastante resiliente a nós entrando e saindo com
frequência do sistema;
No entanto, gera-se problemas de escalabilidade e cargas inesperadas
de tráfego na rede.
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
28 / 36
Arquiteturas Ponto a Ponto Não Estruturadas
Entrada de Nós em Gnutella
Um novo nó inicialmente se conecta a um nó conhecido pertencente à
lista http://gnutellahosts.com, que normalmente estão sempre
disponı́veis;
Uma vez conectado à rede, os nós enviam mensagens para interagir
entre si;
Estas mensagens podem ser enviadas por broadcast (enviada a todos
os nós com os quais o emissor possua um conexão TCP aberta) ou
por propagação retroativa (enviada a uma conexão especı́fica no
caminho inverso de uma mensagem inicial);
Cada mensagem possui um identificador gerado aleatoriamente, bem
como campos TTL e “nós atravessados”.
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
29 / 36
Arquiteturas Ponto a Ponto Não Estruturadas
Mensagens Gnutella
De gerenciamento de grupo
Um nó ao entrar na rede inicia o broadcast de uma mensagem PING
para anunciar sua presença;
A mensagem é enviada aos vizinhos que iniciam uma mensagem PONG
de propagação retroativa informando seu endereço IP, quantidade e
tamanho dos seus itens de dados.
De consulta
Uma mensagem QUERY carrega a string de busca utilizada por cada
nó receptor para procurar pesquisar no nome de seus arquivos
armazenados;
Realiza-se uma propagação retroativa de uma mensagem QUERY
RESPONSE contendo a informação necessária para se realizar o
download do arquivo.
De transferência de arquivo
Dowloads de arquivos são realizados diretamente entre
dois nó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 Não Estruturadas
Superpares (superpeers)
À medida que uma rede não estruturada cresce, pode-se tornar difı́cil
a localização de itens de dados já que não há um modo determinı́stico
para se rotear a mensagem;
Muitos sistemas mantêm nós especiais que armazenam um ı́ndice de
itens de dados, denominados superpares;
Superpares são organizados em uma rede P2P, o que resulta em uma
organização hierá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
Introdução
Em arquiteturas hı́bridas, usualmente um nó se junta ao sistema
através de um esquema cliente-servidor tradicional e tão logo isso
ocorra ele pode usar um esquema descentralizado para colaboração;
Um exemplo clássico é 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 nós;
O download dos arquivos era realizado diretamente pelos nós;
No entanto, um decisão judicial de um processo gerado pela
Recording Industry Association of America (RIAA) forçou o Napster a
desligar o seu serviço de compartilhamento de música digital.
Francisco Silva (UFMA/LSD)
SD: Conceitos e Projeto
6 de junho de 2013
33 / 36
Arquiteturas Hı́bridas
BitTorrent
BitTorrent é um sistema P2P para transferência de arquivos;
Sua ideia básica é que quando um usuário final estiver procurando um
arquivo, ele transfira porções do mesmo de outros usuários até que
possam ser montadas em conjunto, resultando no arquivo completo;
Seu protocolo é projetado para desencorajar caroneiros (free-riders):
Um arquivo só pode ser transferido quando o cliente que o estiver
transferindo estiver transferindo o conteúdo a mais alguém;
Nós que disponibilizem uma alta velocidade para upload poderão,
provavelmente, realizar download à uma velocidade alta;
A taxa de download de um nó será 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 usuário precisa acessar um diretório
global, que é apenas um de alguns sites Web conhecidos;
O diretório contém referências a arquivos .torrent;
Arquivos .torrent contém as informações necessárias para transferir
um arquivo especı́fico;
Em particular, ele referencia um rastreador que mantém uma
contabilidade dos nós ativos que têm porções do arquivo requisitado;
Um nó ativo é aquele que está transferindo outro arquivo no
momento em questão;
Tão logo o nó tenha identificado de onde as porções do arquivo
podem ser transferidas, ele se torana ativo. Neste ponto, ele será
forç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