Przetwarzanie rozproszone

Niezawodność przetwarzania

dr inż. Arkadiusz Danilecki

W oparciu o wykłady prof. J. Brzezińskiego

Plan wykładu

1. Podstawowe pojęcia
2. Implementacje detektorów awarii
3. Algorytm detekcji zakończenia statycznego a awarie

Implementacje detektorów awarii

Implementacje detektorów awarii

Mechanizm pulsu

Implementacje detektorów awarii

Mechanizm odpytywania

Implementacje detektorów awarii

Detektor klasy $P$

Implementacje detektorów awarii

Detektor klasy $P$

Algorytm z użyciem mechanizmu pulsu.

Zakładamy istnienie niezawodnych kanałów komunikacyjnych łączących procesy. Ponadto znany jest maksymalny czas transmisji komunikatu. W porównaniu do tej wartości czasy przetwarzania lokalnego i ewentualne różnice w szybkościach zegarów lokalnych są pomijalnie małe.

Implementacje detektorów awarii

Detektor klasy $P$

				    message $hearbeat$ 

				    local set of channels ~~suspected_i~~ := ~~\emptyset~~ 
				    local set of channels ~~correct_i~~ := ~~\mathcal{P}~~ 
				    local const int ~~period_i^{to}~~ 
				    local const int ~~period_i^{p}~~ 
				    

Implementacje detektorów awarii

Detektor klasy $P$

				    at each ~~period_i^{to}~~ tick at ~~P_i~~ do
				        for all ~~P_k \in \mathcal{P}~~
				            if ~~P_k \not\in correct_i \land P_k \not\in suspected_i~~ then
				               ~~suspected_i \xleftarrow{append} P_k~~
				            end if
				        end for
				        ~~correct_i~~ := ~~\emptyset~~
				    end at each
				    

Implementacje detektorów awarii

Detektor klasy $P$

at each ~~period_i^{p}~~ tick at ~~P_i~~ do
    for all ~~P_k \in \mathcal{P}~~
        send ~~hearbeat~~ to ~~P_k~~
    end for
end at each

when message ~~heartbeat~~ arrives at ~~P_i~~ from ~~P_j~~ do
    ~~correct_i \xleftarrow{append} P_j~~
end when
				    

Implementacje detektorów awarii

Detektor klasy $\Diamond P$

Implementacje detektorów awarii

Detektor klasy $\Diamond P$

Algorytm z użyciem mechanizmu pulsu.

Zakładamy istnienie niezawodnych kanałów komunikacyjnych łączących procesy. Ponadto istnieje maksymalny czas transmisji komunikatu, chociaż nie jest on znany. W porównaniu do tej wartości czasy przetwarzania lokalnego i ewentualne różnice w szybkościach zegarów lokalnych są pomijalnie małe.

Implementacje detektorów awarii

Detektor klasy $\Diamond P$

				    message $hearbeat$ 

				    local set of channels ~~suspected_i~~ := ~~\emptyset~~ 
				    local set of channels ~~correct_i~~ := ~~\mathcal{P}~~ 
				    local int ~~period_i^{to}~~ := ~~t^1~~ 
				    local const ~~period_i^{p}~~
				    

Implementacje detektorów awarii

Detektor klasy $\Diamond P$

at each ~~period_i^{p}~~ tick at ~~P_i~~ do
    for all ~~P_k \in \mathcal{P}~~
        send ~~hearbeat~~ to ~~P_k~~
    end for
end at each

when message ~~heartbeat~~ arrives at ~~P_i~~ from ~~P_j~~ do
    ~~correct_i \xleftarrow{append} P_j~~
end when
				    

Implementacje detektorów awarii

Detektor klasy $\Diamond P$

				    at each ~~period_i^{to}~~ tick at ~~P_i~~ do
				        for all ~~P_k \in \mathcal{P}~~
				            if ~~P_k \not\in correct_i \land P_k \not\in suspected_i~~ then
						~~suspected_i \xleftarrow{append} P_k~~
				            else if ~~P_k \in correct_i \land P_k \in suspected_i~~ then
				                ~~suspected_i~~ := ~~suspected_i \setminus P_k~~
				                ~~period_i^{to}~~ := ~~period_i^{to} + \Delta~~
				            end if
				        end for
				        ~~correct_i~~ := ~~\emptyset~~
				    end at each
				    

