Snapshot Algorytmu Rozproszonego Chandy’ego-Lamporta

Problem: Uchwycenie Momentu w Systemie Bez Centralnego Czasomierza

System rozproszony składa się z procesów, które komunikują się jedynie poprzez wysyłanie wiadomości po kanałach, przy czym każdy proces wie o stanie innych procesów tylko dzięki tym wiadomościom. Nie ma globalnego czasomierza i nie ma chwili, w której wszystkie maszyny mogłyby zostać jednocześnie poproszone o wstrzymanie się, ponieważ sam akt ich powiadomienia zajmuje czas i dociera w różnych momentach. Powoduje to poważny problem: jeśli poprosisz każdy proces o zgłoszenie swojego stanu, gdy tylko otrzyma twoje żądanie, raporty będą odzwierciedlać bardzo różne, niezsynchronizowane chwile, a niektóre mogą opisywać stan, który nigdy nie istniał razem. Na przykład jeden proces może zgłosić, że już odebrał wiadomość, która według raportu innego procesu jeszcze nie została wysłana. Takie ujęcie sytuacji byłoby niespójne i mogło wprowadzić w błąd każdy algorytm polegający na jego wykorzystaniu, taki jak ten sprawdzający, czy system ma wystarczające zasoby lub zablokował się. Potrzebna jest zamiast tego spójna globalna sytuacja, czasami nazywana „spójnym cięciem”: zbiór lokalnych stanów, jeden na proces, oraz zbiór wiadomości w transie na każdym kanale, taki że ten zbiór mógł racjonalnie istnieć w jednym momencie zgodnie z kolejnością przyczynowości zdarzeń. Kluczowe jest to, że nie wymaga to rzeczywistego współbieżności. Wymaga jedynie, aby zarejestrowane stany szanowały przyczynowość: jeśli ujęcie sytuacji rejestruje otrzymanie wiadomości, musi również rejestrować wysłanie tej samej wiadomości. Algorytm Chandy’ego-Lamporta został zaprojektowany specjalnie w celu generowania takiego cięcia wydajnie, wykorzystując jedynie wiadomości, które system już wysyła, oraz jeden nowy rodzaj wiadomości, zwany znacznikiem, i zakłada niezawodne kanały, które dostarczają wiadomości w kolejności wysłania (FIFO), co jest kluczowe dla sposobu, w jaki algorytm rozumie, co widział, a czego nie.

