Conceitos
Transformação operacional vs CRDT
Intuição
Duas pessoas editam o mesmo texto ao mesmo tempo, cada uma na sua cópia, vendo a própria mudança na hora; o problema é que uma instrução como "insira na posição 5" passa a significar outra coisa depois que a outra pessoa inseriu algo antes dessa posição. Há dois jeitos de resolver: cada cópia reescreve as instruções que chegam de fora levando em conta as que ela já aplicou (no Wave, um servidor central organiza isso), ou os dados são desenhados de modo que mudanças feitas ao mesmo tempo deem o mesmo resultado em qualquer ordem. No primeiro caso a complexidade fica no algoritmo de reescrita; no segundo, no desenho dos dados.
Como funciona
Na Operational Transformation (OT), as operações locais são executadas sem bloqueio e as remotas são transformadas antes de serem executadas, de modo que o tempo de resposta local não depende da latência de rede. No Google Wave, as operações de documento descrevem a mudança por posição (reter, inserir, apagar) e o cliente espera o reconhecimento do servidor antes de enviar mais operações e, enquanto espera, compõe as pendentes; assim o servidor mantém um único espaço de estados (o histórico das operações aplicadas) e basta transformar cada operação recebida contra esse histórico, ao custo de um cliente ver blocos de operações de outro em intervalos de cerca de um tempo de ida e volta. Os CRDTs seguem o caminho oposto: em vez de transformar operações, escolhem-se tipos de dados cujas propriedades matemáticas (monotonicidade em um semirreticulado e/ou comutatividade) garantam que não haja conflito, o que dá a Strong Eventual Consistency (SEC), em que réplicas que entregaram o mesmo conjunto de updates têm estado equivalente, sem período de reconciliação nem arbitragem. Num CvRDT (baseado em estado), os estados formam um semirreticulado, o merge calcula o menor limitante superior (LUB) e cada update só faz o estado crescer; como o LUB é comutativo, associativo e idempotente, a ordem e a duplicação dos merges não importam, e com entrega eventual e terminação fica garantida a SEC. Num CmRDT (baseado em operações), não há merge: fica garantida a SEC se as operações concorrentes comutam, a entrega usa broadcast confiável com ordem causal e os métodos terminam. Uma réplica SEC está sempre disponível para leitura e escrita, mesmo sob partição de rede; o objeto SEC tolera até n-1 falhas simultâneas por parada e não exige consenso. O preço é semântico: SEC é incomparável com consistência sequencial, e a regra para operações concorrentes (por exemplo, add vencer ou remove vencer) é uma escolha que depende da aplicação.
Na prática
O Google Wave usou OT para edição ao vivo de texto rico e de documentos estruturados em geral, com clientes e um servidor, e com cada cliente esperando o reconhecimento do servidor antes de enviar mais operações, o que mantém o servidor simples (um único espaço de estados) ao custo do atraso de cerca de um tempo de ida e volta entre os blocos vistos por outro cliente. Você escolheria CRDT quando as réplicas precisam aceitar escritas mesmo sob partição de rede ou desconectadas, sem depender de consenso, como nos cenários de nuvem, P2P e operação desconectada citados no paper. Nesse caso é preciso aceitar a semântica fixada pelo tipo de dado para escritas concorrentes (como add-wins), que pode produzir resultados impossíveis em uma execução sequencial.
Use em um desenho
Pratique na escola de System Design os casos que dependem deste conceito.