Sistemas Distribuídos
Arquiteturas e Modelos
Nazareno Andrade
Universidade Federal de Campina Grande
02/2008
Fundamentos
Coordenando processos
Construíndo sistemas
Sistemas construídos
2
Fundamentos
–
–
–
–
–
–
O que são sistemas distribuídos
Para que distribuímos sistemas
Referências de sistemas distribuídos
Vocabulário sobre sistemas distribuídos
Arquiteturas de sistemas distribuídos
Modelos de sistemas distribuídos
Coordenando processos
Construíndo sistemas
Sistemas construídos
3
Objetivos
Entender possibildiades de organização dos
compontentes de um SD em arquiteturas
Compreender vantagens e desvantagens de
arquiteturas
Aprender para quê modelos são úteis em SDs
Se familiarizar com modelos mais comuns de SDs
4
Arquiteturas de sistemas distribuídos
5
Arquitetura == Arte de edificar
6
Arquiteturas
Arquitetura: organização e interação dos componentes
Arquitetura do software vs. Arquitetura do sistema
– Do software: organização dos componentes lógicos
– Do sistema: organização nos componentes físicos
Repare que a arquitetura do sistema depende da
arquitetura do software
7
Arquitetura de software
Como componentes são configurados em conjunto
para formar o sistema
– Componente: unidade modular com interface definida e
substituível
– Conectores: instrumentos de comunicação para os
componentes
Podemos classificar arquiteturas em estilos
arquiteturais
8
Estilos arquiteturais
FIGURA DO TANENBAUM
9
Arquitetura de sistema
Como os componentes estão distribuídos na prática?
Arquiteturas
centralizadas
Arquiteturas
híbridas
Arquiteturas
descentralizadas
10
Arquiteturas
centralizadas
Arquiteturas
híbridas
Arquiteturas
descentralizadas
11
Arquiteturas centralizadas
Comumente referida como Cliente-Servidor
Clientes requisitam serviço de um servidor
Exemplos: NFS, BDs, ...
Claro, um servidor pode ser cliente de outro servidor
– Usuário requisita do NFS, este requisita do FS local
12
Dividindo responsabilidades
O que fica no cliente, o que fica no servidor?
Consideremos uma aplicação em 3 camadas:
13
Como dividir?
14
Comentário sobre quem faz o quê
Normalmente, clientes magros facilitam a gerência do
sistema
– A funcionalidade a ser atualizada está no servidor
– Algumas vezes, o código do cliente é sempre enviado do
servidor: AJAX
Clientes gordos favorecem responsividade e
escalabilidade
– A revolução do Gmail
15
Arquiteturas
centralizadas
Arquiteturas
híbridas
Arquiteturas
descentralizadas
16
Arquiteturas descentralizadas
Comumente chamadas peer-to-peer (entre-pares)
– Embora descentralizado ≠ entre-pares
Dois tipos de distribuição:
– Vertical: componentes diferentes em máquinas diferentes
– Horizontal: componentes semelhantes em máquinas diferentes
Arquitetura descentralizada: processos são essencialmente
iguais, mas possuem recursos diferentes
– Kazaa, eDonkey e similares
– Skype, MSN e similares
17
Redes de sobreposição
Os componentes estão organizados numa rede lógica
Chamamos essa rede de overlay ou sobreposta
Como um componente acha qual outro componente
tem um recurso?
Duas questões: como gerenciar a topologia da overlay e como
rotear requisições?
(por hora, vamos lidar com a primeira)
Respostas: topologias estruturadas e não estruturadas
18
Topologias não-estruturadas
Se baseiam em algoritmos aleatórios:
– Cada nó obtém uma lista de vizinhos aleatórios
– Quando precisa de um recurso, esse nó pergunta
a seus vizinhos quem tem
• Flooding, popularizado pelo Gnutella v1.0
O BitTorrent constrói sua overlay assim
Multicast no nível da aplicação pode usar o
mesmo
CDNs também
19
Exemplo de topologias não-estruturadas
BitTorrent
– Cada nó recebe uma lista
aleatória de vizinhos e se
conecta a eles
– Nós trocam peças do arquivo
com seus vizinhos
Gnutella v1.0
– Nós conhecem um ou poucos
nós a se juntar na rede
– Nós se anunciam a todos que
queiram ouvir
– Cada nó mantém uma lista
aleatória de conhecidos
20
Supernós (super pares)
Se é necessário localizar recursos freqüentemente na
rede, a não estruturação prejudica escalabilidade
– Inundação  # mensagens proporcional ao # nós
Uma solução é criar índices
– Um supernó é responsável um conjunto de nós ou
recursos
– Um nó requisita um recurso a um supernó
– A descoberta de recursos se restringe aos supernós
21
Exemplos: Kazaa, Skype, JXTA (randomized walks)
22
Supernós do Skype em 2007
23
Topologias estruturadas
Princípio: procedimento determinístico
– Para manter a topologia
– Para descobrir recursos
A topologia reflete uma estrutura de dados
considerando quem tem qual recurso
– Estrutura mais comum é uma Hash Table distribuída: DHT
– Outros exemplo é estruturar nós em uma árvore
distribuída
24
==
25
Entendendo DHTs
Recursos e nós recebem identificadores aleatórios
O espaço de identificadores de recurso é dividido entre
os nós de acordo com os identificadores dos nós
– Protocolo para entrada e saída de nós
Uma consulta lookup(resourceID) retorna um nodeID
– Objetivos: determinismo e eficiência
26
Exemplo: Chord
Nós são organizados em um anel
O item k é mapeado para o nó com menor id com id ≥ k
27
Mantendo a topologia no Chord
Ao entrar no sistema:
– O nó com id i procura quem é responsável por i: succ(i)
– Contata succ(i) e pergunta quem é seu predecessor
– Assume recursos entre i e seu predecessor e muda ponteiros
Ao sair do sistema:
– Avisa sucessor e predecessor para reparar anel
– Transfere recursos para succ(i)
Mais na frente veremos como buscar no anel...
28
Exemplo 2: CAN
Chord usa um espaço de ids unidimensional
Can usa um espaço multidimensional
29
Centralizado vs. descentralizado
Arquiteturas
centralizadas
Arquiteturas
híbridas
Centralização:
– Simplicidade de
implementação
– Simplicidade de gerência
– Gargalo em potencial
Arquiteturas
descentralizadas
Descentralização:
– Escalabilidade
– Robustez
– Complexidade
30
Arquiteturas
centralizadas
Arquiteturas
híbridas
Arquiteturas
descentralizadas
31
Diretório centralizado, função distribuída
Napster, MSN, BitTorrent, GoogleFS, ...
Diretório é simples e razoavelmente escalável se centralizado
32
Serviço descentralizado, interação clienteservidor
Origin
Server
Coral
httpprx
dnssrv
Coral
httpprx
dnssrv
Browser
Browser
Coral
httpprx
dnssrv
Coral
httpprx
dnssrv
Coral
httpprx
dnssrv
Coral
httpprx
dnssrv
Browser
Browser
CDNs, OurGrid, ...
33
Recapitulando
Estilos arquiteturais de software
Arquitetura do sistema
– Centralizada, descentralizada ou híbrida
– Manutenção de overlays
– Tradeoffs entre escalabilidade, eficiência e simplicidade de
implementação
– Repertório de arquiteturas
34
Modelos de sistemas distribuídos
35
Fundamentos
–
–
–
–
–
–
O que são sistemas distribuídos
Para que distribuímos sistemas
Referências de sistemas distribuídos
Vocabulário sobre sistemas distribuídos
Arquiteturas de sistemas distribuídos
Modelos de sistemas distribuídos
Coordenando processos
Construíndo sistemas
Sistemas construídos
36
O que é um modelo?
Representação abstrata de um objeto de estudo
Objetivo: analisar propriedades desse objeto
Tipicamente é mais simples que o objeto
Simplicidade  Análise
Complementam a experimentação
Ajudam a entender resultados do experimento
Podem explorar espaço de possibilidades com menos custos
37
Resultados de modelos
Normalmente fazemos o seguinte:
1. Simplificamos a realidade
2. Analisamos processos ou entidades que importam
3. Derivamos resultados relevantes para a realidade
Resultados geralmente são de impossibilidade ou de
custo
38
Exemplo de uso de modelo
p
t1
q
servidor
p ou q deve baixar t1 e fazer streaming para o outro processo
– Assumimos que p começa o algoritmo distribuído, mandando uma msg para q
Se as mensagens de p e q sempre chegam ao destino, em algum momento
eles começarão o processamento
Porém não podemos dizer nada sobre a demora para começar
Se as mensagens têm atraso mínimo de min e máximo de max:
– p envia “t1”, espera min e começa
– q recebe mensagem, espera 1 e começa
– Atraso máximo é de (max – min + 1)  é conhecido
39
Dimensões úteis em SD
O que é comum a todas as arquiteturas?
Interação entre processos
– Processos precisam se comunicar e coordenar
– Quais as considerações sobre a comunicação?
Falhas
– Em SD, temos falhas parciais
– Como os processos e canais falham e detectam falhas?
Segurança
– Especificar ameaças e atacantes
40
Modelos de interação
Múltiplos processos interagem trocando mensagens
– Desempenho dos canais torna-se importante
– Não há noção de tempo única (já vemos porque)
Definições:
– Latência: Tempo entre envio e chegada da mensagem
– Atraso: Tempo entre decisão de envio e envio (devido a
congestão na rede)
– Largura de banda: capacidade de envio em um instante
– Jitter: variação no tempo para enviar uma série de
mensagens
41
Tempo e interação
Tempo pode ser útil para coordenação e para decisões:
– “Paramos o serviço às 18:00”
– “Se o processo não respondeu em 1s é porque não está funcionando”
Mas apenas se:
– Os relógios dos processos tiverem alguma precisão em comum
– Conhecermos quanto tempo uma mensagem normalmente demora
para chegar a seu destino e quanto tempo um nó demora processando
Decidir se isso é verdade ou não em nosso modelo são as nossas
considerações!
42
A Relatividade e os Sistemas Distribuídos
Praticamente todo relógio tem uma drift rate (inclusive
a Terra)
Em um instante, o tempo em dois processos provavelmente
será diferente
Caso consideremos esse drift, pode não ser possível
usar relógios como referências
– Mas e se nosso sistema se mantiver monitorando os drifts?
O que muda?
43
44
Tempo de envio e de processamento
Quanto tempo uma mensagem pode demorar para
chegar em nosso modelo?
– Na realidade, ela pode demorar para sempre
Um nó sabe quanto tempo esperar pelo
processamento de outro nó?
– Como saber se o outro nó está processando ou falhou?
45
Variantes do modelo de interação
Com relação às considerações:
Modelo síncrono
Modelo assíncrono
Modelo parcialmente síncrono
Sincronismo : coordenação no tempo de ocorrência de fatos ou
eventos (Houaiss)
46
Modelo síncrono
1. Há limites de tempo para a execução de um passo
em um processo
2. Há limite de tempo para a transmissão de uma
mensagem em um canal de comunicação
3. O drift dos relógios dos processos tem limite
conhecido
47
Sincronismo na prática
O modelo síncrono permite a concepção de soluções
simples
Mas como descobrir os limites de na prática?
– Em alguns sistemas especializados, é possível
• Processamento em etapas de tamanho conhecido
• Processamento sem preempção
– Em outros casos, probabilidade pode ser usada
• Limites probabilísticos  Confiança probabilística
48
Modelo assíncrono
Não há limites conhecidos para:
1. Execução de uma instrução por um processo
2. Demora na transmissão de uma mensagem
3. Drift no relógio dos processos
Modelo com menos considerações  Modelo mais
geral
Infelizmente, tipicamente serve para provar
impossibilidades
49
Exemplo: FLP
Impossibilidade de consenso entre processos em um sistema
assíncrono se um deles pode falhar
– Um processo não pode distingüir se o outro falhou ou está demorando
a responder
– Se há uma falha, outros processos esperam para sempre
(No artigo, é uma prova matemática usando o modelo assíncrono)
Ressalva: não quer dizer que nunca acontece consenso; apenas
não é possível garantir
Mas imagine o que esse resultado significa para BDs
distribuídos...
50
Modelos parcialmente síncronos
Alguma sincronia facilita o desenvolvimento de
algoritmos distribuídos
O sistema pode ser síncrono durante um período
O sistema pode ser síncrono em uma parte
51
Sistemas síncronos por algum tempo
Se em algum momento o sistema é síncrono, em algum
momento é possível detectar falhas
Detectores de falhas:
– Acurácia e precisão
Considerando um detector de falhas específico, é
possível desenvolver uma solução com desempenho
conhecido
52
Sistemas síncronos em alguma parte
Uma parte do sistema é síncrona
Exemplo: um canal de comunicação para controle
– Esse canal também dá possibilidade de detecção de falhas
Interface 1
Interface 1
Interface 2
Interface 2
Canal dedicado,
sem congestão
53
Lembrando onde estamos...
Sincronismo diz respeito às considerações de interação
no nosso modelo
– Modelo assíncrono, síncrono e parcialmente síncrono
Há outras 2 dimensões importantes:
– Falhas
– Segurança
54
Modelo de falhas
Processos e canais podem falhar
Falha: sair do comportamento esperado
Tipos de falha:
– Omissão
– Tempo
– Arbitrária
55
Omissão
Processo:
– Crash: pára para sempre, outros não notam
– Fail-stop: pára para sempre, perceptível
• Por exemplo por timeouts num modelo síncrono
Canal:
– Mensagem enviada não chega ao destino
• E.g.: Drop no roteador
A maior parte das falhas que você vai ver são desse tipo
56
Falhas de tempo
Acontecem quando limites de tempo são
desrespeitados em sistemas síncronos
Particularmente relevantes para sistemas de tempo real
– Ex: Skype
Pode ocorrer devido a relógio, atraso na transmissão de
mensagem ou atraso no processamento
57
Falhas Arbitrária
Aka Bizantinas
Processos ou canais produzem qualquer
comportamento indesejado
– Eg.: processo envia resposta válida, mas com resultado
errado
– Eg2.: canal muda mensagem enviada
Mais difíceis de contornar
Embora aconteçam: exemplos do PlanetLab e Amazon
58
Outro exemplo de modelos
Exemplo p. 5x do CDK. Consenso com e sem crashes.
59
Lembrando onde estamos...
Já vimos:
– Modelos de interação
– Modelos de falha
Falta:
– Modelos de Segurança
60
Modelos de segurança
Confidencialidade: Não pode haver acessos nãoautorizados
Integridade: Não pode haver alterações nãoautorizadas
Normalmente modelamos um adversário (ou inimigo),
suas capacidades e seus recursos
– A partir dele, fazemos um modelo de ameaças
– Por exemplo, qual o modelo de ameaças de um caixa
eletrônico?
61
Ataques a recursos
O adversário é capaz de fazer requisições nãoautorizadas
– RMI sem SSL
– Serviços sem senha
É necessário que o serviço seja capaz de verificar a
identidade do requisitante
E o mesmo vale se o adversário puder se passar pelo
servidor
O cliente deve conseguir verificar a identidade do servidor
62
Ataques à interação dos processos
Ataques possíveis para um adversário:
– Se passar por outro processo e enviar uma mensagem
– Escutar mensagens nos canais de comunicação e alterá-las,
omiti-las ou repeti-las
– Enviar tantas requisições a um servidor que o paralisa
(Denial of Service)
– Se passar por vários processos em uma votação (Sybil)
De quais desses ataques nosso adversário é capaz?
De quantos recursos ele dispõe?
63
Lidando com isso tudo (introdução)
Criptografia: ciência de manter mensagens seguras
– Criptografar == embaralhar de forma a só ser desembaralhado por
quem conhece uma chave
– É possível perceber se alguém alterou uma mensagem criptografada
Autenticação: prova uma identidade usando criptografia
Autorização: define que identidades podem fazer o que
Com autenticação + criptografia temos canais seguros:
– Partes sabem a identidade do outro lado do canal
– Esses canais provêem confidencialidade e integridade
– SSL provê essa abstração para um desenvolvedor
Note que cada técnica dessas tem um custo computacional e
administrativo
64
Outra forma de dividir tipos de ataque
Interceptação
–
Acesso a dados ou serviços não-autorizados
Interrupção
–
Pausa indevida na provisão de um serviço ou dado
Modificação
–
Alteração indevida no serviço ou dado
Invenção
–
São gerados dados que não deviam existir (ex.: novos
usuários)
65
Exemplo de modelo de segurança: OurGrid
Tipos de ataque considerados:
– Falsificação de identidade de usuário  Criptografia
– Cliente malicioso  Virtualização
– Servidor malicioso  Tolerância a sabotagem
Não consideramos DoS
– Quão ruim é isso?
Hoje as identidades têm que ser geradas por uma
autoridade
– Tradeoff simplicidade de uso vs capacidade de autorização
66
Lembrando onde estamos...
Já vimos:
– Modelos de interação
– Modelos de falha
– Modelos de Segurança
67
Que modelo usar para meu sistema?
Aquele que captura os aspectos essenciais, e nada mais
Exemplos:
– Se o objetivo é discutir segurança, convém levar
velocidade de processamento em conta?
– Se a camada de comunicação é segura, podemos discutir
apenas propriedades de mais alto nível
68
Onde esses modelos serão úteis nesse
curso?
Vocabulário para discutir propriedades de sistemas
distribuídos
Por exemplo:
– Que tipo de camada de comunicação é necessária para
implementar um BD distribuído?
– Usando UDP ou TCP, como muda o modelo de falhas do
sistema?
– Como tolerar falhas bizantinas? E crash?
– Como definimos os mecanismos necessários para a
segurança de um grid?
69
Recapitulando
Modelos  ferramenta para analisar propriedades de sistemas
distribuídos
Repertório de aspectos usados em modelos de SD:
Quanto à interação dos processos
– Assíncrono; Síncrono; Parcialmente Síncrono
Quanto às falhas que acontecem
– Nos processos; nos canais de comunicação
– De omissão, de tempo, arbitrárias
Quanto à segurança
– Modelos de ameaças
– Criptografia, autenticação, autorização e custo
70
Mais sobre esse assunto
Modelos:
– What good are models and what models are good?
Modelos de interação:
– Timed Asynchronous Distributed System Model
Modelos de falhas:
Segurança:
– A Taste of Computer Security
71
Cenas do próximo capítulo
72