Jak działa algorytm: Oznaczki, Zapisywanie i Propagacja”, “paragraphs”: [

Algorytm rozpoczyna się, gdy dowolny proces decyduje się zainicjować snapshot. Proces inicjujący najpierw zapisuje swój lokalny stan, przechwytując wszystkie wewnętrzne zmienne istotne dla aplikacji, a następnie natychmiast wysyła specjalny komunikat oznaczający granice snapshot do każdego z kanałów, na których wychodzi, zanim wykona cokolwiek innego. Ten znacznik nie zawiera żadnych danych z aplikacji; jego jedynym celem jest sygnalizowanie granic snapshot. Od tego momentu inicjator również rozpoczyna zapisywanie wszystkich otrzymanych komunikatów aplikacji na każdym z kanałów, na których wchodzi, traktując te komunikaty jako stan w tranzycie przez ten kanał, aż do momentu odebrania znacznik na tym kanale. Teraz rozważ dowolny inny proces w systemie. Pierwszeństwo ma odbiór znacznika na jakimś kanale wejściowym - wtedy proces wykonuje natychmiast dwie czynności: zapisuje swój lokalny stan, dokładnie taki, jaki istnieje w danym momencie, oraz zapisuje stan kanału, z którego przybył znacznik, jako pusty, ponieważ znacznik na kanale FIFO sygnalizuje, że żadne wcześniejsze komunikaty aplikacji nie pozostają niezarejestrowane na tym połączeniu. Następnie rozpowszechnia snapshot poprzez wysłanie znacznika na wszystkich swoich kanałach wyjściowych, tak jak zrobił to inicjator, i rozpoczyna zapisywanie komunikatów przychodzących na każdym kanale, na którym jeszcze nie widział znacznika. Jeśli proces później odbiera znacznik na jednym z tych innych kanałów, przestań rejestrować ten kanał i zakończ swój zarejestrowany list komunikatów w tranzycie dla niego, co jest dokładnie zestawem komunikatów, które otrzymał na tym kanale po zapisaniu swojego stanu, ale przed odebraniem znacznika. Jeśli proces odbiera drugi lub kolejny znacznik na kanale, na którym już widział znacznik, to po prostu zamknij zapisywanie tego kanału, ponieważ duplikacja znacznika na tym samym kanale sygnalizuje brak nowych informacji. Algorytm kończy się, gdy każdy proces otrzymał znacznik na każdym z kanałów wejściowych, w punkcie, w którym każdy lokalny stan i stan kanału został zarejestrowany, a kompletny globalny snapshot może zostać zebrany, zwykle poprzez to, że każdy proces przesyła swój zarejestrowany stan do koordynatora.

Dlaczego Snapshot Jest Spójny: Argument Cięcia

Serce dowodu poprawności algorytmu Chandy’ego-Lamporta polega na pokazaniu, że zbiór zarejestrowanych stanów stanowi autentycznie spójne cięcie, czyli dla każdego komunikatu, który snapshot oznaczał jako odebrany przez pewien proces, ten sam komunikat jest również uwzględniony jako albo zarejestrowany w stanie lokalnym nadawcy przed snapshotem, albo wysłany i uchwycony jako część stanu w locie kanału, lub w inny sposób konsekwentnie umieszczony. Kluczowym spostrzeżeniem jest rygorystyczne uporządkowanie narzucone przez znaczniki połączone z właściwością FIFO kanałów. Gdy proces P rejestruje swój stan i wysyła znaczniki na wszystkie kanały wychodzące, każde kolejne komunikaty aplikacyjne wysłane przez P są wysyłane po markerze na tym samym kanale, ponieważ proces nigdy nie przekształca kolejności swoich komunikatów wychodzących względem decyzji o zrobieniu snapshotu. Dlatego też proces Q, który później odbiera ten marker na kanale od P, wiedząc dzięki właściwości FIFO, że każdy komunikat aplikacyjny dotrze na ten kanał przed markerem wysłanym przez P przed snapshotem P, oraz wszystko, co przybywa po markerze, należy do przyszłości po snapshotie i jest poprawnie wykluczone z rejestru w locie. To gwarantuje kluczową właściwość: żaden komunikat nie może być zarejestrowany jako odebrany w snapshotie bez tego, aby jego nadanie również zostało odzwierciedlone, albo już miało miejsce, albo w jakimś stanie w locie kanału. Innymi słowy, algorytm nigdy nie rejestruje efektu bez jego przyczyny. To ma ogromne znaczenie dla każdego algorytmu konsumującego snapshot, ponieważ oznacza to, że zarejestrowany stan globalny, mimo że jego fragmenty były fizycznie obserwowane w różnych momentach rzeczywistych na sieci, odpowiada stanowi, jaki system mógł przejść w prawidłowym wykonaniu zgodnym z rzeczywistym porządkiem zdarzeń (jego przyczynowym, albo „wydarze się przed” porządkiem). Ta gwarancja, a nie dosłowne współbieżność, sprawia, że snapshot jest niezawodny i użyteczny do rozumowania o właściwościach globalnych.”]} pango:false, markdown:false, html:false, json:true, text:false, xml:false, svg:false, image:false, video:false, audio:false, pdf:false, docx:false, xlsx:false, pptx:false, csv:false, txt:false, ttf:false, htm:false, html:false, json:true, text:false, xml:false, svg:false, image:false, video:false, audio:false, pdf:false, docx:false, xlsx:false, pptx:false, csv:false, txt:false, ttf:false, htm:false, html:false, json:true, text:false, xml:false, svg:false, image:false, video:false, audio:false, pdf:false, docx:false, xlsx:false, pptx:false, csv:false, txt:false, ttf:false, htm:false, html:false, json:true, text:false, xml:false, svg:false, image:false, video:false, audio:false, pdf:false, docx:false, xlsx:false, pptx:false, csv:false, txt:false, ttf:false, htm:false, html:false, json:true, text:false, xml:false, svg:false, image:false, video:false, audio:false, pdf:false, docx:false, xlsx:false, pptx:false, csv:false, txt:false, ttf:false, htm:false, html:false, json:true, text:false, xml:false, svg:false, image:false, video:false, audio:false, pdf:false, docx:false, xlsx:false, pptx:false, csv:false, txt:false, ttf:false, htm:false, html:false, json:true, text:false, xml:false, svg:false, image:false, video:false, audio:false, pdf:false, docx:false, xlsx:false, pptx:false, csv:false, txt:false, ttf:false, htm:false, html:false, json:true, text:false, xml:false, svg:false, image:false, video:false, audio:false, pdf:false, docx:false, xlsx:false, pptx:false, csv:false, txt:false, ttf:false, htm:false, html:false, json:true, text:false, xml:false, svg:false, image:false, video:false, audio:false, pdf:false, docx:false, xlsx:false, pptx:false, csv:false, txt:false, ttf:false, htm:false, html:false, json:true, text:false, xml:false, svg:false, image:false, video:false, audio:false, pdf:false, docx:false, xlsx:false, pptx:false, csv:false, txt:false, ttf:false, htm:false, html:false, json:true, text:false, xml:false, svg:false, image:false, video:false, audio:false, pdf:false, docx:false, xlsx:false, pptx:false, csv:false, txt:false, ttf:false, htm:false, html:false, json:true, text:false, xml:false, svg:false, image:false, video:false, audio:false, pdf:false, docx:false, xlsx:false, pptx:false, csv:false, txt:false, ttf:false, htm:false, html:false, json:true, text:false, xml:false, svg:false, image:false, video:false, audio:false, pdf:false, docx:false, xlsx:false, pptx:false, csv:false, txt:false, ttf:false, htm:false, html:false, json:true, text:false, xml:false, svg:false, image:false, video:false, audio:false, pdf:false, docx:false, xlsx:false, pptx:false, csv:false, txt:false, ttf:false, htm:false, html:false, json:true, text:false, xml:false, svg:false, image:false, video:false, audio:false, pdf:false, docx:false, xlsx:false, pptx:false, csv:false, txt:false, ttf:false, htm:false, html:false, json:true, text:false, xml:false, svg:false, image:false, video:false, audio:false, pdf:false, docx:false, xlsx:false, pptx:false, csv:false, txt:false, ttf:false, htm:false, html:false, json:true, text:false, xml:false, svg:false, image:false, video:false, audio:false, pdf:false, docx:false, xlsx:false, pptx:false, csv:false, txt:false, ttf:false, htm:false, html:false, json:true, text:false, xml:false, svg:false, image:false, video:false, audio:false, pdf:false, docx:false, xlsx:false, pptx:false, csv:false, txt:false, ttf:false, htm:false, html:false, json:true, text:false, xml:false, svg:false, image:false, video:false, audio:false, pdf:false, docx:false, xlsx:false, pptx:false, csv:false, txt:false, ttf:false, htm:false, html:false, json:true, text:false, xml:false, svg:false, image:false, video:false, audio:false, pdf:false, docx:false, xlsx:false, pptx:false, csv:false, txt:false, ttf:false, htm:false, html:false, json:true, text:false, xml:false, svg:false, image:false, video:false, audio:false, pdf:false, docx:false, xlsx:false, pptx:false, csv:false, txt:false, ttf:false, htm:false, html:false, json:true, text:false, xml:false, svg:false, image:false, video:false, audio:false, pdf:false, docx:false, xlsx:false, pptx:false, csv:false, txt:false, ttf:false, htm:false, html:false, json:true, text:false, xml:false, svg:false, image:false, video:false, audio:false, pdf:false, docx:false, xlsx:false, pptx:false, csv:false, txt:false, ttf:false, htm:false, html:false, json:true} id=

