Replicação e Tolerância a Faltas

Introdução a sistemas replicados

A replicação consiste no processo de manter cópias de dados e software de um serviço em várias máquinas.

Benefícios de replicar um sistema

• melhor disponibilidade: mesmo que alguns nós falhem ou fiquem indisponíveis devido a falhas na rede, o sistema continua disponível
• melhor desempenho e escalabilidade:
  • Podem existir cópias mais próximas do cliente
  • Algumas operações não precisam de ser executadas sobre todo o sistema, podendo ser executadas apenas sobre algumas cópias (distribuindo assim a carga e aumentando a escalabilidade)

Linearizabilidade

Uma das garantias essenciais que um sistema replicado tem que assegurar é a coerência. O ideal seria um cliente ler a versão mais recente do recurso sempre que lê de uma réplica (mesmo que essa versão tenha sido escrita noutra réplica). Um critério de coerência que podemos utilizar é a linearizabilidade. Antes de definirmos o que é, é necessário ter em conta o seguinte quanto à ordenação de operações:

• As operações realizadas sobre um sistema replicado não são instantâneas:
  • A operação é invocada por um cliente, executada durante algum tempo e o cliente só recebe a resposta mais tarde.
• Se uma operação X começa depois de outra operação Y acabar, então X ocorre depois de Y
• Se uma operação X começa antes de outra operação Y acabar, então X é concorrente com Y

Registos partilhados e replicados

Um registo suporta duas operações:

• Escrita:
  • uma escrita substitui o valor da anterior
  • apenas um cliente pode escrever no registo num dado instante, ou seja, as escritas são ordenadas
• Leitura:
  • múltiplos clientes podem ler do registo ao mesmo tempo

Tipos de registos

Lamport definiu três modelos de coerência para registos:

• Safe:

  • Se uma leitura não for concorrente com uma escrita, lê o último valor escrito
  • Se for, pode retornar um valor arbitrário

• Regular:

  • Se uma leitura não for concorrente com uma escrita, lê o último valor escrito
  • Se for, ou retorna o valor anterior ou o valor que está a ser escrito
  • NOTA: este tipo de registo não é linearizável, já que enquanto decorre uma escrita, é possível que leituras seguidas leiam sequências incoerentes de valores (primeiro o novo valor e depois o antigo)

• Atomic:

  • Equivalente a linearizabilidade quando aplicada a registos
  • O resultado da execução é equivalente ao resultado de uma execução em que todas as escritas e leituras ocorrem instantaneamente num ponto entre o início e o fim da operação

Registos distribuídos

Uma forma de implementar registos distribuídos é a seguinte:

• Cada processo mantém uma cópia do registo
• Cada registo guarda um tuplo <valor, versão>
• Para executar uma operação (leitura ou escrita), os processos trocam mensagens entre si

É possível implementar este funcionamento de forma a que seja tolerante a faltas e não bloqueante!

Algoritmo ABD

Registo regular (com um só escritor):

• Escrita:

  • O escritor incrementa o número de versão e envia o tuplo <valor, versão> para todos os processos.
  • Quando os outros processos recebem esta mensagem, atualizam a sua cópia do registo (caso seja uma versão mais recente que a local) e enviam uma confirmação ao escritor.
  • A operação termina quando o escritor receber resposta de uma maioria.

• Leitura:

  • O leitor envia uma mensagem a todos os processos solicitando o tuplo mais recente
  • Cada processo envia o seu tuplo <valor, versão>
  • Após receber resposta de uma maioria, retorna o valor mais recente e atualiza o valor local (caso necessário)

Registo atómico (com um só escritor):

• Escrita:

  • Idêntico ao anterior.

• Leitura:

  • Executa o algoritmo de leitura anterior mas não retorna o valor
  • Executa o algoritmo de escrita, usando o valor lido
  • Retorna o valor lido apenas após a escrita ter terminado

Espaço de Tuplos

Espaço de Tuplos "Linda"

Consiste num espaço partilhado que contêm um conjunto de tuplos (ex: <"A">, <"A", 1>, <"A", "B">) e que suporta 3 operações:

• Put: adiciona um tuplo (sem afetar os tuplos existentes) no espaço
• Read: retorna o valor de um tuplo (sem afetar o conteúdo do espaço)
• Take: também retorna um tuplo mas remove-o do espaço
• Tanto Read como Take são bloqueantes caso o tuplo não exista
• Tanto Read como Take aceitam wildcards: Read(<"A", *>) pode retornar <"A", 1> ou <"A", "B">

Como o Take é bloqueante, pode ser usado para sincronizar processos:

