DAG explicite au lieu des horloges vectorielles pour la synchronisation

13

J'ai commencé à chercher des approches de synchronisation des données parmi un ensemble de pairs. Les pairs doivent pouvoir travailler de manière déconnectée, puis se synchroniser ensemble pour fusionner leurs modifications locales.

Les pairs devraient pouvoir fusionner les mises à jour locales avec une «fusion à trois» . Ainsi, lors de la synchronisation, les pairs doivent savoir quels faits sont les plus récents, mais là où il n'y a pas d'ordre strict, ils devraient pouvoir fusionner les faits en fonction de la racine commune.

Lorsque des pairs indépendants apportent des modifications, ils peuvent les «horodater» avec une «horloge». J'utilise le terme «horloge» et «horodatage» mais je ne parle pas d'une horloge murale. Je veux dire une sorte d'ordre partiel des événements qui rend la causalité claire. C'est la relation «arrivé avant» entre les événements qui forme un graphe acyclique dirigé (DAG).

Il semble que la façon "habituelle" de construire cet ordre partiel consiste à utiliser une horloge vectorielle . Celles-ci peuvent cependant devenir très importantes. Des développements plus récents tels que les horloges d'arbre à intervalles offrent un stockage plus compact des horodatages.

Ce que je ne sais pas du tout, c'est pourquoi les protocoles de synchronisation ne stockent pas "simplement" le DAG de manière explicite. (Ou le font-ils?)

