Transacções em Sistemas Distribuídosdisciplinas.ist.utl.pt/~leic-sod.daemon/2010-2011/teoricas_tagus/7... · Interblocagem • A sincronização com trincos pode conduzir a interblocagem

1

Departamento de Engenharia Informática

Transacções em Sistemas Distribuídos


Exemplo

O Senhor Silva é possuidor de duas contas em bancos diferentes (A e B) e pretende fazer um movimento de 100 E do banco A para o banco B. O procedimento para fazer esta transferência pode ser o seguinte:

transferencia (bancoA, bancoB, Valor)

{

LerSaldo (bancoA, SaldoA); /* obtendo 200 E */

LerSaldo (bancoB, SaldoB); /* obtendo 200 E */

ActualizarSaldo (bancoA, saldoA-Valor);

ActualizarSaldo (bancoB, saldoB+Valor);

}

2


Transacção Atómica

transferencia (bancoA, bancoB, Valor)

{

begin_transaction;

LerSaldo (bancoA, SaldoA);

LerSaldo (bancoB, SaldoB);



commit;

}


Transacção Atómica

transferência (bancoA, bancoB, Valor)

{

begin_transaction;

LerSaldo (bancoA, SaldoA);

LerSaldo (bancoB, SaldoB);

if (Valor > SaldoA) abort

else

{



commit;

}

}

Diferentes condições para a transacção ser interrompida

3


Transacções Atómicas Locais(Revisão da cadeira de Bases de Dados)


Propriedades das transacções – ACID

• Atomicidade – Transacção ou se executa na totalidade ou não se

executa.

• Consistência – Transacção deve manter invariantes associados à

aplicação (transita de estado consistente para outro estado consistente)

4


Propriedades das transacções - ACID

• Seriabilidade (Isolation) – se diversas transacções se executarem em paralelo

sobre os mesmos objectos, tudo se passa como se as transacções se executassem em série numa determinada ordem.

• Persistência (Durability) – os resultados de uma transacção que confirmou

permanecem depois de esta acabar e sobrevivem ao conjunto de faltas expectáveis

Atomic, Consistent, Isolated, Durable


Tipos de Transacções

• Localização• Duração• Estrutura

– Plana (flat) – Aninhada (nested)

• Aninhada (nested) – Uso de subtransacções permite controlar o grau de atomicidade da aplicação– Em operação complexa pode-se não querer eliminar tudo o que já

foi feito, mantendo atomicidade global– Pode-se evitar desfazer as partes consistentes da actualização

• Pontos de salvaguarda intermédia para a recuperação

Exemplo de transacção aninhada

5


Sistema Transaccional

Aplicações


IniciarConfirmarAbortar

LerEscrever

Sistema Operativo

Hardware

Aplicações


Implementação das Propriedades Transaccionais

• Atomicidade – Possível mecanismo: escrever escritas num diário (log)

e apenas torná-las visíveis após commit

– O sistema tem de ser capaz de repor a situação inicial no caso da transacção abortar (por inciativa do programador ou falha do sistema)

6


Implementação das Propriedades Transaccionais

• Persistência – Resultados escritos em memória estável e com

capacidade de recuperação das faltas dos discos que forem toleradas.

• Consistência – Apenas relacionada com o ambiente de programação

(aplicação).– A consistência pode ser expressa e verificada por um

conjunto de invariantes que o ambiente de programação pode utilizar


Isolamento

• Objectivo:– Criar história de execução das transacções serializadas.

• Uma história é serializada (serially-equivalent) se para qualquer duas transacções Ti e Tj todas as operações de Ti aparecerem antes de Tj ou vice-versa.– Reads retornam o mesmo valor, e variáveis instanciadas dos objectos

ficam com o mesmo valor no fim (comparativamente à execução em série)

É possível encontrar uma história serializada desta execução?

7


Concorrência

Problema das escritas perdidas

Problema das leituras inconsistentes

Execuções equivalentes a história serializada


Recuperação de Aborts

• Dirty Read– Interacção entre

uma operação read de uma transacção e operação write anterior noutra transacção no mesmo objecto

– Estratégias• Atrasar commits• Evitar cascading

aborts

• Escritas prematuras (“Premature Writes”)

– Interacções entre operações write de transacções diferentes no mesmo objecto

Os servidores devem salvar todos os efeitos de todas as transacções confirmadas e nenhum dos efeitos das transacções abortadas

8


Isolamento (cont.)

• Solução pessimista (“pedir licença”)– Pressupõe que os conflitos são frequentes e obriga à prévia

sincronização de todos os acessos.

• Solução optimista (“pedir desculpa”)– Considera que os conflitos são raros– Na confirmação verifica a existência de conflitos– Obriga a manter carimbos temporais das actualizações para