• Elege-se um tuplo especial, por ex. <lock>.
• Cada processo remove o tuplo do espaço antes de aceder à região crítica e volta a colocá-lo no fim, garantindo assim exclusão mútua
• Conseguimos assim através de uma única interface partilhar memória e sincronizar processos

Enquanto que nos registos uma escrita fazia override do valor antigo, aqui o processo equivalente é realizar um Take seguido de um Put (os tuplos são imutáveis). O Take permite fazer operações que em memória partilhada requerem uma instrução do tipo compare-and-swap.

Xu-Liskov

Muitas das implementações de espaços de tuplos adotam uma solução centralizada. Isto tem vantagens em termos de simplicidade, mas tais soluções não são tolerantes a falhas nem escaláveis.

Xu-Liskov é uma implementação distribuída e tolerante a faltas do "Linda".

O objetivo dos autores com este design era obter a solução mais eficiente e com o menor tempo de resposta possível, mas assegurando linearizabilidade.

Visto que este algoritmo foi projetado para minimizar o delay :

• Operações read apenas bloqueiam até que a primeira réplica responda ao pedido
• Operações take bloqueiam até o final da fase 1, quando o tuplo a ser excluído foi acordado
• Operações put podem retornar imediatamente

No entanto, isto introduz níveis inaceitáveis de concorrência. Por exemplo, uma operação read pode aceder a um tuplo que deveria ter sido excluído na segunda fase de uma operação take. Assim, são necessárias as seguintes restrições adicionais:

• As operações de cada worker devem ser executadas em cada réplica na mesma ordem em que foram emitidas pelo worker
• Uma operação put não deve ser executada em nenhuma réplica até que todas as operações take anteriores, emitidas pelo mesmo worker, tenham sido concluídas em todas as réplicas (na visão do mesmo)

Imaginemos que o Read não era bloqueante, ou seja, ou retornava o tuplo ou "null". O sistema continuaria a ser linearizável? Não, pois seria possível:

• Um cliente executa Put de um tuplo $t$
• Um cliente executa Read(t) várias vezes, concorrentemente com o Put
• Se o leitor recebe respostas de réplicas diferentes em cada Read, pode ler $t$ e de seguida "null"

Quanto ao Take, é possível que dois processos tentem fazer Take do mesmo tuplo concorrentemente e nenhum consiga a maioria (deadlock). Para resolver este problema introduz-se um fator de aleatoriedade: cada processo repete o seu pedido um tempo aleatório depois (solução não determinista).

Teorema CAP

Segundo este teorema, é impossível um sistema apresentar simultaneamente:

• Consistency (coerência)
• Availability (disponibilidade)
• Partition-tolerance (tolerância a partições na rede)

Apenas pode ter 2 destas propriedades (quaisquer duas).

Coerência fraca

Nesta secção, vamos explorar técnicas de replicação para tornar os serviços altamente disponíveis. O objetivo é dar aos clientes acesso ao serviço (com tempos de resposta razoáveis) durante o máximo de tempo possível, mesmo que alguns resultados não respeitem a consistência sequencial.

Garantias de sessão

• Read Your Writes:
  • Se um Read $R$ procede um Write $W$ numa sessão, então o valor de $W$ é incluído em $R$
• Monotonic Reads:
  • Se um Read $R1$ precede um Read $R2$ numa sessão, $R2$ tem que incluir todos os Writes completos incluídos em $R1$ (mas pode ter alterações mais recentes)
• Writes Follow Reads:
  • Se um Read $R1$ precede um Write $W2$ numa sessão e $R1$ é executado no servidor $S1$, então qualquer servidor $S2$ que inclui $W2$ também inclui qualquer Write $W1$ incluido em $R1$ na ordem em que foram escritos
• Monotonic Writes:
  • Se um Write $W1$ precede um Write $W2$ numa sessão, então qualquer servidor $S2$ que inclua $W2$ também inclui $W1$ na ordem em que foram escritos

Write(W,S) = {
  if WFR then
    check S.vector dominates read-vector
  if MW then
    check S.vector dominates write-vector
  wid := write W to S
  write-vector[S] := wid.clock
}

Read(R,S) = {
  if MR then
    check S.vector dominates read-vector
  if RYW then
    check S.vector dominates write-vector
  [result, relevant-write-vector] := read R from S
  read-vector := MAX(read-vector, relevant-write-vector)
  return result
}

Propagação epidémica (gossip propagation)

De forma a introduzir o conceito de propagação de informação, vamos pensar sobre a forma menos coordenada possível de fazê-lo:

