Convergência É uma Propriedade da Sua Função de Merge, Não da Rede

Uma vez lancei uma funcionalidade "colaborativa" com um modelo de sync que eu tinha certeza de que estava correto: cada cliente escrevia o estado completo do documento em um store compartilhado, marcado com um timestamp de relógio de parede, e na leitura o timestamp mais recente vencia. Last-writer-wins. Sobreviveu a todas as demos. Então duas pessoas editaram offline em um trem, reconectaram, e a tarde inteira de edições de uma delas desapareceu. Nenhum erro. Nenhum diálogo de conflito. O timestamp mais novo simplesmente sobrescreveu o estado mais antigo, e o estado mais antigo continha trabalho que o mais novo nunca tinha visto.

Aquilo não era um bug de rede. Todos os pacotes chegaram. Era um bug de merge. O store não tinha função de merge nenhuma — tinha uma sobrescrita, disfarçada de merge.

Essa é a armadilha que quero documentar, porque a correção é mais precisa do que "use uma biblioteca de CRDT". A ideia útil por trás dos CRDTs é pequena e testável: convergência é uma propriedade matemática da função que você usa para combinar dois estados. Acerte essa função e as réplicas concordam independentemente da ordem, duplicação ou atraso das atualizações entre elas. Erre, e nenhuma quantidade de lógica de retry, vector clocks adicionados depois ou ordenação cuidadosa vai te salvar.

O tema voltou à tona porque o ferramental cruzou um limiar. O Automerge 3.0, lançado em julho de 2025, reduziu o uso de memória em mais de 10x — colar Moby Dick em um documento caiu de 700 MB em memória para 1,3 MB, e um documento de histórico longo que não tinha terminado de carregar após 17 horas abriu em 9 segundos (anúncio do Automerge 3.0). Esse lançamento colocou o sync local-first com CRDTs de volta na primeira página do Hacker News e de volta à conversa de "será que eu deveria usar isso de verdade?". Antes de adotar uma biblioteca, vale a pena entender o que a função de merge está fazendo, e o que ela custa.

Por que last-writer-wins está eventualmente errado

Um registrador last-writer-wins (LWW) é o "merge" mais simples possível: manter o valor com o maior timestamp. Ele é comutativo e associativo, então de fato converge — toda réplica termina com o mesmo valor. O problema é qual valor.

LWW converge por deleção. Quando duas réplicas têm atualizações concorrentes, uma delas é descartada. Para um escalar único, como um flag de status, tudo bem; a escrita de alguém tinha que vencer. Para qualquer coisa com estrutura interna — um conjunto de itens de carrinho, um documento, uma lista de colaboradores — o LWW joga fora as partes do perdedor que o vencedor nunca continha. Foi exatamente assim que minha tarde de edições no trem desapareceu. O estado era estruturado, o merge o tratou como opaco, e o merge foi destrutivo.

Então o requisito é mais afiado do que "convergir". Eu quero um merge que convirja e preserve toda atualização concorrente que não contradiga logicamente outra. É isso que um Conflict-free Replicated Data Type oferece, e a garantia tem nome: consistência eventual forte. Réplicas que receberam o mesmo conjunto de atualizações estão no mesmo estado, sem rodada de coordenação e sem protocolo de consenso (Shapiro et al., "Conflict-free Replicated Data Types," 2011).

O que a convergência realmente exige

A garantia inteira repousa sobre três propriedades da função de merge. Chame a função de ⊔ (join):

• Comutativa: a ⊔ b = b ⊔ a. A ordem de chegada não importa.
• Associativa: (a ⊔ b) ⊔ c = a ⊔ (b ⊔ c). O agrupamento não importa.
• Idempotente: a ⊔ a = a. Receber a mesma atualização duas vezes não importa.

Essas três juntas significam que o conjunto de estados possíveis forma um semirreticulado de junção (join-semilattice) e ⊔ calcula o supremo (least upper bound). Quando isso vale, a rede pode fazer o seu pior — reordenar mensagens, entregar duplicatas, segurar um pacote por uma hora — e toda réplica que viu as mesmas atualizações chega ao estado idêntico. As garantias de ordenação pelas quais você normalmente lutaria na camada de transporte tornam-se irrelevantes, porque o merge não se importa com ordem.

O truque que considero esclarecedor: pare de raciocinar sobre sequências de operações e comece a raciocinar sobre conjuntos de fatos. Cada réplica acumula fatos. Merge é união de conjuntos sobre esses fatos. União é trivialmente comutativa, associativa e idempotente. O problema de design inteiro se reduz a escolher o que é um "fato" de modo que a união produza a semântica que você quer.

