Laboratorium Hybridnych Logicznych Zegarów

Dlaczego nie wystarcza ani fizyczne, ani logiczne zegary

Fizyczne zegary na oddzielnych maszynach nigdy nie zgadzają się dokładnie. Nawet przy synchronizacji czasu przez sieć, małe odchylenia i przesunięcia są niewykluczone, więc dwie maszyny mogą się różnić o kilka milisekund lub więcej w dowolnym momencie. Jeśli system nakłada na każde zdarzenie lokalny fizyczny czas i przyjmuje, że te etykiety czasu można porównywać, aby ustalić porządek, często popełnia błąd: zdarzenie, które przypuszczalnie nastąpiło przed innym, może otrzymać większy czas fizyczny tylko dlatego, że zegar maszyny, która go rejestruje, lekko się przesunął. Jest to zagrożenie dla poprawności, a nie estetyczne, ponieważ bazy danych i rozproszone logi często zależą od porządku etykiet czasowych do ustalenia, które zapis jest zwycięski lub czy czytanie jest nowe. Zegary logiczne wprowadzone przez Lamport rozwiązują problem porządkowania, całkowicie ignorując fizyczny czas. Każdy węzeł utrzymuje licznik, który rośnie z każdym lokalnym zdarzeniem i, gdy otrzyma wiadomość, skacze do wartości o 1 większej niż maksimum między licznikiem lokalnym a licznikiem zawartym w wiadomości. Gwarantuje to, że porządek przyczynowy jest zawsze prawidłowo reprezentowany: jeśli zdarzenie A nastąpiło przed zdarzeniem B, licznik Lamport A jest gwarancji mniejszy niż B. Problem polega jednak na tym, że licznik jest purzą abstrakcją. Nie ma żadnego związku z rzeczywistym czasem przepłyniętym, więc węzeł otrzymujący wiele wiadomości w krótkim czasie może zobaczyć skok swojego licznika znacznie dalszy niż sugerowałby czas zegara murowego, a węzeł uczestniczący w niewielu interakcjach może się znacznie odchodzić. Porównanie etykiety czasowej Lamport do rzeczywistego momentu, na przykład do ustalenia, czy rekord jest starszy niż pięć minut, ma nieznaczenie. Zegary logiczne hybrydowe istnieją exactly to zamknąć tę wadę. Pod normalnymi warunkami utrzymują etykiety czasowe związanym z rzeczywistym czasem, więc w przypadku powszechnie występującego sytuacji, gdy zegary są odpowiednio synchronizowane i zdarzenia nie są gęsto współcześnie, etykiety czasowe HLC to proste odczyty zegara murowego lokalnego. Tylko wtedy, gdy rzeczywisty czas nie dostarcza wystarczającej rozdzielczości, lub kiedy przyczynowość wymaga tego, że logiczna część wejdzie w akcję i inkrementuje licznik dokładnie tak, jakby sam fizyczny zegar podał błędną porządkowość.

Struktura znacznika czasu HLC

Znak znacznika czasu HLC to para wartości, często zapisywana jako (czas fizyczny, licznik logiczny), a czasem skrócona do (pt, l). Komponent czasu fizycznego pochodzi z zegara boczniczego węzła i reprezentuje najlepsze obecne szacowanie algorytmu rzeczywistego czasu, przesuwane w górę, gdy kausalność wymaga, aby pozostawało przed znacznikami, które zauważył. Komponent licznika logicznego to mały całkowity, który rozwiązuje sytuacje równania i zachowuje informację o kolejności, której nie można wyrazić tylko przy pomocy czasu fizycznego, na przykład gdy wielokrotne zdarzenia występują w tym samym ticku zegara lub gdy znacznik przesłanej wiadomości nie przewyższa lokalnego zegara boczniczego. Porównywanie dwóch znaczników czasowych HLC jest wykonane leksykograficznie: najpierw porównuje się komponenty czasu fizycznego, a tylko wtedy, gdy one są równe, porównuje się liczniki logiczne. To oznacza, że znak znacznika czasu HLC zachowuje się prawie dokładnie tak samo jak znak znacznika czasu fizycznego pod względem interpretacji ludzkich i zapytań zakresowych, ponieważ komponent czasu fizycznego dominuje w porównaniu w większości przypadków. Licznik logiczny zwykle pozostaje mały, często składający się z kilku cyfr, ponieważ akumuluje się tylko wtedy, gdy wielokrotne zdarzenia kausalnie powiązane są wpakowane do tego samego ticku zegara fizycznego, a resetuje się do zera, gdy komponent czasu fizycznego rzeczywiście postępuje dalej niż jego poprzednia wartość. Ta konstrukcja sprawia, że HLC ma jednocześnie dwie cechy, które samodzielnie nie oferują ani czysty czas fizyczny, ani czysty licznik logiczny. Po pierwsze, komponent czasu fizycznego jest zawsze bliski rzeczywistemu czasowi boczniczkom, ograniczony do maksymalnej przesunięcia zegara i opóźnienia wiadomości obserwowanych w systemie, więc znak znacznika czasu HLC może być używany prawie bez zmian dla sprawdzania wygaśnięcia, okien zebrania śmieci lub logów czytelnych dla ludzi. Po drugie, całość pary zawsze zachowuje gwarancję kolejności kausalnej: gdy jedno zdarzenie kausalnie nastąpiło przed innym, porównując ich pary HLC leksykograficznie, zawsze poprawnie zgłoszą tę kolejność, dokładnie tak jak by to zrobił zegar Lamporta.