• Periodicamente, cada processo contacta os outros e envia-lhes informação/atualizações
• A informação é assim propagada como uma espécie de "rumor" (do inglês gossip)
• Apresenta a grande vantagem de ser totalmente descentralizada, balanceando a carga por todos os processos

Ao propagar informação desta forma surgem, naturalmente, duas questões essenciais:

• Por que ordem devem ser aplicadas as atualizações recebidas dos outros processos?
• Se um processo contacta primeiro uma réplica R1 e depois outra R2, que garantias mínimas devem existir?

Pensemos no exemplo em que existem três réplicas R1, R2 e R3 e que se está a executar uma aplicação de preparação de slides de forma cooperativa:

• Em R1 um cliente executa a instrução "criar círculo", que é propagada para R2
• Em R2 outro cliente executa a instrução "pintar círculo", que é propagada para R3
• R3 recebe primeiro a instrução "pintar círculo" antes de "criar círculo", o que pode gerar um erro

Outro exemplo:

• Em R1 um cliente executa a instrução "label=distribúidos" e propaga-a para R2
• Em R2 um cliente apercebe-se da gralha e corrige-a: "label=distribuídos"
• R3 recebe primeiro a instrução executada em R2 e só depois a executada em R1
• Se aplicar as atualizações por esta ordem, a correção da gralha fica sem efeito

A grande maioria dos sistemas de propagação epidémica aplica as atualizações de forma a respeitar a relação aconteceu-antes, ou seja, respeita a ordem causal dos acontecimentos.

E no caso dos clientes móveis?

• Um cliente muda a sua password na réplica R1
• Muda para a réplica R2 antes da alteração ser propagada
• Não consegue utilizar a sua nova password

Existem sistemas capazes de garantir a relação aconteceu-antes para clientes móveis, enquanto que outros oferecem garantias ainda mais fracas como as garantias de sessão apresentadas acima.

Todas estas garantias podem ser atingidas com o uso de relógios lógicos (pouco eficiente).

Lazy Replication - gossip architecture

Foi proposta em 1922 e inspirou muitos dos sistemas fracamente coerentes dos dias de hoje. Tem como objetivo:

• garantir acesso rápido aos clientes
• mesmo quando existem partições na rede
• com o trade-off de sacrificar a coerência

O nome gossip vem de as réplicas propagarem as alterações periodicamente em background, como se fossem boatos.

O algoritmo oferece coerência fraca, mas assegura duas propriedades:

• Monotonic reads
  • mesmo que o cliente aceda a réplicas diferentes
• O estado das réplicas respeitam a ordem causal das alterações
  • se uma modificação $m_2$ depende de outra $m_1$, a réplica nunca executa $m_2$ antes de $m_1$

Interação cliente-réplica

• Cada cliente mantém um timestamp vetorial denominado $prev$

  • vetor de inteiros, um por réplica
  • reflete a última versão acedida pelo cliente

• Em cada contacto com uma réplica, é enviado também o $prev$: (pedido, $prev$)

• A réplica devolve (resposta, $new$)

  • em que $new$ é o timestamp vetorial que reflete o estado da réplica
  • se a réplica estiver atrasada em relação ao cliente, espera até se atualizar para devolver uma resposta (caso seja uma leitura)

• Cliente atualiza $prev$ de acordo com $new$, confrontando cada entrada de $prev$ com a correspondente de $new$

  • se $new[i] \gt prev[i]$, $prev[i] = new[i]$

• Cada réplica mantém também localmente um update log

  • uma réplica pode já ter recebido uma modificação mas não a poder executar devido a ainda não ter recebido/executado dependências causais, pelo que a mantém em estado pendente no log
  • pode assim propagar modificações individuais para as outras réplicas, mantendo o update no log até receber confirmação de todas elas

Quando uma réplica recebe um pedido de leitura:

• verifica se $pedido.prev \leq value~timestamp$
  • se sim, retorna o valor atual juntamente com o $value~timestamp$
  • se não, o pedido fica pendente até estar atualizada

Quando uma réplica $i$ recebe um pedido de modificação:

• verifica se já o executou e em caso afirmativo descarta-o
• incrementa a entrada $i$ do seu $replica~timestamp$ em uma unidade
• atribui à modificação um novo timestamp calculado por:
  • $pedido.prev$ com a entrada $i$ substituída pelo novo valor calculado acima (gerando assim um timestamp único para este update)
• adiciona a modificação ao log e retorna o novo timestamp ao cliente
• espera até $pedido.prev \leq value~timestamp$ se verificar para executar o código localmente
  • garantindo assim que a execução respeita a ordem causal