Implementacje detektorów awarii

Detektor klasy $\Diamond P$

Dowód poprawności.

Silna kompletność - ostatecznie wszystkie błędne procesy będą podejrzewane.

Ostatecznie silna dokładność - ostatecznie żaden poprawny proces nie będzie podejrzewany.

Implementacje detektorów awarii

Detektor klasy $\Diamond P$

Dowód poprawności.

Postęp

Silna kompletność - ostatecznie wszystkie błędne procesy będą podejrzewane.

Bezpieczeństwo

Ostatecznie silna dokładność - ostatecznie żaden poprawny proces nie będzie podejrzewany.

Implementacje detektorów awarii

Detektor klasy $\Diamond P$

Dowód poprawności.

Postęp

Błędne procesy przestaną wysyłać nowe wiadomości, a wcześniej wysłane wiadomości ostatecznie wszystkie dotrą. Ostatecznie więc przestaną przychodzić nowe wiadomości od tych procesów, i gdy minie czas $period_i^{to}$, zostaną dodane do zbioru $suspected_i$

Implementacje detektorów awarii

Detektor klasy $\Diamond P$

Dowód poprawności.

Bezpieczeństwo

Zakładamy pomijalnie małe różnice w zegarach, oraz że istnieje ograniczenie na maksymalny czas przesyłania wiadomości (częściowo synchroniczny model systemu).

Załóżmy, że pewien poprawny proces $P_j$ został niesłusznie dodany do zbioru ~~suspected_i~~ w procesie $P_i$. Poprawne procesy zawsze wysyłają ~~heartbeat~~, a więc $P_j$ już wysłał albo ostatecznie wyśle ~~heartbeat~~ do $P_i$.

Implementacje detektorów awarii

Detektor klasy $\Diamond P$

Dowód poprawności.

Bezpieczeństwo

Kanały są niezawodne, więc wiadomości ~~hearbeat~~ od ~~P_j~~ w końcu dotrą do ~~P_i~~, co spowoduje usunięcie ~~P_j~~ ze zbioru ~~suspected_i~~ i zwiększenie stałej ~~period_i^{to}~~. Skoro istnieje ograniczenie na czas transmisji, to ostatecznie stała ta zostanie zwiększona tak, że będzie większa od tego czasu i wiadomości ~~heartbeat~~ będą przychodzić do $P_i$ na czas, i ostatecznie ~~P_j~~ przestanie być dodawany do ~~suspected_i~~.

Implementacje detektorów awarii

Detektor klasy $\Diamond P$

Dowód poprawności.

Bezpieczeństwo

Kanały są niezawodne, więc wiadomości ~~heartbeat~~ od ~~P_j~~ w końcu dotrą do ~~P_i~~, co spowoduje usunięcie ~~P_j~~ ze zbioru ~~suspected_i~~ i zwiększenie stałej ~~period_i^{to}~~. Skoro istnieje ograniczenie na czas transmisji, to ostatecznie stała ta zostanie zwiększona tak, że będzie większa od tego czasu i wiadomości ~~heartbeat~~ będą przychodzić do $P_i$ na czas, i ostatecznie ~~P_j~~ przestanie być dodawany do ~~suspected_i~~.

Rozumowanie to można powtórzyć dla każdego niesłusznie podejrzewanego $P_j$, a więc każdy poprawny proces ostatecznie nie będzie już podejrzewany.

Implementacje detektorów awarii

Detektor klasy $\Diamond P$

Czy ten algorytm zapewnia własności dla detektora klasy $P$ w systemie częściowo synchronicznym?

Czy ten algorytm zapewnia własności dla detektora klasy $P$ w systemie synchronicznym?

Algorytm detekcji zakończenia statycznego

Dla przypomnienia: łączymy procesy w wirtualną gwiazdę. Inicjator okresowo sprawdza, czy wszystkie procesy są pasywne i czy wszystkie wysłane przez nie wiadomości zostały już odebrane.

Przeanalizujmy, jak na poprawność algorytmu może wpłynąć obecność awarii.

