Transações Distribuídas

Transações

Uma transação consiste numa sequência de instruções que é executada de forma aparentemente atómica, ou seja, ou todas as instruções são executadas ou nenhuma é (é indivisível). Normalmente é delimitada por instruções específicas, como por exemplo:

• início: begin-transaction
• fim: end-transaction, commit, abort

Exemplo de uma transação:

transferir(contaA, contaB, montante) {
  beginTransaction;
  bancoA.lerSaldo(contaA, saldoA);
  bancoB.lerSaldo(contaB, saldoB);
  bancoA.atualizarSaldo(contaA, saldoA - montante);
  bancoB.atualizarSaldo(contaB, saldoB + montante);
  commit;
}

Propriedades ACID

Em Bases de Dados, é costume as transações oferecerem as seguintes propriedades:

• Atomicidade (Atomicity):

  • Ou a transação é executada na totalidade, ou não produz qualquer efeito (como se não tivesse existido)
  • Quando a transação é executada com efeito diz-se confirmada (commited)
  • Se não produz qualquer efeito, diz-se que abortou
    • uma transação pode abortar a pedido ou devido a problemas que ocorram durante a sua execução
  Exemplo

  transferir(contaA, contaB, montante) {
    beginTransaction;
    bancoA.lerSaldo(contaA, saldoA);
    bancoB.lerSaldo(contaB, saldoB);
    if (saldoA < montante) {
      abort;
    } else {
      bancoA.atualizarSaldo(contaA, saldoA - montante);
      bancoB.atualizarSaldo(contaB, saldoB + montante);
      commit;
    }
  }

• Coerência (Consistency):

  • A execução de uma transação não resulta na violação das invariantes que caracterizam o modelo de dados

• Isolamento (Isolation):

  • Define como o sistema se comporta quando são executadas transações de forma concorrente que acedem aos mesmos objetos
  • Alguns exemplos de isolamento (que não iremos estudar):
    • Serializabilidade Estrita
    • Serializabilidade
    • Isolamento Instantâneo (“snapshot isolation”)
    • Coerência transacional causal
  • Serializabilidade de Transações: o resultado da execução concorrente de um conjunto de transações deve ser equivalente ao resultado de as executar em série, uma de cada vez

• Durabilidade (Durability): os resultados da transação ficam registados de forma persistente na base de dados

Iremos analisar de seguida mecanismos para garantir a Atomicidade e Isolamento das transações.

Atomicidade: utilização do "redo log"

• Os resultados da transação não são aplicados durante a execução, apenas quando a transação é commited
• Antes de aplicar os resultados, estes são escritos para um log persistente, juntamente com a informação de que a transação foi confirmada
• Começa-se a aplicar os resultados apenas depois da persistência do log ser garantida
• Se ocorrer um erro/falha que interrompa a aplicação dos resultados, quando a máquina recuperar consulta o log para continuar a partir do ponto de interrupção

Isolamento: strict 2-phase locking (controlo pessimista)

• Método pessimista de controlo de concorrência: à medida que a transação executa e é necessário aceder a um recurso, é obtido o lock associado ao mesmo

• Cada recurso tem read-write locks

• Quando se acede pela primeira vez a um recurso para leitura, tenta-se obter o lock para leitura

• Da mesma forma, quando se acede pela primeira vez para escrita, tenta-se obter o lock para escrita

• Segue-se um modelo de escritores-leitores:

  • Podem estar vários leitores concorrentemente a utilizar o recurso (desde que não haja um escritor)
  • Apenas pode estar um escritor a utilizar o recurso (não é permitido existir leitores)

• Se uma transação não consegue obter o lock pretendido, bloqueia

• Quando a transação termina, libera todos os locks

• Mecanismo sujeito a deadlocks:

  • É possível detetar deadlocks através da construção de um grafo de dependências entre transações e detetando um ciclo, o que significa que de alguma forma uma transação está à espera que outra liberte um lock mas que essa também espera o mesmo de um lock que a primeira possui

  • A maneira mais comum de "detetar deadlocks" é através de timeouts: caso uma transação esteja bloqueada num lock há demasiado tempo, aborta libertando todos os locks que possui

  • Uma maneira de evitar deadlocks é a partir do uso de prioridades:

    • cada transação tem uma prioridade (que geralmente é uma timestamp física ou lógica, de forma a que a transação mais antiga tenha uma maior prioridade)
    • uma transação apenas se bloqueia num lock caso este seja detido por outra mais prioritária
    • uma transação mais prioritária que pretenda um lock detido por outra menos prioritária, força-a a abortar de forma a não ter de se bloquear
    • evitamos assim o deadlock mas ao custo de por vezes abortar transações desnecessariamente
    Exemplo

    

Isolamento: controlo otimista

• A transação lê os recursos sem tentar obter qualquer lock
• Quando quer fazer uma escrita, faz buffer da mesma (não as aplica)
• Na confirmação da transação, é feita uma validação:
  • consiste em validar, de forma atómica, se os valores lidos não foram alterados entre a leitura e o momento da validação
• Se for validada, as escritas vão ser aplicadas de forma atómica
• Caso contrário, a transação é abortada (as escritas são descartadas)