• quando finalmente executar o pedido, atualiza o $value~timestamp$
  • para cada entrada $j$: se $replicaTS[j] \gt valueTS[j]$, $valueTS[j] = replicaTS[j]$

Para propagar as modificações:

• periodicamente, cada gestor de réplica $i$ contacta outro gestor $j$
• $i$ envia de forma ordenada a $j$ as modificações do seu log que estima que $j$ não tem
• para cada modificação que $j$ recebe:
  • se não for duplicada, adiciona ao seu log
  • atualiza o seu $replicaTS$
  • assim que $prev \leq value~timestamp$, executa a modificação
• NOTA: As modificações não são apenas propagadas desta forma (comunicação periódica). Quando um gestor de réplicas descobre que precisa de uma certa atualização para processar um pedido, este pode pedi-la diretamente.

Existem outros tipos de algoritmos para suportar operações que requerem modelos de coerência mais fortes, como por exemplo:

• Forced operations (total e causal)
• Immediate operations

As atualizações immediate-ordered são aplicadas numa ordem consistente em relação a qualquer outra atualização em todos os gestores de réplicas. Esta ordenação é utilizada porque, por exemplo, uma atualização forced e outra causal que não têm uma relação happened-before podem ser aplicadas em ordens diferentes nos diversos gestores de réplicas.

Estas garantias de ordenação não são abordadas nesta cadeira.

Algoritmo de Bayou

No sistema de Lazy Replication assume-se que as operações concorrentes são comutativas, ou seja, independentemente da ordem pela qual são aplicadas, o resultado final é o mesmo (por ex: "desenhar círculo" e "alterar cor da linha"). Se as operações não forem comutativas, é necessário utilizar primitivas mais fortes (forced/immediate).

O Bayou introduz uma solução para reconciliar automaticamente réplicas divergentes:

• Ordenar operações concorrentes por uma ordem total
• Cancelar as operações que foram executadas por uma ordem diferente
• Re-aplicar estas operações pela ordem total, aplicando uma função de reconciliação que é específica da aplicação
• As operações podem ser codificadas de forma a facilitar a reconciliação automática

Updates: tentativo e commit

• Quando se faz um update, ele fica marcado como tentativo
  • podendo ainda sofrer alterações nesta fase
• Quando o update é commited, a sua ordem já não pode ser alterada
  • quem decide a ordem é tipicamente uma réplica especial, o primário
  • quando um update é commited, as outras réplicas podem por isso ter que o ordenar

Na figura acima, $t_i$ tornou-se commited. Todas as atualizações tentative após $c_N$ precisam de ser desfeitas; $t_i$ é então aplicado após $c_N$ e de $t_0$ a $t_{i-1}$ e $t_{i+1}$, etc., reaplicados após $t_i$.

Bayou_Write(
  update = {insert, Meetings, 12/18/95, 1:30pm, 60min, "Budget Meeting"},
  dependency_check = {
    query = "SELECT key FROM Meetings WHERE day = 12/18/95
      AND start < 2:30pm AND end > 1:30pm",
    expected_result = EMPTY
  },
  mergeproc = {
    alternates = {{12/18/95, 3:00pm}, {12/19/95, 9:30am}};
    newupdate = {};
    FOREACH a IN alternates {
      # check if there would be a conflict
      IF (NOT EMPTY (SELECT key FROM Meetings WHERE day = a.date
        AND start < a.time + 60min AND end > a.time))
          CONTINUE;
      # no conflict, can schedule meeting at that time
      newupdate = {insert, Meetings, a.date, a.time, 60min, "Budget Meeting"};
      BREAK;
    }
    IF (newupdate = {}) # no alternate is acceptable
      newupdate = {insert, ErrorLog, 12/18/95, 1:30pm, 60min, "Budget Meeting"};
    RETURN newupdate;
  }
)

CRDTs (Conflict-Free Replicated Datatypes)

Um CRDT é uma estrutura de dados que é replicada em vários computadores numa rede, com as seguintes características:

• A aplicação pode atualizar qualquer réplica de forma independente, concorrente e sem precisar de comunicar com outras réplicas (ou seja, sem coordenação, ao contrário da abordagem operational transformation usada por Bayou)
• Um algoritmo (que faz parte da própria estrutura de dados) resolve automaticamente quaisquer inconsistências que possam surgir entre réplicas
• Embora as réplicas possam ter estados diferentes num determinado momento, é garantido que eventualmente irão convergir

Pequeno exemplo de um contador (CRDT) que apenas suporta as operações "increment" e "read":

// Replica i