Algorytm detekcji zakończenia statycznego

				    message $reply$ is a struct $\left\langle \mbox{ bool } contPassive \right\rangle$
				    message $query$, $ack$

				    local int ~~notAck_i~~ := ~~0~~
				    local bool ~~contPassive_i~~ := true
				    local bool ~~AV_i~~ := ~~\emptyset~~
				    local set of processId ~~correct_i~~ := ~~\mathcal{P}~~
				    local set of ~~\left<\mbox{message},\mbox{processId}\right>~~ ~~notAck_i~~ := ~~\emptyset~~
				    

Algorytm detekcji zakończenia statycznego

				    when ~~{P}_{\alpha}~~ wants to start termination detection
				       repeat
				          local bool sTermDetected := true
  				          send ~~query~~ to all ~~P_k~~ in ~~\mathcal{ P }~~ 
  				          for all ~~P_k~~ in ~~\mathcal{ P }~~ do 
  				              wait until a ~~reply~~ arrives from ~~P_k~~ 
  				              ~~sTermDetected~~ := ~~sTermDetected \land reply.contPassive~~
  				          end for
  				       until sTermDetected = true

				       decide "termination detected"
				    end when
				    

Algorytm detekcji zakończenia statycznego

				    when ~~{P}_{\alpha}~~ wants to start termination detection
				       repeat
				          local bool sTermDetected := true
  				          send ~~query~~ to all ~~P_k~~ in ~~\mathcal{ P }~~ 
  				          for all ~~P_k~~ in ~~\mathcal{ P }~~ do 
  				              wait until either a ~~reply~~ arrives from ~~P_k~~ or 
  				                                                    ~~P_k\not\in correct_i~~
  				              if ~~P_k\in correct_i~~ then
  				                  ~~sTermDetected~~ := ~~sTermDetected \land reply.contPassive~~
  				              end if
  				          end for
  				       until sTermDetected = true

				       decide "termination detected"
				    end when
				    

Algorytm detekcji zakończenia statycznego

when process ~~P_i~~ wants to sent a message ~~m~~ to ~~{P}_{j}~~ do
    ~~notAck_i~~ := ~~notAck_i~~ + 1 
    send ~~m~~ to ~~P_j~~
end when

when a message ~~m~~ arrives at process ~~P_i~~ from ~~{P}_{j}~~ do
    send ~~ack~~ to ~~P_j~~
    deliver ~~m~~ 
end when

when a message ~~ack~~ arrives at process ~~P_i~~ from ~~{P}_{j}~~ do
    ~~notAck_i~~ := ~~notAck_i~~ - 1 
end when
				    

Algorytm detekcji zakończenia statycznego

when process ~~P_i~~ wants to sent a message ~~m~~ to ~~{P}_{j}~~ do
    ~~notAck_i \xleftarrow{append}\left\{ m, P_j\right\}~~
    send ~~m~~ to ~~P_j~~
end when

when a message ~~m~~ arrives at process ~~P_i~~ from ~~{P}_{j}~~ do
    send ~~ack~~ to ~~P_j~~
    deliver ~~m~~ 
end when

when a message ~~ack~~ arrives at process ~~P_i~~ from ~~{P}_{j}~~ do
    ~~notAck_i~~ := ~~notAck_i\setminus\left\{m,P_j\right\}~~ - 1 
end when
				    

Algorytm detekcji zakończenia statycznego

when a message ~~query~~ arrives at process ~~P_i~~ from ~~{P}_{j}~~ do
    wait until ~~passive_i~~ and ~~notAck_i = 0~~ and ~~\neg activate( AV_i )~~
    ~~reply.contPassive~~ := ~~contPassive_i~~
    ~~contPassive_i~~ := true
    send ~~reply~~ to ~~P_j~~
end when

when a process ~~P_i~~ activates do
    ~~contPassive_i~~ := false
end when

				    

Algorytm detekcji zakończenia statycznego

when a message ~~query~~ arrives at process ~~P_i~~ from ~~{P}_{j}~~ do
    wait until ~~passive_i~~ and ~~notAck_i = \emptyset~~ and ~~\neg activate( AV_i )~~
    ~~reply.contPassive~~ := ~~contPassive_i~~
    ~~contPassive_i~~ := true
    send ~~reply~~ to ~~P_j~~
end when

when a process ~~P_i~~ activates do
    ~~contPassive_i~~ := false
end when
				    

Algorytm detekcji zakończenia statycznego

