Sistemas Distribuídos
Jorge Surian
[email protected]
Sistemas Distribuídos: Nomeação
Nomeação: Conceitos Básicos
 Nomes, Identificadores e Endereços
– Entidades: Máquinas, impressoras, discos, processos,
usuários, páginas Web, janelas gráficas, mensagens,
etc.
– São acessadas através de um ponto de acesso, ou
simplesmente, endereço
» Ex: Servidor e seu número IP
– Um endereço pode ser utilizado como uma maneira
de nomear, identificar uma entidade
» Problema: Entidade pode mudar facilmente de ponto de acesso!
–Ex: Servidor Web alocado em outra rede
2
2
Nomeação: Conceitos Básicos
 Nomes, Identificadores e Endereços
– Como nomear entidades, sem utilizar especificamente
seu endereço, ou seja, nomeá-las
independentemente da sua posição física
(localização)?
Resposta: Identificadores ou Nomes amigáveis a
seres humanos. É muito comum estabelecer
nomes de países, de jogadores de futebol do
passado ou de deuses mitológicos. É mais fácil ao
usuário entender que “Afrodite” não está
disponível do que “XPTO001X” está indisponível...
3
3
Nomeação: Conceitos Básicos
 Identificadores
– Em muitos casos, são cadeias aleatórias de bits, com
as seguintes propriedades:
» Um identificador referencia, no máximo, UMA entidade
» Cada entidade é referenciada por, no máximo, um
identificador
» Um identificador sempre referencia a mesma entidade, isto
é, nunca é reutilizado
–Exemplo: Identificadores de entidades em
sistemas P2P baseados no sistema Chord
4
4
Nomeação: Conceitos Básicos
 Nomes Amigáveis
– Nomes representados por uma cadeia de caracteres
» Pathnames, domínios na Internet, números de processos
» Ex: http://www.gmail.com; /etc/linux
– Como resolver a questão dos nomes e identificadores
para endereços?
» Com Sistemas de Nomeação
5
5
Nomeação: Sistemas de Nomeação
 Mantém uma vinculação nome-endereço
– Na forma mais simples
» Tabela de pares (nome,endereço)
» Contudo, sistemas que abrangem redes de grande porte,
uma tabela centralizada não vai funcionar como é
necessário...
 Três Classes
– Nomeação Simples
– Nomeação Estruturada
– Nomeação Baseada em Atributo
6
6
Nomeação: Sistemas de Nomeação
 Nomeação Simples
– Aplicada a identificadores
» Cadeias aleatórias de bits → nomes simples
» Não contém sequer uma informação sobre como localizar o
ponto de acesso de uma entidade associada
– Problema: Dado um identificador, como localizar o
ponto de acesso (endereço)?
» Soluções Simples (broadcasting)
» Localização Nativa
» Tabelas de Hash Distribuídas (DHT)
7
7
Nomeação Simples
 Nomeação Simples – Broadcasting e Multicasting
– Consideradas soluções simples
– Aplicáveis somente a redes locais
 Broadcasting
– Recursos oferecidos por redes locais nas quais todas
as máquinas estão conectadas a um único cabo ou
seu equivalente lógico
– Como funciona?
» Mensagem que contém o identificador da entidade é enviada
a todos as máquinas da rede.
» Cada uma das máquinas verifica se tem esta entidade.
» Máquinas com ponto de acesso para a entidade, enviam
uma mensagem que contém o endereço procurado.
8
8
Nomeação Simples
 Broadcasting
– Se torna ineficiente quando a rede cresce
» Largura de banda da rede é desperdiçada, com grande
número de mensagens de requisição
» Aumento da probabilidade de colisões de mensagens,
diminuindo o throughput do sistema
» Grande número de máquinas pode ser interrompido por
requisições que não podem responder
9
9
Nomeação Simples
 Multicasting
– Somente um grupo restrito de máquinas recebe a
requisição
– Banco de Dados Replicado
» Endereço multicast é associado a uma entidade replicada.
» Multicasting é usado para localizar a réplica mais próxima.
» Requisição para o endereço multicast, cada réplica responde
com seu endereço IP,
» Réplica mais próxima → aquela cuja resposta chega antes.
10
10
Nomeação Simples
 Multicasting
11
11
Nomeação Simples
 Localização Nativa
– Abordagem para suportar entidades móveis em redes
de grande escala
– Monitora a localização corrente de uma entidade
– Localização nativa costuma ser escolhida como o
lugar em que a entidade foi criada
12
12
Nomeação Simples
 Mobile IP
– Cada host móvel usa um endereço fixo
– Toda a comunicação é dirigida inicialmente ao agente
nativo do host móvel (situado na rede local do
endereço do host)
– Ao mudar de rede, host recebe um endereço externo
(care-of-adress) e registra no agente nativo
– Quando o agente nativo recebe um pacote para o
host móvel
» Se na rede local → pacote repassado
» Senão → túnel até a localização corrente
13
13
Nomeação Simples
 Localização Nativa
14
14
Nomeação Simples
 Localização Nativa
