- CRDT (Conflict-free Replicated Data Type) é uma estrutura de dados distribuída que permite mesclagem consistente de dados sem coordenação, mesmo em situações de particionamento de rede ou edições simultâneas
- Quando a mesclagem de dados satisfaz comutatividade, associatividade e idempotência, todas as réplicas acabam convergindo para o mesmo estado
- Entre os tipos mais representativos estão G-Counter, PN-Counter, G-Set, 2P-Set, OR-Set, LWW-Register, MV-Register, RGA, WOOT e Logoot, cada um lidando com diferentes necessidades de adição, remoção, readição e preservação de ordem
- Delta CRDT aumenta a eficiência ao transmitir apenas as alterações, em vez do estado completo, e Garbage Collection é um desafio central para resolver o problema do acúmulo de metadados
- CRDT não é uma solução perfeita, mas é considerado uma opção poderosa em sistemas nos quais a disponibilidade é mais importante do que a consistência imediata
Conceitos básicos de CRDT
- CRDT é uma estrutura de dados que pode ser mesclada sem coordenação em ambientes distribuídos, mesmo quando há edições simultâneas
- Se a operação de mesclagem for comutativa (commutative), associativa (associative) e idempotente (idempotent), todas as réplicas convergem para o mesmo estado
- Ele é projetado com base no conceito de lattice (reticulado), de forma que o estado sempre se mova apenas “para cima”
- Ex.: o G-Counter mescla a contagem de cada réplica com
max, garantindo soma sem perda
- Há duas abordagens para CRDT: State-based (CvRDT) e Operation-based (CmRDT)
- CvRDT mescla o estado completo, enquanto CmRDT propaga as operações
Principais tipos de CRDT
- G-Counter: contador que só permite incremento, somando os valores de cada réplica
- PN-Counter: combina um G-Counter para incremento e outro para decremento, permitindo contagem nos dois sentidos
- G-Set: conjunto que só permite adição
- 2P-Set: permite adição e remoção, mas não readição
- LWW-Element-Set: baseado em timestamp, no qual a operação mais recente vence
- OR-Set: usa tags únicas para mesclar adições simultâneas sem perda de dados, com comportamento add-wins
- LWW-Register / MV-Register: para armazenar um único valor; o LWW tem um único vencedor, enquanto o MV preserva todos os valores simultâneos
- OR-Map: estrutura de mapa que combina OR-Set por chave
- RGA / WOOT / Logoot / LSEQ: CRDTs para dados de sequência com ordem
- RGA é baseado em árvore, WOOT em referências bidirecionais e Logoot/LSEQ em identificadores de posição
Conceitos avançados de CRDT
- Causal CRDTs: usam vetores de versão para rastrear relações causais, permitindo detecção de conflitos mais precisa
- Delta CRDTs: enviam apenas as mudanças (delta), em vez do estado completo, melhorando a eficiência de rede
- Tree CRDTs: dão suporte à replicação de dados hierárquicos (como sistemas de arquivos), exigindo manutenção da relação pai-filho
- Observed-Remove Shopping Cart: exemplo de carrinho de compras de e-commerce que combina OR-Set e PN-Counter
Problema de Garbage Collection
- Para garantir convergência, CRDT acumula metadados continuamente, o que causa um problema de crescimento infinito
- Ex.: tags no OR-Set, tombstones no RGA
- Existem várias estratégias, como expiração baseada em tempo, remoção baseada em consenso, rastreamento causal com vetores de versão, definição de limite superior de metadados e checkpoint/rebase
- Cada abordagem exige um equilíbrio entre segurança (evitar restauração zumbi) e eficiência de espaço
Desempenho e guia de escolha
- A complexidade de espaço e tempo varia conforme o tipo de CRDT, o número de réplicas, a quantidade de elementos e o número de tags
- G/PN-Counter é proporcional ao número de réplicas, OR-Set ao número de tags, e RGA acumula tombstones
- Delta CRDT melhora bastante o desempenho de mesclagem
- Critérios de escolha:
- Só precisa de adição → G-Counter, G-Set
- Precisa de remoção, mas não de readição → 2P-Set
- LWW é aceitável → LWW-Set/Register
- Preservar edições simultâneas → OR-Set, MV-Register
- Precisa manter ordem → RGA, Logoot
- Estrutura aninhada → OR-Map
Conclusão
- CRDT garante convergência sem coordenação, mas tem como desvantagens o crescimento de metadados e a complexidade
- É útil em sistemas orientados à disponibilidade, e cada CRDT é otimizado para um tipo específico de problema
- Na prática, é usado em paralelo com bancos de dados tradicionais, e uma estratégia de garbage collection é indispensável
- Não existe um “CRDT perfeito”; o essencial é escolher de acordo com os requisitos da aplicação
1 comentários
Comentários no Hacker News
Uma das coisas interessantes sobre CRDT é que não se trata apenas de uma biblioteca que combina vários CRDTs de baixo nível
Por exemplo, o Automerge é por si só um CRDT completo e garante consistência mesmo sob concorrência por meio de provas matemáticas
A equipe do Automerge valida o design com ferramentas de prova de teoremas como Isabelle e busca uma implementação rápida e correta aplicando as técnicas de desempenho mais recentes do mundo dos bancos de dados
Se você estiver criando um SaaS que precisa de colaboração em tempo real, como Notion ou Figma, pode aplicar imediatamente estruturas de dados colaborativas sem precisar dominar a teoria complexa
No backend, um armazenamento simples de chave-valor já é suficiente, e no frontend basta uma biblioteca
Eu também cheguei a criar uma biblioteca automerge baseada em Redis, e com pub/sub consegui implementar um servidor completo de sincronização persistente
Aproveitando o recurso de websocket do Webdis, também consegui montar rapidamente uma demo de sincronização de documentos entre vários navegadores
Se você quiser um DX melhor e um banco de dados full-stack baseado em CRDT, recomendo o Triplit.dev. O ritmo de desenvolvimento ficou um pouco mais lento, mas os recursos já estão bastante maduros
Pessoalmente, também gosto do Loro, mas ele ainda tem uma estrutura centrada em documentos, então falta um motor de consultas. Para obter os dados desejados, é preciso apontar diretamente para itens aninhados específicos
Foi um texto muito bem organizado, cobrindo desde o básico até conceitos avançados de CRDT
Como referência, o Riak ainda está sendo mantido na forma de OpenRiak
Desenvolvi CRDTs diretamente nos últimos dois anos, mas percebi que havia trade-offs demais e acabei migrando para um framework de OT baseado em IDs
Pretendo lançar o Docnode.dev nesta terça-feira. Gostaria de ouvir feedback
No futuro, também planejo adicionar um modo CRDT para situações em que P2P seja necessário
CRDT e OT são estruturas pensadas para resolver casos em que pessoas editam o mesmo parágrafo ao mesmo tempo, mas na prática isso quase não acontece
O OR-Set mencionado neste texto é semelhante ao método de merge que o Monotone já usava desde 2005
Mais detalhes podem ser vistos na documentação do MarkMerge
CRDT continua sendo uma área em que ainda é preciso implementar por conta própria
Há dois meses, também criei um motor de CRDT baseado em sequência inspirado no diamond types
Pedi ajuda à IA, mas ela não ajudou em nada nesse tipo de problema centrado em lógica
Senti que seria necessário um teste de caixa-preta para verificar se um LLM realmente consegue entender uma lógica nova
O texto foi excelente, mas acho que um glossário precisa mesmo de um índice (index)
Fico pensando se, no fim das contas, CRDT não é só empurrar os conflitos de merge do banco de dados para a lógica da aplicação
Se for escrito corretamente, é possível ter resolução automática de merge em qualquer camada
O maior problema foi lidar com conflitos de UNIQUE/PRIMARY KEY
Dá para resolver distribuindo namespaces de ID para cada servidor, fazendo a primeira criação vencer e renomeando ou removendo em caso de conflito
Usando um esquema EAV, é possível implementar facilmente travessia de grafo em SQL com CTEs recursivas
Porém, o PostgreSQL não tem um tipo ANY, então é difícil representar objetos com atributos variados, e a funcionalidade de FOREIGN KEY também precisa ser implementada manualmente
Ainda assim, a estrutura EAV é favorável a projetos de metaesquema como herança
Seria ótimo se fosse possível definir tipos de CRDT diretamente no PostgreSQL, mas hoje não dá para restringir operações de monoid
No fim, os CRDTs para colunas que não são chave precisam ser tratados na camada da aplicação
Em resumo, CRDT pode ser implementado dentro de um RDBMS, mas a abordagem muda conforme onde você decide colocar a lógica de negócio