Zasada Aktualizacji, Krok Po Kroku

Algorytm HLC definiuje dwie zasady aktualizacji: jedną dla czynności lokalnych i drugą dla otrzymywania wiadomości zawierającej odległy timestamp HLC. Oba zasady opierają się na tej samej podstawowej myśli: nigdy nie pozwalaj, aby timestamp był mniejszy, a zawsze włącz najnowsze dostępne informacje. W przypadku czynności lokalnej, węzeł czyta swój fizyczny zegar i oznacza wynik jako pt_now. Następnie oblicza nową komponentę czasu fizycznego jako maksimum z pt_now i własnej poprzedniej komponenty czasu fizycznego. Jeśli to maksimum jest równe poprzedniej komponentie czasu fizycznego, co oznacza, że fizyczny zegar węzła nie widocznie postąpił od ostatniej aktualizacji, licznik logiczny inkrementuje się o jeden. Jeśli maksimum jest stricte większe niż poprzednia komponenta czasu fizycznego, co oznacza, że rzeczywisty czas postąpił dalej, licznik logiczny resetuje się do zera. To dokładnie przypomina zasadę inkrementacji Lamporta na każdym zdarzeniu, z tym różnictwem, że inkrementacja jest potrzebna tylko wtedy, gdy fizyczny czas samego siebie nie dostarcza nowej rozdzielczości. W przypadku otrzymywania wiadomości zawierającej odległy timestamp (pt_remote, l_remote), węzeł ponownie czyta swój lokalny fizyczny zegar pt_now i oblicza nową komponentę czasu fizycznego jako maksimum trzech wielkości: pt_now, własnej poprzedniej komponenty czasu fizycznego oraz pt_remote. Tym zatem z największą wartością staje się nowa komponenta czasu fizycznego. Następnie licznik logiczny ustawia się w zależności od tego, która z tych trzech wielkości osiągnęła to maksimum: jeśli tylko odczyt lokalnego zegara fizycznego osiągnął to maksimum, licznik logiczny resetuje się do zera; jeśli nowa komponenta czasu fizycznego jest równa poprzedniej lokalnej komponentie czasu fizycznego i/lub odległej komponentie czasu fizycznego, licznik logiczny staje się o jeden większy niż maksimum z odpowiednich poprzednich liczników logicznych, inkrementując się w celu rozwiązań konfliktu. W każdym przypadku licznik nigdy nie maleje, gwarantując, że połączony timestamp jest większy od obecnego timestampa nadawcy i własnego poprzedniego timestampa węzła, co dokładnie zachowuje garancję kolejności przyczynowej między wymianami wiadomości.

Jak HLC Zachowuje Czasem Cauzalny Bez Stracenia Znaczenia Fizycznego