Praktyczne Zastosowania: Punktowe Kontrolne i Wykrywanie Zamrożeń

Najbardziej bezpośrednim zastosowaniem punktowych kontrolnych Chandy’ego-Lamporta jest mechanizm checkpointingu dla odporności na błędy. W długotrwałych obliczeniach rozproszonych, takich jak duże symulacje naukowe lub systemy przetwarzania transakcji, okresowe zapisywanie spójnego globalnego stanu pozwala całemu systemowi odzyskać po awarii, cofając się do ostatniego punktu kontrolnego zamiast rozpoczynania wszystkiego od zera. Ponieważ punktowy kontrolny jest gwarantowany jako spójny, przywracanie się z niego nigdy nie stawia systemu w niemożliwym stanie, w którym proces wydaje się otrzymał wiadomość, która, zgodnie z przywróconym stanem, nigdy nie była wysyłana; zawartość odnotowanego kanału jest po prostu odtwarzana tak, jakby została niedawno odebrana. Drugim głównym zastosowaniem jest wykrywanie zamrożeń w systemach rozproszonych. W systemach, w których procesy trzymają zasoby i czekają na siebie nawzajem, takie jak w bazach danych rozproszonych negocjujących bloki, zablokowanie odpowiada cyklowi w grafie oczekiwań, ale żaden pojedynczy proces nie może go bezpośrednio zobaczyć, ponieważ każdy wie tylko o swoich lokalnych zależnościach. Poprzez wykonanie punktowego kontrolnego każdego procesu stanu zasobu i oczekiwania, algorytm monitoringu może dokładnie odtworzyć pełny graf oczekiwań w jednym spójnym momencie i przeszukać go w poszukiwaniu cykli, a ponieważ punktowy kontrolny jest udowodniony jako spójny, znaleziony tam cykl odpowiada rzeczywistemu zamrożeniu, a nie artefaktowi porównywania niezgodnych momentów czasowych. Algorytm ten wpłynął również na szersze techniki wykrywania stabilnych właściwości, czyli takich, które, gdy są prawdziwe, pozostają prawdziwe, takie jak wykrywanie zakończenia lub zbieranie śmieci w systemach rozproszonych obiektów, ponieważ punktowy kontrolny jest dokładnie narzędziem potrzebnym do bezpiecznego sprawdzenia, czy taka właściwość obecnie obowiązuje we wszystkich procesach bez przerywania ich.