O diagrama abaixo mostra a forma que mantenho na cabeça: duas réplicas acumulam fatos diferentes enquanto desconectadas, e então um único merge funde os dois conjuntos de fatos em um estado que contém tudo que cada lado observou.

​

Um OR-Set mínimo que você pode executar

O exemplo canônico em que o merge precisa ser mais esperto do que união-de-valores é um conjunto com adições e remoções. Um conjunto simples falha imediatamente: se a réplica A adiciona pen e a réplica B concorrentemente remove pen, a união de conjuntos diz presente e a diferença de conjuntos diz ausente, e as duas réplicas divergem. Não há ordem de operações que resolva isso, porque as operações são concorrentes — nenhuma aconteceu "depois" da outra.

O Observed-Remove Set (OR-Set) resolve isso com semântica add-wins. Uma adição e uma remoção concorrentes do mesmo elemento se resolvem em favor da adição. Uma remoção só cancela as adições específicas que ela de fato observou (Almeida, Shoker, Baquero, "Delta State Replicated Data Types," 2018). O mecanismo é uma tag única por adição — um "dot" no formato replica:counter. O elemento está presente se tiver pelo menos uma tag de adição que nenhuma remoção marcou como tombstone. O merge é a união das tags de adição e a união dos tombstones. União, de novo, então as três propriedades valem de graça.

Aqui está a coisa toda em TypeScript, executável como está:

// orset.ts — um Observed-Remove Set (OR-Set) CRDT add-wins, baseado em estado.
// A convergência vem da função de merge, não da rede.

type Tag = string; // um "dot" único: `${replica}:${counter}`

class ORSet<T> {
  private adds = new Map<T, Set<Tag>>();
  private removed = new Set<Tag>();
  private counter = 0;

  constructor(private readonly replica: string) {}

  add(e: T): void {
    const tag = `${this.replica}:${this.counter++}`;
    const tags = this.adds.get(e) ?? new Set<Tag>();
    tags.add(tag);
    this.adds.set(e, tags);
  }

  remove(e: T): void {
    // Marca como tombstone apenas as tags que esta réplica já observou para e.
    for (const tag of this.adds.get(e) ?? []) this.removed.add(tag);
  }

  has(e: T): boolean {
    for (const tag of this.adds.get(e) ?? []) {
      if (!this.removed.has(tag)) return true; // existe uma tag de adição viva
    }
    return false;
  }

  values(): T[] {
    return [...this.adds.keys()].filter((e) => this.has(e)).sort();
  }

  clone(): ORSet<T> {
    const c = new ORSet<T>(this.replica);
    for (const [e, tags] of this.adds) c.adds.set(e, new Set(tags));
    c.removed = new Set(this.removed);
    return c;
  }

  // Supremo (least upper bound): une as tags de adição, une os tombstones.
  // comutativo + associativo + idempotente => a ordem não pode mudar o resultado.
  merge(other: ORSet<T>): void {
    for (const [e, tags] of other.adds) {
      const mine = this.adds.get(e) ?? new Set<Tag>();
      for (const t of tags) mine.add(t);
      this.adds.set(e, mine);
    }
    for (const t of other.removed) this.removed.add(t);
  }
}

// Duas réplicas divergem offline, depois trocam estado.
const a = new ORSet<string>("A");
const b = new ORSet<string>("B");

a.add("book");
a.add("pen");
b.merge(a.clone());     // B sincroniza uma vez e aprende os dois itens
b.remove("pen");        // B remove pen (observou a tag de adição de A)
a.add("pen");           // A concorrentemente readiciona pen com uma tag NOVA

// Merge nas duas direções a partir de cópias independentes.
const ab = a.clone(); ab.merge(b);
const ba = b.clone(); ba.merge(a);

// Idempotência: aplicar o mesmo delta duas vezes não muda nada.
const twice = ab.clone(); twice.merge(b); twice.merge(b);

console.log("A then B :", ab.values());
console.log("B then A :", ba.values());
console.log("merged 2x:", twice.values());
console.log("converged:", JSON.stringify(ab.values()) === JSON.stringify(ba.values()));
console.log("add-wins :", ab.has("pen")); // a readição concorrente vence a remoção

Execute com um comando:

A saída:

