Wydajne porównanie DAG przez sieć

W rozproszonych systemach kontroli wersji (takich jak Mercurial i Git ) istnieje potrzeba skutecznego porównywania ukierunkowanych wykresów acyklicznych (DAG). Jestem programistą Mercurial i bardzo chcielibyśmy usłyszeć o pracy teoretycznej, która omawia złożoność czasową i sieciową porównywania dwóch DAG.

Wspomniane DAG są tworzone na podstawie zarejestrowanych zmian. Wersje są jednoznacznie identyfikowane przez wartość skrótu. Każda wersja zależy od zera (początkowe zatwierdzenie), jednej (normalne zatwierdzenie) lub więcej (scalanie zatwierdzenia) poprzednich wersji. Oto przykład, gdzie poprawki ado ewykonano jeden po drugim:

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

Porównanie wykresów pojawia się na zdjęciu, gdy ktoś ma tylko część historii i chce odzyskać brakującą część. Wyobraź sobie, miałem ado ci wykonana xi yna podstawie c:

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

W Mercurial robiłbym hg pulli pobierał di e:

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

Celem jest identyfikacja di ewydajna identyfikacja, gdy wykres ma wiele (powiedzmy ponad 100 000) węzłów. Wydajność dotyczy obu

• złożoność sieci: liczba przesłanych bajtów i liczba potrzebnych podróży w obie strony do sieci
• złożoność czasu: ilość obliczeń wykonanych przez dwa serwery wymieniające zestawy zmian

Typowe wykresy będą wąskie z kilkoma równoległymi ścieżkami, jak powyżej. Zwykle będzie też tylko kilka węzłów liści (nazywamy je głowami w Mercurial) jak ei ywyżej. Wreszcie, gdy używany jest serwer centralny, klient często ma kilka zestawów zmian, których nie ma na serwerze, podczas gdy serwer może mieć ponad 100 nowych zestawów zmian dla klientów, w zależności od tego, kto dawno temu klient ostatnio ściągnął z serwera . Asymetryczne rozwiązanie jest preferowane: scentralizowany serwer powinien zrobić trochę obliczeń w stosunku do swoich klientów.

W tym kontekście węzły wykresu mają jakiś unikalny identyfikator (skrót lub suma kontrolna), prawda? Nie musisz więc przeprowadzać żadnych testów izomorfizmu podgraphów, potrzebujesz jedynie listy węzłów różniących się między dwiema wersjami, a krawędzie nie są w ogóle przydatne na tym etapie. Mój artykuł SIGCOMM 2011 „ Jaka jest różnica? Skuteczne uzgadnianie zestawów bez wcześniejszego kontekstu„(z Goodrich, Uyeda i Varghese) rozważa dokładnie ten problem: okazuje się, że można określić tożsamości węzłów, które są utrzymywane przez jeden, ale nie oba z dwóch komunikujących się serwerów, używając ilości komunikacji, która jest tylko proporcjonalna do liczby zmienionych węzłów i korzystania tylko z jednej podróży w obie strony. Po uzyskaniu tych informacji łatwo jest wprowadzić zmiany w drugiej podróży w obie strony, ponownie z optymalną komunikacją.

W rozwiązaniu, które wdrożyliśmy dla Mercurial, kolejnym problemem była asymetria: obciążenie serwera powinno być zminimalizowane zarówno dla przepustowości wychodzącej, jak i czasu procesora, kosztem obciążenia klienta.

Brzmi jak dwuetapowy proces.

1. zapytaj wszystkich klientów, czy mają zatwierdzenia tam, gdzie rodzic jest c
2. jeśli tak, znajdź wszystkie dzieci c

Zadanie 1. Myślę, że jest przetwarzane głównie po stronie klienta i wszyscy klienci potrzebują skrótu zatwierdzenia przez sieć.