poder determinar quando há um conflito e nesse caso abortar as transacções envolvidas

Leitura EscritaLeitura Compatível ConflitoEscrita Conflito Conflito

Trincos de Leitura/Escrita


Trincos Exclusivos - Exemplo

• Implementação: Instância de Gestor de Trincos em cada servidor, várias instâncias de Trincos

• Para melhor desempenho, adoptar solução que permita várias transacções executarem em paralelo se não executarem operações em conflito sobre os mesmos objectos– Várias transacções

podem ler de um objecto em paralelo, mas apenas uma única pode escrever

– read, write locks

9


Trincos Hierárquicos


Modelo de Sincronização: Sincronização com Trincos

• Sincronização em duas fases estrita (strict two phase locking)– Na primeira fase a transacção começa por adquirir

sucessivamente todos os trincos que lhe permitem aceder aos objectos.

– Na segunda fase liberta-os.

10


Interblocagem

• A sincronização com trincos pode conduzir a interblocagem obrigando a mecanismos para a resolver:– Prevenção (ex: ordem parcial sobre trincos, adquirir todos

os trincos pela mesma ordem, caso sejam conhecidos de antemão)

• Problema: na maior parte das vezes não é possível, e origina quebra de desempenho

– Detecção da interblocagem• usando temporizador – método simples , pouco preciso, mas

adequado• ou grafo com história de sincronização das transacções (indica

recursos protegidos por trincos e as transacções que esperam por eles)

• e obrigando a abortar as transacções


Interblocagem: exemplo

11


Detecção da interblocagem - Grafos


Outro exemplo

• Apesar de cada transacção esperar “wait” apenas por um Lock, no grafo pode aparecer em vários ciclos de interblocagem

12


Solução optimista


Concurrência Optimista - Validação

• Validação Backward– Verifica se algum conjunto de reads da transacção intersecta com conjunto de

writes de transacções concurrentes anteriores

• Validação Forward– Verifica se algum conjunto de writes da transacção actual intersecta com conjunto

de reads de transacções concurrentes activas no momento

13


Recuperação das Falhas de Paragem

• A recuperação tem de basear-se na existência de informação redundante.

• A política de recuperação é condicionada pela política de actualização dos dados:– actualização directa (in-place updating) - as escritas

são efectuadas sobre os dados reais residentes nos suportes magnéticos.

– actualização em versões (out-of-place updating) - são criadas novas versões dos dados, preservando os valores originais.


Actualização Directa

• A política de recuperação depende da forma como é actualizada a cache.

• No momento da confirmação:– Limpar a cache (cache flush) na altura da confirmação – ou– Manter os dados em cache

• No momento da escrita de dados– Permitir a escrita de dados de transacções activas na memória persistente.– ou– Manter os dados das transacções activas apenas em memória volátil

(gestão assíncrona)

• Necessário manter informação redundante no ficheiro de diário (log)

• A informação a manter depende destas decisões

14


Write Ahead Logging

• A gestão assíncrona da cache é sempre mais eficiente e permite gerir melhor a memória volátil.

• Neste caso o diário tem de conter informação para fazer e desfazer o resultado das operações (redo/undo)

• É também necessário garantir que a informação é

escrita no diário antes da modificação das

páginas (write-ahead logging)


Actualização em Versões:Páginas sombra (Shadow pages)

• Copia-se inicialmente a tabela de páginas de modo a poder reconstituir a versão

• Se a transacção confirmar é necessário comutar atomicamente o ficheiro no directório

• A dispersão de ficheiros pelo disco e a proliferação de versões são limitações deste método.

15


Gestão do Diário

• Aspecto a considerar– Registos: físicos ou lógicos

– Robustez do diário a falhas dos discos

– Escrita síncrona/assíncrona dos registos

– Redução do espaço do ficheiro do diário através de marcas de recuperação (checkpointing)

– Faltas durante a recuperação


Log

16


Arquitectura do Sistema Transaccional

• Gestor de Sincronização – é responsável pela sincronização de todos os acessos aos dados

manipulados pelas transacções. Deve, portanto, ser chamado em todas as situações de leitura ou escrita para gerir os trincos associados aos objectos e tratar os problemas de interblocagem.

• Gestor da cache – gere a relação entre os discos e a memória volátil. A optimização é obtida,

evitando tanto quanto possível executar escritas síncronas e agrupando escritas em bloco para o disco.

• Gestor do Diário (Log) – gere a informação redundante. Esta informação é mantida numa lista que

regista as operações relevantes de actualização da estrutura de dados. – O diário é na realidade um ficheiro escrito sequencialmente, o que garante

que a informação é registada segundo a ordem de execução das operações.



• Gestor da recuperação – recupera o sistema para um estado consistente sempre