As linhas que merecem pausa são o merge e o cenário. O merge não faz nada além de duas uniões, e é por isso que fazer merge de A-depois-B e de B-depois-A produz resultados byte a byte idênticos, e por isso fazer merge do mesmo estado duas vezes é um no-op. O cenário é a parte que quebra um conjunto ingênuo: B remove pen depois de observar a tag de adição original de A, mas a readição de A cunha uma tag nova que a remoção de B nunca viu. Essa tag sem tombstone mantém pen no conjunto. Add-wins não é uma regra de desempate colocada por cima — ela emerge diretamente do design de tags e tombstones.

Um detalhe que errei na primeira vez: remove deve marcar como tombstone apenas as tags que a réplica observou até o momento, não o nome do elemento. Se você remove pelo nome do elemento, uma remoção pode cancelar uma adição futura que ela nunca viu, e você perde o add-wins. A garantia inteira vive naquele único loop.

O que o add-wins custa

CRDTs não são convergência grátis. São convergência paga em metadados, e a conta chega em três lugares.

Tombstones nunca vão embora. Meu conjunto removed só cresce. Uma deleção não recupera espaço; ela adiciona um registro. Para CRDTs de texto os números são concretos: cerca de 16–32 bytes de metadados por caractere, então um documento de 50.000 palavras pode carregar 1,6–3,2 MB de overhead além do conteúdo, e um documento de 1.000 caracteres muito editado pode conter dezenas de milhares de tombstones internamente. CRDTs delta-state — o design por trás do artigo de Almeida acima — reduzem isso enviando deltas pequenos e rastreando remoções em um contexto causal compacto em vez de tombstones por elemento, mas eles reduzem o overhead, não o eliminam.

Memória era o teto real, não disco. Foi isso que tornou o Automerge 3.0 notável. O formato comprimido em disco já era pequeno; o custo era que carregar um documento expandia seu histórico completo na memória. Rearquitetar para manter a representação colunar comprimida em tempo de execução foi o que produziu a queda de 700 MB → 1,3 MB. Se você está avaliando uma biblioteca de CRDT, a pergunta a fazer não é "qual o tamanho do arquivo", mas "quanta memória um documento aberto com histórico longo consome", porque é aí que os designs mais antigos desabavam.

Você pode nem precisar de consenso descentralizado. Este é o ponto contracorrente que vale levar a sério. CRDTs resolvem a resolução de conflitos sem um servidor coordenador. Se você já tem um servidor — e a maioria dos produtos SaaS tem — Operational Transformation oferece resolução determinística de conflitos sem tombstones, sem IDs por elemento e sem problema de garbage collection, ao preço de uma autoridade central que ordena as operações. Adotar um CRDT em um app centralizado porque parece mais moderno significa pagar o imposto de metadados por uma autonomia que você não está usando. A troca honesta é: CRDTs compram offline-first e peer-to-peer; se você não precisa de nenhum dos dois, um log ordenado pelo servidor é mais simples e mais barato.

Quando recorrer a isso, e quando não

Do que aprendi trabalhando nisso, minha regra prática:

• Recorra a um CRDT quando réplicas precisam aceitar escritas desconectadas e reconciliar depois sem árbitro central — mobile offline-first, apps desktop local-first, stores multi-região ativo-ativo, colaboração peer-to-peer.
• Projete o fato, não a operação. Decida o que é uma unidade de evidência (uma tag de adição, um incremento de contador, um registrador versionado) de modo que a união de conjuntos produza a semântica que você quer. Se a união não produz, você escolheu o fato errado.
• Teste a álgebra, não só a funcionalidade. As três propriedades são verificáveis diretamente: faça merge nas duas ordens e verifique igualdade; faça merge de uma duplicata e verifique que nada muda. Testes baseados em propriedades sobre intercalações aleatórias de operações pegam um merge quebrado mais rápido do que qualquer teste de integração, porque um merge quebrado é uma equação quebrada, não uma requisição quebrada.
• Evite quando um servidor já ordena suas escritas e você não precisa de edição offline. Operational Transformation ou uma escrita versionada simples com controle de concorrência otimista custará muito menos metadados.
• Orce o crescimento de tombstones desde o início. Se os documentos são longevos e muito editados, planeje compactação ou um design delta-state antes do lançamento, não depois de um incidente de memória.

A frase que quero guardar: um map last-writer-wins não é eventualmente consistente, é eventualmente errado, e a diferença entre os dois é se a sua função de merge é comutativa, associativa e idempotente. Todo o resto — tags, tombstones, codificações delta, a escolha da biblioteca — é detalhe de implementação a serviço dessas três propriedades.