Zatrzymanie (ang. stopping failure ) oznacza, że serwer przestaje zwracać wyniki w sposób dający się stwierdzić przez inne procesy. Najłagodniejszą formą zatrzymania jest omówione wcześniej załamanie. Inną formą jest np. błąd ominięcia.

Serwery z reguły nie uprzedzają innych, że mają zamiar ulec awarii. Jest to szczególnie problematyczne w systemach z awariami uciszającymi (ang. fail-silent systems ). Procesy dokonując oceny pracy serwerów mogą dojść do przekonania, że uległy one awarii, pomimo że awaria jest tylko przejściowa i polega jedynie na zwolnieniu pracy, a więc na niedostatku efektywności.

Generowanie całkowicie losowych odpowiedzi przez serwer może być w stosunkowo prosty sposób wykryte przez procesy. Tego typu awaria jest awarią dowolną, ale o łagodnej formie. Mówimy, że jest to awaria bezpieczna (ang. fail-safe ).

Grupy są dynamiczne, co oznacza, że procesy mogą dołączać się do nich i odłączać podczas pracy systemu. Co więcej: procesy mogą w tym samym czasie należeć do kilku grup. Potrzebny jest więc mechanizm zarządzania grupami i przynależnością do nich.

Protokoły oparte na kopii podstawowej stosują najczęściej model podstawa-zapas (ang. primary-backup ), w którym wszystkie modyfikacje przetwarzane są najpierw przez wybrany węzeł koordynujący, a następnie propagowane do pozostałych węzłów. Odczyty mogą być realizowane współbieżnie przez dowolny węzeł będący kopią serwera podstawowego. Procesy są więc zorganizowane w postaci hierarchicznej grupy z wyróżnionym węzłem-koordynatorem. Wadą takiego rozwiązania jest oczywiście ryzyko awarii węzła-koordynatora. W takiej sytuacji należy wykonać algorytm elekcji i dokonać wyboru nowego węzła-koordynatora spośród kopii zapasowych.

Protokoły zwielokrotnionych zapisów działają na zasadzie aktywnego zwielokrotniania (ang. active replication ) lub poprzez dobieranie kworum . W obu podejściach procesy są zorganizowane w równouprawnioną grupę. W aktywnym zwielokrotnianiu wszystkie żądania (również zapisy) przesyłane są w identycznej postaci do wszystkich węzłów i przetwarzane współbieżnie. Algorytmy oparte na kworum wymagają wykonania modyfikacji przez procesy tworzące kworum. Zaletą protokołów zwielokrotnionych zapisów jest brak elementu centralnego przetwarzania, ale pojawia się w nich dodatkowy koszt związany z rozproszoną koordynacją.

Istotną kwestią jest liczba replik procesów, jakie będą tworzone w systemie. Mówimy, że system jest w stanie tolerować k uszkodzeń, gdy jego funkcjonowanie będzie nadal poprawne po wystąpieniu k awarii. Osiągnięcie takiego poziomu odporności zależy od charakteru awarii występujących w systemie. Jeżeli awarie mają charakter uciszający, to do tolerowania k awarii wystarczy k+1 procesów. Proces k+1 będzie w stanie udzielić odpowiedzi po awarii k procesów. W przypadku awarii bizantyjskich, w najgorszym przypadku k błędnie działających procesów może generować złą, ale spójną odpowiedź. Stwierdzenie tego faktu jest możliwe pod warunkiem posiadania dostępu do k+1 poprawnych węzłów. W efekcie do tolerowania k awarii bizantyjskich potrzeba 2k+1 węzłów.

Problemy uzgadniania stają się bardzo trudne w systemach, w których mogą występować awarie. Klasycznym przykładem obrazującym możliwe trudności jest problem dwu armii . W problemie tym rozpatrywany jest atak dwóch armii niebieskich o sile 3000 pododdziałów każda, na armię czerwoną o sile 5000 pododdziałów. Armie niebieskie stacjonują w odległych miejscach i muszą wspólnie podjąć decyzję o ataku. Jedynie ich wspólny atak może zakończyć się zwycięstwem. Decyzja jest więc w tym przypadku binarna: atakować lub nie. Niestety komunikacja armii niebieskich wymaga wysyłania posłańców, którzy mogą być przechwyceni przez wroga – obrazuje to zawodny kanał komunikacyjny.