when a detector ~~FD_i~~ suspects ~~P_j~~ do
    ~~correct_i~~ := ~~correct_i \setminus P_j~~
    for all ~~x = \left\{ *, P_q \right\} :: x \in notAck_i :: P_q = P_j ~~ do
        ~~notAck_i~~ := ~~notAck_i \setminus x~~
    end for
end when
				    

Problem wyboru lidera

Ostateczna dokładność (ang. eventual accuracy) - ostatecznie wszystkie poprawne procesy uznają za lidera jakiś poprawny proces.

Ostateczna zgodność (ang. eventual agreement) - ostatecznie jeżeli jakiś proces jest uznany za lidera przez pewien poprawny proces, to nie istnieje inny proces uznawany za lidera przez jakikolwiek inny poprawny proces.

Problem wyboru lidera

Założenia

• Doskonały detektor awarii

Liderem wybrany będzie proces poprawny o najwyższym identyfikatorze.

Problem wyboru lidera

				    local processId ~~leader_i~~ := nil
				    local set of processId ~~correct_i~~ := ~~\mathcal{P}~~
				    

Problem wyboru lidera

when a detector ~~FD_i~~ suspects ~~P_j~~ do
    ~~correct_i~~ := ~~correct_i \setminus P_j~~
    if ~~leader_i = P_j~~ then ~~leader_i~~ := nil 
end when

when ~~leader_i~~ = nil do
    ~~leader_i~~ := ~~P_q\in correct_i~~ such that ~~\forall P_k\in correct_i: q\gt k~~
end when
				    

Problem wyboru lidera

Założenia

• Dostępność pamięci stałej (logu) zdolnej przetrwać awarie

Nb. "pamięć stała" to nie musi być dysk - pamięć trwała NVRAM, pamięć innego procesu...

• Doskonały detektor awarii
• Poprawny proces ulega skończonej liczbie awarii i po każdej zostaje odtworzony

Problem wyboru lidera

Zarys algorytmu

Liderem wybrany będzie proces poprawny o najwyższym identyfikatorze spośród tych o najmniejszej liczbie awarii

Problem wyboru lidera

				    message $heartbeat$ is a struct $\left\langle \mbox{ int } epochNo \right\rangle$
				    message $trusted$ is a struct $\left\langle \mbox{ processId } pId, \mbox{int} epochNo \right\rangle$

				    local processId ~~leader_i~~ := ~~P_i~~
				    local set of ~~trusted~~ messages ~~candidateSet_i~~ := ~~\forall P_k\in\mathcal{P}: \left\{P_k,0\right\}~~
				    local int ~~epochNo_i~~ := 0
				    

Problem wyboru lidera

when a process ~~P_i~~ recovers from failure do
    retrieve ~~epochNo_i~~ from log
    ~~epochNo_i~~ := ~~epochNo_i~~ + 1
    store ~~epochNo_i~~ to log
    sent ~~heartbeat~~ to ~~\mathcal{P}~~
end when

when a message ~~heartbeat~~ arrives at process ~~P_i~~ from ~~P_j~~ do
    ~~candidateSet_i \xleftarrow{append} \left\{ P_j, heartbeat.epoch\right\}~~
end when
				    

Problem wyboru lidera

when a detector ~~FD_i~~ suspects ~~P_j~~ do
    ~~candidateSet_i~~ := ~~candidateSet_i \setminus \left\{ P_j, * \right\}~~
    if ~~leader_i~~ = ~~P_j~~ then
       ~~leader_i, \mbox{local int } epoch~~ := nil, 0
       for all ~~\left\{ P_q, epoch_q \right\} \in candidateSet_i~~ do
           if ~~leader_i~~ = nil then 
              ~~leader_i, epoch~~ := ~~P_q, epoch_q~~
           else
              if ~~epoch_q \lt epoch~~ then 
                 ~~leader_i, epoch~~ := ~~P_q, epoch_q~~
              else if ~~epoch_q~~ = ~~epoch~~ and ~~P_q \gt leader_i~~ then
                 ~~leader_i, epoch~~ := ~~P_q, epoch_q~~
              end if
           end if
       end for
end when
				    

Problem wyboru lidera

Zamiast używania detektora, można wprost co pewien czas wysyłać wiadomości ~~heartbeat~~ i sprawdzać, czy lider ostatnio wysłał nam ~~heartbeat~~, albo periodycznie inicjować procedurę wyboru lidera.

