Wektory czasowe:PORządzanie zdarzeń bez wspólnego zegara

Dlaczego zegary ścianowe nie działają na różnych maszynach

Każdy fizyczny zegar odchyla się. Nawet zgodnie z protokolami, jak NTP, które napędzają maszyny do zgody, zegary na różnych serwerach mogą różnić się o milisekundy lub więcej, a opóźnienia sieciowe są nieprzewidywalne i asymetryczne. Jeśli dwie masziny po prostu nakładają na swoje zdarzenia czas lokalny zegara ścianowego, porównując te nakłady do ustalenia, które zdarzenie nastąpiło najpierw, jest niewielkościami: wiadomość może być nakładana jako wysłana przed tym, jak naprawdę została odebrana według zegara innej maszyny, lub dwie niepowiązane zdarzenia mogą wydawać się nastąpić dokładnie w tym samym momencie. Gorsze jest to, że czas zegara ścianowego nie mówi niczego o kauzalności, czyli czy jedno zdarzenie rzeczywiście wpłynęło na drugie, a nie to, że dwie różne sytuacje miały miejsce wokół tego samego fizycznego momentu, choć były całkowicie niewspartane. Kopieta rozproszonej bazy danych muszą wiedzieć, na przykład, czy aktualizacja, którą właśnie otrzymały, była reakcją na wartość, którą już przechowywały, czy też została zapisana niezależnie przez osobę, która nigdy nie widziała tej wartości. Rozwiązanie tego problemu wymaga całkowitego odwołania się do pojęcia jednego globalnego zegara i zamiast tego śledzenia dla każdego procesu własny widok na to, jak daleko postąpiły wszystkie inne procesy. To dokładnie to, co kopię wektora czasowego zapisuje.

Jak jest budowany i aktualizowany wektor czasowy

W systemie z N procesami każdy z nich przechowuje wektor, czyli tablicę N liczników, jedno pole dla każdego procesu, wszystkie początkowo ustawione na zero. Kiedy proces doświadcza lokalnego zdarzenia, takiego jak wykonywanie obliczeń lub zapisywanie w swoim magazynie, zwiększa tylko swoje własne pole wektorze. Gdy proces wysyła komunikat do innego procesu, przypisuje kopię swojego aktualnego wektora do tego komunikatu. Gdy proces otrzymuje komunikat, wykonuje dwie rzeczy: najpierw bierze elementowy maksimum między swoim wektorem a wektorem przylegającym do przychodzącego komunikatu, co oznacza porównanie każdego pola po kolei i zachowanie wartości większej, a następnie zwiększa swoje własne pole o jeden. Rozważmy trzy procesy A, B i C, każdy początkowo na zero zero zero. A wykonuje lokalne zdarzenie, więc jego wektor staje się jeden zero zero. Następnie A wysyła komunikat do B zawierający ten wektor. B, którego wektor był zero zero zero, bierze elementowy maksimum ze wchodzącego jedno zero zero, otrzymując jeden zero zero, a następnie zwiększa swoje własne pole, co daje jeden jeden zero. W tym czasie C, nie mając na uwadze żadnej z tych operacji, może samodzielnie wykonać własne lokalne zdarzenie, przenosząc swój wektor do zero zero jeden. Teraz wektor B jasno pokazuje, że wie o jednym zdarzeniu od A i jednym zdarzeniu własnym, podczas gdy wektor C reprezentuje tylko swoje samodzielne historię.

Czytanie kausalności z wektorów

Aby określić, czy jedno zdarzenie nastąpiło przed drugim za pomocą ich wskazówek czasowych (vector clocks), porównujesz dwie wskazówki po kolei, slot po slotu. Jeśli każda komórka wektora pierwszego zdarzenia jest mniejsza lub równa odpowiedniej komórce wektora drugiego zdarzenia, a jednocześnie co najmniej jedna z tych komórek jest rzeczywiście mniejsza niż dokładnie równa, to pierwsze zdarzenie nastąpiło przed drugim. W prostych słowa: liczniki wcześniejszego zdarzenia nigdy nie mogą przekroczyć liczników późniejszego zdarzenia w żadnym slotu, a musi być co najmniej jeden slot, w którym licznik późniejszego zdarzenia rzeczywiście postąpił dalej. Jeśli ten warunek jest spełniony, wcześniejsze zdarzenie powiadamia, że kausalnie przystępuje do późniejszego, co oznacza, że między nimi istnieje łańcuch lokalnych zdarzeń i wysyłania oraz odbierania wiadomości. Ta porównanie działa dokładnie dlatego, że każda inkrementacja i każda operacja maksimum elementu tylko wypycha liczniki w górę, a odbiorca wiadomości zawsze akceptuje wszystko, co nadawca wiedział na chwilę wysyłania. Jeśli wektor drugiego zdarzenia dominuje nad wektorem pierwszego zdarzenia w ten sposób, to dowodzi, że niektóre informacje z pierwszego zdarzenia mogły przepłynąć, bezpośrednio lub pośrednio, do drugiego zdarzenia.

