Arquitetura de sistemas distribuídos

Prévia do material em texto

Click to edit Master title style
Click to edit Master subtitle style
*
*
*
Arquitetura de sistemas distribuídos
Ingrid Jansch Pôrto
2006
Agradecimentos a Taisy Silva Weber pelo conjunto de slides original, a partir do qual este foi realizado.
Ingrid Jansch Porto
*
*
Arquitetura de sistemas distribuídos
Material baseado
Pankaj Jalote. Fault Tolerance in Distributed Systems. Prentice Hall, 1994.
Mukesh Singhal & Niranjan Shivaratri. Advanced Concepts in Operating Systems. McGraw Hill, 1994.
Sape Mullender. Distributed Systems. Addison-Wesley, 2nd edition, 1994.
Ingrid Jansch Porto
*
*
Níveis
processador fail-stop, armazenamento estável,
comunicação confiável, consenso bizantino, 
difusão confiável e atômica
recuperação para um estado consistente
resiliência de dados
resiliência de processos
ações atômicas
software tolerante a falhas
serviços
blocos
básicos
sistema distribuído
Ingrid Jansch Porto
*
*
Sistemas distribuídos
Modelos de Sistemas Distribuídos (SD): modelos físico e lógico; comunicação entre processos
Relógios lógicos e ordenação de eventos
Estado global do SD
Canais de comunicação
Modelos de computação. Modelos de defeitos
Acordo bizantino
Ingrid Jansch Porto
*
*
Modelos de sistemas distribuídos
Modelo físico: definido pelos componentes físicos do sistema. Ë o nível de realização da computação (rede real). 
Modelo lógico: definido do ponto de vista do processamento ou da computação. Corresponde ao ponto de vista do usuário; serve de base para a definição de serviços.
Em sistemas robustos, o modelo lógico é independente das falhas que ocorrem sobre o modelo físico.
Ingrid Jansch Porto
*
*
Sistemas distribuídos
sem memória compartilhada
sem relógio global
modelos
modelo físico
modelo lógico
 nodos e rede
processos e canais
o modelo físico é de interesse secundário nessa disciplina; entretanto, para melhorar o desempenho, características físicas especiais do meio podem ser consideradas
processador
relógio local
memória local volátil
armazenamento não volátil
interface de rede
software
Ingrid Jansch Porto
*
*
Modelo físico
processador
memória
local
relógio
local
disco
interface
de
rede
NODO i
- memória não é compartilhada com demais nodos
- o relógio é local a cada nodo
NODO k
mensagens
NODO j
Ingrid Jansch Porto
*
*
Comunicação:
topologias ponto a ponto
totalmente
conectado
estrela
árvore
Ingrid Jansch Porto
*
*
Topologia barramento
barramento
comum
nodos
nodos
uma mensagem enviada pelo barramento pode ser recebida simultaneamente por todos os nodos (broadcast) 
bus, barra ou via
Ingrid Jansch Porto
*
*
Modelo lógico
aplicação distribuída
conjunto de processos concorrentes
processos cooperam para realizar uma computação
cada processo é seqüencial
progresso finito
nada pode ser dito sobre velocidades relativas entre os processos
cada processo pode estar em um nodo diferente
todos os processos avançam na execução
Ingrid Jansch Porto
*
*
Modelo lógico
rede completamente conectada
topologia não é considerada
processos e canais
existe um canal entre quaisquer dois processos que interagem
canais com buffer infinito e livres de erros
canais entregam mensagens na ordem que foram enviadas (ordem preservada no canal)
Observe-se que estas características não são necessariamente válidas para o meio físico
Ingrid Jansch Porto
*
*
Modelo lógico
ordenação de mensagens
ordem das mensagens é preservada em um canal
nada é estabelecido sobre mensagens que chegam a um nodo vindos de diferentes canais
não existe ordenação total de mensagens, apenas ordenação parcial
razão: retardos nos canais (delay)
Ingrid Jansch Porto
*
*
Canal
c b a
c b a
p i
p j
canal
ordem de mensagens
preservada
processo
no modelo físico, as mensagens a, b e c podem trafegar por rotas diferentes
ordem de envio
Ingrid Jansch Porto
*
*
Canal
p a
p d
p c
p b
x y
x y
m n
m n
m x y n
x m n y
ordem parcial preservada
ordem total não preservada
Ingrid Jansch Porto
*
*
Sistemas síncronos e assíncronos
sistema síncrono
existe um limite de tempo finito e conhecido
sistema correto opera dentro desse limite
sistema assíncrono
não existe um limite de tempo
impossível determinar se o sistema está simplesmente atrasado por sobrecarga ou se está com defeito
definidos pela existência de limites de tempo
Ingrid Jansch Porto
*
*
Limites de tempo
canal de comunicação síncrono
retardo (delay) máximo é conhecido
processador síncrono
tempo de execução de um conjunto de instruções é conhecido e limitado
existem limites de tempo que podem ser estabelecidos para determinar a conclusão de uma atividade
Ingrid Jansch Porto
*
*
Vantagem do sistema síncrono
detecção de defeito
defeito de um componente do sistema pode ser deduzido pela ausência de resposta
timeout
usado para detectar defeitos em nodos e perda de mensagens
se um nodo não reponde após certo intervalo de tempo
	sistema síncrono - nodo com defeito
	sistema assíncrono - nada se pode afirmar
