DAG explícito em vez de relógios vetoriais para sincronização

13

Comecei a analisar abordagens para sincronização de dados entre um conjunto de pares. Os pares devem poder trabalhar de maneira desconectada e sincronizar juntos para mesclar suas alterações locais.

Os pares devem poder mesclar atualizações locais com uma "mesclagem de três maneiras" . Portanto, na sincronização, os pares devem saber quais fatos são mais recentes, mas onde não há uma ordem estrita, eles devem ser capazes de mesclar os fatos com base na raiz comum.

Quando pares independentes fazem alterações, eles podem "marcá-los" com um "relógio". Uso os termos "relógio" e "carimbo de hora", mas não estou querendo dizer um relógio de parede. Quero dizer algum tipo de ordenação parcial de eventos que torna clara a causalidade. É a relação "aconteceu antes" entre os eventos que forma um gráfico acíclico direcionado (DAG).

Parece que a maneira "usual" de criar essa ordem parcial é usando um relógio de vetor . Estes podem se tornar muito grandes, no entanto. Desenvolvimentos mais recentes, como relógios de árvore com intervalo, fornecem armazenamento mais compacto de registros de data e hora.

O que não estou claro é por que os protocolos de sincronização aparentemente não "simplesmente" armazenam o DAG explicitamente. (Ou eles?)

Os pares podem criar um carimbo de data / hora independentemente, gerando aleatoriamente um UUID (ou por outros meios, como <peer-name> + <local-monotonically-increasing-counter>). A ordem desse carimbo de data e hora é totalmente clara para esse par.

Quando dois pares se sincronizam, eles podem concordar com um novo carimbo de data / hora. Novamente, a ordem desse carimbo de data e hora é clara para os dois pares.

Agora existe um requisito para passar o ocorrido antes do DAG entre pares, mas os requisitos de armazenamento e largura de banda são pequenos. Pontos no tempo são vértices gráficos. Como tal, eles têm 1 ou 2 arestas de entrada (1 para um evento em um cliente e 2 para uma sincronização entre clientes). Isso é limitado e independente do número de pares na rede.

Para usar um ponto no tempo individual, é necessário o gráfico dos pontos no tempo que levam a isso. No entanto, tanto quanto eu posso ver, qualquer par que é capaz de conhecer um ponto no tempo (ele próprio o gerou, ou o gerou com outro par, ou foi informado por outro par ao sincronizar com ele) também teve uma oportunidade de conhecer a história que antecedeu esse momento. Eu acho que provavelmente há uma prova indutiva para isso.

Dado que armazenar e sincronizar o DAG parece explicitamente simples: isso é usado na prática? Caso contrário, por que os relógios vetoriais são preferidos?

Notas

Pessoa para pessoa

Prefiro uma solução ponto a ponto do que uma solução de servidor cliente.

A provável topologia final será que muitos clientes se conectem a um grupo muito menor de servidores que se replicam entre si. No entanto, seria bom ter uma solução geral que suporte essa topologia específica, em vez de uma solução que exija essa topologia específica.

synchronization Benjohn
fonte
Posso estar entendendo mal o que você está dizendo, mas não está claro como um gráfico de todos os eventos que levam a um estado pode ser menor que um vetor de contadores. A menos que você esteja em um sistema que tenha um número extremamente grande de nós e um número extremamente pequeno de alterações.
kdgregory
Obrigado @kdgregory - bom ponto. Para poder calcular uma fusão de três vias no futuro, você precisa conhecer o passado (e poder determinar o DAG dos pontos no tempo passado). Portanto, se você estiver armazenando esses pontos no tempo passado, armazenar explicitamente o DAG é mais barato. Se você não estiver armazenando esses pontos no tempo passado, não poderá calcular uma mescla de dados de três maneiras. - Será que esse requisito de três vias pode ser o ideal? Se você não quiser usar os três sentidos, talvez os relógios de vetor sejam melhores que o DAG explícito?
Benjohn
Eu acho que esse pode ser o ponto crucial @kdgregory, então eu adicionei um pouco sobre isso à pergunta. Suponho que seja possível realizar uma mesclagem de três vias, o que também implica que toda a história é conhecida. Se toda a história é conhecida, então (eu acho) um DAG explícito é mais barato. Se o histórico for truncado, os relógios vetoriais provavelmente serão a abordagem menos dispendiosa.
Benjohn
1
Sim, meu entendimento dos relógios vetoriais é que eles destinam-se simplesmente a uma decisão de aceitação / rejeição: "o nó C está tentando atualizar esses dados, mas não está ciente da atualização do nó B".
kdgregory

Respostas:

1

Até onde eu sei, sistemas de controle de versão como Git e Mercurial usam a abordagem DAG em vez de relógios vetoriais.

bikeman868
fonte
1
Sem uma explicação, essa resposta pode se tornar inútil se outra pessoa postar uma opinião oposta. Por exemplo, se alguém postar uma afirmação como "Os sistemas de controle de conversão como Git e Mercurial usam relógios vetoriais em vez da abordagem DAG" , como essa resposta ajudaria o leitor a escolher duas opiniões opostas? Considere editá -lo em uma forma melhor, para atender aos padrões de qualidade Como responder .
Gnat
2
Do jeito que eu entendi a pergunta, eles estavam perguntando se existem exemplos do mundo real de onde o DAG é usado, em vez de relógios de vetor.
precisa saber é o seguinte
1
Tanto o Git quanto o Mecurial são exemplos reais de sincronização de alterações ponto a ponto usando o DAG, e espero que benjohn ache minha resposta útil, mesmo que você tenha votado contra.
Rockman868
Oi @ bikeman868 Eu votei em você por uma rede 0 (desculpe). Sua resposta é útil, mesmo que repleta de incertezas! Embora referências ou respostas autorizadas sejam sempre boas, as trocas de pilhas não exigem isso! Sua sugestão faz sentido com pontos nos comentários sobre a pergunta. Parece que quando você deseja armazenar histórico e conseguir mesclar históricos, um DAG é apropriado. Quando você não armazena histórico e deseja sincronização e consenso sobre o estado atual, os relógios vetoriais são o que você precisa.
Benjohn
1

Dê uma olhada no problema de consenso . Dependendo dos requisitos da sua tarefa (quantos dados você possui, quantos nós de sincronização, quantas vezes etc.), as soluções existentes para esse problema (como "Raft") podem ser adequadas para o seu caso.

Outra abordagem (talvez tangencial) para esse problema é projetar um CRDT .

battlmonstr
fonte
O Braid HTTP está tentando criar um protocolo de sincronização de estado baseado em CRDT via HTTP aumentado. Eles têm uma ótima visualização de um DAG de Tempo e DAG de Espaço, e como esses dois conceitos se inter-relacionam para chegar a uma consistência eventual.
Duane J