Sistemas Distribuídos
Nomeação
Nazareno Andrade
Universidade Federal de Campina Grande
02/2008
Fundamentos
Coordenando processos
Construíndo sistemas
Sistemas construídos
2
Fundamentos
Coordenando processos
– Mensagens (e fluxos): UDP, TCP, MPI, Enfileiramento,
Gossiping
– RPC e objetos distribuídos: RMI
– Mensagens vs. RPC
– Nomeação
– Sincronização e replicação
Construíndo sistemas
Sistemas construídos
3
Objetivos
Compreender o uso de nomes em sistemas distribuídos
Entender o processo de descoberta de recursos em
diferentes tipos de sistema distribuído
Analisar o espaço de soluções para um sistema de
nomes distribuído
4
Pra que nomes?
Como um componente do sistema usa nomes?
O que um serviço de descoberta (ou de nomes) precisa
ser capaz de fazer?
– Nomes úteis a seres humanos são os mais apropriados
para o serviço?
E se não quero usar um nome, mas atributos da
entidade?
5
O serviço de nomes ou de descoberta de recursos
mapeia nomes ou atributos para pontos de acesso a
entidades
Um nome referencia uma entidade
Ponto de acesso  acesso à entidade
Endereço  nome do ponto de acesso
6
Endereços na prática
Qual o mapeamento ponto de acesso  entidade?
Por que não usamos sempre o endereço como nome?
– Mobilidade de dispositivos, de código, de serviços
– Múltiplos servidores replicados
Qual a relação disso com transparência?
7
Identificadores
Outro tipo de nome
1. Identifica no máximo uma entidade
2. Entidade tem no máximo um identificador
3. Identificadores não são reutilizados
Como isso é possível?
8
Atributos
E se eu quero uma descoberta de recursos menos
acoplada?
“Quero a máquina menos carregada do sistema”
Atributos podem referenciar entidades
9
O problema
Dado que temos nomes, identificadores, atributos e endereços
Como resolver [nome ou identificador ou atributos] 
endereço(s)?
Essencialmente, usando uma tabela
– Centralizada, hierárquica, distribuída, ...
Para sistemas de nomes distribuídos, resolver é próximo de
rotear
10
Onde estamos
Pra que servem nomes
Resolvendo identificadores
Nomes estruturados
Atributos
11
Resolvendo identificadores
Nomeadores podem ter referência ao endereço da
entidade?
Problema 0:
– Localizar máquina na rede com endereço MAC XYZW
– Localizar máquina que roda o DHCP na rede
12
Problema 1: entidades que se movem
– Ponteiros repassadores
– Localização nativa
13
DHTs
Tabelas hash distribuídas  escalabilidade
Operação central: lookup(chave)
Princípios:
1.
2.
3.
4.
Mapear chaves para nós de forma balanceada
Função de distância entre chave e id de um nó
Um nó que recebe uma requisição deve ser capaz de repassá-la a um
nó mais perto de key ou respondê-la
Tabelas de roteamento devem ser adaptativas
As principais diferenças estão na implementação da função de
distância e na construição da tabela de roteamento
14
Roteamento com skiplists: Chord
Espaço mesmo de nomes para nós e objetos
– Distância é distância entre identificadores em lista circular
Objeto está em succ(k)
Tabela de roteamento (finger table) de p:
FTp[i] = succ(p + 2i-1)
Roteamento:
Envie para nó com índice j em FT tal que
FTp[j] ≤ k ≤ FTp[j+1]
(envia para sucessor, caso não haja nós assim)
15
16
Detalhes operacionais
A topologia precisa ser mantida
– Nós monitoram sucessor e predecessor
– Periodicamente verifico se eu == predecessor de meu sucessor
• Se ele falhou, procuro um novo sucessor
– Se meu predecessor falha, salvo essa informação e aguardo contato de
novo predecessor
Redundância nos sucessores aumenta robustez
A topologia da overlay pode explorar topologia da rede
– IDs podem ser distribuídos de acordo com topologia da rede
17
Roteamento com árvores
Pastry, Tapestry e Kademlia usam uma árvore para construir
tabela de roteamento
Em Kademlia a distância entre k e i é k XOR i
Para identificadores de 128 bits, cada nó considera 128
distâncias possíveis
– Para cada distância, mantem uma lista de nós naquela distância
– No momento da busca, envia requisições recursivas para os nós da
distância mais próxima do id
18
Exemplo Kademlia
Divisão da rede para nó 0011
19
Busca no Kademlia
Busca por 1110
20
Sistemas de nome hierárquicos
Nós-folha têm conhecem endereço do identificador
Nós um nível acima, conhecem que nós abaixo
resolvem um identificador
21
22
Onde estamos
Pra que servem nomes
Resolvendo identificadores
Nomes estruturados
Atributos
23
Nomeação estruturada
Identificadores não são bons para seres humanos
Nomes estruturados são mais intuitivos:
Espaço de nomes é um grafo:
– Nós-folha são entidades nomeadas
– Demais nós são diretórios à lá sistemas de arquivos
– Tipicamente, há uma raiz, geralmente não há ciclos
Tudo muito parecido com sistemas de arquivos.
Como funciona a resolução de ‘ls nome’?
24
Resolução de nomes estruturados
distribuída
Mecanismo de fechamento
Determina por onde começar a resolução
– Sistemas de arquivos: /
– Variáveis de ambiente unix: espaço de nomes do usuário
Montagem
– Combinar espaços de nomes distribuídos
– FS é um bom exemplo novamente
25
Nomes estruturados em grande escala
Camadas com diferentes requisitos
Replicação horizontal e caching para escalabilidade e disponibilidade
26
Resolução iterativa vs. recursiva
Vantagens / desvantagens?
– Caching
– Localidade de tráfego
27
Exemplo: DNS
Espaço de nomes
– www.lsd.ufcg.edu.br na verdade é www.lsd.ufcg.edu.br.
– Domínios == sub-árvores do espaço de nomes
Conteúdo de um nó na árvore
– Além do que usamos: servidor de email para esse nome,
email do administrador, IPs alternativos, servidor de
nomes desse domínio, ...
28
29
Raiz do DNS
30
Onde estamos
Pra que servem nomes
Resolvendo identificadores
Nomes estruturados
Atributos
31
Atributos
Nem sempre nomes são suficientes
Atributos referenciam entidades por características
– Cada entidade tem conjuntos (atributo, valor)
Por vezes há distinção entre serviços que usam nomes
e atributos
– Nomes  Serviço de nomeação
– Atributos  Serviço de diretório
32
Atributos: Implementação hierárquica
LDAP é um padrão bastante usado
Cada recurso é descrito por uma tabela de atributos
– dsc.ufcg.edu.br == /C=BR/TO=edu/O=ufcg/OU=DSC/…
O espaço de nomes é dividido em uma árvore
A árvore é dividida em nós
– Parece um DNS, mas com pesquisas mais complexas
– Search((C=BR)(TO=edu)(O=ufcg)(OU=*))
33
Atributos: implementação decentralizada
estruturada
Várias abordagens, ainda nenhum consenso
SWORD:
– Identificadores dos nós não são mais hashes
– Identificador = [bits identificando atributo + bits
identificando valor + bits aleatórios]
– Um nó é responsável pelo atributo k, outro por k > 50,
outro por k > 75, ...
– Consulta na DHT na verdade procura índices de atributos
34
Atributos decentralizados e nãoestruturados
Explorando localidade em redes P2P
– Nós procuram outros nós com interesses semelhantes e se
aproximam deles
– Gossiping é útil aqui
IMM: encontrando nó menos carregado em uma árvore
de multicast
– Um nó que esteve rápido recentemente provavelmente
estará rápido agora
Há também a descoberta semi-estruturada, com supernós...
35
Recapitulando
Pra que servem nomes
– Endereços, nomes, identificadores e atributos
Resolvendo identificadores
– Broadcast, hierarquia, DHTs
Nomes estruturados
– Fechamento, montagem, resolução iterativa vs. Recursiva
Atributos
– Implementação hierárquica
– Implementação decentralizada estruturada
– Implementação decentralizada não-estruturada
36
Mais sobre esse assunto
DHTs:
– Visão geral: Looking up data in p2p systems
– Artigo do Kademlia
DNS:
– Livro online explicando e mostrando porque o DNS ainda é
suficiente
Nomes em geral:
– Naming and binding of objects, 1978: artigo filosófico
sobre sistemas de nomes (nomenclatura hoje em desuso)
37