Ingrid Jansch Porto
*
*
Classificação de defeitos
colapso ou crash
uma falha que causa a parada de um componente ou a perda do seu estado interno
omissão
um componente não responde a determinadas entradas
engloba crash
temporização
o componente responde ou muito cedo ou muito tarde
engloba omissão
modelo de Cristian
mais restritiva de todas as classes
também chamada falha de desempenho
Ingrid Jansch Porto
*
*
Classificação de falhas 
resposta
computação incorreta, o componente produz respostas incorretas para algumas entradas
não engloba as anteriores
bizantinas (arbitrárias ou maliciosas)
falha arbitrária que provoca um comportamento totalmente arbitrário e imprevisível do componente durante o defeito
engloba todas as classes de falhas
considerada caso especial de bizantinas
Ingrid Jansch Porto
*
*
Classificação de falhas
resposta
temporização
arbitrária
omissão
crash
comportamento totalmente arbitrário e imprevisível
respostas
incorretas
para algumas entradas
resposta adiantada ou retardada
sem resposta para
algumas entradas
parada ou perda do
estado interno
Ingrid Jansch Porto
*
*
Exemplos de classes de falhas
Processador:
crash ou bizantinas
Rede de comunicação: todos os tipos
Clock:
temporização ou bizantinas
Meio de armazenamento
temporização, omissão ou resposta
Software: resposta
Ingrid Jansch Porto
*
*
Modelos de falhas
Fred B. Schneider
Failstop (detectável pelos demais)
Crash (Lamport and Fischer, 1982)
crash + link (Budhiraja et al., 1992)
omissão de recepção (Perry and Toueg, 1986)
omissão de envio (Hadzilacos, 1984)
omissão geral (Perry and Toueg, 1986)
comportamento bizantino (Lamport, Shostak and Pease, 1982)
várias classificações diferentes na literatura, mas que não diferem muito das de Cristian e Schneider
Ingrid Jansch Porto
*
*
Comunicação entre processos
troca de mensagens
SEND e RECEIVE
primitivas de comunicação e sincronização
RPC (remote procedure call)
mais alto nível que SEND e RECEIVE
interação cliente / servidor
invocação remota de métodos
orientação a objetos
Ingrid Jansch Porto
*
*
Comunicação entre processos
troca de mensagens
assíncrona
síncrona (sem buffer - CSP)
troca de mensagens assíncrona
buffer infinito
transmissor nunca bloqueia
buffered message passing
buffer finito
opera assincronamente até buffer ficar cheio
Ingrid Jansch Porto
*
*
Comunicação entre processos
RPC
call service (value_args, result_args)
comunicação síncrona
falhas executando RPC
órfãos
execuções indesejadas de procedimento remoto, ocasionada por defeito durante invocação
ordem de chamadas
Ingrid Jansch Porto
*
*
Orientação a objetos
modelo orientado a objetos
outro paradigma de comunicação de alto nível
atualmente muito popular
um processoexecuta um método em um objeto particular
objeto pode residir em qualquer nodo
processo envia mensagem ao objeto 
objeto executa uma ação e retorna resultado
Ingrid Jansch Porto
*
*
Ordenação de eventos
dificuldade de determinar relações temporais
RAZÃO: inexistência de clock global
problema
determinar ordenação temporal de eventos que ocorrem em nodos diferentes, medidos por relógios diferentes
relação: a “aconteceu antes de” b : a b
Ingrid Jansch Porto
*
*
Ordenação de eventos
ordem parcial
se a e b são eventos do mesmo processo e a é executado antes de b então a  b
se a é send e b é receive da mesma mensagem então a  b
a  b e b  c então a  c
eventos concorrentes:
nem a  b, nem b  a
Ingrid Jansch Porto
*
*
Clocks lógicos
Lamport (78)
meio de assinalar um número a um evento
nenhuma relação com o tempo físico
sistema de clock lógico
Ci - clock local ao proc Pi, C - sistema de clock
um sistema de clock lógico é correto se é consistente com a relação 
 		para quaisquer eventos a e b,
 		se a  b então C(a) < C(b)