Okresy reelekcji można dynamicznie dostosowywać do czasów komunikacji.

Przy okazji omawiania konsensusu zobaczymy inny algorytm wyboru lidera.

Po co nam lider?

Wprawdzie rozwiązania w pelni rozproszone są bardziej eleganckie, odporniejsze na błędy, ale... Bywają mniej wydajne, a już zdecydowanie są cięższe do zrozumienia (porównaj Paxos vs Raft!).

Replikacja

• Odporność na awarie
• Zwiększona dostępność (np. w wypadku partycji sieci)
• Zwiększona wydajność (np. interakcje z najbliższą repliką)

Replikacja

Przykład: serwer prowadzący interakcję z klientami plus jego kopie zapasowe.

Załóżmy deterministyczne operacje i/lub możliwość transferu stanu. Repliki możemy wtedy traktować jako maszyny stanowe (state machines), w których dla danego stanu początkowego, powtórzenie operacji w dokładnie tym samym porządku na każdej replice zakończy się identycznymi zmianami stanu.

Replikacja

Replikacja

Replikacja

W przypadku interakcji z klientem, kiedy można zwrócić odpowiedź do klienta?

Co w przypadku awarii lidera?

Tylko część replik mogła otrzymać ostatnią operację...

Replikacja

Zgodne rozgłaszanie z całkowitym uporządkowaniem wiadomości (TOcast)

W skrócie:

• jeżeli jakiś poprawny proces dostarczył wiadomość ~~m~~, to wszystkie poprawne procesy dostarczą ~~m~~
• jeżeli proces dostarczył wiadomości ~~m^1~~ przed ~~m^2~~, to wszystkie poprawne procesy dostarczą ~~m^1~~ przed ~~m^2~~

Replikacja

Replikacja

Zgodne rozgłaszanie z całkowitym uporządkowaniem wiadomości może być zastąpione mechanizmem konsensusu. W praktyce pojawia się jednak kilka problemów...

Co w przypadku modelu z powtarzalnymi awariami (crash recovery)?

Co jeżeli skład grupy replik się zmieni?

Co w przypadku podziału (partycji) sieci?

Replikacja

Inne podejście: Algorytm z kworum.

Przy zapisie odwołujemy się do W replik, zapisujemy razem z wartością znacznik wersji.

Przy odczycie odwołujemy się do R replik, wybieramy najnowszą wartość.

Dobieramy wartości R oraz W tak, by zawsze istniała część wspólna kworum odczytów i zapisów.

Widzimy jakieś problemy?

Więcej o replikacji na Systemach Wysokiej Niezawodności

Skład grupy

Do tej pory zakładaliśmy, że zbiór ~~\mathcal{P}~~ jest niezmienny, ale w praktyce mogą pojawiać się nowe procesy, inne mogą odchodzić (nie tylko w efekcie awarii). W literaturze mówi się wtedy o zmianie konfiguracji i/lub o problemie zapewnienia spójnego widoku grupy (i "instalowaniu widoku" grupy).

Problem: co jeżeli kilka procesów jednocześnie chce się dostać do grupy lub z niej odejść?

Problem: Jak zapewnić, by komunikaty docierały do wszystkich procesów w danym obrazie grupy? (Komunikacja zsynchronizowana z obrazami grup, view synchronous communication).

Skład grupy

Detektory błędów (nawet doskonałe!) nie rozwiązują problemu, bo ich wiedza jest rozproszona, a procesy widzą awarie w różnej kolejności.

Chcemy więc, by poglądy na skład grupy ("widoki") procesów zmieniały się w sposób spójny.

Widok (ang. view) - obraz składu grupy. Każdy widok posiada unikalny identyfikator. Identyfikatory widoków można jednoznacznie uporządkować.

Proces instaluje widok (ang. installs view) - gdy uznaje widok o danym identyfikatorze za aktualny.

Skład grupy

Własności

Monotoniczność (ang. monotonicity) - Jeżeli proces ~~P_i~~ instaluje obraz ~~V(j,\mathcal{M})~~ po obrazie ~~V(k,\mathcal{N})~~ to ~~j\gt k~~ oraz ~~\mathcal{M}\subset\mathcal{N}~~ (drugi warunek często się pomija).