– Desvantagens
» Para se comunicar com uma entidade móvel, em
primeiro lugar um cliente tem que contatar a
localização nativa, que pode estar em um lugar
completamente diferente → Latência de
comunicação
» Assegurar que a localização nativa sempre exista
» Entidade decide mudar permanentemente para
outra localização → localização nativa deve
também mudar.
15
15
Nomeação: Tabelas de Hash Distribuídas (DHT)
 Exemplo: Nós são organizados logicamente em um anel
(Chord)
– Usa um espaço de identificadores de m bits para
designar nós e entidades específicas (arquivos,
processos)
– Número m bits é usualmente 128 ou 160
– Entidade com chave k cai sob a jurisdição do nó que
tenha o menor identificador id >= k → succ(k)
 Como resolver com eficiência uma chave k para o
endereço de succ(k)?
– Abordagem linear
– Tabela de Derivação
16
16
Nomeação: Tabelas de Hash Distribuídas (DHT) - Chord
 Abordagem linear
– Cada nó p monitora o sucessor succ(p+1) e o
predecessor pred(p)
– Ao receber uma requisição para a chave k, p repassa a
requisição para os seus vizinhos, a menos que
pred(p) < k <= p → p retorna o próprio endereço
– Não escalável!
17
17
Nomeação: Tabelas de Hash Distribuídas (DHT) - Chord
a) Suponhamos que
p = 4 receba uma
requisição para
k = 7 → succ(p+1)
→ repassa a
requisição ao nó = 9
b) Suponhamos que
p = 4 receba uma
requisição para
k = 3 → como
pred(4) = 1< 3<=4
→ retorna o próprio
endereço.
18
18
Nomeação: Tabelas de Hash Distribuídas (DHT) - Chord
 Tabela de derivação (finger table)
– Possui, no máximo, m entradas
– Denotando a tabela de derivação de p por Ftp
» Ftp[i]=succ(p+2 i -1) i-ésima entrada aponta para o primeiro nó que
sucede p por no mínimo 2 i -1
19
19
Nomeação: Tabelas de Hash Distribuídas (DHT) - Chord
 Como encontrar uma entidade k?
– Referências na tabela de derivação são atalhos para
nós existentes no espaço de identificadores.
– 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 ao nó q com índice j na tabela de
derivação de p.
q = Ftp [ j ] <= k <= Ftp [j+1]
20
20
Nomeação: Tabelas de Hash Distribuídas (DHT) - Chord
 Exemplo:
1) Considere a resolução de k=26, a
partir do nó 1.
2) Nó 1 consultará k=26 → verifica
que o valor é maior do que FT1[5].
3) Requisicão será repassada para o
nó 18.
4) O nó 18 selecionará o nó 20,
porque FT18[2] < k<= FT18[3].
5) Por fim, requisição é repassada do
nó 20 para o nó 21 e deste para 28
Consulta → O(log(N)) passos
21
21
Proximidade na Rede
 Problema: Organização lógica do nós em uma rede de
sobreposição (orvelay) pode levar a uma escolha errada
no roteamento de mensagens → k e succ(k+1) podem
estar muito longe fisicamente!
 Solução:
– Identificar nós com base na topologia:
» Ao atribuir um ID a um nó, ter certeza que nós próximos no espaço
de endereçamento estejam também próximos fisicamente.
– Roteamento por proximidade:
» Manter mais de um sucessor e repassar a requisição para o mais
próximo.
– Seleção de vizinho por proximidade:
» Ao escolher um vizinho (não em Chord), pegue o mais próximo
22
22
Nomeação Estruturada
 Nomes simples são bons para máquinas, mas não são
convenientes para a utilização de seres humanos
 Sistemas de nomeação comumente suportam nomes
estruturados
– Exemplo: Nomeação de arquivos, hosts na Internet
 Nomes são organizados em um espaço de nomes
 Espaços de nomes podem ser representados como um
grafo dirigido, com dois tipos de nós:
– Nó-folha: entidade
– Nó de diretório: entidade que se refere a outros nós
 Nó de diretório possui uma tabela de diretório
<nome aresta, nome nó>
23
23
Nomeação Estruturada
 Sistemas de nomeação possuem, na maioria, um nó raiz
– Cada caminho no grafo de nomeação pode ser
referenciado pela sequência dos labels nas arestas
N:<label1, label2, ..., labeln>
– Nome de caminho absoluto: primeiro nó no caminho é
a raiz
– Nome de caminho relativo: primeiro nó pode ser
qualquer nó.
24
24
Nomeação Estruturada – Resolução de Nomes
 Espaços de nomes oferecem um mecanismo para
armazenar e recuperar informações sobre entidades por
meio de nomes.
 Dado um nome de caminho, deve ser possível consultar
qualquer informação armazenada no nó referenciado por
aquele nome.
 Problema: Para resolver um nome, precisamos de
um nó de diretório. Como escolher este nó inicial?
25
25
Nomeação Estruturada – Resolução de Nomes
 Mecanismo de fechamento: Trata da seleção do nó