Ze względu na przewidywane dowolne awarie procesów, należy w tym przypadku inaczej zdefiniować porozumienie. Generałowie dążą do ustalenia liczebności oddziałów i wymieniają te informacje między sobą. Porozumieniem jest ustalenie wektora liczebności oddziałów przez poszczególnych generałów, w taki sposób, że jeżeli i-ty generał jest lojalny, to i-ta pozycja wektora zawiera liczebność jego oddziału. W przeciwnym razie pozycja ta będzie nieokreślona.

Na wyższym poziomie komunikacja może być realizowana z wykorzystanie zdalnych wywołań procedur (RPC) lub metod (RMI). Jedną z motywacji stosowania mechanizmu RPC było ukrywanie faktu rozproszenia wywołania procedury. Jeżeli w systemie występują awarie, to pojawiają się podczas przetwarzania sytuacje, które nie wystąpiłyby w przypadku lokalnego wywoływania procedur. Powoduje to, że zachowanie pełnej przezroczystości nie zawsze będzie możliwe. Błędy, które mogą się pojawić podczas realizacji zdalnego wywołania procedur można podzielić na 5 wymienionych klas.

Druga kategoria błędów występujących podczas realizacji zdalnych wywołań procedur to zaginięcie komunikatu z żądaniem klienta. Jest to kategoria, której poprawne obsłużenie jest najprostsze. Klient wysyłając komunikat z żądaniem ustawia czasomierz i po upływie ustalonego czasu uznaje, że komunikat nie dotarł do serwera, ponieważ nie odebrano odpowiedzi. W efekcie następuje retransmisja żądania. Jeżeli komunikat faktycznie został zagubiony, serwer obsłuży retransmitowane żądanie tak, jakby to był oryginał. Jeżeli komunikat jednak dotarł do serwera, to mechanizm wywołań zdalnych należy rozbudować o środki do wykrywania powielonych wywołań. W przypadku przeciążonego serwera klient może po kilku retransmisjach zrezygnować z wysyłania kolejnych. Następuje wtedy przejście do obsługi błędu typy „brak dostępu do serwera”.

Załamanie serwera może nastąpić po obsłużeniu żądania lub przed. W zależności od tego czy żądanie zostało obsłużone czy nie, reakcja klienta powinna być różna. Jeżeli serwer nie przystąpił do obsługi odebranego żądania, to żądanie takie powinno zostać retransmitowane przez klienta. Jeżeli serwer obsłużył żądanie i uległ awarii to powinno to zostać zgłoszone po stronie klienta. Problem polega jednak na tym, że klient nie jest w stanie tych dwóch sytuacji rozróżnić. Jedyne co stwierdza to fakt upłynięcia czasu od momentu wysłania żądania.

Istnieje kilka metod reakcji na awarię serwera. Pierwsza metoda polega na oczekiwaniu na wznowienie pracy serwera i przesłaniu ponownego żądania w celu uzyskania odpowiedzi. Metoda ta określana jest jako semantyka co najmniej jednokrotna (ang. at least once semantics ). Gwarantuje ona, że każde wywołanie procedury zostanie wykonane przynajmniej jeden raz, ale być może, że również wiele razy. Drugie podejście polega na natychmiastowym przerwaniu prób komunikacji z serwerem po stwierdzeniu wystąpienia problemów. Jest to semantyka co najwyżej jednokrotna (ang. at most once semantics ), która gwarantuje, że wywołanie procedury nastąpi najwyżej raz, ale być może, że nie nastąpi w ogóle. Najprostszym rozwiązaniem jest oczywiście nie gwarantowanie niczego. W takiej sytuacji wywołanie zdalne mogło nie nastąpić, mogło nastąpić raz lub wielokrotnie.

Oczywiście semantyki te nie są tym, czego oczekuje klient. Użytkownik oczekuje tak naprawdę semantyki dokładnie jednokrotnej (ang. exactly once semantics ). Niestety semantyka taka jest niemożliwa do zrealizowania.

Podsumowując: możliwość załamania serwera wyraźnie różnicuje systemy scentralizowane i rozproszone w kontekście wykonywania procedur. W przypadku systemów scentralizowanych awaria serwera pociąga za sobą awarię klienta. W systemach rozproszonych awaria serwera wymaga obsłużenia tej sytuacji po stronie klienta.