increment() {
  value[i]++;
}

read() {
  return SUM k: 1..N_REPLICAS (value[k])
}

merge_with_replica_j() {
  for k: 1..N_REPLICAS {
    i.value[k] = max(i.value[k], j.value[k])
  }
}

Os CRDTs foram apresentados em aula apenas como uma curiosidade, se tiveres interesse em aprender mais recomendamos a palestra do Martin Kleppmann na QCon London 2018.

Coerência forte

Tolerância a faltas

Existem duas estratégias principais:

• Recuperação "para trás":
  • guardar o estado do sistema de forma periódica ou em momentos relevantes, utilizando um algoritmo de salvaguarda distribuída
  • quando os processos falham, são relançados o mais rapidamente possível
  • os novos processos recomeçam a partir do último estado guardado
  • solução tipicamente designada por "checkpoint-recovery"
• Recuperação "para a frente":
  • são mantidas várias cópias (réplicas) do processo
  • quando é feita uma alteração a uma réplica, esta deve ser propagada para todas as outras de forma a estarem atualizadas/sincronizadas
  • se uma réplica falha, o cliente pode passar a utilizar outra
  • estrutura de dados replicada:
    • registo (algoritmo ABD)
    • espaço de tuplos (Xu-Liskov)
    • qualquer estrutura de dados que ofereça uma interface remota (exige algoritmos de replicação genéricos, tema deste capítulo)

De forma resumida:

• na recuperação para trás os estados guardados pelos vários processos que falharam devem estar mutuamente coerentes
• na recuperação para a frente os estados das réplicas que sobrevivem devem estar mutuamente coerentes.

Iremos analisar dois algoritmos de replicação genéricos (por recuperação para a frente):

• Primário-secundário
• Replicação de máquina de estados

Objetivo: assegurar linearizabilidade (coerência forte).

Algoritmo Primário-secundário (esboço)

• É eleito um processo como primário (sendo outro eleito em caso de falha)
• Os pedidos dos clientes são enviados para o primário
• Quando o primário recebe um pedido:
  • executa-o
  • propaga o estado para os secundários e aguarda confirmação de todos
  • responde ao cliente
  • (processa o próximo pedido que estiver na fila)

Vantagem: Suporta operações não determinísticas (primário decide o resultado).

Desvantagens:

• Se o primário produzir um valor errado, o erro vai ser propagado para as réplicas
• Se o detetor de falhas não for perfeito, pode existir mais que um primário concorrentemente, havendo o risco dos estados divergirem

Replicação de máquina de estados (esboço)

• Os clientes enviam os pedidos para todas as réplicas
• Os pedidos são ordenados por ordem total
• Todas as réplicas processam os mesmos pedidos, pela mesma ordem
  • assume-se que as operações são determinísticas, de forma a todas as réplicas ficarem idênticas
• Cada réplica responde ao cliente (o número de respostas pelo qual o cliente aguarda depende das suposições de falhas)

Vantagem: Se uma réplica produzir um valor errado, não afecta as outras.

Desvantagens:

• As operações necessitam de ser determinísticas.
• Se o detetor de falhas não for perfeito, pode ser impossível estabelecer uma ordem total dos pedidos

Abstrações para a construção de sistemas replicados

Construir sistemas replicados com estes algoritmos é bastante complicado e complexo, pelo que iremos falar de algumas abstrações sobre as quais podemos construir de forma a facilitar a implementação dos mesmos.

Canais Perfeitos

• Garante a entrega de mensagens ponto a ponto de forma ordenada, caso nem o emissor nem o destinatário falhem

• Implementação prática: retransmitir a mensagem até que a receção desta seja confirmada pelo destinatário

Difusão Fiável

• Permite difundir uma mensagem com a garantia de que ou todos os destinatários a recebem ou nenhum recebe

• Duas variantes: Regular e Uniforme

Difusão Fiável Regular

Propriedades:

• Seja $m$ uma mensagem enviada para um grupo de processos $\Set{p_1, p_2, ..., p_N}$ por um elemento do grupo
• Validade: se um processo correto $p_i$ envia $m$ então eventualmente $p_i$ entrega $m$
• Não-duplicação: nenhuma mensagem $m$ é entregue mais que uma vez
• Não-criação: se uma mensagem $m$ é entregue então $m$ foi enviada por um processo correto
• Acordo: se um processo correto entrega $m$ então todos os processos corretos entregam $m$

Algoritmo:

• O emissor envia a mensagem usando canais perfeitos para todos os membros do grupo
• Quando um membro do grupo recebe a mensagem, entrega-a à aplicação e reenvia-a para todos os membros do grupo

