Arquiteturas e Modelos

Nazareno AndradeUniversidade Federal de Campina Grande

02/2008

Sistemas Distribuídos

2

FundamentosCoordenando processosConstruíndo sistemasSistemas construídos

3

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 processosConstruíndo sistemasSistemas construídos

4

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

5

Arquiteturas de sistemas distribuídos

6

Arquitetura == Arte de edificar

7

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

8

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

9

FIGURA DO TANENBAUM

Estilos arquiteturais

10

Arquitetura de sistema

Como os componentes estão distribuídos na prática?

Arquiteturas centralizadas

Arquiteturas descentralizadas

Arquiteturas híbridas

11

Arquiteturas centralizadas

Arquiteturas descentralizadas

Arquiteturas híbridas

12

Arquiteturas centralizadas

Comumente referida como Cliente-ServidorClientes 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

13

Dividindo responsabilidades

O que fica no cliente, o que fica no servidor?Consideremos uma aplicação em 3 camadas:

14

Como dividir?

15

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

16

Arquiteturas centralizadas

Arquiteturas descentralizadas

Arquiteturas híbridas

17

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

18

Redes de sobreposição

Os componentes estão organizados numa rede lógicaChamamos 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

19

Topologias não-estruturadasSe 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 assimMulticast no nível da aplicação pode usar o

mesmoCDNs também

20

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

21

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

22

Exemplos: Kazaa, Skype, JXTA (randomized walks)

23

Supernós do Skype em 2007

24

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

25

==

26

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

27

Exemplo: Chord

Nós são organizados em um anelO item k é mapeado para o nó com menor id com id ≥ k

28

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...

29

Exemplo 2: CAN

Chord usa um espaço de ids unidimensionalCan usa um espaço multidimensional

30

Centralizado vs. descentralizado

Descentralização: – Escalabilidade– Robustez– Complexidade

Arquiteturas centralizadas

Arquiteturas descentralizadas

Arquiteturas híbridas

Centralização: – Simplicidade de

implementação– Simplicidade de gerência– Gargalo em potencial

31

Arquiteturas centralizadas

Arquiteturas descentralizadas

Arquiteturas híbridas

32

Diretório centralizado, função distribuída

Napster, MSN, BitTorrent, GoogleFS, ...Diretório é simples e razoavelmente escalável se centralizado

33

Serviço descentralizado, interação cliente-servidor

OriginServer

Coralhttpprxdnssrv

Coralhttpprxdnssrv

Coralhttpprxdnssrv

Coralhttpprxdnssrv

Coralhttpprxdnssrv

Coralhttpprxdnssrv

Browser

Browser

Browser

Browser

CDNs, OurGrid, ...

34

Recapitulando

Estilos arquiteturais de softwareArquitetura 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

35

Modelos de sistemas distribuídos

36

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 processosConstruíndo sistemasSistemas construídos

37

O que é um modelo?

Representação abstrata de um objeto de estudoObjetivo: analisar propriedades desse objeto

Tipicamente é mais simples que o objetoSimplicidade Análise

Complementam a experimentaçãoAjudam a entender resultados do experimentoPodem explorar espaço de possibilidades com menos custos

38

Resultados de modelos

Normalmente fazemos o seguinte: 1. Simplificamos a realidade2. Analisamos processos ou entidades que importam3. Derivamos resultados relevantes para a realidade

Resultados geralmente são de impossibilidade ou de custo

39

Exemplo de uso de modelo

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 processamentoPoré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

p

qt1

servidor

40

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

41

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

42

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!

43

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?

44

45

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?

46

Variantes do modelo de interação

Com relação às considerações:

Modelo síncronoModelo assíncronoModelo parcialmente síncrono

Sincronismo : coordenação no tempo de ocorrência de fatos ou eventos (Houaiss)

47

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

48

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

49

Modelo assíncrono

Não há limites conhecidos para: 1. Execução de uma instrução por um processo2. Demora na transmissão de uma mensagem3. Drift no relógio dos processos

Modelo com menos considerações Modelo mais geral

Infelizmente, tipicamente serve para provar impossibilidades

50

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...

51

Modelos parcialmente síncronos

Alguma sincronia facilita o desenvolvimento de algoritmos distribuídos

O sistema pode ser síncrono durante um períodoO sistema pode ser síncrono em uma parte

52

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

53

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 2

Interface 1

Interface 2

Canal dedicado, sem congestão

54

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

55

Modelo de falhas

Processos e canais podem falharFalha: sair do comportamento esperado

Tipos de falha:– Omissão – Tempo– Arbitrária

56

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

57

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

58

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 contornarEmbora aconteçam: exemplos do PlanetLab e Amazon

59

Outro exemplo de modelos

Exemplo p. 5x do CDK. Consenso com e sem crashes.

60

Lembrando onde estamos...

Já vimos: – Modelos de interação– Modelos de falha

Falta:– Modelos de Segurança

61

Modelos de segurança

Confidencialidade: Não pode haver acessos não-autorizados

Integridade: Não pode haver alterações não-autorizadas

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?

62

Ataques a recursos

O adversário é capaz de fazer requisições não-autorizadas– 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 servidorO cliente deve conseguir verificar a identidade do servidor

63

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?

64

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 criptografiaAutorizaçã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

65

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)

66

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

67

Lembrando onde estamos...

Já vimos: – Modelos de interação– Modelos de falha– Modelos de Segurança

68

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

69

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?

70

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

71

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

72

Cenas do próximo capítulo