Como contar os hits da página google.com? E como armazenar o contador de gostos de usuários muito populares? Este artigo propõe considerar a solução desses problemas usando o CRDT (tipos de dados replicados sem conflitos, que em russo se traduz aproximadamente como tipos de dados replicados sem conflitos) e, no caso mais geral, tarefas de sincronização de réplicas em um sistema distribuído com vários nós principais.

1. Introdução

Há muito que estamos acostumados a usar aplicativos como um calendário ou um serviço de anotações como o Evernote. Eles estão unidos pelo fato de permitir que você trabalhe offline, de vários dispositivos e para várias pessoas ao mesmo tempo (nos mesmos dados). O desafio enfrentado pelos desenvolvedores de cada aplicativo é como garantir a sincronização mais "suave" dos dados alterados simultaneamente em vários dispositivos. Idealmente, o envolvimento do usuário não deve ser necessário para resolver conflitos de mesclagem.

Em um artigo anterior, já consideramos uma abordagem para resolver esses problemas - Transformação Operacional, também descreverá um método muito semelhante que possui vantagens e desvantagens (por exemplo, o CRDT para JSON ainda não foi inventado. Upd: Graças ao msvn pelo link, aqui Aqui está um projeto dos autores de um artigo de pesquisa sobre a implementação do JSON no CRDT)

2. Forte consistência eventual

Recentemente, muito trabalho foi escrito e muita pesquisa foi feita no campo da eventual consistência. Na minha opinião, agora há uma forte tendência para uma mudança de consistência forte para várias opções de consistência, para pesquisar qual consistência em que situações / sistemas é mais rentável aplicar, para repensar as definições existentes. Isso leva a alguma confusão, por exemplo, quando os autores de algumas obras, falando sobre consistência, significam consistência eventual com alguma propriedade adicional, e outros autores usam certa terminologia para isso.

A pergunta levantada pelos autores de um dos artigos critica a definição atual de consistência eventual: de acordo com ela, se o seu sistema sempre responde “42” a todas as solicitações, tudo está bem, e eventualmente é consistente.

Sem violar a correção deste artigo, eu, seguindo os autores dos artigos originais, usarei a seguinte terminologia (observe que essas não são definições estritas, são diferenças):

• Consistência forte (SC): todas as operações de gravação são estritamente ordenadas, uma solicitação de leitura em qualquer réplica retorna o mesmo resultado, último registro. É necessário um consenso em tempo real para resolver conflitos (com as conseqüências resultantes), pode suportar uma queda para n / 2 - 1 nós.
• Eventual consistência (EC): atualize os dados localmente, envie a atualização ainda mais. A leitura em réplicas diferentes pode retornar dados obsoletos. Em caso de conflito, revertemos ou de alguma forma decidimos o que fazer. T.O. ainda é necessário um consenso, mas não mais em tempo real .
• Forte consistência eventual (SEC): EC + para resolver conflitos, as réplicas têm um algoritmo predefinido. T.O. não é necessário um consenso , pois pode suportar uma queda para n - 1 nós.

Observe que a SEC (por assim dizer) resolve o problema do teorema da CAP: todas as três propriedades são satisfeitas.

Portanto, estamos prontos para doar o SC e queremos ter um certo conjunto de tipos de dados básicos para o nosso sistema distribuído potencialmente instável que resolverá automaticamente os conflitos de gravação para nós (nenhuma interação do usuário ou solicitação a algum árbitro é necessária)

3. Tarefas sobre curtidas e hits

Sem dúvida, existem vários algoritmos para resolver esses problemas. O CRDT oferece uma maneira bastante elegante e fácil.

Contagem de hits do Google.com.br:

O google.com processa aproximadamente 150.000 solicitações por segundo de todo o mundo. Obviamente, o contador precisa ser atualizado de forma assíncrona. As filas resolvem parcialmente o problema - por exemplo, se fornecermos uma API externa para obter esse valor, teremos que fazer a replicação para não colocar o repositório com solicitações de leitura. E se já houver replicação, talvez sem filas globais?

Contando gostos do usuário:

A tarefa é muito semelhante à anterior, só que agora você precisa contar hits únicos.

4. Terminologia

Para uma compreensão mais completa do artigo, você precisa conhecer os seguintes termos:

1. Idempotência
   Diz que a aplicação da operação várias vezes não altera o resultado.
   Exemplos - operação GET ou adição com zero: $$$f (x) = x + 0$
   
2. Comutatividade
   $$$f (x, y) = f (y, x)$
   
3. Ordem parcial
   Reflexividade + transitividade + antissimetria
   
4. Meia estrutura
   Conjunto parcialmente pedido com a face superior (inferior) exata
   
