Эффективное сравнение DAG по сети

11

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

Рассматриваемые группы обеспечения доступности баз данных формируются по зарегистрированным изменениям. Редакции однозначно идентифицируются хеш-значением. Каждая ревизия зависит от нуля (начальная фиксация), одной (нормальная фиксация) или более (фиксация слияния) предыдущих ревизий. Ниже приведен пример , где изменения aк eбыли сделаны один за другим:

a --- b --- c --- d --- e

Сравнение графиков входит в картину, когда кто-то имеет только часть истории и хочет извлечь недостающую часть. Представьте, что я должен aбыл cи сделал xи yна основе c:

a --- b --- c --- x --- y

В Mercurial я бы сделал hg pullи скачал dи e:

a --- b --- c --- x --- y
              \
                d --- e

Цель состоит в том, чтобы идентифицировать dи eэффективно, когда граф имеет много (скажем, более 100 000) узлов. Эффективность касается как

  • сложность сети: количество переданных байтов и количество необходимых сетевых обходов
  • временная сложность: объем вычислений, выполненных двумя серверами, которые обмениваются наборами изменений

Типичные графики будут узкими с несколькими параллельными дорожками, как указано выше. Также обычно будет только несколько конечных узлов (мы называем их головами в Mercurial), как eи yвыше. Наконец, когда используется центральный сервер, у клиента часто будет несколько наборов изменений, которых нет на сервере, в то время как на сервере может быть более 100 новых наборов изменений для клиентов, в зависимости от того, кто давно клиент последний раз брал с сервера , Асимметричное решение является предпочтительным: централизованный сервер должен сделать небольшое вычисление по сравнению со своими клиентами.

Мартин Гайслер
источник
Обсуждение немного продолжилось на Google Plus .
Мартин Гайслер

Ответы:

13

В этом контексте узлы графа имеют своего рода уникальный идентификатор (хэш или контрольную сумму), верно? Таким образом, вам не нужно выполнять какие-либо тесты на изоморфизм подграфов, вам просто нужен список узлов, которые отличаются между вашими двумя версиями, а ребра на этом этапе вообще не нужны. Моя статья SIGCOMM 2011 "В чем разница? Эффективное согласование набора без предварительного контекста«(с Goodrich, Uyeda и Varghese) рассматривает именно эту проблему: оказывается, что вы можете определить идентификаторы узлов, которые удерживаются одним, но не обоими двумя взаимодействующими серверами, используя объем связи, который пропорционален только на количество измененных узлов и использование только одного приема-передачи. Как только у вас есть эта информация, легко получить сами изменения во втором и обратно, опять же с оптимальной связью.

Дэвид Эппштейн
источник
Это звучит интересно! Вы правы, что прямое сравнение идентификаторов наборов изменений (да, это хэш-значения) будет работать. Мы просто всегда пытаемся использовать структуру графа: если мы оба знаем X, то я также знаю, что вы знаете всех предков X. Это кажется важной информацией, но, возможно, это не так. Я сейчас прочитаю вашу статью, спасибо за указатель!
Мартин Гайслер
@David: точность (я один из авторов алгоритма, используемого в настоящее время Mercurial). Мы на самом деле заботимся о наборе «общих» узлов, не нужно знать значение отсутствующего узла.
tonfa
1
Если вы знаете, что отличается, то вы также знаете, что общего: все, что у вас есть, не является частью разницы. Но, как правило, разница должна быть относительно небольшой, даже если общая часть велика, поэтому лучше передавать только объем данных, пропорциональный разнице, чем передавать всю историю DAG или общую часть.
Дэвид Эппштейн
@David: из-за отношений с предками мы фактически вычисляем головки (листовые узлы) общей области. Так что это все еще небольшой объем данных, даже если существует огромная общая история.
Мартин Гайслер,
Я обновил свой ответ, включив в него также количество использованных поездок туда и обратно (которое оказывается очень маленьким).
Дэвид Эппштейн
3

В решении, которое мы внедрили для Mercurial, еще одной проблемой была асимметрия: нагрузка на сервер должна быть минимизирована как для исходящей полосы пропускания, так и для времени ЦП, за счет нагрузки на клиента.

Петр Арренбрехт
источник
1
Спасибо, я немного обновил вопрос, чтобы отметить это.
Мартин Гейслер
0

Похоже, двухступенчатый процесс для меня.

  1. спросите всех клиентов, есть ли у них коммиты, где родитель
  2. если так, найдите всех детей

Задача 1. Я думаю, что в основном обрабатывается на стороне клиента, и все клиенты нуждаются в хеше коммитов по сети.

Рон
источник
Какой сценарий вы описываете? Случай , когда я сделал xи yи необходимость тянуть eи dс сервера? Изначальная проблема заключается в том, что я (как клиент) не знаю «точки ветвления» c.
Мартин Гайслер