Les pairs peuvent créer indépendamment un horodatage en générant aléatoirement un UUID (ou par d'autres moyens tels que <peer-name> + <local-monotonically-increasing-counter>). L'ordre de cet horodatage est parfaitement clair pour ce pair.

Lorsque 2 pairs se synchronisent, ils peuvent convenir d'un nouvel horodatage. Encore une fois, l'ordre de cet horodatage est clair pour les deux pairs.

Il est maintenant nécessaire de transmettre les événements avant le DAG entre homologues, mais les exigences de stockage et de bande passante sont faibles. Les points temporels sont des sommets de graphe. En tant que tels, ils ont 1 ou 2 fronts entrants (1 pour un événement sur un client et 2 pour une synchronisation entre les clients). Ceci est limité et indépendant du nombre de pairs dans le réseau.

Pour utiliser un point temporel individuel, vous avez besoin du graphique des points temporels qui y mènent. Cependant, pour autant que je puisse voir, tout homologue capable de connaître un point dans le temps (il l'a généré lui-même, ou l'a généré avec un autre homologue, ou a été informé par un autre homologue lors de la synchronisation avec lui) a également eu une occasion de connaître l'histoire menant à ce moment. Je pense qu'il y a probablement une preuve inductive pour cela.

Étant donné que le stockage et la synchronisation du DAG semblent explicitement simples: est-ce utilisé en pratique? Sinon, pourquoi privilégier les horloges vectorielles?

Remarques

D'égal à égal

Je préfère une solution peer to peer à une solution client-serveur.

La topologie de fin probable sera que de nombreux clients se connectent à un groupe beaucoup plus petit de serveurs qui se répliquent entre eux. Cependant, ce serait bien d'avoir une solution générale qui prend en charge cette topologie particulière plutôt qu'une solution qui nécessite cette topologie spécifique.

synchronization Benjohn
la source
Je comprends peut-être mal ce que vous dites, mais on ne sait pas comment un graphique de tous les événements menant à un état pourrait être plus petit qu'un vecteur de compteurs. Sauf si vous êtes dans un système qui a un nombre extrêmement élevé de nœuds et un nombre extrêmement faible de modifications.
kdgregory
Merci @kdgregory - bon point. Pour pouvoir calculer une fusion à trois dans le futur, vous devez connaître le passé (et être capable de déterminer le DAG des points temporels passés). Donc, si vous stockez ces points dans le temps, le stockage explicite du DAG est moins cher. Si vous ne stockez pas ces points dans le temps, vous ne pouvez de toute façon pas calculer une fusion à trois des données. - Je me demande si cette exigence à trois pourrait être la chose? Si vous ne voulez pas d'une horloge à 3 voies, peut-être que les horloges vectorielles sont meilleures qu'un DAG explicite?
Benjohn
Je pense que cela pourrait être le point crucial @kdgregory, j'ai donc ajouté un peu à ce sujet à la question. Je suppose qu'il est possible d'effectuer une fusion à 3 voies, ce qui implique également que toute l'histoire est connue. Si toute l'histoire est connue, alors (je pense) un DAG explicite est moins cher. Si l'histoire est tronquée, les horloges vectorielles sont probablement l'approche la moins coûteuse.
Benjohn
1
Oui, ma compréhension des horloges vectorielles est qu'elles sont simplement destinées à une décision d'acceptation / rejet: "le nœud C essaie de mettre à jour cette donnée, mais il n'est pas au courant de la mise à jour du nœud B".
kdgregory

Réponses:

1

Pour autant que je sache, les systèmes de contrôle de version comme Git et Mercurial utilisent l'approche DAG plutôt que les horloges vectorielles.

bikeman868
la source
1
Sans explication, cette réponse peut devenir inutile au cas où quelqu'un d'autre posterait une opinion opposée. Par exemple, si quelqu'un publie une affirmation comme «Les systèmes de contrôle de la propversion comme Git et Mercurial utilisent des horloges vectorielles plutôt que l'approche DAG» , comment cette réponse aiderait-elle le lecteur à choisir entre deux opinions opposées? Pensez à le modifier sous une meilleure forme, pour répondre aux normes de qualité Comment répondre .
moucher
2
D'après la façon dont j'ai compris la question, ils demandaient s'il y avait des exemples concrets d'utilisation du DAG plutôt que des horloges vectorielles.
bikeman868
1
Git et Mecurial sont des exemples réels de synchronisation de changement d'égal à égal à l'aide de DAG, et j'espère que benjohn trouvera ma réponse utile même si vous l'avez rejetée.
bikeman868
Salut @ bikeman868 Je vous ai voté pour un net 0 (désolé). Votre réponse est utile, même si elle est formulée d'incertitude! Bien que les références ou les réponses faisant autorité soient toujours agréables, les échanges de piles ne l'exigent pas! Votre suggestion est logique avec des points dans les commentaires sur la question. Il semble que lorsque vous souhaitez stocker l'historique et pouvoir fusionner les historiques, un DAG est approprié. Lorsque vous ne stockez pas l'historique et que vous souhaitez une synchronisation et un consensus sur l'état actuel, les horloges vectorielles sont ce dont vous avez besoin.
Benjohn
1

Jetez un oeil sur le problème du consensus . En fonction des exigences de votre tâche (en ce qui concerne la quantité de données dont vous disposez, le nombre de nœuds de synchronisation, la fréquence, etc.), les solutions existantes à ce problème (comme «Raft») peuvent être adaptées à votre cas.

Une autre approche (peut-être tangentielle) de ce problème consiste à concevoir un CRDT .

battlmonstr
la source
Braid HTTP tente de créer un protocole de synchronisation d'état basé sur CRDT via HTTP augmentant. Ils ont une excellente visualisation d'un DAG temporel et d'un DAG spatial, et de la façon dont ces deux concepts interagissent pour arriver à une cohérence éventuelle.
Duane J
-1

Le protocole Aleph est un protocole sans leader p2p qui construit un DAG distribué d'ensembles de transactions (ou événements) par consensus

https://arxiv.org/pdf/1908.05156

ferranpujolcamins
la source
Vous devez développer votre réponse pour montrer comment le protocole référencé aborde les points soulevés par la question d'origine. Il est important de rendre les réponses autosuffisantes, car cela profite à tous ceux qui rencontrent cette question.
BobDalgleish