5. Vetor de versão
   Um vetor de dimensão é igual ao número de nós e cada nó, quando ocorre um determinado evento, incrementa seu valor no vetor. Durante a sincronização, os dados são transmitidos com esse vetor e isso introduz uma relação de ordem, que permite determinar qual réplica possui dados antigos / novos.

5. Modelos de sincronização

Baseado no estado:

Também chamada de sincronização passiva, forma o Tipo de dados replicado convergente - CvRDT.
É usado em sistemas de arquivos como NFS, AFS, Coda e nos armazenamentos KV Riak, Dynamo
Nesse caso, as réplicas trocam os estados diretamente, a réplica de recebimento mescla o estado recebido com seu estado atual.


Para executar a convergência de réplicas usando essa sincronização, é necessário que:

• Os dados formaram um semilático
• A função de mesclagem produziu um limite superior exato
• As réplicas formaram um gráfico conectado.

Um exemplo:

• Conjunto de dados: números naturais $$$\ mathbb {N}$
• Item mínimo: $$$- \ infty$
• $$$mesclagem (x, y) = máximo (x, y)$

Esses requisitos nos fornecem uma função de mesclagem comutativa e idempotente que cresce monotonicamente em um determinado conjunto de dados:


Isso garante que as réplicas converjam mais cedo ou mais tarde e permita que você não se preocupe com o protocolo de transferência de dados - podemos perder mensagens com um novo estado, enviá-las várias vezes e até mesmo em qualquer ordem .

Baseado em operação:

Também chamado de Sincronização Ativa, ele forma o Tipo de Dados Replicado Comutativo - CmRDT.
Utilizado em sistemas cooperativos como Bayou, Rover, IceCube, Telex.

Nesse caso, as réplicas trocam operações de atualização de estado. Ao atualizar dados, a réplica original:

• Chama o método generate (), que retorna o método effector () para executar nas réplicas restantes. Em outras palavras, effector () é o fechamento para alterar o estado das réplicas restantes.
• Aplicando um efetor a um estado local
• Envia efetor para todas as outras réplicas

Para executar a convergência de réplicas, as seguintes condições devem ser atendidas:

• Protocolo de Entrega Confiável
• Se o efetor for entregue a todas as réplicas de acordo com a ordem inserida (para um determinado tipo), os efetores simultâneos serão comutativos ou
• Se o efetor for entregue a todas as réplicas sem levar em conta o pedido, todos os efetores serão comutativos.
• Caso o efetor possa ser entregue várias vezes, ele deve ser idempotente
• Algumas implementações usam filas (Kafka) como parte do protocolo de entrega.

Baseado em Delta:

Considerando o estado / operação, é fácil perceber que, se uma atualização altera apenas parte do estado, não faz sentido enviar o estado inteiro e, se um grande número de alterações afeta um estado (por exemplo, um contador), você pode enviar uma alteração agregada e nem todas as operações mudanças.

A sincronização delta combina as duas abordagens e envia mutadores delta que atualizam o estado de acordo com a data da sincronização mais recente. Na sincronização inicial, é necessário enviar o estado completamente, e algumas implementações nesses casos já levam em consideração o estado das réplicas restantes ao construir delta-mutadores.

O próximo método de otimização é compactar o log baseado em op, se atrasos forem permitidos.

Baseado em operação pura:

Há um atraso na criação do opector na sincronização baseada em op. Em alguns sistemas, isso pode não ser aceitável, então você deve enviar a alteração original com o custo de complicar o protocolo e a quantidade adicional de metadados.

Abordagens de uso padrão:

• Se as atualizações forem enviadas imediatamente no sistema, a escolha com base no estado seria uma má escolha, pois o envio de todo o estado é mais caro do que apenas uma operação de atualização. Baseado em Delta funciona melhor, mas nesse caso em particular, a diferença com base em estado será pequena.
• Se você precisar sincronizar a réplica após uma falha , será baseada em estado e em delta a escolha perfeita. Se você precisar usar operações, então as opções são:
  
  1) Role todas as operações perdidas desde o momento da falha
  2) Uma cópia completa de uma das réplicas e reversão de operações perdidas
• Como observado acima, o sistema operacional exige que as atualizações sejam entregues exatamente uma vez para cada réplica. O requisito de entrega apenas uma vez pode ser omitido se o efetor for idempotente. Na prática, é muito mais fácil implementar o primeiro que o segundo.

A relação entre Op-based e State:

Duas abordagens podem ser emuladas uma pela outra, portanto, no futuro, consideraremos o CRDT sem referência a qualquer modelo de sincronização específico.

6. CRDT

6.1 Contador

Um número inteiro que suporta duas operações: inc e dec. Como exemplo, considere possíveis implementações para sincronizações baseadas em op e baseadas em estado:

Contador baseado em Op:

