dr inż. Arkadiusz Danilecki
Leslie Lamport w 1989 zaproponował algorytm Paxos, który doczekał się kilku implementacji (używany jest przez google, microsoft, amazon) ... oraz artykułów próbujących wyjaśnić laikom, jak Paxos działa.
Z uwagi na skomplikowanie Paxos, w 2013 Ongaro i Ousterhout zaproponowali prostszy algorytm (Raft), którego jednym z celów było to, by był bardziej zrozumiały. Paxos zostanie omówiony na przedmiocie Systemy Wysokiej Niezawodności.
Ważne - zarówno Paxos, jak i Raft zapewniają własność bezpieczeństwa, ale w ogólności nie zapewniają postępu!
Założenia
Awarie są rzadkie (i krótkotrwałe)
System jest częściowo synchroniczny - zegary są mniej-więcej zsynchronizowane, czasy przesyłania wiadomości są znane i można odpowiednio dobrać okresy elekcji, pulsu itd wspomniane dalej w algorytmie.
Kanały są niezawodne.
Skład grupy się nie zmienia i jest znany wszystkim procesom oraz wszystkim klientom. Używany model to crash-recovery.
Przyjmujemy, że procesy można modelować jako maszyny stanów.
Oryginalny algorytm używa RPC niby "bo są łatwiejsze". Pseudokod dalej został przerobiony na używanie wiadomości.
Raft nie używa detektorów błędów, ale my pokażemy jak zapisać algorytm z użyciem tej abstrakcji.
Wytłumaczymy Rafta po kawałku, by było łatwiej go zrozumieć.
Raft pracuje w dwóch trybach - normalnym oraz elekcji.
W normalnym trybie istnieje jeden lider, pozostałe procesy są wykonawcami (ang. follower). Tylko lider wykonuje zlecenia klienta.
Do trybu elekcji przechodzimy, gdy podejrzewamy awarię lidera. W trybie elekcji procesy mogą przyjąć rolę kandydata na lidera. Po wyborze nowego lidera wracamy do normalnego trybu.
Szkic stanów procesów
Klient
Klienci zawsze komunikują się z liderem. Procesy nie będące liderem przekierowują żądania do lidera lub powiadamiają klienta, kto jest liderem. Klient powtarza żądania, aż otrzyma odpowiedź i ignoruje kolejne odpowiedzi. W dalszym opisie zignorujemy żądania nie zmieniające stanu.
Lider odpowiada klientowi dopiero, gdy zatwierdzi i wykona jego żądanie - co będzie wymagało wymiany wiadomości z wykonawcami (zobaczymy to później).
Klient
Chcemy zapewnić semantykę exactly-once.
Żądania klientów są rozróżnialne (np. mają identyfikator). Lider nie aplikuje ponownie starych żądań. Jeżeli żądanie z danym identyfikatorem już istnieje w logu, i nie jest zatwierdzone, lider nic nie robi. Jeżeli jest już zatwierdzone, odpowiada natychmiast.
Odpowiedzi mogą być przechowywane w pamięci podręcznej i na stare żądanie lider może odesłać odpowiedź z pamięci podręcznej.
Każdy proces utrzymuje log zawierający sekwencję poleceń, oraz wskaźnik na ostatnią zatwierdzoną pozycję.
Po otrzymaniu żądania, lider dopisuje je do logu w pamięci stałej. (actually tymczasowo może być w pamięci ulotnej)
Lider regularnie wywołuje AppendEntries, czyli wysyła wykonawcom listę poleceń do zatwierdzenia. Lider na razie nie wykonuje trzymanych w logu, otrzymanych od klienta poleceń (tj. nie zmienia stanu) i niczego na razie jeszcze zatwierdza.
Każdy proces posiada numer kadencji term, zwiększany przy każdej elekcji.
Z każdym wpisem w logu zapamiętany jest numer kadencji term w którym dokonano wpisu, oraz index.
Każda wiadomość wysyłana przez proces zawiera jego aktualny term.
Podsumowując - kiedy odpowiadamy klientowi?
Jeżeli nie otrzymamy AppendEntries (czyli de facto pulsu) od lidera, zwiększamy term i proponujemy siebie jako lidera, prosząc innych o głosy. Wygram, gdy otrzymam zgodę od większości procesów.
Jeżeli nie uda się zdobyć większości w ciągu jakiegoś czasu, odczekuję chwilę i próbuję jeszcze raz (chyba że ktoś inny w międzyczasie został liderem.
Chcemy wybrać kogoś, kto będzie miał:
Największy term
Każda wiadomość (AppendEntries, RequestVote, odpowiedzi..) zawiera term.
Po otrzymaniu wiadomości z term większym od naszego:
Najbardziej aktualny log
Po otrzymaniu prośby o głos z hisTerm, hisLogTerm,hisLogIndex: zgodzę się, jeżeli:
Najwięcej szczęścia
Po otrzymaniu prośby o głos zgadzam się tylko jeżeli wcześniej jeszcze na nikogo nie zagłosowałem.
Restart głosowania, gdy nikt nie zdobędzie większości - losowy timeout i próbuję jeszcze raz.
Odpowiedź zawiera mój term i zgodę/niezgodę.
Najwięcej szczęścia
Po otrzymaniu prośby o głos zgadzam się tylko jeżeli wcześniej jeszcze na nikogo nie zagłosowałem.
A co jeżeli zgodziłem się oddać głos na A po czym uległem awarii i po wznowieniu poprosi mnie o głos proces B?
Przed wysłaniem głosu zapisuję go w trwałej pamięci.
Gdy otrzymamy AppendEntries od procesu A z większym hisTerm, ustawiamy term na hisTerm, uznajemy A za lidera.
Gdy otrzymamy AppendEntries od procesu A z mniejszym hisTerm, powiadamiamy A że obecny term jest już większy, a wywołanie AppendEntries się nie powiedzie. Proces A widząc, że my mieliśmy większy term zrezygnuje z funkcji lidera.
Pamiętacie ten slajd?
Podsumowując - kiedy odpowiadamy klientowi?
Jest jeszcze jeden detal, ale powiemy o nim TERAZ
Przenalizujmy sytuację na następnym slajdzie. Liderem jest proces A. Czy może wysłać klientowi odpowiedź na żądanie trzecie i czy to żądanie inne repliki mogą spokojnie zaaplikować?
Podsumowując - kiedy odpowiadamy klientowi?
Pytanie za sto punktów (czyście nie spali na wykładzie?) - co z własnością postępu?
NIE MA
... ale w praktyce działa.
Bieżący lider zrezygnuje z funkcji gdy tylko się dowie o nowej elekcji z większym term, ale to wcale nie znaczy, że nowym liderem zostanie Bonifacy.
Co ze spójnością logów po elekcji? Obecny lider mógł zacząć rozsyłać już jakieś operacje do wykonawców, może już jakieś zatwierdził...
Co ze spójnością logów po elekcji? Obecny lider mógł zacząć rozsyłać już jakieś operacje do wykonawców, może już jakieś zatwierdził...
Pamiętajmy, że procesy nie zagłosują na kogoś z mniej aktualnym logiem, a przy decyzji który log jest bardziej aktualny ważny jest nie term kandydata, ale logTerm ostatniego wpisu w logu.
Pamiętajmy, że procesy nie zagłosują na kogoś z mniej aktualnym logiem, a przy decyzji który log jest bardziej aktualny ważny jest nie term kandydata, ale logTerm ostatniego wpisu w logu.
Czy Bonifacy mógł mieć wpis w logu od poprzedniego lidera, który umarł przed wyborem Archibalda, którego nie miał nikt inny? Czy ten wpis mógł być zatwierdzony?
A co jeżeli Bonifacy był liderem, został odcięty od pozostałych, i pozostała trójka wybierze nowego lidera? Będziemy mieli dwóch liderów! Czy to wpłynie na spójność logów? Czy klienci będą otrzymywali różne odpowiedzi?
Czy Bonifacy będzie mógł zatwierdzić jakiekolwiek żądanie od klienta? Nie , bo nie zdobędzie potrzebnej większości.
Czas na pytania sprawdzające!
Czy jest możliwe, by w systemie z czterema procesami miały one takie logi?
Który log jest najświeższy, abstrahując od tego, czy takie logi są możliwe?
Jeżeli procesy ulegały awariom i były wznawiane, w jakiej kolejności mogły być wybierane na lidera?
Czy jest możliwe, by w systemie z czterema procesami miały one takie logi?
Które wartości mogą być już zatwierdzone?
W jakiej kolejności procesy były wybierane na liderów w przeszłości?
Które z procesów mogą zostać wybrane w głosowaniu, gdyby zaczęło się przy takim stanie logów?
Czy zmieni coś w odpowiedzi, jeżeli D będzie miał term największy ze wszystkich innych procesów?
Po awarii lidera (lub liderów) logi procesów mogą różnić się zawartością.
Logi są uspójniane w leniwy sposób przy wywoływaniu AppendEntries; lider optymistycznie zakłada, że logi są spójne, a gdy wykonawca powiadomi go o niespójności, lider wysyła temu wykonawcy coraz większe "łatki".
Log lidera jest zawsze decydujący. Wpisy w innych logach, których nie ma w logu lidera, są porzucane.
Oryginalnie lider regularnie wywołuje "AppendEntries", co jest traktowane jako heartbeat; używane są też budziki ("tajmery") do ograniczania czasu elekcji, wykrywania awarii oraz minimalizowania prawdopodobieństwa konfliktów podczas elekcji.
Używane wiadomości
message ~~addEntries~~ is a struct of
~~\langle \mbox{int } term, \mbox{processId } leader, \mbox{int } prevLogIdx, \mbox{int } prevLogTerm,~~
~~\mbox{set of requests } entries, \mbox{int } leaderCommitIdx \rangle~~
message ~~result~~ is a struct of
~~\langle\mbox{bool } result, \mbox{int } term \rangle~~
message ~~requestVotes~~ is a struct of
~~\langle~~int ~~term, \mbox{int } lastLogIdx, \mbox{int } lastLogTerm \rangle~~
message ~~vote~~ is a struct of ~~\langle~~int ~~value \rangle~~
Zmienne w pamięci trwałej
persistent state $state_i$ := $nil$
persistent map of int and struct of $\langle \mbox{request}, \mbox{int } term\rangle$ $log_i$ := $nil$
persistent int $lastLogIdx_i$ := 0
persistent int $lastLogTerm_i$ := 0
persistent int $commitIdx_i$ := 0
persistent set of response $cache_i$ := $\emptyset$
Pozostałe zmienne
local int $term_i$ := 1
local enum of $\left\{ \mbox{follower},\mbox{candidate},\mbox{leader}\right\}$ $mode_i$ := follower
local processId $leader_i$ := $nil$
local processId $votedFor_i$ := $nil$
local int $timer_i$ := RANDOM
local set of processId $correct_i$ := $\emptyset$
local map of int and set of processId $committed_i$ := $\emptyset$
local set of processId $votesGranted_i$ := $\emptyset$
local set of processId $votesNotGranted_i$ := $\emptyset$
local array of int $nextIdx\left[1 \ldots n\right]$ := $\{ 0, \ldots 0\}$
local array of int $matchIdx\left[1 \ldots n\right]$ := $\{ 0, \ldots 0\}$
Obsługa żądań klienta
when a message ~~request~~ arrives from client ~~C_i~~ at process ~~P_i~~ do
if ~~leader_i \neq P_i~~ then
redirect ~~request~~ to ~~leader_i~~
else
if ~~request \in cache_i~~ then
send ~~cache_i\left[request\right]~~ to ~~C_i~~
else if ~~request \not\in requests_i~~ then
~~requests_i \xleftarrow{append} request~~
~~log_i\left[ lastLogIdx \right]~~ := ~~\langle request, term_i \rangle~~
~~committed_i\left[ lastLogIdx_i \right]~~ := ~~\emptyset~~
~~lastLogIdx_i~~ := ~~lastLogIdx_i~~ + 1
end if
end if
end when
Obsługa żądań klienta
when ~~mode_i~~ = leader at each period ~~t_i~~ at process ~~P_i~~ do
for each process ~~P_j \in \mathcal{P}~~ do
if ~~matchIdx_i\left[ P_j\right]~~ = ~~lastLogIdx_i~~ then
continue
end if
for each ~~entry~~ in ~~log_i\left[ nextIdx_i\left[ P_j\right] \ldots lastLogIdx_i\right]~~ do
~~entries \leftarrow entry~~
end for
~~prevLogIdx~~ := ~~nextIdx_i\left[ P_j \right]~~ - 1
~~prevLogTerm~~ := ~~log_i\left[ prevLogIdx \right].term~~
send ~~addEntries\langle term_i, prevLogIdx, prevLogTerm, entries, commitIdx_i\rangle~~ to ~~P_j~~
end for
end when
Obsługa żądań klienta
when ~~mode_i~~ = leader and a message ~~result~~ arrives at process ~~P_i~~ from ~~P_j~~ do
if ~~result.result~~ = true then
for ~~N~~ from ~~matchIdx_i\left[ P_j\right]+1~~ to ~~result.last~~ do
~~committed_i\left[N\right] \xleftarrow{append} P_j~~
if ~~\left|committed_i\left[ N \right]\right|\gt n/2~~ and
~~log_i\left[ N\right].term~~ = ~~term_i~~ then
for ~~k~~ from ~~commitIdx_i~~+1 to ~~N~~ do
apply ~~log_i[ k ].request~~ to ~~state_i~~
~~commitIdx_i~~ := ~~commitIdx_i~~ + 1
~~cache_i \xleftarrow{append} response~~
send ~~response~~ to ~~C_k~~ which originated the ~~request~~
end for
end if
end for
Obsługa żądań klienta
if ~~matchIdx_i\left[ P_j\right] \lt result.last~~ then
~~matchIdx_i\left[ P_j \right]~~ := ~~result.last~~
end if
if ~~nextIdx_i\left[ P_j\right] \lt result.last + 1~~ then
~~nextIdx_i\left[ P_j \right]~~ := ~~nextIdx_i\left[ P_j \right]~~ +1
end if
else if ~~result.term \leq term_i~~
~~nextIdx_i\left[ P_j \right]~~ := MAX(~~1, nextIdx_i\left[ P_j \right]~~ - 1)
else
~~mode_i~~ := follower
end if
if ~~term_i \lt result.term~~ then
~~term_i~~ := ~~result.term~~
end if
end when
Procedura AppendEntries
when a message ~~addEntries~~ arrives at ~~{P}_{i}~~ from ~~{P}_{j}~~ do
if ~~mode_i~~ = candidate or
(~~mode_i~~ = leader and ~~term_i\lt addEntries.term~~) then
~~mode_i~~ := follower
end if
if ~~addEntries.term\lt term_i~~ or
send ~~result\langle term_i, false, lastLogIdx_i\rangle~~
else if ~~addEntries.prevLogIdx \gt lastLogIdx_i~~ or
(~~addEntries.prevLogIdx \leq lastLogIdx_i~~ and
~~addEntries.prevLogTerm \neq log_i[addEntries.prevLogIdx].term~~ then
send ~~result\langle term_i, false, lastLogIdx_i\rangle~~
else
else
for each ~~entry~~ in ~~addEntries.entries~~ do
~~log_i\left[ entry.index \right]~~ := ~~entry~~
~~last~~ := ~~entry.index~~
end for
for ~~k~~ from ~~last~~ to ~~lastLogIdx_i~~ do
~~log_i\left[ k \right]~~ := $nil$
end for
~~lastLogIdx_i~~ := ~~last~~
if ~~addEntries.commitIdx \gt commitIdx_i~~ then
for ~~k~~ from ~~commitIdx_i~~+1 to ~~addEntries.commitIdx~~ do
apply ~~log_i[ k ].request~~ to ~~state_i~~
~~commitIdx_i~~ := ~~commitIdx_i~~ + 1
end for
// to chyba niepotrzebne - ~~lastLogIdx_i~~ musi być}
//~~commitIdx_i~~ := MIN(~~addEntries.commitIdx, lastLogIdx_i~~)
end if
send ~~result\langle term_i, true, lastLogIdx_i\rangle~~
end if
end when
W oryginale każdy proces oczekuje na wywołania procedury AppendEntries, traktując ją jako heartbeat, z innymi czasami dla każdego procesu.
when $FD_i$ starts suspecting $P_j$ do
$correct_i$ := $correct_i \setminus P_j$
if $leader_i$ = $P_j$ then
$leader_i$ := $nil$
end if
end when
when $FD_i$ stops suspecting $P_j$ do
$correct_i \xleftarrow{append} P_j$
if $leader_i$ = $P_j$ then
$leader_i$ := $nil$
end if
end when
Elekcja
when ~~leader_i~~ = ~~nil~~ and ~~mode_i~~ = follower at process ~~{P}_{i}~~ do
~~mode_i~~ := candidate
~~term_i~~ := ~~term_i~~ + 1
~~votedFor_i~~ := ~~P_i~~
~~votedNotGranted_i~~ := ~~\emptyset~~
broadcast ~~requestVotes\langle term_i, lastLogIdx_i, lastLogTerm_i\rangle~~ to ~~\mathcal{P}~~
end when
Elekcja
when ~~mode_i = \mbox{candidate }~~ and
~~correct_i\subseteq votesGranted_i\cup votesNotGranted_i~~ at process ~~P_i~~ do
if ~~\left|votesGranted_i\right|\gt n/2~~ then
~~leader_i~~ := ~~P_i~~
~~mode_i~~ := leader
for each ~~P_k~~ in ~~\mathcal{P}~~ do
~~nextIdx_k\left[ P_k \right]~~ := ~~lastLogIdx_i~~ + 1
~~matchIdx\left[ P_k \right]~~ := 0
end for
else
~~mode_i~~ := nil
wait random time
~~mode_i~~ := follower
end if
end when
Elekcja
when a message ~~requestVote~~ arrives at ~~{P}_{i}~~ from ~~{P}_{j}~~ do
if ~~requestVote.term \geq term_i~~ then
if ~~mode_i\neq \mbox{leader }~~ and ~~votedFor_i = nil~~ then
if ~~requestVote.lastLogTerm\gt lastLogTerm_i~~ or
(~~requestVote.lastLogTerm = lastLogTerm_i~~ and
~~requestVote.lastLogIdx \geq lastLogIdx_i~~) then
~~term_i~~ := ~~requestVote.term~~
~~votedFor_i~~ := ~~requestVote.candidateId~~
send ~~vote\langle term: term_i, voteGranted: true\rangle~~ to ~~P_j~~
end if
end if
end if
if ~~votedFor_i \neq P_j~~ then
send ~~vote\langle term: term_i, voteGranted: false\rangle~~ to ~~P_j~~
end if
end when
Elekcja
when ~~mode_i~~ = candidate and a message ~~vote~~ arrives at ~~{P}_{i}~~ from ~~{P}_{j}~~ do
if ~~vote.term \gt term_i~~ then
~~mode_i~~ = follower
else if ~~vote.granted~~ then
~~votesGranted_i \xleftarrow{append} P_j~~
else
~~votesNotGranted_i \xleftarrow{append} P_j~~
end if
end when
Zmiana konfiguracji mogłaby doprowadzić do sytuacji, w której różne procesy widzą różne konfiguracje, co mogłoby doprowadzić do dwóch różnych większości.
Rozwiązanie: dwufazowy algorytm zmiany konfiguracji
Lider dostaje polecenie zmiany konfiguracji z $C_{old}$ na $C_{new}$. Polecenie to jest zapisywane w logu i wysyłane do wszystkich.
Do czasu zatwierdzenia tej operacji, wszystkie operacje wymagają zatwierdzenia przez większość zarówno z $C_{old}$ oraz $C_{new}$ (ang. joint consensus).
Po zatwierdzeniu operacji zmiany konfiguracji przez wszystkie procesy, lider dodaje $C_{new}$ do logu i wysyła tę operację do wszystkich procesów.
Modyfikacja - nowa rola "learner" dla nowych węzłów w pierwszej fazie (i ewentualnie starych węzłów w starej fazie).
Powiedzmy, że większość węzłów ze starej konfiguracji uległa awarii i dodajemy nowe węzły na miejsce tych starych. Czy ten algorytm rekonfiguracji poradzi sobie z tą sytuacją?
Powiedzmy, że uległ awarii tylko lider starej konfiguracji. Czy ten algorytm rekonfiguracji poradzi sobie z tą sytuacją?
Czy naprawdę jest taki prosty?
Czasami rozwiązanie typu fail-over + zewnętrzna usługa konsensus może być lepsze.
| Raft | Paxos | |
|---|---|---|
| RethinkDB, CockroachDB, mongoDB | Cassandra, Amazon DynamoDB | |
| etcd (używany np. w Kubernetes) | Google Chubby, Spanner | |
| Consul (hashicorp), TiDB | Microsoft Azure CosmosDB | |
| Vault, RabbitMQ, YugabyteDB | Azure Storage | |
| NATS JetStream | Neo4j | |
| Camunda, Ceph | ScyllaDB | |
| Apache Druid | Apache Zookeeper | |
| Raft-rs (Rust), PandaRaft, JRaft, Rafty, BRaft | LibPaxos |
... i przechodzimy do wykładu powtórkowego. Przerwa?