Conceitos
Convergência sem coordenação com CRDTs
Intuição
Imagine duas pessoas editando cópias da mesma lista de compras sem internet, cada uma anotando o que quiser. Quando as cópias se encontram de novo, você gostaria que elas virassem a mesma lista automaticamente, sem ninguém decidir quem tem razão e sem desfazer nada. Isso fica garantido se as regras de como a lista muda forem escolhidas de modo que a ordem em que as mudanças chegam não faça diferença: aí cada pessoa trabalha à vontade e todas acabam vendo o mesmo resultado.
Como funciona
O paper define a Strong Eventual Consistency (SEC): além de entrega eventual e terminação, réplicas que entregaram o mesmo conjunto de updates têm estado equivalente imediatamente, sem período de reconciliação nem arbitragem de conflitos. Um tipo de dado que satisfaz condições suficientes para isso é um CRDT (Conflict-free Replicated Data Type). No estilo baseado em estado (CvRDT), os estados formam um semirreticulado, cada update só faz o estado crescer nessa ordem parcial e o merge calcula o menor limitante superior (LUB) de dois estados; como o LUB é comutativo, associativo e idempotente, a ordem e a duplicação de merges não alteram o resultado (Teorema 1). No estilo baseado em operações (CmRDT), cada update tem 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; exige-se que operações concorrentes comutem e que a entrega use broadcast confiável com ordem causal (Teorema 2). O paper prova que os dois estilos são equivalentes, pois cada um pode emular o outro. Como a convergência vem das propriedades matemáticas do tipo, a réplica fica sempre disponível para leitura e escrita, tolera até n-1 falhas por parada e não exige resolver consenso. O preço é semântico: SEC é incomparável com consistência sequencial, e em um conjunto com add e remove concorrentes é preciso escolher uma semântica (por exemplo, add vence), dependente da aplicação.
Na prática
Considere CRDTs quando réplicas precisam aceitar escritas durante partições ou operação desconectada e você prefere projetar o tipo de dado para não ter conflitos a arbitrá-los depois, como num contador replicado, que converge porque incrementar e decrementar comutam. O paper cita as anomalias do carrinho de compras da Amazon como exemplo de abordagens ad hoc frágeis. Em contrapartida, não os use onde a aplicação exige a ordem total de consistência sequencial, e decida explicitamente a semântica de operações concorrentes, como add versus remove.
Use em um desenho
Pratique na escola de System Design os casos que dependem deste conceito.