Papers
Conflict-free Replicated Data Types
Marc Shapiro, Nuno Preguiça, Carlos Baquero, Marek Zawirski · SSS 2011 (Stabilization, Safety, and Security of Distributed Systems), 2011
O problema: replicar sem sincronizar, mas sem conflitos ad hoc
A consistência forte tradicional serializa todos os updates em uma ordem global total. Isso vira gargalo de desempenho e escalabilidade e, pelo teorema CAP, entra em conflito com disponibilidade e tolerância a partições. Por isso, em cenários com latência de rede alta ou partições (computação em nuvem, redes P2P, operação desconectada), a consistência eventual (EC) é atraente: um update executa em uma réplica sem sincronização, é enviado depois às demais, e todos acabam sendo aplicados em todas as réplicas, de forma assíncrona e possivelmente em ordens diferentes. O custo é que updates concorrentes podem conflitar, e arbitrar o conflito pode exigir consenso e desfazer operações (roll-back). Os autores observam que a literatura dá pouca orientação para projetar um sistema otimista correto: as abordagens EC publicadas são ad hoc, frágeis e propensas a erro, e citam as anomalias de concorrência do carrinho de compras da Amazon como exemplo. A proposta do paper é uma abordagem teoricamente fundamentada: em vez de resolver conflitos depois, escolher tipos de dados cujas propriedades matemáticas (monotonicidade em um semirreticulado e/ou comutatividade) garantam que não haja conflito. Um exemplo trivial dado é um contador replicado, que converge porque incrementar e decrementar comutam, supondo ausência de overflow.
Strong Eventual Consistency: convergência imediata entre quem viu os mesmos updates
O paper formaliza a consistência eventual com três requisitos: entrega eventual (um update entregue a uma réplica correta chega, no fim, a todas as réplicas corretas), convergência (réplicas corretas que entregaram os mesmos updates alcançam, em algum momento, estados equivalentes) e terminação (toda execução de método termina). A ideia informal é que as réplicas chegam ao mesmo valor final se os clientes pararem de enviar updates. O modelo proposto, Strong Eventual Consistency (SEC), acrescenta uma condição mais forte, a convergência forte: réplicas que entregaram o mesmo conjunto de updates têm estado equivalente, sem esperar nenhum período de reconciliação e sem precisar de um mecanismo de arbitragem. Isso evita o padrão de executar um update logo, descobrir mais tarde que ele conflita com outro e desfazê-lo, o que desperdiça recursos e em geral exige consenso para que todas as réplicas arbitrem do mesmo jeito. Um tipo de dado que satisfaz as condições suficientes para SEC é chamado de Conflict-free Replicated Data Type (CRDT). O modelo de sistema assume processos não bizantinos conectados por rede assíncrona que pode particionar e se recuperar; processos podem falhar por parada silenciosa e, se voltarem, mantêm a memória.
Duas condições suficientes: CvRDT (baseado em estado) e CmRDT (baseado em operações)
O paper dá duas condições suficientes para SEC, uma para cada estilo de replicação. No estilo baseado em estado, cada réplica altera seu próprio estado com updates e, de tempos em tempos, envia seu estado a outra réplica, que o mescla (merge) ao dela. Um CvRDT exige que os possíveis estados formem um semirreticulado (semilattice) com uma ordem parcial, que o merge calcule o menor limitante superior (LUB) dos dois estados e que cada update só faça o estado crescer nessa ordem. Como o LUB é comutativo, associativo e idempotente, a ordem e a duplicação de merges não importam. O Teorema 1 afirma que, com entrega eventual e terminação, esse objeto é SEC. No estilo baseado em operações, não existe merge: cada update é um par formado por um método prepare, sem efeitos colaterais e executado só na réplica de origem, e um método effect, executado em todas as réplicas. Um CmRDT exige que todas as operações concorrentes comutem e que a entrega use um broadcast confiável com ordem causal (cada mensagem entregue exatamente uma vez, em ordem consistente com o happened-before). O Teorema 2 garante SEC nesse caso. O paper também prova (Teoremas 3 e 4) que os dois estilos são equivalentes: cada um pode emular o outro.
Trade-offs: CAP, tolerância a falhas e a relação com consistência sequencial
Sobre o CAP, os autores argumentam que, como falhas de rede são inevitáveis em larga escala e disponibilidade costuma ser prioridade, abrir mão de consistência forte não precisa significar abrir mão de toda garantia. Uma réplica SEC está sempre disponível para leitura e escrita, independentemente das condições da rede, e qualquer subconjunto de réplicas que consiga se comunicar converge mesmo isolado do resto. SEC tolera até n-1 falhas simultâneas por parada e não exige resolver consenso. Há, porém, um preço semântico: SEC é incomparável com consistência sequencial. Para mostrar que um objeto SEC pode não ser sequencialmente consistente, o paper usa um conjunto com add e remove em que, num add concorrente a um remove do mesmo elemento, o add vence. Em um cenário com duas réplicas que fazem operações em paralelo e uma terceira que faz o merge, o estado final contém ao mesmo tempo dois elementos cuja remoção seria o último evento em qualquer ordem sequencial, resultado impossível em execução sequencial. O paper nota que existem outras semânticas possíveis para add e remove concorrentes (o remove vencer, por exemplo), todas compatíveis com a convergência forte, e que a escolha depende da aplicação. Na direção inversa, sem falhas, um objeto sequencialmente consistente é SEC, mas em geral a consistência sequencial exige consenso, o que não é possível diante de n-1 falhas.
Veja as ideias em ação
Pratique na escola de System Design os desenhos que usam este paper.