CRDTs: estruturas de dados para colaboração sem conflito

1. Fundamentos dos CRDTs na Arquitetura de Software

1.1. Definição e motivação

Em sistemas distribuídos, conflitos de escrita surgem quando múltiplos nós modificam o mesmo dado simultaneamente sem coordenação central. Arquiteturas tradicionais resolvem isso com bloqueios (pessimista) ou resolução posterior (otimista). Os CRDTs (Conflict-free Replicated Data Types) oferecem uma terceira via: estruturas de dados que, por construção matemática, nunca geram conflitos — mesmo sob concorrência total.

CRDTs garantem que réplicas divergentes possam ser fundidas (merged) sem perda de informação, produzindo um estado final idêntico em todos os nós, desde que todas as atualizações sejam eventualmente propagadas.

1.2. Propriedades matemáticas

Três propriedades fundamentais tornam os CRDTs possíveis:

  • Monotonicidade: o estado de uma réplica só cresce (nunca regride). Novas operações adicionam informação, nunca removem.
  • Comutatividade: a ordem das operações não altera o resultado final (A+B = B+A).
  • Idempotência: aplicar a mesma operação múltiplas vezes produz o mesmo resultado que aplicar uma vez.

Essas propriedades permitem que réplicas evoluam independentemente e depois sincronizem sem negociação.

1.3. Posicionamento arquitetural

CRDTs substituem abordagens baseadas em timestamps (como Last-Writer-Wins) que perdem dados. Enquanto timestamps exigem sincronização de relógios e descartam escritas "antigas", CRDTs preservam toda a informação — cada operação é um acréscimo monotônico ao estado.

Exemplo de comportamento:
Timestamp tradicional: A escreve "x=1", B escreve "x=2" → perde-se "1"
CRDT (PN-Counter): A incrementa +1, B incrementa +1 → resultado: 2 (soma correta)

2. Tipos de CRDTs e Seu Comportamento

2.1. State-based CRDTs (CvRDTs)

Propagam o estado completo da réplica. Quando dois nós se encontram, executam uma função merge que combina ambos os estados. A função merge deve ser:
- Comutativa: merge(A,B) = merge(B,A)
- Associativa: merge(merge(A,B),C) = merge(A,merge(B,C))
- Idempotente: merge(A,A) = A

Vantagem: tolerância a perda de mensagens — o próximo merge recupera tudo.
Desvantagem: alto custo de largura de banda (envia estado completo).

2.2. Operation-based CRDTs (CmRDTs)

Propagam apenas as operações (eventos). Cada operação deve ser:
- Efetivamente comutativa: operações concorrentes podem ser aplicadas em qualquer ordem.
- Entregue exatamente uma vez: requer middleware confiável (ex: entrega causal).

Vantagem: baixa largura de banda (apenas operações delta).
Desvantagem: dependência de ordenação causal, mais complexo de implementar.

2.3. Trade-offs arquiteturais

Característica State-based Operation-based
Largura de banda Alta (estado completo) Baixa (apenas ops)
Tolerância a perda Alta (merge recupera) Baixa (requer entrega confiável)
Complexidade Baixa Média
Latência de sincronização Pode ser maior Menor

3. Estruturas de Dados CRDT Clássicas

3.1. G-Counter e PN-Counter

G-Counter (Grow-only Counter): apenas incrementa. Cada réplica mantém seu próprio contador local. O valor global é a soma de todos os contadores.

text
// Estado de uma réplica com 3 nós
{
  "replica1": 5,
  "replica2": 3,
  "replica3": 7
}
// Valor total = 5 + 3 + 7 = 15
// Merge: max de cada posição
merge(A, B) = { max(A.r1, B.r1), max(A.r2, B.r2), ... }

PN-Counter: permite incrementos e decrementos usando dois G-Counters: um para positivos (P) e outro para negativos (N). O valor é P - N.

text
PN-Counter = { P: G-Counter, N: G-Counter }
valor = sum(P) - sum(N)

3.2. Set CRDTs

  • G-Set: apenas adiciona elementos. Remoções não são possíveis.
  • 2P-Set: dois conjuntos — "adicionados" e "removidos". Um elemento pode ser adicionado e depois removido, mas não readicionado.
  • LWW-Set (Last-Writer-Wins): cada elemento tem timestamp. Na dúvida, vence a operação mais recente.
  • OR-Set (Observed-Remove Set): permite readicionar elementos após remoção, usando tags únicas (UUIDs) para distinguir instâncias.
text
OR-Set estado:
{
  "elemento_a": { tag1, tag2, tag3 },  // 3 adições ativas
  "elemento_b": { tag4 }               // 1 adição ativa
}
// Remover "elemento_a" remove tag1, tag2, tag3
// Readicionar "elemento_a" gera nova tag única

3.3. Map CRDTs e Registros

LWW-Register: armazena um valor com timestamp. O merge escolhe o valor com timestamp mais recente. Simples, mas perde dados concorrentes.

Map com merge: cada chave do mapa é um CRDT independente. Permite composição: um mapa pode conter contadores, sets, ou outros mapas.

4. Modelagem de Dados com CRDTs

4.1. RGA (Replicated Growable Array)

RGA representa listas ordenadas (como caracteres em um documento). Cada elemento tem:
- Um identificador único (ID do nó + contador local)
- Uma referência ao elemento anterior na ordem desejada

Inserções concorrentes no mesmo local são resolvidas pela ordenação dos IDs (ex: usando timestamps lógicos).

