DAG explícito en lugar de relojes vectoriales para sincronización

13

Comencé a buscar enfoques para la sincronización de datos entre un conjunto de pares. Los pares deben poder trabajar de forma desconectada y luego sincronizarse para fusionar sus cambios locales.

Los pares deberían poder fusionar las actualizaciones locales con una "fusión de tres vías" . Por lo tanto, en la sincronización, los pares deben saber qué hechos son más recientes, pero donde no hay un orden estricto, deben poder fusionar los hechos en función de la raíz común.

Cuando los pares independientes hacen cambios, pueden "marcarlos" con un "reloj". Uso el término "reloj" y "marca de tiempo" pero no me refiero a un reloj de pared. Me refiero a algún tipo de ordenamiento parcial de eventos que aclara la causalidad. Es la relación "sucedido antes" entre los eventos lo que forma un gráfico acíclico dirigido (DAG).

Parece que la forma "habitual" de construir esta ordenación parcial es mediante el uso de un reloj vectorial . Sin embargo, estos pueden llegar a ser muy grandes. Desarrollos más recientes, como los relojes de árbol de intervalos, proporcionan un almacenamiento más compacto de las marcas de tiempo.

Lo que no estoy del todo claro es por qué los protocolos de sincronización aparentemente no "simplemente" almacenan el DAG explícitamente. (¿O ellos?)

Los pares pueden crear independientemente una marca de tiempo generando aleatoriamente un UUID (o por otros medios, como <peer-name> + <local-monotonically-increasing-counter>). El orden de esta marca de tiempo es completamente claro para ese compañero.

Cuando 2 pares se sincronizan entre sí, pueden acordar una nueva marca de tiempo. Nuevamente, el orden de esta marca de tiempo es claro para ambos pares.

Ahora hay un requisito para pasar lo sucedido antes de DAG entre pares, pero los requisitos de almacenamiento y ancho de banda son pequeños. Los puntos de tiempo son vértices gráficos. Como tal, tienen 1 o 2 bordes entrantes (1 para un evento en un cliente y 2 para una sincronización entre clientes). Esto es limitado e independiente del número de pares en la red.

Para usar un punto de tiempo individual, necesita la gráfica de los puntos de tiempo que conducen a esto. Sin embargo, por lo que puedo ver, cualquier par que puede conocer un punto de tiempo (lo ha generado él mismo, o lo ha generado con otro par, o se lo ha dicho otro par al sincronizar con él) también ha tenido Una oportunidad para conocer la historia previa a ese momento. Creo que probablemente haya una prueba inductiva para esto.

Dado que almacenar y sincronizar el DAG parece explícitamente simple: ¿se usa esto en la práctica? Si no, ¿por qué se prefieren los relojes vectoriales?

Notas

De igual a igual

Prefiero una solución de igual a igual que una solución de servidor de cliente.

La topología final probable será que muchos clientes se conecten a un grupo mucho más pequeño de servidores que se replican entre ellos. Sin embargo, sería bueno tener una solución general que respalde esta topología en particular en lugar de una solución que requiera esta topología específica.

synchronization Benjohn
fuente
Puedo estar malinterpretando lo que está diciendo, pero no está claro cómo una gráfica de todos los eventos que conducen a un estado podría ser más pequeña que un vector de contadores. A menos que esté en un sistema que tenga una cantidad extremadamente grande de nodos y una cantidad extremadamente pequeña de cambios.
kdgregory
Gracias @kdgregory - buen punto. Para poder calcular una fusión de tres vías en el futuro, debe conocer el pasado (y poder determinar el DAG de los puntos de tiempo pasados). Entonces, si está almacenando esos puntos de tiempo pasados, entonces almacenar explícitamente el DAG es más barato. Si está no caben estas últimos puntos de tiempo, entonces no puede calcular una combinación de tres vías de los datos de todos modos. - Me pregunto si este requisito de tres vías podría ser la cosa. Si no desea 3 vías, ¿quizás los relojes vectoriales sean mejores que los DAG explícitos?
Benjohn
Creo que este podría ser el punto crucial @kdgregory, así que he agregado un poco sobre eso a la pregunta. Supongo que es posible realizar una fusión de 3 vías, lo que también implica que se conoce toda la historia. Si se conoce toda la historia, supongo que un DAG explícito es más barato. Si la historia se trunca, entonces los relojes vectoriales son probablemente el enfoque menos costoso.
Benjohn
1
Sí, mi comprensión de los relojes vectoriales es que están destinados simplemente a una decisión de aceptar / rechazar: "el nodo C está tratando de actualizar este dato, pero no tiene conocimiento de la actualización del nodo B".
kdgregory

Respuestas:

1

Por lo que puedo decir, los sistemas de control de versiones como Git y Mercurial utilizan el enfoque DAG en lugar de los relojes vectoriales.

bikeman868
fuente
1
Sin una explicación, esta respuesta puede volverse inútil en caso de que alguien más publique una opinión opuesta. Por ejemplo, si alguien publica un reclamo como "Los sistemas de control de Proversión como Git y Mercurial usan relojes vectoriales en lugar del enfoque DAG" , ¿cómo respondería esto al lector a elegir dos opiniones opuestas? Considere editarlo en una mejor forma, para cumplir con los estándares de calidad de Cómo responder .
mosquito
2
Según entendí la pregunta, preguntaban si hay ejemplos del mundo real de dónde se usa DAG en lugar de relojes vectoriales.
bikeman868
1
Tanto Git como Mecurial son ejemplos del mundo real de sincronización de cambio de igual a igual utilizando DAG, y espero que benjohn encuentre útil mi respuesta a pesar de que la haya rechazado.
bikeman868
Hola @ bikeman868 Te he votado a favor de un 0 neto (lo siento). ¡Su respuesta es útil, incluso si se expresa con incertidumbre! Si bien las referencias o las respuestas autorizadas siempre son agradables, ¡los intercambios de pila no requieren eso! Su sugerencia tiene sentido con los puntos en los comentarios sobre la pregunta. Parece que cuando desea almacenar el historial y poder fusionarlos, entonces es apropiado un DAG. Cuando no almacena el historial y desea sincronización y consenso sobre el estado actual, entonces los relojes vectoriales son lo que necesita.
Benjohn
1

Echa un vistazo al problema del consenso . Dependiendo de los requisitos de su tarea (en cuanto a la cantidad de datos que tiene, cuántos nodos de sincronización, con qué frecuencia, etc.), las soluciones existentes para ese problema (como "Balsa") pueden ser adecuadas para su caso.

Otro enfoque (quizás tangencial) para este problema es diseñar un CRDT .

battlmonstr
fuente
Braid HTTP está intentando crear un protocolo de sincronización de estado basado en CRDT mediante el aumento de HTTP. Tienen una gran visualización de un DAG del tiempo y un DAG del espacio, y cómo estos dos conceptos se interrelacionan para llegar a una consistencia eventual.
Duane J
-1

El protocolo Aleph es un protocolo sin líder p2p que crea un DAG distribuido de conjuntos de transacciones (o eventos) por consenso

https://arxiv.org/pdf/1908.05156

ferranpujolcamins
fuente
Debe ampliar su respuesta para mostrar cómo el protocolo referenciado aborda los puntos planteados por la pregunta original. Es importante que las respuestas sean autosuficientes, ya que esto beneficia a todos los que se encuentren con esta pregunta.
BobDalgleish