Można zrobić globalny snapshot systemu bez zatrzymywania wszystkich komputerów w tej samej chwili
Jak zapisać „stan całego systemu”, jeśli nie ma globalnego zegara, maszyny pracują bez przerwy, a wiadomości są w drodze? Chandy i Lamport pokazali w 1985 r., że da się zarejestrować spójny globalny snapshot bez jednoczesnego zatrzymania wszystkich procesów. Specjalne markery przesyłane kanałami pozwalają każdemu procesowi zapisać własny stan oraz odpowiednio uchwycić wiadomości będące „w locie”. Wynik nie jest fotografią wykonaną jednym fizycznym aparatem w jednej nanosekundzie. Jest logicznie spójnym przekrojem wykonania, który mógł odpowiadać stanowi systemu.
Globalny stan obejmuje więcej niż pamięć serwerów
Jeżeli A wysłał B przelew, ale B jeszcze go nie odebrał, pieniądz nie powinien zniknąć ze snapshotu. Samo zapisanie lokalnej pamięci A i B w przypadkowych momentach może stworzyć stan niemożliwy: A uważa wiadomość za wysłaną, B jeszcze jej nie ma, a snapshot pomija kanał sieciowy.
Nie ma przycisku pauzy dla całego świata
W dużym systemie zatrzymanie wszystkich procesów jednocześnie byłoby kosztowne, a przy braku wspólnego zegara nawet pojęcie „jednocześnie” jest problematyczne. Algorytm Chandy’ego-Lamporta działa podczas normalnej pracy przy określonych założeniach dotyczących kanałów komunikacji.
Marker wyznacza granicę lokalnie
Proces inicjujący zapisuje swój stan i wysyła specjalne markery. Gdy inny proces otrzyma pierwszy marker, zapisuje własny stan i przekazuje markery dalej. Wiadomości otrzymywane na odpowiednich kanałach pomiędzy lokalnym snapshotem a markerem są rejestrowane jako stan kanału.
Rezultat jest spójnym cięciem
Kluczowa własność polega na tym, że snapshot nie zawiera efektu wiadomości bez uwzględnienia odpowiedniej przyczyny w sposób łamiący spójność. Nie musi odpowiadać jednemu timestampowi z fizycznego zegara. Wystarczy, że stanowi możliwy, przyczynowo spójny przekrój rozproszonego wykonania.
Algorytm przydaje się do myślenia o checkpointach i analizie
Globalne snapshoty są użyteczną abstrakcją dla wykrywania własności systemu, checkpointingu czy analizy rozproszonych obliczeń. Najbardziej niezwykła lekcja jest jednak ogólna: gdy fizyczna jednoczesność jest niedostępna, można skonstruować logiczny odpowiednik oparty na komunikacji i przyczynowości.
Snapshot nie musi zawierać „najświeższych” wartości wszędzie
Spójność snapshotu nie oznacza, że każdy lokalny stan pochodzi z tej samej fizycznej chwili. Jedna część może zostać zarejestrowana wcześniej, inna później. Warunek dotyczy relacji przyczynowych: wynik ma opisywać możliwy stan wykonania, a nie mieszankę, w której skutek istnieje bez odpowiedniej przyczyny. To subtelna, ale kluczowa różnica między fotografią zegarową a consistent cut.
Wiadomości w locie są częścią systemu
Na pojedynczej maszynie często myślimy o stanie jako o pamięci i dysku. W systemie rozproszonym istotny stan może znajdować się także w kanałach komunikacyjnych. Wiadomość wysłana, ale jeszcze nie odebrana, jest realnym fragmentem przyszłego zachowania. Algorytm snapshotu uczy więc szerszej lekcji: granice „stanu programu” rozszerzają się, gdy program składa się z komunikujących się procesów.
Algorytm ma założenia: klasyczna wersja rozpatruje niezawodne kanały FIFO i brak awarii procesów podczas wykonywania snapshotu. To ważne, bo popularny opis może brzmieć jak uniwersalna sztuczka działająca w dowolnej sieci. Jak zwykle w systemach rozproszonych, gwarancja zależy od modelu. Inne środowiska potrzebują rozszerzeń lub innych algorytmów. Wartość Chandy’ego-Lamporta polega na pokazaniu, że globalny stan da się skonstruować bez globalnego zegara, nie na zniesieniu wszystkich możliwych awarii.
Ciekawym skutkiem jest możliwość sprawdzania własności globalnych, takich jak zakończenie obliczenia czy brak wiadomości w locie, na podstawie snapshotu, którego nikt nie wykonał jednym globalnym poleceniem stop. Algorytm zamienia problem synchronizacji czasu na problem przepływu markerów. To powracający motyw tej dziedziny: jeśli czegoś nie da się zmierzyć bezpośrednio, można czasem zrekonstruować wystarczającą informację z relacji komunikacyjnych.