Założenia, Ograniczenia i Wybory Projektowe

Elegancja algorytmu Chandy’ego-Lamporta opiera się na specyficznym zbiorze założeń, które należy zrozumieć jasno. Wymaga to niezawodności kanałów, co oznacza brak utraty, duplikatów lub uszkodzeń wiadomości, a także działania w trybie kolejkowym (FIFO), dostarczania wiadomości w dokładnie takiej kolejności, w jakiej zostały wysłane, ponieważ argument poprawności zależy całkowicie od znacznika pełniącego rolę niezawodnej granicy w uporządkowanym strumieniu. Zakłada również silnie połączoną sieć bazową, dzięki której znaczniki zainicjowane gdziekolwiek mogą ostatecznie dotrzeć do każdego procesu, oraz że każdy proces, po odebraniu znacznika, poprawnie przestrzega protokołu bez awarii w trakcie samego tworzenia snapshotu. Jeśli kanały mogą przesuwać wiadomości w kolejności lub je zgubić, podstawowe gwarancje algorytmu ulegają naruszeniu i wymagane są bardziej złożone warianty z numerami sekwencji lub potwierdzeniami. Algorytm jest również milczący co do tego, co dzieje się między momentem wykrycia właściwości globalnej a momentem podjęcia jakichkolwiek działań na jej podstawie; ponieważ system nadal działa, snapshot opisuje stan, który jest już przeszłością w momencie jego pełnego zebrania, więc jego wnioski muszą dotyczyć stabilnych właściwości lub być wykorzystywane do odzyskiwania, a nie do podejmowania natychmiastowych decyzji kontrolnych w czasie rzeczywistym. Kolejna subtelność to nakładki: liczba wiadomości znacznika rośnie wraz z liczbą kanałów, a każdy proces tymczasowo buforuje przychodzące wiadomości na nienaznaczonych kanałach, co kosztuje pamięć proporcjonalną do szybkości propagacji znaczników. Pomimo tych ograniczeń, kluczowym wkładem algorytmu jest oddzielenie koncepcji sensownego globalnego snapshotu od niemożliwej wymaganej dosłowności współbieżności, a jego potomkowie pojawiają się na szeroką skalę w nowoczesnych ramach przetwarzania strumieniowego i protokołach sprawdzania punktów kontrolnych rozproszonych baz danych.”]} p1:

paragraphs_pl2

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz The Chandy-Lamport Distributed Snapshot Algorithm i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.