Klient nie odbierając potwierdzenia ze strony serwera nie ma możliwości poprawnego ocenienia zaistniałej sytuacji. Powodem braku odpowiedzi może bowiem być zaginięcie komunikatu z odpowiedzią potwierdzającą wykonanie operacji, ale równie dobrze źródłem braku odpowiedzi może być znaczące spowolnienie pracy przez serwer. Jedyną sensowną reakcją ze strony klienta jest w tym przypadku retransmisja żądania. Poprzednie zlecenie być może jednak dotarło do serwera i po retransmisji zostanie wykonane ponownie. W przypadku pewnych zleceń nie jest to problemem. Np. zlecenie odczytu fragmentu pliku od określonej pozycji, przy założeniu braku współbieżnego zapisu, zawsze da ten sam rezultat. Operacje takie są określane jako operacje idempotentne (ang. idempotent ). Wiele operacji nie jest jednak idempotentnych. Np. usunięcie pliku przy ponownej próbie wykonania zwróci błąd, ponieważ pliku już nie będzie istniał. Podobnie wygląda sytuacja z tworzeniem nowego pliku. Rozwiązaniem jest numerowanie zleceń pochodzących od poszczególnych klientów. Serwer przed wykonaniem zlecenia sprawdza czy dane żądanie, pochodzące od konkretnego klienta, zostało już zrealizowane czy nie. Jeżeli było, to odsyła jedynie potwierdzenie, nie wykonując samej operacji. Dodatkowym zabezpieczeniem może być sygnalizowanie serwerowi, że dane żądanie jest retransmitowane, co powinno wzmóc czujność serwera. Rozwiązania te niestety wymuszają przechowywanie po stronie serwera informacji o klientach w postaci numerów ostatnio zrealizowanych zleceń. Informacje te będą niestety tracone przy ewentualnej awarii serwera.

Kolejnym problemem pojawiającym się podczas wykonywania zdalnych wywołań metod jest awaria klienta następująca po zleceniu zdalnego przetwarzania. Obliczenia zainicjowanie przez klienta mogą pozostać aktywne po stronie serwera niepotrzebnie go obciążając. Takie pozostałości nazywane są sierotami (ang. orphan ). Sieroty mogą powodować problemy jeżeli np. powodowały zajmowanie zasobów. Również komunikaty zwrotne po zakończeniu przetwarzania mogą być mylące dla klienta, który wznowił swoje przetwarzania.

Istnieje kilka metod radzenia sobie z sierotami. Pierwsza, zwana eksterminacją (ang. extermination ), polega na rejestrowaniu w pamięci trwałej (dysk) wszystkich zleceń przez namiastkę klienta i jawnym usuwaniu odpowiedzi-sierot. Wadą tego rozwiązania jest bardzo duży koszt związany z rejestrowaniem wywołań. Drugie rozwiązanie, zwane reinkarnacją (ang. reincarnation ), polega na oznaczaniu każdego wywołania numerem epoki, oznaczającej logicznie upływający czas pomiędzy kolejnymi wznowieniami pracy klienta. Po wznowieniu pracy klient wysyła do wszystkich serwerów komunikat o nastaniu nowej epoki, który powoduje zatrzymanie wszystkich obliczeń tego klienta. Jeżeli jakaś sierota przeżyje na serwerze, do którego aktualnie nie ma dostępu, to i tak będzie mogła być łatwo wykryta poprzez stwierdzenie nieaktualnego numeru epoki. W łagodnej wersji reinkarnacji (ang. gentle reincarnation ), serwer po odebraniu komunikatu o nastaniu nowej epoki próbuje ustalić właścicieli każdej z wykonywanych prac. Usuwane są tylko te zadania, dla których nie udało się ustalić właściciela. Ostatnią propozycją jest przydział ustalonego kwantu czasu zdalnej procedurze na jej wykonanie. Przekroczenie tego czasu jest możliwe tylko po uzyskaniu potwierdzenia od klienta. Jeżeli klient ulegnie awarii, potwierdzenie nie zostanie udzielone i automatycznie zadanie takie ulegnie anulowaniu. Metoda ta jest nazywana wygaśnięciem (ang. expiration ).

Zatwierdzanie rozproszone

---

Zatwierdzanie rozproszone (ang. distributed commit ) jest ogólnym problemem, w którym chodzi o wykonanie danej operacji przez każdego członka grupy procesów lub przez żadnego. Problem niezawodnego rozsyłania jest przykładem problemu zatwierdzania rozproszonego, w którym operacją, która ma być wykonana przez wszystkich (lub przez nikogo) jest dostarczenie konkretnej wiadomości.

