Tipos de dados replicados sem conflitos (CRDTs) são uma classe de estruturas de dados que permitem colaboração e sincronização de dados perfeitas em sistemas distribuídos, permitindo atualizações colaborativas sem conflitos. Os CRDTs são projetados para alcançar consistência eventual entre múltiplas réplicas de dados, garantindo que mesmo quando as atualizações ocorrem de forma independente, todas as réplicas convergem para o mesmo estado sem exigir mecanismos complexos de resolução de conflitos.

Nesta postagem do blog, vamos nos aprofundar no que são CRDTs, explorar seus usos e tipos, entender como funcionam e aprender como implementá-los, com foco em JavaScript e na poderosa biblioteca Yjs.

Casos de uso de CRDTs

CRDTs são particularmente úteis em cenários onde a colaboração em tempo real e o suporte offline são cruciais:

1. Editores de texto colaborativos: Google Docs, Notion e Etherpad usam estruturas semelhantes a CRDT para edição em tempo real.
2. Ferramentas de design colaborativo: Figma, uma popular ferramenta de design baseada na web, usa CRDTs para permitir a colaboração em tempo real em projetos de design. Vários designers podem trabalhar no mesmo arquivo simultaneamente, com as alterações sincronizadas perfeitamente entre todos os usuários.
3. Bancos de dados distribuídos: RxDB e Riak usam CRDTs para replicação sem conflitos.
4. Jogos multijogador: para manter um estado de jogo consistente entre os jogadores.

Tipos de CRDT

Existem dois tipos principais de CRDTs:

1. CRDTs baseados em estado: replicam todo o estado da estrutura de dados. A fusão é feita comparando e reconciliando os estados de diferentes réplicas.
2. CRDTs baseados em operações: replicam as operações realizadas na estrutura de dados. A fusão é feita aplicando operações de diferentes réplicas de maneira comutativa.

Como funcionam os CRDTs

CRDTs (Tipos de dados replicados livres de conflitos) operam com base em princípios que garantem consistência eventual em todas as réplicas dos dados, mesmo quando as atualizações são feitas simultaneamente ou quando ocorrem partições de rede. Vamos nos aprofundar na mecânica:

Propriedades principais

1. Comutatividade: Esta propriedade garante que a ordem das operações não afeta o resultado final. Por exemplo, em um contador CRDT, incrementar em 2 e depois em 3 produz o mesmo resultado que incrementar em 3 e depois em 2.
2. Associatividade: Isso significa que o agrupamento de operações não importa. Usando o exemplo do contador novamente, (1 2) 3 é igual a 1 (2 3).
3. Idempotência: Aplicar a mesma operação várias vezes tem o mesmo efeito que aplicá-la uma vez. Isto é crucial para lidar com mensagens duplicadas em sistemas distribuídos.

Resolução de Conflitos

CRDTs resolvem conflitos automaticamente por design:

• Para CRDTs baseados em estado (CvRDTs), isso é conseguido por meio de uma função de mesclagem que combina os estados de duas réplicas. Esta função de mesclagem deve ser comutativa, associativa e idempotente.
• Para CRDTs baseados em operações (CmRDTs), as operações são projetadas para serem comutativas, garantindo que aplicá-las em qualquer ordem leve ao mesmo estado final.

Relógios Lógicos

Muitas implementações de CRDT usam relógios lógicos (como vetores de versão ou vetores de versão pontilhados) para rastrear o histórico causal das operações. Isso ajuda a determinar a ordem das operações simultâneas e a identificar quais atualizações uma réplica já viu.

Usando CRDTs em JavaScript com Yjs

Implementar CRDTs do zero pode ser complexo. No entanto, existem bibliotecas disponíveis que simplificam o processo. Para JavaScript, uma das bibliotecas CRDT mais populares é Yjs. É uma implementação CRDT de alto desempenho que oferece suporte a vários tipos de dados. Vamos criar um aplicativo simples de lista de tarefas usando Yjs, simulando vários usuários trabalhando no mesmo documento na memória.

Aqui está um exemplo de como implementar uma lista de tarefas compartilhada usando Yjs:

Vamos usar os ydocs criados:

Neste exemplo, criamos dois documentos Yjs (ydoc1 e ydoc2) para simular dois usuários trabalhando na mesma lista de tarefas. Cada documento tem seu próprio mapa compartilhado para todos.

Definimos funções para adicionar, atualizar e excluir todos, bem como uma função syncDocs para sincronizar manualmente o estado entre os dois documentos. Isso simula o que aconteceria em um ambiente de rede onde as atualizações são trocadas entre clientes.

Conclusão

CRDTs fornecem uma solução poderosa para a criação de aplicativos colaborativos e distribuídos que podem funcionar perfeitamente on-line e off-line. Embora os conceitos subjacentes possam ser complexos, bibliotecas como Yjs tornam mais fácil para os desenvolvedores aproveitarem o poder dos CRDTs em seus aplicativos. À medida que os sistemas distribuídos se tornam mais predominantes, compreender e utilizar CRDTs se tornará uma habilidade cada vez mais valiosa para os desenvolvedores.

Links úteis

1. Sim
2. CRDT
3. Tiptap - Um editor de texto colaborativo