que uma falta for detectada. A gestão da cache, a informação escrita no diário e o algoritmo de recuperação estão intimamente relacionados

• Gestor da memória estável – garante a persistência dos dados. – fornece uma abstracção de memória persistente, capaz

de manter a informação mesmo quando existem falhas dos discos.

17


Transacções Atómicas Distribuídas


Interacção Cliente-CoordenadorAPI do Coordenador

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 return value indicates that the transaction has committed; an abort return value indicates that it has aborted.

abortTransaction(trans);

aborts the transaction.

18


Execução da Transacção Distribuída

..

BranchZ

BranchX

participant

participant

C

D

Client

BranchY

B

A

participantjoin

join

join

T

a.withdraw(4);

c.deposit(4);

b.withdraw(3);

d.deposit(3);

openTransaction

b.withdraw(T, 3);

closeTransaction

T = openTransaction

a.withdraw(4);

c.deposit(4);b.withdraw(3);d.deposit(3);

closeTransaction

Note: the coordinator is in one of the servers, e.g. BranchX

Só quando é chamado closeTransaction se executa o protocolo para confirmar ou abortar a transacção atomicamente


Transacções Distribuídas - Estrutura

19


Transacções Distribuídas Aninhadas: Exemplo


Transacções distribuídas:Problemas a considerar

• Distribuição implica lidar com:–Falta dos discos

–Falta das máquinas

–Falta das comunicações

• A tomada de decisão de abortar ou confirmar uma transacção é o problema mais complexo a resolver

• Requer um consenso entre os diferentes participantes numa transacção distribuída

20


Protocolo de confirmação em duas fases

(Two-Phase Commit, 2PC)


Especificação do Problema da Confirmação Atómica

• n processos, identificados por i ∈ {1, …, n}– Processo ⇔ máquina

• Modelo assíncrono

• Input do processo i: votoi ∈ {sim, não}

• Output do processo i: decisãoi ∈ {commit, abort}

21


Especificação do Problema

• CA1: Todos os processos tomam a mesma decisão

• CA2: A decisão só pode ser commit se todos os votos forem sim

• CA3: Se todos os votos forem sim e não houverem falhas nos processos, a decisão é commit

• CA4: Se todos processos recuperarem das suas falhas, e não ocorrerem mais falhas, então todos os processos eventualmente tomam uma decisão


Especificação do Problema

• CA4: Se todos processos recuperarem das suas falhas, e não ocorrerem mais falhas, então todos os processos eventualmente tomam uma decisão

• Alternativa: “Todos os processos que não falham eventualmente decidem”– Problema da confirmação atómica não-bloqueante.

– 2PC não verifica esta condição � requer 3PC

22


Operações no 2PC

canCommit?(trans)-> Yes / No

Call from coordinator to participant to ask whether it can commit a transaction. Participant replies with its vote.

doCommit(trans)

Call from coordinator to participant to tell participant to commit its part of a transaction.

doAbort(trans)

Call from coordinator to participant to tell participant to abort its part of a transaction.

haveCommitted(trans, participant)

Call from participant to coordinator to confirm that it has committed the transaction.

getDecision(trans) -> Yes / No

Call from participant to coordinator to ask for the decision on a transaction after it has voted Yes but has still had no reply after some delay. Used to

recover from server crash or delayed messages.


Protocolo (sem falhas)

CoordenadorEnvia PREPARAR a todos

if (todos votaram sim)decisãocoord = commit

Envia COMMIT a todoselse

decisãocoord = abort

Envia ABORT a todos que votaram simexit

Participante i

Envia votoi ao coord.if (votoi == não)

decisãoi = abort

exit

if (recebe ABORT)decisãoi = abort

elsedecisãoi = commit

exit

23


Protocolo (Coordenador)

inicial

espera

abort commit

temporizadorexpirou

Input: -Output: Envia PREPARAR a todos

Input: Recebe SIM de todosOutput: Envia COMMIT a todos

Input: Recebe um ou mais NÃOOu temporizador expira

Output: Envia ABORT a todos


Protocolo (Participante)

inicial

espera

abort commit

Input: Recebe PREPARAR e votoi == simOutput: Envia sim ao coordenador

Input: Recebe COMMIT

Input: (Recebe PREPARARe votoi == não)Ou temporizador expira

Output: Envia não ao coord.

Input: Recebe ABORT

temporizadorexpirou

Executar protocolo de

terminação

24


Protocolo de Terminação

• Se o temporizador expirar no participante após votar sim, envia PEDIDO_DECISÃO a todos participantes

• Restantes participantes respondem com:– decisãoi se já decidiram– ABORT se estiverem no estado inicial– INDECISO se estiverem no estado espera