Zgodność (ang. agreement) - Jeżeli procesy ~~P_i~~ oraz ~~P_j~~ instalują obrazy ~~V(j,\mathcal{M})~~ oraz ~~V(k,\mathcal{N})~~ gdzie ~~j = k~~, to ~~\mathcal{M} = \mathcal{N}~~.

Kompletność (ang. completeness) - Jeżeli procesy ~~P_i~~ ulega awarii (opuszcza grupę) to ostatecznie istnieje takie ~~k~~, że każdy poprawny proces ostatecznie instaluje widok ~~V(k,\mathcal{M})~~ taki, że ~~P_i\not\in\mathcal{M}~~

Dokładność (ang. accuracy) - Jeżeli procesy ~~P_i~~ instaluje widok ~~V(k,\mathcal{M})~~ taki, że ~~P_j\not\in\mathcal{M}~~, to ~~P_j~~ uległ awarii (lub opuścił grupę).

Skład grupy

				    message $install$ is a struct $\left\langle \mbox{ set of processId } proc, \mbox{ int } id \right\rangle$
				    message $ack$ is a struct $\left\langle \mbox{ set of processId } proc, \mbox{ int } id \right\rangle$
				    message $done$ is a struct $\left\langle \mbox{ set of processId } proc, \mbox{ int } id \right\rangle$

				    local ~~view_i~~ is a struct ~~$\left\langle \mbox{ set of processId} proc, \mbox{ int } id \right\rangle~~ := ~~\langle \mathcal{P}, 0\rangle~~
				    local bool ~~block_i~~ := false
				    

Skład grupy

when a leader ~~P_i~~ receives ~~remove\langle P_j \rangle~~ do
   wait until ~~\neg block~~
   if ~~P_j\in view_i.proc~~ then
      ~~block_i~~ := true
      broadcast ~~install\langle proc := view_i \setminus P_j, id := view_i.id + \mbox{1}\rangle~~ to ~~\mathcal{P}~~
      receive ~~ack\langle view = view_i \rangle~~ from ~~\mathcal{P}~~
      broadcast ~~done\langle view = view_i \rangle~~ to ~~\mathcal{P}~~
      ~~block_i~~ := false
   end if
end when
				    

Skład grupy

when a message ~~install~~ arrives at process ~~P_i~~ from ~~P_j~~ do
    ~~block_i~~ := true
    ~~view_i~~ := ~~install.view~~
    sent ~~ack\langle view \rangle~~ to ~~P_j~~
end when

when a message ~~done~~ arrives at process ~~P_i~~ from ~~P_j~~ do
    ~~block_i~~ := false
end when

when a detector ~~FD_i~~ suspects ~~P_j~~ do
   sent ~~remove\langle P_j \rangle~~ to ~~leader_i~~
end when
				    

Skład grupy

Co jeżeli lider ulegnie awarii?

Wybieramy jako nowego lidera ten proces, który ma największy numer widoku.

Co jeżeli ulegnie awarii podczas zmiany widoku?

Podczas elekcji lidera blokujemy przetwarzanie. Lider przed rozpoczęciem pracy sprawdza, czy istnieją procesy, które uległy awarii, a są w jego widoku; usuwa je i instaluje nowy widok.

Jak uzupełnić algorytm o dodawanie nowych procesów?

Przy dodawaniu banalnie prosto - proces dodawany musi tylko powtarzać prośbę o dodanie, gdyby lider uległ awarii. Przy elekcji - sprawdzamy, czy trzeba rozszerzyć widok.

Skład grupy

Co z odtwarzaniem stanu?

Proces po odtworzeniu zyskuje nową tożsamość (traktujemy go tak, jakby to był nowy proces proszący o dołączenie do grupy).

Czy dałoby się pozbyć lidera?

Zmiany widoku bez lidera najprościej zaimplementować z użyciem mechanizmu konsensusu (jednolitego), więc przykładowy algorytm pokażemy na następnym wykładzie.

Koniec wykładu!

Kolory

Placeholder

Zwykły Thistle zwykły Orange Tomato blue lightsalmon zwykły moccasin zwykły white zwykły PowderBlue zwykły MintCrem zwykły chartreuse zwykły Palegreen mistyrose zwykły silver zwykły azure zwykły