Experimentos · JavaScript: das closures aos sistemas autônomos · Capítulo 17

Duas réplicas sem conexão

Tipos de dados replicados livres de conflito (CRDT)

Tema
ExperimenteDuas réplicas sem conexão
Mude um contador, um carrinho e reservas em duas réplicas e depois mescle em qualquer ordem, quantas vezes quiser. Dá para ver o “último a gravar” perder um incremento, a união trazer de volta a bola removida e um CRDT mesclar honestamente duas reservas para um lugar.

Tudo é calculado no seu navegador; nada é enviado.

Sobre este experimento

O que é um CRDT?

Um CRDT, tipo de dados replicado livre de conflito, é uma estrutura de dados feita para que réplicas alteradas de forma independente sempre possam ser mescladas sem coordenação, e o resultado não depende da ordem nem de quantas vezes as réplicas trocam estado. Réplicas que viram as mesmas mudanças chegam ao mesmo estado. Um G-Counter guarda uma célula por réplica e soma todas; um OR-Set marca cada adição, e a remoção apaga só as marcas que viu. Marc Shapiro e colegas formalizaram a ideia em 2011. Um CRDT garante a convergência, não que o estado mesclado respeite as regras da aplicação.

Quando um sistema escolhe a disponibilidade durante uma partição da rede, as réplicas continuam trabalhando separadas e precisam ser mescladas quando a conexão volta. O artigo da Amazon sobre o Dynamo, de 2007, usou o carrinho de compras como exemplo principal e mesclava carrinhos divergentes por união: um item adicionado nunca se perde, e um removido pode voltar. Muitos bancos simplesmente deixam valer a última gravação. Os CRDTs levam a regra de mesclagem para dentro da própria estrutura de dados.

Escolha uma aba e edite as duas réplicas, um celular e um notebook, que não se enxergam. Depois aperte “Mesclar A e B”, “Mesclar de novo” e “Mesclar na outra ordem”, ou rode o cenário do livro. O contador põe “último a gravar vence” ao lado de um G-Counter. O carrinho põe a união de conjuntos ao lado de um OR-Set e deixa tirar um item numa réplica enquanto ele é posto de novo na outra. A aba dos lugares tem um lugar livre, um botão de reserva em cada réplica, uma conexão que dá para cortar e a escolha entre responder já e combinar antes.

No livro, no Node 24.16.0, um contador em 5 com +1 em cada réplica mesclou em 6 com “último a gravar vence” e em 7 como G-Counter, em qualquer ordem e ao mesclar de novo. O carrinho {livro, bola}, com a bola tirada numa réplica e uma caneta posta na outra, saiu da união como livro, bola e caneta, e do OR-Set como livro e caneta. Quando a bola foi tirada numa réplica e posta de novo na outra, venceu a adição. Um lugar livre reservado nas duas réplicas virou 2 reservas, e a regra “não mais reservas que lugares” foi violada.

O ponto do capítulo está na última aba. Um CRDT promete que as réplicas convergem, não que o resultado faz sentido. Regras como não vender mais lugares do que existem ou não deixar uma conta ficar negativa exigem que as réplicas combinem antes de responder ao usuário, e nenhuma estrutura de dados elimina essa exigência. Onde as réplicas precisam se coordenar e quanta latência isso vale, quem decide é o programador.

Do livro

JavaScript: das closures aos sistemas autônomos · Capítulo 17

Os limites da consistência

Ao lado deste experimento no capítulo
O último modo do experimento mostra isso. No salão há um lugar livre, e duas pessoas o reservam em duas cópias que naquele momento não se enxergam. O contador de reservas se junta em dois sem um único conflito, porque num CRDT conflitos não existem por construção. Só que o lugar era um. Em 2014, Peter Bailis e coautores analisaram quais regras de integridade dos dados podem ser respeitadas sem coordenação entre as cópias e quais não. Uma regra como «não vender mais lugares do que existem» ou «não deixar a conta ficar negativa» exige que as cópias entrem em acordo antes de responder ao usuário. Nenhuma estrutura de dados elimina isso.