Notion adota CRDT baseado em RGA para edição concorrente

O problema: last write wins apagava edições

Até 2025, o editor do Notion não era verdadeiramente colaborativo. Cada bloco de página era armazenado como um registro separado no banco de dados, e o servidor processava as atualizações à medida que chegavam: quem enviava por último vencia, em um modelo "last write wins" (LWW). Com dois usuários editando o mesmo bloco ao mesmo tempo, as alterações de um deles eram completamente perdidas. Quanto maior o número de colaboradores, maior a chance de sobrescrita. Edição simultânea de blocos diferentes funcionava, mas o mesmo bloco em edição concorrente podia custar o trabalho de alguém. O plano de lançar um Offline Mode tornava o risco ainda maior: alguém editando offline poderia perder todas as mudanças se outros tivessem editado os mesmos blocos antes de reconectar.

A solução foi adotar um CRDT (Conflict-free Replicated Data Type), estrutura de dados que permite a múltiplos clientes manter cópias locais dos mesmos dados e mesclar alterações simultâneas de forma determinística, sem perder as edições de ninguém.

RGA: a base do CRDT

O CRDT do Notion é baseado no Replicated Growable Array (RGA), um CRDT de sequência clássico. É uma árvore que contém todos os caracteres já inseridos, cada um como um nó com ID único e estável, chamado de "text item". Operações de inserção e exclusão referenciam esses IDs, chamados de "origins". A árvore é inicializada com itens de início e fim.

A exclusão não remove o item: marca-o como "tombstone" (túmulo), porque operações em voo ou offline podem depender dos IDs dos caracteres apagados - removê-los da árvore deixaria as operações sem destino.

Os IDs combinam um ID de sessão (que diferencia clientes) e um relógio de Lamport, um timestamp lógico crescente. Dois clientes podem colidir no relógio, mas não na sessão; itens com o mesmo origin são ordenados pelo timestamp lógico mais recente, com o ID de sessão como desempate.

Para ganhar eficiência de armazenamento, o sistema não atribui um ID a cada caractere: caracteres contíguos da mesma sessão e relógio são agrupados em uma única unidade, com o comprimento armazenado junto.

Rich text com Peritext

Documentos do Notion têm formatação como negrito, itálico e menções, o que exige resolver conflitos também em anotações. Para isso, o time implementou operações baseadas no algoritmo Peritext. As árvores armazenam operações de adicionar e remover anotações sobre os text items, aplicadas na interpretação da árvore.

As âncoras de início e fim definem se uma anotação é "extensível": negrito é extensível (texto digitado no fim permanece em negrito, então a âncora final fica "antes" do limite), enquanto hyperlinks não são (texto digitado depois não herda o link). Cada item pode carregar um array de operações de anotação para suportar anotações sobrepostas; uma anotação que atravessa vários itens guarda sua operação apenas no primeiro, com o intervalo de IDs identificando o resto.

Divisão concorrente de blocos

No Notion, apertar "Enter" no meio de um bloco cria um novo bloco e divide o texto entre os dois. Em edição concorrente, a divisão pode ocorrer enquanto outro usuário acrescenta texto ao bloco original - e o acréscimo precisa parar no bloco correto, mesmo que o origin da operação não exista mais no mesmo registro do banco.

O time criou três conceitos: "text slices" (as partes de texto de um bloco, que se dividem e migram entre blocos), "text slice trees" (a árvore que organiza as fatias de um bloco) e "text instances" (agrupamento estável de fatias descendentes da mesma fatia inicial, com o ID do bloco de origem). Um mapeamento entre instâncias de texto e blocos permite localizar onde editar cada fatia.

Uma limitação dessa abordagem é que pode ser preciso carregar muitos blocos: dividir um bloco 99 vezes gera 100 blocos com fatias da mesma instância, todos carregados para inserir um caractere. Para mitigar isso, cada fatia recebe um "search label" - vazio no início e acrescido de L ou R a cada divisão -, incluído no mapeamento e nas operações para restringir a consulta. A busca usa correspondência de prefixo (e não igualdade exata) porque a fatia alvo pode ter sido dividida simultaneamente. Na prática, o rótulo é codificado de forma compacta, com eficiência de armazenamento cinco vezes melhor que armazenar strings literais no Postgres.

O time suspeita - sem validar - que a técnica de divisão também sirva para outros sistemas que modelam trechos de texto como nós independentes, como um editor ProseMirror com Yjs, em que divisões são modeladas como exclusão num bloco e inserção no outro, o que pode deixar edições concorrentes no nó original.

Implantação e consequências

O sistema entrou em produção em julho de 2025, tornando-se uma das maiores implantações de CRDT do mundo, com milhões de operações processadas por minuto. O modelo de dados também dá suporte ao Offline Mode e à colaboração de agentes, e serve de base para funcionalidades futuras, como presença de colaboradores em tempo real e sugestões em lote que possam ser publicadas e aceitas em conjunto.