Obviamente, basta enviar atualizações. Exemplo para inc:

function generator() { return function (counter) { counter += 1 } } 

Contador baseado em estado:

A implementação não é mais tão óbvia, pois não está claro como deve ser a função de mesclagem.

Considere as seguintes opções:

Contador de aumento monotônico (contador de incremento apenas, contador G):

Os dados serão armazenados como um vetor de dimensão igual ao número de nós (vetor de versão) e cada réplica aumentará o valor na posição com seu ID.

A função de mesclagem assumirá o máximo nas posições correspondentes, e o valor final é a soma de todos os elementos do vetor

$$

$$\ begin {align} inc () &: V [id ()] = V [id ()] + 1 \\ valor () &: \ sum_ {i = 0} ^ {n} V [i] \\ mesclar (C_1, C_2) &: i \ em [1..n] \ Resultado [i] = máximo (C_1.V [i], C_2.V [i]) \ end {align$$

Você também pode usar o G-Set (veja abaixo)

Aplicação:

• Contando cliques / hits (sic!)

Contador com suporte de decremento (contador PN)

Começamos dois contador G - um para operações de incremento, o segundo - para decremento

Aplicação:

• O número de usuários conectados em uma rede p2p, como o Skype

Contador não negativo

Uma implementação simples ainda não existe. Sugira suas idéias nos comentários, discuta.

6.2 Registrar

Uma célula de memória com duas operações - atribuir (escrever) e valor (ler).
O problema é que a atribuição não é comutativa. Existem duas abordagens para resolver esse problema:

Último registro de vitórias de gravação (LWW-Register):

Entramos no pedido completo por meio da geração de ID exclusivo para cada operação (registro de data e hora, por exemplo).

Um exemplo de sincronização é a troca de pares (valor, id):


Aplicação:

• Colunas em cassandra
• NFS - arquivo no todo ou em parte

Registre-se com vários valores (Multi-Value Register, MV-Register):

A abordagem é semelhante a um contador G - armazenamos o conjunto (valor, vetor de versão). Registre o valor - todos os valores, ao mesclar - o LWW separadamente para cada valor no vetor.


Aplicação:

• Cesta na Amazônia. Um bug conhecido é associado a isso, quando, após remover um item da cesta, ele aparece lá novamente. O motivo é que, apesar do registro armazenar um conjunto de valores, ele não é um conjunto (veja a figura abaixo). A propósito, a Amazon nem considera isso um bug - na verdade, aumenta as vendas.
• Riak. Em um caso mais geral, mudamos o problema de escolher o valor real (observação - não há conflito!) Para o aplicativo.

Explicação do bug na Amazon:

6.3 Lotes

O conjunto é o tipo básico para a construção de contêineres, mapas e gráficos e suporta operações - add e rmv, que não são comutativas.

Considere a implementação ingênua do conjunto baseado em op, no qual add e rmv são executados à medida que chegam (add chega a 1 e 2 réplicas ao mesmo tempo e, em seguida, rmv vai para 1)


Como você pode ver, as réplicas eventualmente se dispersaram. Considere as várias opções para construir conjuntos sem conflito:

Conjunto crescente (G-Set):

A solução mais fácil é impedir que itens sejam excluídos. Tudo o que resta é a operação de adição, que é comutativa. A função de mesclagem é a união de conjuntos.

Conjunto bifásico (conjunto 2P):

Permitimos que você exclua, mas não será possível adicioná-lo novamente após a remoção. Para implementar, configuramos um conjunto separado de elementos remotos do conjunto G (esse conjunto é chamado de conjunto de marca de exclusão)
Exemplo para baseado em estado:

$$

$$\ begin {align} pesquisa (e) &: e \ em A \ land e \ não em R \\ add (e) &: A = A \ cup \ {e \} \\ rmv (e) &: R = R \ cup \ {e \} \\ mesclar (S_1, S_2) &: \\ Res & ult.A = S_1.A \ cup S_2.A \\ Res & ult.R = S_1.R \ cup S_2.R \ end {align}$$

Conjunto de elementos LWW:

A próxima maneira de implementar um conjunto sem conflito é introduzir um pedido completo, uma das opções é gerar registros de data e hora exclusivos para cada elemento.

Temos dois conjuntos - add-set e remove-set, quando add () é chamado, add (elemento, unique_id ()), ao verificar se há um elemento no conjunto - veja onde o timestamp é maior - em remove-set ou em add-set

Conjunto PN:

Variação com a ordenação do conjunto - iniciamos um contador para cada elemento, quando o adicionamos, aumentamos, quando o excluímos, diminuímos. Um elemento está no conjunto se seu contador for positivo.

Observe o efeito interessante - na terceira réplica, adicionar um elemento não leva à sua aparência.

Conjunto Observar-Remover, Conjunto OR ou Conjunto Add-Win:

Nesse tipo, adicionar tem precedência sobre remover. Exemplo de implementação: a cada elemento adicionado recentemente é atribuída uma tag exclusiva (relativa ao elemento e não ao conjunto inteiro). Rmv remove um elemento do conjunto e envia todos os pares vistos (elemento, tag) para as réplicas para remoção.

Conjunto Remover-Ganhar:

Semelhante ao anterior, mas ao mesmo tempo, add / rmv rmv vence.

6.4 Gráfico

Este tipo é construído com base em muitos. O problema é o seguinte: se houver operações simultâneas addEdge (u, v) e removeVertex (u) - o que devo fazer? As seguintes opções são possíveis:

• Prioridade RemoveVertex, todas as arestas incidentes nesse vértice são excluídas
• Prioridade AddEdge, vértices excluídos restaurados
• Adiamos a execução do removeVertex até que todos os addEdge simultâneos sejam executados.

A opção mais fácil é a primeira, para sua implementação (gráfico 2P2P) basta obter dois conjuntos 2P, um para os vértices e o segundo para as arestas

6.5 Mapa

Mapa de literais:

Dois problemas a resolver:

• O que fazer com operações de venda simultânea? Por analogia com os contadores, você pode escolher semântica LWW ou MV
• O que fazer com o put / rmv simultâneo? Por analogia com os conjuntos, é possível semântica put-wins ou rmv-wins ou last-put-wins.

Mapeamento CRDT (Mapa de CRDTs):

Um caso mais interessante, porque permite criar mapeamentos aninhados. Não consideramos casos de alteração de tipos aninhados - isso deve ser decidido pelo próprio CRDT aninhado.

Mapa Remover-como-redefinição recursiva

A operação de remoção "redefine" o valor do tipo para um determinado estado inicial. Por exemplo, para um contador, esse é um valor zero.

Considere um exemplo - uma lista de compras geral. Um dos usuários adiciona farinha e o segundo faz uma finalização da compra (isso leva a uma chamada para a operação de exclusão em todos os elementos). Como resultado, uma unidade de farinha permanece na lista, o que parece lógico.


Mapa Remove-wins

A operação rmv tem precedência.

Exemplo: em um jogo online, um jogador de Alice tem 10 moedas e um martelo. Em seguida, dois eventos ocorrem simultaneamente: na réplica A, ela produziu uma unha, e na réplica B, seu personagem é excluído com a remoção de todos os objetos:



Observe que, ao usar remover como recursivo, uma unha acabaria por permanecer, o que não é o estado correto quando o personagem é removido.

Atualizar mapa de vitórias

As atualizações têm precedência, ou melhor, cancelam operações anteriores para excluir rmv simultâneas.

Exemplo: em um jogo online, o personagem Alice na réplica B é excluído devido à inatividade, mas a atividade ocorre na réplica A ao mesmo tempo. Obviamente, a operação de exclusão deve ser cancelada.


Há um efeito interessante ao trabalhar com essa implementação - suponha que tenhamos duas réplicas, A e B, e elas armazenem o conjunto por alguma chave k. Então, se A excluir o valor da chave k e B excluir todos os elementos do conjunto, no final, as réplicas deixarão um conjunto vazio com a chave k.

Observe que uma implementação ingênua não funcionará corretamente - você não pode simplesmente desfazer todas as operações de exclusão anteriores. No exemplo a seguir, com essa abordagem, o estado final seria o estado inicial, incorreto:

Lista

O problema com esse tipo é que os índices de itens em réplicas diferentes serão diferentes após as operações locais de inserção / exclusão. Para resolver esse problema, a abordagem Transformação operacional é aplicada - ao aplicar a alteração obtida, o índice do elemento na réplica original deve ser levado em consideração.

7. Riak

Como exemplo, considere o CRDT em Riak:

• Contador: Contador PN
• Conjunto: Conjunto OR
• Mapa: atualização ganha mapa de CRDTs
• Sinalizador (booleano): OR-Defina onde no máximo 1 elemento
• Registro: pares (valor, registro de data e hora)

8. Quem usa CRDT

A seção wiki contém bons exemplos.

9. Referências

• Lojas Key-CRDT
• Um tipo de dados JSON replicado sem conflitos
• Um estudo abrangente dos tipos de dados replicados convergentes e comutativos
• Tipo de dados replicado convergente e comutativo
• Tipo de dados replicado sem conflitos
• Um guia de bluffers para CRDTs em Riak
• CRDTs: uma atualização (ou apenas um PUT)
• Tipos de dados replicados sem conflitos: uma visão geral
• Consistência Eventual Forte e Tipos de Dados Replicados sem Conflitos
• Estruturas de dados eventualmente consistentes