relógios lógicos
Ingrid Jansch Porto
*
*
Clocks lógicos
clock lógico
carimba um evento de forma que a relação de ordem parcial é mantida
pode ser facilmente implementado
usando contadores
numerando mensagens com numeração crescente
exemplo de implementação: timestamp T
a maior parte dos problemas de ordenação podem ser resolvidos com clocks lógicos, sem necessidade de relógios físicos sincronizados
Ingrid Jansch Porto
*
*
Timestamps
Pi inclui seu timestamp nas mensagens m que envia
Tm: timestamp da mensagem m 
Duas condições:
cada Pi incrementa Ci entre 2 eventos sucessivos
recebendo mensagem m com Tm , Pj torna Cj maior ou igual ao seu valor atual e maior que Tm
Ci - clock local ao processo Pi
Ingrid Jansch Porto
*
*
Timestamps
as duas condições asseguram realização da ordem parcial
implementação:
um contador por nodo é suficiente
impossível assinalar timestamps consistentes com a relação de ordem parcial puramente usando relógios físicos
clocks físicos precisariam ser sincronizados para assegurar a relação de ordem parcial
Ingrid Jansch Porto
*
*
Ordenação total com clock lógico
relógio lógico pode ser usado para ordenação total (Lamport 78)
mensagens de diferentes processos podem possuir o mesmo timestamp
se duas mensagens possuem o mesmo timestamp devem ter sido originadas em diferentes processos
para estabelecer uma ordem, basta ordenar os processos de alguma forma
a mesma forma de ordenação deve ser seguida por todos os processos 
Ingrid Jansch Porto
*
*
Ordenação total
uma implementação possível
eventos com mesmo timestamp são ordenados pela ordem lexicográfica dos nomes dos processos
preserva a relação de ordem parcial 
todos os nodos classificam os eventos na mesma ordem,
não assegura preservação de ordem temporal dos eventos concorrentes
se a ordem temporal for importante, clocks lógicos não podem ser empregados
Ingrid Jansch Porto
*
*
Exemplo
p a
p d
p c
p b
a1 a2
b1 b3
ordem parcial preservada
a2
a1 b1 a2 b3 
ordem total preservada
b1 a1 b3 a2 
Pb recebe a2 após enviar b1
Pb envia b1 antes de Pa enviar a1
a1 b1 a2 b3 
Ingrid Jansch Porto