Zatwierdzanie rozproszone b. często odbywa się przy udziale koordynatora. W najprostszym przypadku koordynator informuje procesy czy mają dokonać lokalnego zatwierdzenia wykonywanych operacji (np. transakcji). Podejście to określane jest jako protokół zatwierdzania jednofazowego (ang. one-phase commit protocol ). W podejściu tym nie uwzględnia się sytuacji, w której lokalne zatwierdzenie operacji nie będzie możliwe, np. ze względu na zablokowane zasoby. W przypadku zatwierdzania rozproszonego potrzebne są więc bardziej rozbudowane schematy, np. protokół zatwierdzania dwufazowego .

Protokół zatwierdzania dwufazowego - 2PC

---

Protokół zatwierdzania dwufazowego (ang. two-phase commit protocol ) uwzględnia fakt, że lokalne zatwierdzenie transakcji nie zawsze będzie możliwe. W związku z tym, przed zatwierdzeniem transakcji realizowane jest głosowanie mające na celu ustalenie czy wszyscy uczestnicy przetwarzania będą mogli transakcję zatwierdzić. Koordynator wysyła w tym celu komunikat GŁOSOWANIE do wszystkich uczestników przetwarzania, rozpoczynając w ten sposób głosownie. Uczestnik głosowania odpowiada komunikatem ZA lub PRZECIW , w zależności od tego czy może zatwierdzić operację lokalnie czy nie. Koordynator po odebraniu wyników głosowania podejmuje decyzję. Jeżeli wszyscy głosowali na tak, wysyła komunikat ZATWIERDŹ , powodujący globalne zatwierdzenie transakcji. Jeżeli pojawił się choć jeden głos na nie, wysyłany jest komunikat ZANIECHAJ . Uczestnicy przetwarzania, którzy głosowali na tak, po odebraniu komunikatu ZATWIERDŹ dokonują lokalnego zatwierdzenie transakcji. Jeżeli uczestnik głosował na nie, lub otrzymał komunikat ZANIECHAJ , dokonuje wycofania transakcji.


Stany w protokole 2PC

---

Podstawową wadą protokołu 2PC jest jego wrażliwość na awarie, zarówno koordynatora jak i poszczególnych uczestników. W przetwarzaniu zarówno po stronie koordynatora jak i uczestników występują stany oczekiwania na komunikat (CZEKANIE u koordynatora, ROZPOCZĘCIE i GOTOWOŚĆ u uczestnika). Awaria któregoś z procesów może powodować w tym przypadku zablokowanie pozostałych, a więc prowadzi do niepowodzenia protokołu jako całości. W celu rozwiązania tego problemu można zastosować odliczanie czasu celem wykrycia awarii.

Uczestnik głosowania czeka na początku w stanie ROZPOCZĘCIE na komunikat GŁOSOWANIE. Jeżeli komunikat nie nadchodzi, uznaje, że transakcję należy wycofać. Jeżeli komunikat jednak nadejdzie, odeśle odpowiedź PRZECIW.

Koordynator jest blokowany w stanie CZEKANIE. Jeżeli w określonym czasie nie otrzyma odpowiedzi od wszystkich uczestników, podejmuje decyzję o wycofaniu transakcji (wyśle komunikat ZANIECHAJ ).

Uczestnik może być także blokowany w stanie GOTOWOŚĆ. Jeżeli nie nadejdzie komunikat od koordynatora, to uczestnik może podjąć decyzję o wycofaniu transakcji. Lepszym rozwiązaniem jest jednak próba skomunikowania się z innymi uczestnikami w celu uzyskania informacji o decyzji koordynatora. Jeżeli uczestnik P dowie się od innego uczestnika Q , że on przeszedł do stanu ZATWIERDZENIE, to P również może zatwierdzić transakcję, ponieważ jedynym sposobem na przejście do stanu ZATWIERDZENIE jest uzyskanie od koordynatora komunikatu ZATWIERDŹ wskazującego na taką decyzję koordynatora (komunikat ZATWIERDŹ nie dotarł po prostu do P ). Podobnie jeżeli Q jest w stanie ZANIECHANIE , to P również może bez obaw wycofać swoją lokalną transakcję.

Sytuacja jest trudniejsza, gdy proces Q jest w stanie ROZPOCZĘCIE. Oznacza to, że Q nie dostał od koordynatora komunikatu GŁOSOWANIE . W takiej sytuacji bezpieczniej jest przejść w obu procesach do stanu ZANIECHANIE.

