Transações e Controle de
Concorrência
Redundância de
Arquivos e Tolerância a
Falhas
Prof. Dr. Norian Marranghello
Grupo 15
Cláudia Macedo Amorim
Tamer Albuquerque Pereira
Transações e Controle de
Concorrência
•Revisão de Conceitos
•Transações Atômicas
•Transações Distribuídas
•Propriedades das Transações
•Protocolos de Efetivação
• Serviços de Transações
•Serviços de Transações usando Transações Distribuídas
Transações e Controle de
Concorrência
• Serialização
•Controle de Concorrência
• Controle de Concorrência para transações que possuem
operações endereçadas em um único servidor
•Controle de Concorrência para transações distribuídas
Revisão de Conceitos:
• Transação atômica: ou é completamente realizada ou nenhuma de
suas operações é efetivada.
• Transação Distribuída: transação atômica que requer operações
em diversos servidores
= objeto
= transação T
Servidor X
Servidor Y
Cliente
Servidor Z
Revisão de Conceitos:
• Propriedades das Transações:
- Atomicidade;
- Consistência;
- Isolamento;
- Durabilidade.
• Protocolos de Efetivação
Two -Phase Commit Protocol
Serviços de Transação
• Definição: são serviços que disciplinam as transações provendo o
two-phase commit entre os objetos
Transações que possuem operações endereçadas em um único
servidor;
Transações Distribuídas
Serviços de Transação
Transações em um único servidor
• Coordenador :
•gerencia e cria cada transação
•Dá a cada transação um identificador (TID)
Figure 12.2 Transactional service operations.
OpenTransaction Trans;
starts a new transaction and delivers a
unique TID Trans. This identifier will be used
in the other operations in the transaction.
CloseTransaction(Trans) (Commit,
Abort)
ends a transaction: a Commit returned value
indicates that the transaction has committed;
an Abort returned value indicates that it has
aborted.
AbortTransaction(Trans)
Serviços de Transação
Transações Distribuídas
• Identificadores de transações para transações distribuídas devem
ser únicos dentro de um sistema distribuído.
• O coordenador que abriu a transação se torna o coordenador para a
transação distribuída e, até o final é responsável por efetiva-la ou
aborta-la
• . Cada um dos servidores que administram um objeto acessado pela
transação é chamado de participante
• Cada participante é responsável pela manutenção da rota de todos
os objetos recuperáveis no servidor envolvido na transação
•Os participantes são responsáveis pela cooperação com o
coordenador em prover o protocolo de efetivação.
•Durante o progresso da transação, o coordenador armazena uma
lista de referências dos participantes e os participantes armazenam
uma referência do coordenador.
Serviços de Transação
Transações Distribuídas
• O serviço de transações irá armazenar mais um método, o
método join, que é usado quando um novo participante se unir à
transação:
join (Trans, reference to participant)
•O coordenador armazena o novo participante à sua lista de
participantes. O fato do coordenador conhecer todos os participantes
e cada participante conhecer o coordenador torna-os capazes para
coletar as informações que serão necessárias na hora da efetivação.
• Obs:é possível para um participante chamar o método
abortTransaction no coordenador se por alguma razão ele não for
capaz de continuar com a transação.
Serviços de Transação
Transações Distribuídas
Exemplo:
coordenador
Participante X
join
A
openTransaction
closeTransaction
join
Participante Y
T
join
T = OpenTransaction
a.withdraw(4);
c.deposit(4);
b.withdraw(3);
d.deposit(3);
closeTransaction
cliente b.whithdraw(T,3)
B
Participante Z
C
D
Serialização
• A serialização assegura que se duas ou mais transações estiverem
rodando ao mesmo tempo, para cada uma delas e para os outros
processos , o resultado aparece como se todas elas rodassem
seqüencialmente em alguma ordem pré-definida dependente do
sistema.
Serialização
BEGIN_TRA NSA CTION
BEGIN_TRA NSA CTION
BEGIN_TRA NSA CTION
X = 0;
X = 0;
X = 0;
X = X+1;
X = X+2;
X = X+3;
END_TRANSACTION
END_TRA NSA CTION
END_TRANSACTION
(a)
(b)
(c)
Tempo 
Escalonamento 1 X = 0;
X = X+1;
X = 0;
X = X+2;
X = 0;
X = X+3; Legal
Escalonamento 2 X = 0;
X = 0;
X = X+1;
X = X+2;
X = 0;
X = X+3; Legal
Escalonamento 3 X = 0;
X = 0;
X = X+1;
X = 0; ;
X = X+2;
X = X+3; Ilegal
Controle de Concorrência
Transações em um único servidor
• Protocolos de Bloqueio
• Protocolo de Concorrência Otimista
• Protocolo de Timestamp
Controle de Concorrência
Transações em um único servidor
•Protocolos de Bloqueio
• bloqueio exclusivo - o servidor tenta bloquear qualquer objeto
que esteja prestes a ser usado por alguma operação da transação
do cliente. Se um cliente requisita acesso a um objeto que já
esteja bloqueado devido a outra transação de cliente , a
requisição é suspensa e o cliente deve esperar até que o objeto
seja desbloqueado.
bloqueio em duas fases
Primeira fase
Segunda fase
• alguns leitores / único escritor - várias transações
concorrentes lendo um objeto, ou uma única transação
escrevendo um objeto, mas não ambas . Dois tipos de bloqueio
são usados: bloqueio de leitura e bloqueio de escrita.
Controle de Concorrência
Transações em um único servidor
•
Protocolo de Concorrência Otimista
probabilidade de duas transações de clientes acessarem o
mesmo objeto  pequena
Controle de Concorrência
Transações em um único servidor
Protocolo de Timestamp
Rule Tc
1. write
Ti
read
2.
write
write
Tc must not write an object that has been written by any Ti where Ti >Tc
this requires that Tc > write timestamp of the committed object.
3.
read
write
Tc must not read an object that has been written by any Ti whereTi >Tc
this requires that Tc > write timestamp of the committed object.
Tc must not write an object that has been read by any Ti where Ti >Tc
this requires that Tc ≥ the maximum read timestamp of the object.
Controle de Concorrência
Transações em um único servidor
Protocolo de Timestamp
(a) T3
Before
T2
After
T2
(b) T3 write
write
Before
T1
Key:
T2
Ti
Committed
T3
After
T1
T2
T3
Ti
Time
Time
Tentative
(c)
T3 write
(d) T3 write
Before
T1
T4
After
T1
T3
T4
Time
Before
T4
After
T4
Transaction
aborts
Time
object produced
by transaction Ti
(with write timestamp Ti
T1<T2<T3<T4
Controle de Concorrência
Transações em um único servidor
Protocolo de Timestamp
(b) T3 read
(a) T3 read
T2
read
proceeds
Selected
T2
Time
T2
read
proceeds
Selected
Ti
Time
read waits
Selected
T4
Time
Committed
Ti
(d) T3 read
(c) T3 read
T1
T4
Key:
Tentative
Transaction
aborts
Time
object produced
by transaction Ti
(with write timestamp Ti)
T1 < T2 < T3 < T4
Controle de Concorrência
Transações Distribuídas
Cada servidor gerencia um conjunto de objetos e é responsável por
garantir que estes objetos permanecerão consistentes quando
acessados por transações concorrentes. Portanto, cada servidor é
responsável por aplicar controle de concorrência em seus próprios
objetos
• Protocolo de Bloqueio
•bloqueios em um objeto são mantidos localmente (no mesmo
servidor)
•o gerenciador não pode liberar bloqueios até saber que a
transação tenha sido efetivada ou abortada em todos os
servidores envolvidos nesta transação
Protocolo de Bloqueio - Transações Distribuídas
T
Write(A)
Read(B)
em X
U
locks A
Write(B)
em Y
locks B
Read(A)
em X espera T
em Y espera U
Protocolo Otimista
Transações Distribuídas
• Uma transação distribuída é validada por uma coleção de servidores
independentes, cada um dos quais valida transações que acessam
seus próprios objetos.
Protocolo Timestamps
Trasações Distribuídas
• é necessário que cada coordenador emita globalmente timestamps
únicos
• Um timestamp globalmente único de uma transação é emitido para o
cliente pelo primeiro coordenador acessado por uma transação
• . O timestamp de transação é passado ao coordenador através de
cada servidor que possui objetos que efetuam uma operação na
transação.
• os coordenadores devem concordar em como ordenar seus
timestamps.
Replicação de Arquivos e
Tolerância a Falhas
• Replicação
• Algoritmos de controle de réplicas
• Propagação de atualizações
• Algoritmo de votação por quorum
• Motivação para aplicação de Tolerância a falhas
• Validação de técnicas de tolerância a falhas
Replicação
• Motivos para o uso da replicação:
• Aumento da confiabilidade
• A queda de um servidor não pode derrubar um sistema
• A carga de trabalho é divida por vários servidores
Replicação(2)
• Confiabilidade-> Obtida através de backups
• Disponibilidade:
• Lema: “o espetáculo deve continuar”
• Dois problemas devem ser tratados: Falhas no servidor e
particionamento de redes e operação desconectada
Replicação(3)
• Alta confiabilidade e disponibilidade são requisitos essenciais para
sistemas críticos;
Exemplos de sistemas críticos:
- Centrais nucleares
- Controle de tráfego aéreo
- Bolsas de valores
Replicação(4)
• Desempenho: o fato de ter todos os arquivos em um único servidor
vai-se transformar seguramente em um gargalo para o desempenho;
• Consistência: operações com um grupo de objetos produzem
resultados que condizem com a especificação para esses objetos.
• Transparência: Clientes não devem estar cientes que existem
múltiplas cópias físicas de dados.
Algoritmo de Controle de
Réplicas
• Algoritmos baseados em cópias primárias
• Algoritmos baseados em cópias ativas
• Algoritmos baseado em gossip
Algoritmos baseados em
cópias primárias(1)
• Modelos que existem apenas um gerenciador de réplicas primário
• Podem ter um ou mais gerenciadores de réplicas secundários
• Caso o primário falha outro é provido a primário
Algoritmos baseados em
cópias primárias(2)
- Pedido;
- Coordenação
- Execução
- Acordo
- Resposta
Primary
C
FE
RM
RM
Backup
C
FE
RM
Backup
Algoritmos baseados em
cópias primárias(3)
• Este modelo pode ser usado onde o gerenciador de réplicas primário
se comporta em um meio não determinístico;
• Desvantagens:
Fornece enorme overheads
Fraca consistência
• Vantagens:
Alta disponibilidade
Bom desempenho
Algoritmos baseados em
cópias ativas(1)
• Gerenciadores de réplicas são máquinas de estados e são
organizados em grupos;
• Gerenciadores processam pedidos independentemente e
identicamente;
• Se houver crash em um gerenciador há impacto no desempenho;
Algoritmos baseados
cópias ativas(2)
- Pedido;
- Coordenação
- Execução
- Acordo
- Resposta
RM
C
FE
RM
RM
FE
C
Algoritmos baseados
cópias ativas(2)
• Vantagem: Garante consistência
• Desvantagem: Não garante linearlização.
Propagação de atualizações
por gossip(1)
• A arquitetura gossip provê dois tipos básicos de operações:
• Queries que são operações apenas de leitura
• Updates que modificam mas não lêem os dados
Propagação de atualizações
por gossip(2)
Service
- Pedido;
RM
- Resposta ao update
- Coordenação
RM
gossip
RM
- Execução
- Resposta à query
- Acordo
Query,
prev
Val,new Update,
prev
FE
Update id
FE
Query Val
Update
Clients
Propagação de atualizações
por gossip(3)
• O tempo de demora para que todos os gerenciadores de réplicas
receba uma dada atualização depende de 3 fatores:
• A freqüência e duração das partições de rede
• A freqüência com o qual os servidores de réplicas enviam
mensagens gossip
• A política de escolha de um parceiro com o qual serão
trocadas as mensagens gossip
Algoritmo de votação por
Quorum(1)
• É um esquema de replicação de arquivos onde o número de votos é
atribuído a cada cópia física de um único arquivo em um gerenciador
de réplicas;
• Cada voto pode ser considerado como um peso a mais no desejo do
uso de uma cópia particular;
• Cada operação de leitura deve obter primeiro uma leitura do quorum
de R votos antes de poder efetuar a leitura, o mesmo ocorre com a
escrita;
Algoritmo de votação por
Quorum(2)
• O algoritmo de votação de quorum garante a consistência de
arquivos;
• Garante também que quaisquer pares, consistindo de quorum de
leitura e escrita ou dois quora de escrita, devem conter cópias
comuns;
• Portanto, não é possível realizar operações conflitantes na mesma
cópia mas em partições diferentes;
Motivação para aplicação
de tolerância a falhas(1)
• Garante alta confiabilidade e disponibilidade;
• Necessária em aplicações com restrições de tempo;
• Necessária em sistemas críticos;
Motivação para aplicação
de tolerância a falhas(2)
• Como resolver falhas!?
Através dos algoritmos de replicação de arquivos!!. Estes algoritmos
resolvem principalmente a inconsistência de arquivos sob escrita
concorrente
Validação de técnicas de
tolerância a falhas(1)
Como saber se as técnicas implementadas resulta realmente em
aumento de confiabilidade??
Através da injeção de falhas no sistema(simulação). A principal função
da injeção de falhas é a validação.
A injeção de falhas pode ser vista, então, como um procedimento de
teste da eficácia de técnicas de tolerância a falhas.
Validação de técnicas de
tolerância a falhas(2)
• Vantagens:
Baixo custo;
Baixa complexidade;
Baixo esforço de desenvolvimento;
• Desvantagens:
A execução do software responsável pela injeção de falhas
afeta as características de temporização do sistema,
prejudicando a execução de funções críticas no tempo