Transações Distribuídas

Quando queremos alterar dados que estão distribuídos por várias máquinas, torna-se mais complicado realizar uma transação, já que temos que garantir que todas as máquinas ou dão commit ou abort. Se quisermos transferir dinheiro do banco A para o banco B, não pode acontecer o banco A confirmar a transferência mas o B abortar, iria-se "perder" dinheiro (sistema incoerente).

Precisamos assim de garantir que todas as máquinas tomam a mesma decisão, ou seja, que a confirmação da transação é atómica, o que envolve coordenação por parte dos nós que participam na transação. A solução mais simples para este problema é conhecida como "confirmação (atómica distribuída) em 2 fases" (2-phase-commit)

Coordenador da transação distribuída

Os servidores que executam requests como parte de uma transação distribuída precisam de comunicar entre si para coordenar as suas ações quando a transação é confirmada.

Um cliente inicia uma transação enviando um request openTransaction para um servidor (qualquer um). O servidor que abriu a transação torna-se no coordenador da mesma e, no final, é responsável por confirmá-la ou abortá-la. Cada servidor que gere um objeto acedido pela transação é considerado um participante da mesma e este fornece pelo menos um objeto participante.

A figura anterior ilustra um cliente cuja transação bancária envolve as contas A, B, C e D nos servidores BranchX, BranchY e BranchZ. A transação, T, transfere 4€ da conta A para a conta C e depois transfere 3€ da conta B para a conta D. Note que as operações openTransaction e closeTransaction são direcionadas ao coordenador.

Quando o cliente invoca um dos métodos na transação, por exemplo b.withdraw(T,3), o objeto que recebe o request (B na BranchY, neste caso) passa a saber que pertence à transação T. Se ainda não tiver informado o coordenador, o objeto participante usa a operação join para fazê-lo. Desta forma, quando o cliente invocar closeTransaction, o coordenador já possui referências para todos os participantes.

Confirmação em 2 fases (2-phase commit)

Durante uma transação, não há comunicação entre o coordenador e os participantes (para além dos participantes informarem o coordenador quando se juntam à transação). É quando o cliente solicita ao coordenador para confirmar a transação que o protocolo 2-phase commit entra em ação.

Funcionamento do protocolo:

• Um dos participantes é eleito como coordenador
• O coordenador envia uma mensagem especial "prepare" para sinalizar o início do processo de confirmação
• Caso o participante possa confirmar a transação (transação executou sem abortar e o "redo log" está salvaguardado em memória persistente), regista no log que vota favoravelmente e envia "OK" ao coordenador
• Caso contrário, regista no log que vota desfavoravelmente e envia "NOT-OK" ao coordenador
• Se o coordenador receber "OK" de todos os participantes, confirma a transação, registando no seu log essa informação e enviando-a a todos os participantes (que também registam no seu log o resultado)
• Se receber pelo menos um "NOT-OK", aborta a transação, registando no seu log essa informação e enviando-a a todos os participantes (que também registam no seu log o resultado)
• Caso algum dos participantes não responda, o coordenador pode tentar contactá-lo de novo ou, se suspeitar que falhou, abortar a transação. A ausência de resposta do participante é interpretada como um "NOT-OK"
• Os participantes que votaram "OK" têm de esperar pela decisão do coordenador (confirmar ou abortar). Quando um participante recebe esta informação, toma as ações necessárias de acordo com a decisão tomada e, no caso da confirmação, informa o coordenador que os logs referentes à transação podem ser apagados (a transação foi concluída).

Confirmação atómica tolerante a falhas

Uma maneira de obter uma versão tolerante a faltas da confirmação é através do uso do consenso como módulo:

• inicia-se o algoritmo da mesma forma que no 2-phase commit, em que o coordenador despoleta o processo de verificação em todos os participantes, mas agora estes enviam a resposta para todos os outros participantes

• todos os participantes guardam as respostas dos outros e invocam o consenso da seguinte forma:

  • Se um participante recebe "OK" de todos os participantes, inicia o consenso propondo "commit"
  • Se recebe um "NOT-OK", inicia o consenso propondo "abort"
  • Se suspeita que outro participante falhou, inicia o consenso propondo "abort"
  • No fim, todos os participantes dão commit ou abort consoante o resultado do consenso
  Pseudocódigo

  Quando recebe "Prepare":
    Broadcast(OK / NOT-OK);
  
  Quando recebe OK de Px:
    númeroOKs++;
    Se númeroOKs == n:
      Ready = TRUE;
      Input = COMMIT;
  
  Quando recebe NOT-OK:
    Ready = TRUE;
    Input = ABORT;
  
  Quando Px falhou:
    Ready = TRUE;
    Input = ABORT;
  
  Quando Ready:
    Consenso.propoe(Input);
    result = Consenso.decide()

Referências

• Coulouris et al - Distributed Systems: Concepts and Design (5th Edition)
  • Secções 17.1-17.3
• Departamento de Engenharia Informática - Slides de Sistemas Distribuídos (2023/2024)
  • SlidesAlameda-Aula10