• Se algum participante responder COMMIT ou ABORT, essa é a decisão final do participante

• Caso todos respondam INDECISO � esperar que coordenador recupere– 3PC evita espera no caso de falha do coordenador


Protocolo de Recuperação

• Assume um diário (log) persistente com escritas atómicas (no caso de falhas)

Evento Info. escrita no log Instante da escrita

Coord. envia PREPARAR Begin commit Em paralelo com envio

Participante vota sim Sim Antes de enviar voto

Participante vota não Não Em paralelo com envio

Coord. decide commit Commit Antes de enviar commit

Coord. decide abort Abort Em paralelo com envio

Particip. recebe decisão Commit ou Abort Em paralelo com decisão

25


Protocolo de Recuperação

• Após recuperar, processo inspecciona o diário

• Se exisitir registo de “Begin Commit”, era coordenador:– Se decidiu subsequentemente, protocolo terminou, senão decide

abort

• Caso contrário era participante:– Se decidiu subsequentemente, protocolo terminou

– Se não existir registo que votou “Sim”, decide abort

– Caso contrário, corre protocolo de terminação.


2008/2009 José Alves Marques, Rodrigo Rodrigues e João Barreto

Transacções distribuídas:Problemas do 2PC

• O protocolo é bloqueante– Obriga os Participantes a esperar pela recuperação do

Coordenador

E vice-versa– O protocolo bloqueia componentes funcionais por causa de outras

com falhas

• Não é possível fazer uma recuperação totalmente independente

• Há alternativas não-bloqueantes (sob modelos de faltas mais restritivos)

– Normalmente muito mais complexas (ex. 3PC)

26


Interblocagem em Transacção Distribuída


Duas fases entre Coordenador e Participantes

canCommit?

Yes

doCommit

haveCommitted

Coordinator

1

3

(waiting for votes)

committed

done

prepared to commit

step

Participant

2

4

(uncertain)

prepared to commit

committed

statusstepstatus

27


2PC Aninhado: Operações do coordenador

openSubTransaction(trans) -> subTrans

Opens a new subtransaction whose parent is trans and returns a unique subtransaction identifier.

getStatus(trans)-> committed, aborted, provisional

Asks the coordinator to report on the status of the transaction trans. Returns values representing one of the following: committed, aborted, provisional.


2PC Aninhado: Exemplo

1

2

T11

T12

T22

T21

abort (at M)

provisional commit (at N)

provisional commit (at X)

aborted (at Y)

provisional commit (at N)

provisional commit (at P)

T

T

T

Coordinator of

transaction

Child

transactions

Participant Provisional

commit list

Abort list

T T1, T2 yes T1, T12 T11, T2

T1 T11, T12 yes T1, T12 T11

T2 T21, T22 no (aborted) T2

T11 no (aborted) T11

T12, T21 T12 but notT21 T21, T12

T22 no (parent aborted)T22

28


2PC Aninhado: opções para o canCommit

• canCommit em 2PC Hierárquico

• canCommit em 2PC PlanocanCommit?(trans, abortList) -> Yes / No

Call from coordinator to participant to ask whether it can commit a transaction. Participant replies with its vote Yes / No.

canCommit?(trans, subTrans) -> Yes / No

Call a coordinator to ask coordinator of child subtransaction whether it can commit a subtransaction subTrans. The first argument trans is the transaction identifier of top-level transaction. Participant replies with its vote Yes / No.



Transacções distribuídas:Arquitectura distribuída

• Consórcio X/OPEN:– Esforço de normalização dos protocolos e interfaces para interligação de sistemas

de informação heterogéneos• DTP (Distributed Transaction Processing)• Muito influenciado pela norma de facto que constituiu a arquitectura SNA da IBM e a sua

interface LU 6.2

• Arquitectura X/Open:– Gestores de Recursos - RM (resource manager)

• Armazenam os dados– Em BDs relacionais, sistemas de ficheiros com actualizações atómicas, etc.

• Garantem localmente as propriedades das transacções– Monitores Transaccionais - TM (transaction managers)

• Coordenadores dos RM– Através da interface XA

• Execução dos protocolos de iniciação/terminação das transacções• Um em cada máquina (ou em cada grupo de máquinas)

29



Transacções distribuídasX/Open

Aplicação

TM

RM

Iniciar

Confirmar

Abortar

Ler

Escrever

Associar

Preparar

Confirmar

Abortar



Transacções distribuídas:X/Open (com distribuição)

Aplicação

TM

RM

SC

TM

RM

SC

Documents

Transacções em Sistemas Distribuídosdisciplinas.ist.utl.pt/~leic-sod.daemon/2010-2011/teoricas_tagus/7... · Interblocagem • A sincronização com trincos pode conduzir a interblocagem