Wykrywanie współcześnieństwa, czego nie mogą zrobić skalowe zegary logiczne

Proste skalowe zegary logiczne, takie jak pierwotny zegar logiczny Lamporta, przypisują każdemu zdarzeniu pojedynczą rosnącą liczbę i gwarantują, że jeśli jedno zdarzenie kauzalnie przewyższa drugie, to liczba tego pierwszego zdarzenia jest mniejsza. Ale odwrotność nie jest pewna: dwa zdarzenia mogą otrzymać różne liczby, jedna mniejszą a druga większą, nawet jeśli ani jedno z nich nie przyczyniło się do drugiego, tylko miały miejsce samodzielnie i zostały porównane przypadkowo ze względu na ich numerację. Jedna liczba prosto nie może zawierać wystarczającej ilości informacji, aby rozróżnić prawdziwe kauzalne uporządkowanie od puro losowego zbiegu okoliczności. Zegary wektorowe naprawiają to, zachowując historię procesu zamiast sprowadzać wszystko do jednego licznika. Dwa zdarzenia nazywamy współcześnieśnymi, gdy ani jedno wektora nie dominuje nad drugim w sposób opisany wyżej, co oznacza, że żaden wektor nie jest mniejszy lub równy drugiemu w każdym położeniu. W naszym wcześniejszym przykładzie wektor B z wartością jeden zero jeden i wektor C z wartością zero zero jeden są współcześnieśne: wektor B ma większą wartość w pierwszym położeniu, ale wektor C ma większą wartość w trzecim położeniu, więc żaden wektor nie wygrywa w każdym położeniu. To dokładnie i poprawnie sygnalizuje, że zdarzenie B i zdarzenie C miały miejsce samodzielnie, bez kauzalnej relacji, co jest informacją, której nie mogłaby nigdy odkryć skalna etykieta czasu.

Zastosowania w praktyce: bazy danych i zarządzanie wersjami

Ta umiejętność wykrywania współcześnieństwa, a nie tylko przybliżonego porządku, jest dokładnie tym, czym potrzebowali wielu wpływowych systemów praktycznych. System Dynamo oryginalny Amazona opisany w jego znanej z 2007 roku publikacji używał zegarów wektorowych do śledzenia historii aktualizacji każdego elementu danych na replikach. Gdy dwie repliki otrzymały pisania konfliktujące, które były współcześnieiste według ich zegarów wektorowych, Dynamo nie próbowano bezgłośnie wybrania zwycięzcy i potencjalnie stracenia danych; zamiast tego wyróżniło obie wersje dla aplikacji, lub w niektórych przypadkach dla końcowego użytkownika, aby konflikt mógł być rozstrzygnięty z prawdziwym znaczeniowym zrozumieniem, ponieważ maszyna nie zawsze wie, która z dwóch współcześnieściowych edycji powinna mieć priorytet. Wiele współczesnych bazy danych dystrybucyjnych i magazynów wartości kluczowych używa podobnych mechanizmów, często nazywanych wektorami wersji, bliskimi krewnymi zegarów wektorowych skoncentrowanymi na śledzeniu wersji replikami, a nie pojedynczych zdarzeń. Systemy zarządzania wersjami dystrybucyjnymi, takie jak Git, stoją przed podobną problemem przy scalaniu gałęzi: muszą wiedzieć, czy jedna komit jest potomkiem drugiej, co oznacza, że jest jasno spowodowana przez nią, czy obie komity odłączyły się niezależnie i zatem potrzebują rzeczywistej trójstronnej scalenia. Podstawowa logika, śledzenie postępu pochodzącego z źródełami zamiast zaufania do jednego globalnego licznika, jest tą samą myślą, którą formalizował zegar wektorowy dla ogólnego obliczania dystrybucyjnego.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Vector Clocks: Ordering Events Without a Shared Clock i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.