Sistemas Distribuídos
Tempo e sincronizaçã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
Construíndo sistemas
Sistemas construídos
3
Objetivos
Entender como garantir que processos entreguem
mensagens em uma dada ordem
– Ordenação total
– Ordenação causal
Entender como organizar sincronizar condições de
corrida em um sistema distribuído
4
Sincronismo
Sincronia é a organização de eventos no tempo
Investigaremos 2 aspectos de sincronia:
– Como diferentes processos organizam sua visão de eventos
no tempo: ordenação de eventos
– Como processos se organizam no tempo para acessar um
recurso: exclusão mútua
5
Mantendo a ordem
Várias vezes, queremos que a ordem de eventos em
diferentes processos seja a mesma
– Mensagens recebidas por um grupo de réplicas
– Fornecimento e cancelamento de leases
Exemplo no DB distribuído da Yahoo!:
PNUTS provides a consistency model that is between the two extremes of general
serializability and eventual consistency ... We provide per-record timeline
consistency: all replicas of a given record apply all updates to the record in the
same order .... The application [can] indicate cases where it can do with some
relaxed consistency for higher performance .... [such as reading] a possibly stale
version of the record.
6
O problema da ordem de mensagens
P1
P2
m3
m1
m2
P3
Como garantir que processos têm a mesma visão da
ordem das mensagens?
– Necessário para replicação
7
Solução 1: sincronizamos relógios e usamos
timestamps
– Se o sistema é sincrono, isso é factível
– Se é assíncrono, podemos usar aproximações
Solução 2: inventamos um tempo lógico
– Boa parte do tempo, só queremos saber o que acontece
antes do que
8
O tempo e relógios
Os relógios de nosso sistema necessitam de um referencial
– Referencial externo
– Sincronização interna de relógios
O referencial externo absoluto é a Terra
– Mas a Terra está desacelerando!
– Além do que turbulências no núcleo do planeta precisam ser levadas
em conta
O Bureau International de l’Heure cuida disso:
– Monitora a hora solar e ajusta um relógio de alta precisão a ela
– Publica a hora correta (UTC) para o mundo: ondas curtas e satélites
9
Ajustando o tempo
O problema é deixar o relógio de p1 o mais próximo possível do
de p2
– Seja P2 um servidor com o tempo UTC ou náo
Como lidar com os atrasos de mensagem se o sistema for
síncrono?
– P1 envia tempo para P2 e conhecemos min e max no envio da
mensagem
E se o sistema é assíncrono?
T2
P1
T3
T4
P2
T1
10
Network Time Protocol
Um dos protocolos mais antigos da Internet
Atinge precisão de 1/100s na Internet e até
20 microssegundos em LANs
11
Tempo e relógios lógicos
Por vezes, os relógios dos processos não precisam estar
em UTC, apenas concordarem suficientemente
Por vezes, eles não precisam concordar na hora
também; basta concordar em o que acontece antes
do que
Duas soluções bem conhecidas:
– Relógios lógicos de Lamport
– Marcas de tempo (ou relógios) vetoriais
12
Relógios lógicos de Lamport
Idéias chave:
–
–
Queremos poder dizer se e  e’; não queremos dizer o quanto
Só queremos ordenar eventos entre processos que interagem
Ordenamos eventos em duas situações:
1.
2.
Se e1 e e2 aconteceram em um mesmo processo, o processo sabe se
e1  e2
Se e1 é o envio de uma mensagem e e2 seu recebimento, e1  e2
Note que  é transitivo
13
•
•
•
•
Cada processo tem um contador C
A cada evento local, C += 1
C vai em toda mensagem enviada
Quando p1 recebe uma mensagem de p2, C = max(Cp1, Cp2)
Se a  b, então C(a) < C(b)
Se C(a) < C(b), então a  b ??
14
Exemplo: Multicast totalmente ordenado
Podemos garantir consistência entre réplicas com essa primitiva
– Mensagens dos clientes chegam sempre na mesma ordem aos
servidores
V0: uma abordagem centralizada
Com os relógios de Lamport, podemos fazer isso de maneira
distribuída:
– Processos se comunicam por multicast, mensagens recebidas são
enfileiradas de acordo com ts(m)
– Para cada mensagem, cada processo envia ‘reconheço’
– Uma mensagem só é entregue se está na frente da fila e depois de
receber ‘reconheço’ de todos
Em outras palavras, p só entrega m depois que os contadores de todos os
outros processos são maiores que o timestamp lógico de m
(assume que m1 de p1 chega antes de m2 de p1)
(desempates com id do processo)
15
P1
C=(1)
P2
P3
16
O que acontece com a mensagem vermelha?
P1
P2
P3
17
Note que eventos potencialmente concorrentes
também são ordenados (ordem total)
P1
P2
P3
18
Mais sobre multicasts
T1
Há diferentes
semânticas para
ordenação das
mensagens
– FIFO por processo
– Total
– Causal
• Se C(a) < C(b), então
a deve ser entregue
antes de b
T2
F1
F3
F2
T ime
C1
C2
P1
C3
P2
P 319
Relógios vetoriais
O relógiode Lamport não é suficiente para decidir se há causalidade:
– No relógio de Lamport a  b implica C(a) < C(b), mas o contrário não é
verdadeiro
Relógios vetoriais são um construto para isso
– Cada processo mantém um vetor de relógios lógicos com um contador para
cada outro processo, VCi[j]
• VCi[i] é incrementado a cada evento
• i envia VCi de carona em cada msg m como ts(m) (um vetor!)
– Ao receber VCi , k faz VCk[j]  max(VCk[j], ts(m)[j]) para cada j
• k sabe quantas mensagens i processou
– Mensagem é entregue se:
• ts(m)[i] == VCk[i] + 1
• ts(m)[j] == VCk[j] para todo j ≠i
(msg é a próxima esperada de i)
(k viu tudo que i viu antes de enviar m)
20
Multicast ordenado por causalidade
VC1=(1,0,0)
P1
VC1=(1,1,0)
P2
P3
VC2=(1,1,0)
VC3=(0,0,0)
VC3=(1,1,0)
VC3=(1,0,0)
21
Mensagens sem causalidade não são mais ordenadas
– Equivale à ordenação total se processos apenas respondem
mensagens (ou estão sincronizados como com condição de corrida)
– É mais barato que ordenação total
P1
VC1=(1,0,0)
VC1=(1,0,1)
P2
VC2=(1,0,1)
VC2=(1,0,0)
P3
VC3=(0,0,1)
VC3=(1,0,1)
22
Quem deve implementar isso?
Multicasts assim estão implementados em bibliotecas
como ISIS, Horus e Ensemble
– Usados em bolsas de valores, controladores de tráfego e
coisas assim
Argumento fim-a-fim: quem deve implementar a lógica
de causalidade
– Middleware  mais simplicidade, menos inteligência
– Applicação  mais complexidade, mais inteligência
23
Onde estamos
Sincronia é a organização de eventos no tempo
Agora nos interessam 2 aspectos:
– Como diferentes processos organizam os mesmos eventos
no tempo: ordenação
– Como processos se organizam no tempo para acessar um
recurso: exclusão mútua
24
Exclusão mútua distribuída
Lembre que em SDs, concorrência é a norma
–
–
Necessitamos de sincronismo entre processos para
acessar um recurso
Não temos semáforos ou variáveis compartilhadas
Duas abordagens para exclusão mútua em SDs:
1. Baseada em fichas (token-based)
2. Baseada em permissão
25
Antes dos detalhes
Note que o problema é semelhante a acesso ao meio em redes
Consideramos um sistema assíncrono sem falhas e com links
confiáveis
Queremos duas propriedades
– Safety: no máximo um processo está na região crítica em cada instante
– Liveness: requisições para entrar na região crítica em algum momento
dão certo
Aparte: safety e liveness são conceitos úteis em SDs
26
Algoritmo 1: centralizado
Um nó é eleito coordenador e mantém a fila de reqs
– Simplicidade e eficiência vs. Escalabilidade e robustez
27
Algoritmo 2: decentralizado
Podemos replicar o coordenador
– rname-1, rname-2, rname-n em uma DHT
Para obter o lock, p precisa de m > n/2 permissões de
coordenadores
Potencialmente robusto, mas se há falhas, é
probabilístico
Claro que para alguns casos isso é bom o suficiente
28
Algoritmo 3: distribuído
Baseado em relógios lógicos de Lamport
– Requer ordenação total
Processos fazem multicast de requisições pela RC e só
entram nela após receber permissão (‘reconheço’)
de todos
– Requisições com tempos lógicos menores têm prioridade
– Cada processo mantém variável que contrla RC: [ released
| requested | held ]
29
Determinístico
Custo: (n-1) requisições + (n-1) respostas
Falha de qualquer processo necessita de recuperação
– Respostas negativas aumentam isso com maior custo
Custo cai um pouco usando maiorias em lugar de unanimidades30
Decentralização + token, versão 1
Nó que tem o token tem direito à RC
Token guarda quando cada nó acessou a RC
Quando acaba, dono do token passa-o para próximo processo
com requisição pendente
31
Mais barato:
– N-1 requisições + 1
resposta
– Apenas falhas do
dono do token são
críticas
32
Token ring
Dono do token o usa e o passa
adiante
– Simples
– Eficiente com muita carga
Necessidade de reconfigurar anel
sempre que há falhas
33
Recapitulando
Ordenando eventos no tempo
– Sincronismo de relógios físicos
– Relógios lógicos de Lamport
– Relógios vetoriais
Ordenando acesso a uma região crítica
–
–
–
–
Algoritmo decentralizado
Algoritmo decentralizado
Algoritmo distribuído
Algoritmos baseados em ficha
34
Mais sobre esse assunto
Sincronização de relógios
– Artigo dando uma visão geral sobre o problema e soluções
Ordenação de eventos
– Post em um bom blog sobre o Yahoo PNUTS
– Texto de 1993 explicando uso de multicast ordenado em
diversas aplicações
– Artigo criticando a ordenação de mensagens em
middleware e resposta de K. Birman
– Spread, um toolkit de comunicação em grupo
35