Явный DAG вместо Vector Clocks для синхронизации

13

Я начал смотреть на подходы к синхронизации данных среди множества пиров. Узлы должны иметь возможность работать автономно и затем синхронизироваться друг с другом, чтобы объединить свои локальные изменения.

Узлы должны иметь возможность объединять локальные обновления с «трехсторонним объединением» . Таким образом, при синхронизации узлы должны знать, какие факты являются более свежими, но там, где нет строгого упорядочения, они должны иметь возможность объединять факты, основанные на общем корне.

Когда независимые узлы вносят изменения, они могут «помечать» их «часами». Я использую термины «часы» и «отметка времени», но я не имею в виду настенные часы. Я имею в виду некоторый частичный порядок событий, который проясняет причинность. Это отношение «произошло раньше» между событиями, которое формирует направленный ациклический граф (DAG).

Кажется, что «обычный» способ сделать это частичное упорядочение - использовать векторные часы . Однако они могут стать очень большими. Более поздние разработки, такие как интервальное дерево, обеспечивают более компактное хранение меток времени.

Я не совсем понимаю, почему протоколы синхронизации явно «просто» не хранят DAG явно. (Или они?)

Одноранговые узлы могут независимо создавать метку времени путем случайного генерирования UUID (или другими способами, такими как <peer-name> + <local-monotonically-increasing-counter>). Порядок этой отметки времени совершенно ясен для этого пира.

Когда 2 узла синхронизируются друг с другом, они могут договориться о новой отметке времени. Опять же, порядок этой метки времени понятен обоим пирам.

В настоящее время существует требование для передачи произошедшего до DAG между узлами, но требования к хранилищу и пропускной способности этого невелики. Точки времени - вершины графа. Таким образом, они имеют 1 или 2 входящих фронта (1 для события на клиенте и 2 для синхронизации между клиентами). Это ограничено и не зависит от количества пиров в сети.

Чтобы использовать отдельную временную точку, вам нужен график временных точек, которые приводят к этому. Однако, насколько я могу видеть, любой узел, который может знать момент времени (он сгенерировал его сам, или сгенерировал его с другим узлом, или ему сказали об этом другой узел при синхронизации с ним), также имел возможность узнать об истории, ведущей к тому времени. Я думаю, что, вероятно, есть индуктивное доказательство этого.

Учитывая, что хранение и синхронизация DAG явно кажутся простыми: используется ли это на практике? Если нет, то почему предпочитают векторные часы?

Примечания

Пиринговый

Я бы предпочел одноранговое решение, а не клиент-серверное решение.

Вероятной конечной топологией будет множество клиентов, подключающихся к гораздо меньшей группе серверов, которые реплицируются между собой. Однако было бы неплохо иметь общее решение, которое поддерживает эту конкретную топологию, а не решение, которое требует этой конкретной топологии.

synchronization Benjohn
источник
Возможно, я неправильно понимаю, что вы говорите, но неясно, как график всех событий, ведущих к состоянию, может быть меньше, чем вектор счетчиков. Если вы не находитесь в системе, которая имеет чрезвычайно большое количество узлов и крайне небольшое количество изменений.
kdgregory
Спасибо @kdgregory - хороший момент. Чтобы иметь возможность рассчитать трехстороннее слияние в будущем, вам необходимо знать прошлое (и иметь возможность определять DAG из прошлых моментов времени). Таким образом, если вы сохраняете эти прошедшие временные точки, то явное хранение DAG обходится дешевле. Если вы не сохраняете эти прошлые моменты времени, то вы все равно не сможете рассчитать трехстороннее объединение данных. - Интересно, может быть, это трёхстороннее требование? Если вам не нужны 3-полосные, возможно, векторные часы лучше, чем явные DAG?
Benjohn
Я считаю, что это может быть решающим моментом @kdgregory, поэтому я немного добавил об этом к вопросу. Я предполагаю, что можно выполнить трехстороннее слияние, что также подразумевает, что вся история известна. Если вся история известна, то (я считаю) явный DAG дешевле. Если история усечена, то векторные часы, вероятно, менее затратный подход.
Benjohn
1
Да, я понимаю, что векторные часы предназначены для простого принятия / отклонения решения: «узел C пытается обновить этот фрагмент данных, но он не знает об обновлении узла B».
kdgregory

Ответы:

1

Насколько я могу судить, системы контроля версий, такие как Git и Mercurial, используют подход DAG, а не векторные часы.

bikeman868
источник
1
Без объяснения этот ответ может стать бесполезным в случае, если кто-то постит противоположное мнение. Например, если кто-то публикует утверждение типа «Системы контроля проправитации, такие как Git и Mercurial, используют векторные часы, а не подход DAG» , как этот ответ поможет читателю выбрать два противоположных мнения? Подумайте о том, чтобы изменить его в лучшую форму, чтобы соответствовать стандартам качества « Как отвечать» .
комнат
2
Как я понял вопрос, они спрашивали, есть ли примеры из реальной жизни, где используется DAG, а не векторные часы.
bikeman868
1
И Git, и Mecurial являются реальными примерами синхронизации одноранговых изменений с использованием DAG, и я надеюсь, что benjohn найдет мой ответ полезным, даже если вы проголосовали за него.
bikeman868
Привет @ bikeman868 Я проголосовал за чистую 0 (извините). Ваш ответ является полезным, даже если выдержан с неопределенностью! Хотя ссылки или авторитетные ответы всегда хороши, обмен стеками не требует этого! Ваше предложение имеет смысл с точки зрения в комментариях по вопросу. Кажется, что когда вы хотите хранить историю и иметь возможность объединять истории, тогда подходит DAG. Если вы не сохраняете историю и хотите синхронизировать и согласовывать текущее состояние, тогда вам нужны векторные часы.
Бенджон
1

Посмотрите на проблему консенсуса . В зависимости от требований вашей задачи (относительно того, сколько у вас данных, сколько узлов синхронизации, как часто и т. Д.) Существующие решения этой проблемы (такие как «Плот») могут подходить для вашего случая.

Другой (возможно, тангенциальный) подход к этой проблеме - разработка CRDT .

battlmonstr
источник
HTTP-код Braid пытается создать протокол синхронизации состояний на основе CRDT с помощью расширения HTTP. Они имеют отличную визуализацию Time DAG и Space DAG и того, как эти две концепции взаимосвязаны для достижения конечной согласованности.
Дуэйн J
-1

Протокол Aleph - это протокол p2p без лидера, который создает распределенную группу обеспечения доступности баз данных наборов транзакций (или событий) на основе консенсуса.

https://arxiv.org/pdf/1908.05156

ferranpujolcamins
источник
Вы должны расширить свой ответ, чтобы показать, как указанный протокол решает вопросы, поднятые в исходном вопросе. Важно сделать ответы самодостаточными, так как это приносит пользу всем, кто сталкивается с этим вопросом.
BobDalgleish