Dowód poprawności dla HLC odzwierciedla klasyczne dowody dla zegarów Lamporta, dodając granicę związanej z czasem fizycznym. Ponieważ każda reguła aktualizacji przyjmuje maksimum wszystkich odpowiednich wcześniejszych timestampów i, gdy jest to konieczne, zawsze zwiększa licznik logiczny, wynikający timestamp dowolnego wydarzenia jest zawsze większy od timestampów każdego wydarzenia, które go przyczynowo poprzedza. To samo warunki zegarowe, które spełniają czyste zegary logiczne: jeśli wydarzenie A nastąpiło przed wydarzeniem B, czy przez porządek programowy na jednym węźle, czy przez łańcuch wysyłek i odbiorów wiadomości między węzłami, to HLC(A) jest zawsze mniejszy niż HLC(B), jak opisano wcześniej. To, co dodaje HLC na topie tej gwarancji, to dowodzona granica relacjonująca składnik fizyczny do rzeczywistego czasu zegara. Pod warunkiem odpowiednich założeń, takich jak ograniczona skojarzona przesunięcie czasowe między węzłami i ograniczone opóźnienie wysyłki wiadomości, składnik czasu fizycznego dowolnego timestampa HLC pozostaje blisko rzeczywistego czasu fizycznego, w którym wydarzenie nastąpiło. Ta granica jest to, co sprawia, że timestampi HLC są użyteczne dla celów rzeczywistych: porównywanie timestampa HLC z terminem zegara, obliczanie przybliżonej długości czasu między dwoma wydarzeniami na różnych węzłach, lub wyświetlanie wpisu logu czytelnego dla człowieka pozostaje znaczące. To, co byłoby niemożliwe przy użyciu jedynie liczników logicznych. Warto być precyzyjnym co do tego, co HLC nie daje Ci. Nie daje on dokładnej porządkowania w czasie rzeczywistym tak jak idealnie zgodny globalny zegar i nie zastępuje struktur stronger causality tracking, gdy system musi wiedzieć pełną historię przyczynową każdego wydarzenia, a nie tylko jednolitego porządkowania zgodnego z przyczynowości. HLC dostarcza pojedynczy wartość skalarny dla każdego wydarzenia, która jest łatwa do przechowywania, porównywania i indeksowania, z kosztem tylko przybliżonej simultanności i tylko zachowania przyczynowego precedencji zamiast pełnej informacji o zależnościach przyczynowych.

Zastosowanie w Praktyce: CockroachDB, MongoDB i dalej

Hybrydowe logiczne zegary stały się popularne w produkcyjnych bazy danych dystrybuowanych, ponieważ rozwiązują konkretny problem inżynieryjski: te systemy potrzebują etykiet czasowych używanych zarówno dla celów poprawności, aby uporządkować transakcje consistentnie poza całą klastrą, jak i dla operacyjnych celów, takich jak wygaszanie starych danych, usuwanie wielorzędowego magazynu lub raportowanie granic zapytań przechodniowych w sposób przypominający czas kalendarzowy. CockroachDB używa HLC jako podstawy do uporządkowania transakcji i zarządzania wielorzędowym zgodnością. Każdy węzeł utrzymuje hybrydowe logiczne zegary, a każda operacja czytania i pisania jest etykietowana za pomocą tego zegara. Ponieważ komponent fizyczny śledzi czas rzeczywisty bardzo dokładnie, CockroachDB może ograniczyć, jak daleko od reszty klastra może się odchylić zegar danego węzła i używać tego ograniczenia do zapewniania zgodności transakcji, podczas gdy licznik logiczny upewnia się, że nawet operacje wystąpiłe w tym samym fizycznym ticku lub przychodzące poza porządkowanie czasu fizycznego ze względu na opóźnienia sieciowe są nadal uporządkowane zgodnie z przyczynowości. MongoDB wprowadził podobny mechanizm, ogólnie nazywany jako czas klastra, który follows tę samą hybrydową metodę do uporządkowania operacji w causally consistent sesjach poza kopiami zapasowymi i klonami. Gdy klient wykonuje causally consistent czytanie po zapisie, sterownik propaguje hybrydowe etykiety czasu tak, aby wszystkie operacje na dowolnym węźle klastra były gwarantowane do obserwacji widoku danych co najmniej tyle nowego, ile klient już widział, ponownie korzystając z tej samej reguły aktualizacji maksimum i inkrementacji, aby połączyć czas fizyczny z uporządkowaniem logicznym. Poza tymi dwoma systemami ta sama idea pojawia się tam, gdzie inżynierzy potrzebują etykiet czasowych, które działają zarówno jako mecanizm uporządkowy, jak i operacyjnie znaczący zegar, włącznie z różnymi ramkami dystrybuowanych logów i źródeł zdarzeń, niektórymi implementacjami zgody i replikacji oraz akademickimi pracami nadawcymi, które rozszerzają podstawowy pomysł HLC o strictejsze ograniczenia lub dodatkowe metadane.

Często zadawane pytania