text
Lista de caracteres:
"a" (id: n1-1) → "b" (id: n1-2) → "c" (id: n2-1)
Inserção concorrente entre "a" e "b":
- Nó 1 insere "x" (id: n1-3, anterior: n1-1)
- Nó 2 insere "y" (id: n2-2, anterior: n1-1)
Resultado merge: "a" → "x" (n1-3 < n2-2) → "y" → "b" → "c"

4.2. Logoot e Treedoc

Logoot: atribui identificadores baseados em posição (ex: fração entre dois vizinhos). Inserções geram novos identificadores que cabem entre os existentes. Escalável para documentos grandes.

Treedoc: estrutura de árvore binária onde cada caractere é uma folha. Inserções concorrentes no mesmo local criam subárvores que são ordenadas por ID de nó.

4.3. Composição para documentos JSON

Documentos complexos (como JSON) são modelados como mapas aninhados de CRDTs:

text
Documento JSON como CRDT:
{
  "usuarios": Map<ID, LWW-Register>,
  "contagem": PN-Counter,
  "tags": OR-Set<String>,
  "historico": RGA<String>
}

Cada campo é independente. Operações concorrentes em campos diferentes nunca conflitam.

5. Integração com Padrões de Arquitetura Distribuída

5.1. CRDTs e Eventual Consistency

CRDTs são a implementação mais pura de consistência eventual: garantem convergência sem resolução manual de conflitos. Diferente de sistemas baseados em timestamps (que descartam dados), CRDTs preservam toda a semântica.

5.2. Uso com Caching Strategies

Em arquiteturas offline-first, cada dispositivo mantém um cache local de CRDTs. Quando online, executa merge com o servidor. O merge é executado localmente no cliente, sem necessidade de lógica de resolução no servidor.

text
Cliente offline:
1. Aplica operações localmente (CRDT monotônico)
2. Persiste estado em IndexedDB/SQLite

Cliente online:
1. Envia estado local para servidor
2. Recebe estado do servidor
3. Executa merge(A_local, B_servidor)
4. Resultado: estado convergente sem perda

5.3. Relação com Offline-first

CRDTs são a fundação matemática do padrão offline-first. Frameworks como Automerge e Yjs implementam CRDTs especificamente para permitir:
- Edição local sem latência
- Sincronização assíncrona quando conectado
- Ausência de conflitos visíveis ao usuário

6. Cache Invalidation e CRDTs

6.1. Eliminação da invalidação tradicional

Em sistemas CRDT, não existe "cache stale" no sentido tradicional. Cada réplica contém um subconjunto monotônico do estado global. Ao fazer merge, o estado sempre avança — nunca regride. A invalidação é substituída por merge.

6.2. Merge sem perda

A monotonicidade garante que:
- Nenhuma operação é perdida
- Nenhum dado é sobrescrito injustamente
- O estado final é determinístico (dado o mesmo conjunto de operações)

6.3. Desafios remanescentes

  • Crescimento de metadados: identificadores e vetores de versão crescem com o número de réplicas e operações.
  • Garbage collection: remover metadados de réplicas que não existem mais requer protocolos adicionais (ex: tombstone GC).
  • Limites de memória: OR-Sets guardam todas as tags; RGA guarda todos os caracteres mesmo após remoção (até GC).

7. Implementação e Considerações de Performance

7.1. Estruturas de dados eficientes

  • Vetores de versão: array de inteiros, um por réplica. Tamanho O(n) onde n é número de réplicas ativas.
  • Mapas de estado: dicionários onde chave = ID da réplica, valor = estado local.
  • Bloom filters: para detectar rapidamente se um merge é necessário.

7.2. Serialização e compactação

Para transmissão em rede, CRDTs podem ser serializados como:
- Delta-state: apenas as diferenças desde o último merge (reduz largura de banda).
- Compressão de vetores: usar run-length encoding para vetores esparsos.

text
Vetor de versão completo: [5, 3, 0, 0, 0, 7, 0, 0, 2]
Vetor comprimido: {0:5, 1:3, 5:7, 8:2}

7.3. Estratégias de poda (pruning)

  • Tombstone GC: após confirmação de que todas as réplicas receberam uma remoção, os tombstones podem ser removidos.
  • Limpeza de réplicas mortas: réplicas que não enviam heartbeats há N períodos podem ter seus metadados removidos.
  • Compactação de histórico: em RGA, operações antigas podem ser substituídas por snapshots.

8. Casos de Uso e Limitações Arquiteturais

8.1. Aplicações reais

  • Google Docs: usa CRDTs internamente (operational transformation, precursor dos CRDTs modernos).
  • Figma: utiliza CRDTs para colaboração em design em tempo real.
  • Redis: módulo CRDT para replicação multi-mestre (Redis CRDTs).
  • Automerge: biblioteca JS/Go/Rust para aplicações offline-first.
  • Yjs: framework CRDT para web, usado em editores colaborativos.

8.2. Quando NÃO usar CRDTs

  • Consistência forte: se o sistema exige que leituras vejam todas as escritas anteriores (ex: transações bancárias), CRDTs não são adequados.
  • Operações que dependem de ordem global: se a semântica exige ordenação total (ex: "o terceiro item"), CRDTs oferecem apenas ordenação parcial.
  • Remoção com reutilização de identificadores: OR-Sets resolvem, mas com custo de metadados.

8.3. Futuro e tendências

  • Edge computing: CRDTs permitem que dispositivos IoT colaborem sem servidor central.
  • Sistemas multi-dispositivo: sincronização contínua entre smartphone, tablet e desktop.
  • CRDTs em bancos de dados: Riak, Redis e Cosmos DB já incorporam conceitos CRDT.
  • CRDTs híbridos: combinação de state-based e operation-based para otimizar latência vs. largura de banda.

Referências