Difusão Fiável Uniforme

Propriedades:

• Seja $m$ uma mensagem enviada a para um grupo de processos $\Set{p_1, p_2, ..., p_N}$ por um elemento do grupo
• Validade, Não-duplicação e Não-criação tal como Difusão Regular
• Acordo: se um processo entrega $m$ então todos os processos corretos entregam $m$

Algoritmo:

• O emissor envia a mensagem usando canais perfeitos para todos os membros do grupo
• Quando um membro do grupo recebe a mensagem, reenvia-a para todos os membros do grupo
• Quando um membro receber uma mensagem $m$ de $f$ membros distintos, entrega a mensagem $m$ à aplicação
• Em que $f$ é o número de processos que pode falhar

Sincronia na Vista

Vista: conjunto de processos que pertence ao grupo:

• Novos membros podem ser adicionados dinamicamente
• Um processo pode sair voluntariamente do grupo ou ser expulso caso falhe

Propriedades:

• Permite alterar a filiação de um grupo de processos de uma forma que facilita a tolerância a faltas
• A evolução do sistema é dada por uma sequência totalmente ordenada de vistas
  • Exemplo: $V_1 = \Set{p_1, p_2, p_3}~V_2 = \Set{p_1, p_2, p_3, p_4}~ V_3 = \Set{p_1, p_2, p_3, p_4, p_5}~V_4 = \Set{p_2, p_3, p_4, p_5}$
• Um processo é considerado correto numa vista $V_i$ se faz parte dessa vista e de $V_{i\op{+}1}$
  • Por outro lado, se um processo pertence à vista $V_i$ mas não faz parte de $V_{i\op{+}1}$, pode ter falhado durante $V_i$
• Uma aplicação à qual já foi entregue a vista $V_i$ mas à qual ainda não foi entregue a vista $V_{i\op{+}1}$ diz-se que "está na vista $V_i$"
• Uma aplicação que usa o modelo de Sincronia na Vista recebe vistas e mensagens
• Se uma aplicação envia uma mensagem $m$ quando se encontra na vista $V_i$, diz-se que $m$ foi enviada na vista $V_i$
• Se uma mensagem $m$ é entregue à aplicação depois da vista $V_i$ mas antes da vista $V_{i\op{+}1}$, diz-se que $m$ foi entregue na vista $V_i$
• Uma mensagem $m$ enviada na vista $V_i$ é entregue na vista $V_i$
• Se um processo $q$ se junta a um grupo e se torna indefinidamente alcançável a partir do processo $p$ (sendo $p \neq q$), então eventualmente $q$ estará sempre nas views que $p$ entrega (a mesma lógica pode ser aplicada a processos que não conseguem comunicar)

Todas estas propriedades culminam nestas duas principais:

• Comunicação fiável:

  • Se um processo correto $p$ na vista $V_i$ envia uma mensagem $m$ na vista $V_i$, então $m$ é entregue a $p$ na vista $V_i$
  • Se um processo entrega uma mensagem $m$ na vista $V_i$ todos os processos corretos da vista $V_i$ entregam $m$ na vista $V_i$

• Corolário:

  • Dois processos que entregam as vistas $V_i$ e $V_{i\op{+}1}$ entregam exactamente o mesmo conjunto de mensagens na vista $V_i$

Para mudar de vista:

• é necessário interromper temporariamente a transmissão de mensagens de forma a que o conjunto de mensagens a entregar seja finito
• é necessário executar um algoritmo de coordenação para garantir que todos os processos corretos chegam a acordo sobre:
  • qual a composição da próxima vista
  • qual o conjunto de mensagens a ser entregue antes de mudar de vista

Difusão Atómica

Consiste em ter as garantias de Difusão Fiável + Ordem total:

• Difusão Fiável: se uma réplica recebe o pedido, todas as réplicas recebem o pedido
• Ordem total: todas as réplicas recebem os pedidos pela mesma ordem

A abordagem básica para implementar ordenação total é atribuir identificadores totalmente ordenados às mensagens multicast, de modo a que cada processo tome a mesma decisão de ordenação com base nesses identificadores.

Algoritmos de ordem total (sem falhas):

• Ordem total baseada em sequenciador:

  • as mensagens são enviadas para todas as réplicas usando um algoritmo de Difusão Fiável
  • é eleito um líder que decide a ordem pela qual as mensagens devem ser processadas, enviando esta informação para as réplicas restantes
  • quando existe uma falha, as réplicas podem ser confrontadas com um estado incoerente:
    • mensagens de dados que não foram ordenadas pelo líder
    • mensagens do líder referentes a mensagens que ainda não chegaram
    • podem existir de forma geral diferenças nas perspectivas que cada réplica tem do sistema
    • Todos estes problemas são resolvidos na camada de Sincronia na Vista

