Zacząłem przyglądać się podejściom do synchronizacji danych między zestawami peerów. Uczestnicy muszą być w stanie pracować w sposób odłączony, a następnie synchronizować się ze sobą, aby scalić swoje lokalne zmiany.
Uczestnicy powinni mieć możliwość scalania lokalnych aktualizacji za pomocą „scalania trójstronnego” . Tak więc podczas synchronizacji rówieśnicy powinni wiedzieć, które fakty są nowsze, ale tam, gdzie nie ma ścisłego uporządkowania, powinni być w stanie połączyć fakty w oparciu o wspólny rdzeń.
Gdy niezależni partnerzy dokonują zmian, mogą „oznaczyć je czasem” za pomocą „zegara”. Używam terminów „zegar” i „znacznik czasu”, ale nie mam na myśli zegara ściennego. Mam na myśli pewnego rodzaju częściowe uporządkowanie wydarzeń, które wyjaśnia przyczynowość. Jest to „zdarzyło” relacji między wydarzeniami, które tworzy skierowany graf acykliczny (DAG).
Wydaje się, że „zwykłym” sposobem na zbudowanie tego częściowego uporządkowania jest użycie zegara wektorowego . Mogą one jednak stać się bardzo duże. Nowsze osiągnięcia, takie jak zegary drzewa interwałowego, zapewniają bardziej kompaktowe przechowywanie znaczników czasu.
Nie jestem wcale pewien, dlaczego protokoły synchronizacji najwyraźniej nie „po prostu” przechowują DAG jawnie. (A może oni?)
Uczestnicy mogą niezależnie tworzyć znacznik czasu, losowo generując UUID (lub innymi środkami, takimi jak <peer-name> + <local-monotonically-increasing-counter>). Kolejność tego znacznika czasu jest całkowicie jasna dla tego elementu.
Gdy 2 osoby synchronizują się ze sobą, mogą uzgodnić nowy znacznik czasu. Ponownie, porządek tego znacznika czasu jest jasny dla obu partnerów.
Istnieje teraz wymóg, aby zdarzenie miało miejsce przed DAG między równorzędnymi urządzeniami, ale wymagania dotyczące pamięci i przepustowości są niewielkie. Punkty czasowe są wierzchołkami wykresu. Jako takie mają 1 lub 2 przychodzące krawędzie (1 dla zdarzenia na kliencie i 2 dla synchronizacji między klientami). Jest to ograniczone i niezależne od liczby peerów w sieci.
Aby użyć indywidualnego punktu czasowego, potrzebujesz wykresu punktów czasowych, które do tego prowadzą. Jednakże, o ile widzę, każdy sieci peer, że jest w stanie wiedzieć o punkcie czasowym (nie przyniosła ona sama lub generowane go innym peer lub zostało mu go przez innego uczestnika podczas synchronizacji z nim) ma również miał okazja do poznania historii prowadzącej do tego momentu. Myślę, że jest na to prawdopodobnie indukcyjny dowód.
Biorąc pod uwagę, że przechowywanie i synchronizowanie DAG wyraźnie wydaje się proste: czy jest to stosowane w praktyce? Jeśli nie, dlaczego preferowane są zegary wektorowe?
Notatki
Peer to peer
Wolałbym rozwiązanie peer to peer zamiast rozwiązania typu klient-serwer.
Prawdopodobnie końcową topologią będzie wielu klientów łączących się ze znacznie mniejszą grupą serwerów, które replikują się między sobą. Byłoby jednak miło mieć ogólne rozwiązanie, które obsługuje tę konkretną topologię, niż rozwiązanie wymagające tej konkretnej topologii.
źródło
Odpowiedzi:
O ile wiem, systemy kontroli wersji, takie jak Git i Mercurial, wykorzystują podejście DAG, a nie zegary wektorowe.
źródło
Spójrz na problem konsensusu . W zależności od wymagań zadania (liczby posiadanych danych, liczby węzłów synchronizujących, częstotliwości itp.) Istniejące rozwiązania tego problemu (takie jak „Raft”) mogą być odpowiednie dla danego przypadku.
Innym (być może stycznym) podejściem do tego problemu jest zaprojektowanie CRDT .
źródło
Protokół Aleph to bezcelowy protokół p2p, który buduje rozproszone DAG zestawów transakcji (lub zdarzeń) w drodze konsensusu
https://arxiv.org/pdf/1908.05156
źródło