Najtrudniejsza sytuacja jest wtedy, gdy Q jest w stanie GOTOWOŚĆ, również czekając na decyzję od koordynatora. Mogło się zdarzyć, że koordynator uległ awarii po zainicjowaniu głosowania i wszystkie procesy są w stanie oczekiwania. Nawet jeżeli wszystkie są gotowe do zatwierdzenia, to i tak nie uda się podjąć żadnej decyzji – trzeba czekać na wznowienie pracy koordynatora.

Protokół 2PC z rekonstrukcją - koordynator

---

Slajd przedstawia działania protokołu 2PC zakładającego możliwość rekonstrukcji (odtwarzania stanu) procesów. Rekonstrukcja procesu wymaga zapisywania jego stanu do pamięci trwałej (np. dysk), dlatego wszystkie zmiany stanów w procesach są najpierw zapisywane do lokalnego rejestru, a następnie dopiero wykonywane.

Proces koordynatora rozsyła do wszystkich komunikat GŁOSOWANIE i oczekuje na odpowiedzi. Brak odpowiedzi (przekroczenie czasu oczekiwania) powoduje, że zapada decyzja o wycofaniu transakcji (linia 6). Jeżeli wszyscy odpowiedzą pozytywnie, transakcja jest zatwierdzana. W przeciwnym wypadku następuje jej wycofanie poprzez rozesłanie komunikatu ZANIECHAJ .

Protokół 2PC z rekonstrukcją - uczestnik

---

Jeżeli proces uczestnika w momencie zajścia awarii był w stanie ROZPOCZĘCIE i nie podjął jeszcze decyzji o zatwierdzeniu transakcji, to może ją po prostu wycofać po odtworzeniu stanu. Jeżeli zdążył przejść do stanu ZATWIERDZENIE lub ZANIECHANIE, to powinien zostać odtworzony właśnie do tego stanu. Problematyczne staje się załamanie w stanie GOTOWOŚCI. W tym przypadku proces nie jest w stanie sam zadecydować co powinien zrobić dalej. Musi skontaktować się z innymi uczestnikami, w celu zadecydowania o losie lokalnej transakcji. Sytuacja jest analogiczna do braku odpowiedzi od koordynatora po zainicjowaniu głosowania (linia 9).

Decyzja o zatwierdzeniu transakcji w normalnych warunkach przychodzi od koordynatora. Jeżeli jednak on nie odpowiada, można próbować uzyskać informacje o decyzji od innych uczestników – następuje wysłanie komunikatu do wszystkich uczestników w linii 10. Decyzja, która nadejdzie jest zapisywana i ostatecznie egzekwowana.

Jeżeli proces głosuje na nie w głosowaniu, lub zapada decyzja o odrzuceniu transakcji (komunikat ZANIECHAJ bezpośrednio od koordynatora lub pośrednio od innych uczestników), transakcja jest wycofywana.

Obsługa pytania o decyzję

---

Innym problemem wstecznego odtwarzania jest niemożliwość wycofania pewnych operacji, szczególnie jeśli dotyczą one świata zewnętrznego.

Tworzenie punktów kontrolnych również jest dużym obciążeniem dla systemu. W przeciwieństwie do samej operacji odtwarzania, która wykonywana jest w momencie zajścia awarii, tworzenie punktów kontrolnych musi być realizowane nieustannie i to możliwie często. Z tego względu chętnie łączy się metodę odtwarzania wstecznego z rejestrowaniem komunikatów (ang. message logging ). Rejestrowanie może się odbywać po stronie nadawcy (ang. sender-based logging ) lub po stronie odbiorcy (ang. receiver-based logging ). W przypadku wystąpienia załamania procesu można wycofać go do ostatniego punktu kontrolnego i dostarczyć aplikacji wiadomości, które były do niej dostarczone od momentu utworzenia tego punktu kontrolnego. W ten sposób można dokonać odtworzenia pojedynczego procesu bez konieczności wycofywania przetwarzania innych procesów systemu rozproszonego.

Rejestrowanie komunikatów ma dodatkową zaletę w postaci zachowania determinizmu przetwarzania. W systemie rozproszonym kolejność dostarczania komunikatów może być za każdym razem inna, co może powodować, że powtórne wykonanie tego samego programu da inny efekt. Wycofanie procesu i dostarczenie mu tych samych komunikatów pozwala na zachowanie spójności przetwarzania względem innych procesów.

Na rysunku odcięcie stworzone przez ostatnie punkty kontrolne nie jest spójne, a więc nie może być wykorzystane do odtworzenia stanu. Wcześniejsza para punktów kontrolnych daje już spójne odcięcie i tworzy linię odtwarzania.