• Ordem total baseada em acordo coletivo:

  • um processo envia uma mensagem multicast para os membros do grupo. Estes processos propõem números de sequência para a mensagem (atribuição "tentativa") e devolvem-nos ao remetente, que gera o número de sequência acordado com base nos números propostos (atribuição final).
  • o algoritmo funciona mesmo que cada mensagem seja enviada para um sub-conjunto diferente de nós
  • quando há falhas, é preciso executar um algoritmo de reconfiguração que fica bastante simplificado pela Sincronia na Vista
  Exemplo de aplicação no algoritmo de Maekawa

  Iremos analisar o funcionamento do algoritmo de Skeen (em que o cliente escolhe o maior dos números de sequência propostos) aplicado à exclusão mútua de Maekawa.

  Existem três clientes $A$, $B$ e $C$, com quóruns $\Set{P_1, P_2}$, $\Set{P_2, P_3}$ e $\Set{P_1, P_3}$.

  

  $P_1$ e $P_2$ já receberam o pedido de $A$, marcando-os com o número de sequência 1 e 2 (respectivamente) e enviando essas propostas ao cliente. Estes pedidos encontram-se no estado "tentativo" (T), já que se tratam de propostas, ainda não foram confirmados.

  

  O cliente ao receber estes dois números, escolhe o mais alto (2) e envia essa informação ao seu quórum. O pedido de $A$ encontra-se agora ordenado definitivamente (estado final, F).

  

  Ao chegar ao topo da lista de $P_1$ com estado final, $A$ é enviado para a camada de aplicação, que neste caso é o algoritmo Maekawa. $P_1$ dá acesso a $A$ à exclusão mútua dado estar livre. Entretanto chegou também o pedido de $C$ a $P_1$, que foi marcado com o número 3.

  

  O cliente $C$ recebe 1 e 3 como propostas, pelo que escolhe 3. Chega agora o pedido de $B$ a $P_3$, que lhe atribui o número 4.

  

  Os pedidos de $C$ chegaram ao topo, pelo que foram enviados para a camada superior. $P_1$ colocou $C$ como pendente, pois $A$ tem a exclusão mútua, e $P_3$ concedeu-lhe acesso. $B$ recebe como respostas 1 e 4, pelo que escolhe 4, o que faz com que $A$ vá para o topo da lista de $P_2$.

  

  O pedido de $A$ é enviado para a camada superior e ganha o acesso à exclusão mútua em $P_2$. Em $P_3$, é enviado o pedido de $B$, que fica na lista de pendentes dado já existir outro cliente na exclusão mútua. De seguida, o pedido de $B$ em $P_2$ passa a estar no topo da lista com estado final, pelo que também é enviado. $A$ já está na exclusão mútua, portanto $B$ é adicionado à lista de pendentes.

  Recordar: O algoritmo de Maekawa tinha uma falha: era suscetível a deadlocks. Ao utilizarmos ordem total, garantindo que todos os processos recebem os pedidos pela mesma ordem, este problema fica resolvido.

Algoritmo Primário-secundário (concretizado)

• Primário usa Difusão Fiável Uniforme síncrona na vista para propagar novos estados aos secundários
  • só responde ao cliente quando a uniformidade estiver garantida
• Réplicas usam Sincronia na Vista para lidar com falhas do primário:
  • quando o primário $p$ falha, eventualmente será entregue nova vista sem $p$
  • quando uma nova vista é entregue e o anterior primário não consta nela, os restantes processos elegem o novo primário
  • o novo primário anuncia o seu endereço num serviço de nomes (para que os clientes o descubram)

Replicação de máquina de estados (concretizado)

• Processos usam Sincronia na Vista
• Clientes usam Difusão Atómica síncrona na vista para enviar pedidos a todas as réplicas

Consenso e Replicação

Iremos agora analisar como resolver problemas/algoritmos relacionados com replicação através do consenso.

Difusão atómica usando Consenso

Uma primeira abordagem poderia ser:

• cada processo guarda uma lista de mensagens Recebidas ($R$) e Ordenadas ($O$)
• sempre que tiver alguma mensagem recebida que ainda não está ordenada, propõe essa mensagem para consenso (uma instância de consenso por mensagem a ordenar)
• o consenso decide qual a próxima mensagem, que é adicionada à lista de mensagens ordenadas de cada processo