inicial em um espaço de nomes a partir do qual a
resolução de nomes deve começar.
 São implícitos ao contexto em que a resolução de nomes
está se aplicando
– www.cs.vu.nl: início da resolução é feito através do
servidor de nome DNS
– /home/steen/mbox:início da resolução ocorre no
servidor local NFS
26
26
Nomeação Estruturada – Resolução de Nomes - Alias
 Outro nome para a mesma entidade
 Vários nomes absolutos para o mesmo nó (hard link)
27
27
Nomeação Estruturada – Resolução de Nomes - Alias
 Symbolic link: permite a um nó-folha ter associado um
caminho absoluto.
28
28
Nomeação Estruturada – Resolução de Nomes
 Diversos Espaços de Nomes
– Como fundir diferentes espaços de nomes de maneira
transparente? Dado dois espaços de nomes A e B,
como A acessa B e B acessa A?
» Possível Solução: Montagem (Mouting).
– Mount point: O nó de diretório que armazena o
identificador de nó do espaço de nome externo.
– Mounting point: Nó de diretório no espaço de nomes
externo.
29
29
Implementação de um Espaço de Nomes
 Implementação de um Espaço de Nomes
– Serviço que permite que usuários e processo
adicionem, removam e consultem nomes
– Serviço de nomeação é implementado por servidores
de nomes
– Servidores de nomes devem prover:
»
»
»
»
Escalabilidade
Manutenção descentralizada
Tolerância a falhas, robustez
Escopo global: Nomes possuem o mesmo significado em
todos lugares
30
30
Implementação de um Espaço de Nomes
 Costumam ser organizados em hierarquia
 Segundo Cheriton e Mann (1989) é conveniente dividir
os espaço de nomes em três camadas
– Camada global
» Raiz e seus filhos
» Principal característica: Estabilidade
» Podem representar organizações
31
31
Implementação de um Espaço de Nomes
 Segundo Cheriton e Mann (1989) é conveniente dividir
os espaço de nomes em três camadas
– Camada Administrativa
» Nós de diretórios
» Gerenciados por uma única organização
» Relativamente estáveis
– Camada Gerencial
» Nós cujo comportamento típico é a mudança periódica
» Mantidos por administradores de sistemas e usuários finais
32
32
Implementação de um Espaço de Nomes
33
33
Comparação entre servidores de Nomes
34
34
Como resolver nomes?
 Resolução Iterativa
– Servidor responde somente o que sabe: o nome do
próximo servidor que deve ser buscado
– Cliente procura iterativamente os outros servidores
 Resolução Recursiva
– Servidor passa o resultado para o próximo servidor
que encontrar
– Para o cliente, somente existe uma mensagem de
retorno: o endereço do nome ou 'não encontrado'
35
35
Como resolver nomes?
36
36
Resolução Iterativa x Recursiva
37
37
Resolução Iterativa x Recursiva
38
38
DNS: Domain Name System
 Pessoas: muitos identificadores:
– CPF, nome, no. da Identidade
 Hospedeiros, roteadores Internet :
– endereço IP (32 bit) - usado para endereçar
datagramas.
– “nome”, ex., jambo.ic.uff.br - usado por gente
» complexidade na borda da rede.
39
39
DNS: Domain Name System
 Pergunta: como mapear entre nome e endereço IP?
 Resposta: DNS - Domain Name System!
– base de dados distribuída implementada na
hierarquia de muitos servidores de nomes
– protocolo de camada de aplicação permite que
hospedeiros, roteadores, servidores de nomes e
comuniquem para resolver nomes (tradução
endereço/nome)
» Nota: função imprescindível da Internet implementada como
protocolo de camada de aplicação.
40
40
DNS: Domain Name System
Serviços DNS.
 Tradução de nome de hospedeiro para IP
 Apelidos para hospedeiros (aliasing)
– Nomes canônicos e apelidos
 Apelidos para servidores de e-mail
 Distribuição de carga
– Servidores Web replicados: conjunto de endereços IP
para um nome canônico.
41
41
DNS: Domain Name System
Serviços DNS.
 Por que não centralizar o DNS?
– ponto único de falha
– volume de tráfego
– base de dados centralizada e distante
– manutenção (da BD)
– Não é escalável!
42
42
DNS: Domain Name System
 Base de Dados Hierárquica e Distribuída
43
43
DNS – Servidores Raiz
 Procurado por servidor local que não consegue resolver o
nome, remetido ao servidor raiz.
 Servidor raiz (13 “espalhados” pelo mundo):
– procura servidor oficial se mapeamento desconhecido
– obtém tradução
– devolve mapeamento ao servidor local
44
44
Fonte:
Tanenbaum, Andrew S. e Steen, Marteen Van. Sistemas Distribuídos, São
Paulo: Prentice Hall, 2008.
Copyright © 2010 Prof. Jorge Surian
Todos direitos reservados. Reprodução ou divulgação total ou parcial deste
documento é expressamente proíbido sem o consentimento formal, por escrito, do
Professor Surian.
45
45