Esta abordagem tem um problema: como o consenso pode decidir qualquer uma das mensagens propostas, é possível que uma mensagem que apenas um processo recebeu nunca seja decidida (e portanto entregue):

A solução é propôr para consenso todas as mensagens recebidas mas não ordenadas ($R \setminus O$). A decisão do consenso será qualquer um dos sets propostos pelos processos:

Primário-secundário com detector de falhas não perfeito

Já abordámos uma implementação de replicação com Primário-secundário que utilizava Sincronia na Vista e Difusão Fiável, mas será que é possível construir uma solução robusta sem um detector de falhas perfeito?

Utilizaremos o detector não perfeito para escolher o primário:

• devido à natureza do detector, podem existir dois processos que pensam ser o primário
• as réplicas secundárias podem também divergir sobre quem consideram ser o primário

No exemplo acima, o primário $P_1$ decide que a primeira mensagem é $B$ e envia essa informação a $P_2$, que a regista com sucesso. No entanto, a mensagem não chegou a $P_3$ devido a uma partição na rede, que após não receber mensagens do primário durante algum tempo se elegeu como primário, escolhendo $E$ como primeira mensagem.

Precisamos agora de um algoritmo que consegue resolver consenso sem um detector de falhas perfeito... O floodset consensus não consegue, já que foi arquitetado exatamente com esse pressuposto. Mas podemos usar o Paxos mencionado anteriormente!

Resumidamente, o Paxos garante que o sistema apenas avança quando tem aprovação da maioria das réplicas. Desta forma, P1 e P2 conseguem continuar a execução normal do algoritmo enquanto que as propostas de P3 (por exemplo, escolher a mensagem E como primeira) não são aceites por uma maioria. Quando a estabilidade da rede voltar ao normal, P3 irá receber as operações que foram realizadas na sua "ausência" e o sistema voltará a estar consistente.

Sincronia na Vista usando Consenso

Mudar da vista $V_i$ para a $V_{i + 1}$ consiste essencialmente em:

• recolher todas as mensagens entregues durante $V_i$
• propôr para consenso um tuplo:
  • $V_{i + 1}$ = $<\text{membros de } V_{i + 1} \text{, mensagens entregues em } V_i>$
• esperar decisão do consenso
• entregar mensagens em falta
• entregar nova vista

Funcionamento do algoritmo:

• cada processo $p_i$ mantém um registo $h_i$ de todas as mensagens que já entregou numa dada vista
• quando se inicia a mudança de vista de $V_i$ para $V_{i + 1}$, é enviada uma mensagem especial "$\text{view-change(saídas, entradas)}$" para todos os processos da vista $V_i$ (podendo a lista de saídas e/ou entradas ser vazia)
• quando um processo recebe uma mensagem "$\text{view-change(saídas, entradas)}$", pára de entregar novas mensagens e inicia $V_{i + 1} = V_i - \text{saídas} - \text{entradas}$, $h_j = \text{null}$ para todos os processos $p_j$ na vista $V_i$ e envia $h_i$ para todos os outros processo em $V_{i + 1}$
• cada processo recebe os valores $h_j$ de todos os outros processos $p_j$ em $V_i$
• se um processo $p_i$ não recebe $h_j$ de um processo $p_j$ e suspeita que $p_j$ falhou, remove $p_j$ de $V_{i + 1}$ e coloca $h_j = \Set{}$
• quando um processo $p_i$ tem todos os valores de $h_j \not = \text{null}$ (ou seja, se já recebeu $h_j$ de $p_j$ ou se assume que $p_j$ falhou), define o conjunto de mensagens a entregar $m-V_i$ como a união de todos os $h_j$ recebidos e inicia o consenso propondo $<V_{i + 1}, m-V_i>$
• o resultado do consenso define a nova vista e o conjunto de mensagens a entregar na vista anterior

Referências

• Coulouris et al - Distributed Systems: Concepts and Design (5th Edition)
  • Secções 6.5 e 18.1-18.4
• Departamento de Engenharia Informática - Slides de Sistemas Distribuídos (2023/2024)
  • SlidesTagus-Aula05 (informação + imagens)
  • SlidesAlameda-Aula05
  • SlidesTagus-Aula06
  • SlidesAlameda-Aula06
  • SlidesTagus-Aula07
  • SlidesAlameda-Aula07
  • SlidesAlameda-Aula09
• D. B. Terry, A. J. Demers, K. Petersen, M. J. Spreitzer, M. M. Theimer and B. B. Welch, "Session guarantees for weakly consistent replicated data"
• Conflict-free replicated data type, Wikipedia