Paxos: How Five Machines Agree on One Truth Without a Boss

Problem, którego rozwiązuje konsensus

Każdy system, który replikuje dane na wielu maszynach w celu zapewnienia odporności na awarie, staje przed tym samym pytaniem: kiedy maszyny się nie zgadzają – ponieważ jedna uległa awarii podczas zapisu lub sieć rozłączyła je od siebie – która wersja jest prawidłowa? Konsensus to gwarancja, że klastr węzłów zgadza się na pojedynczą sekwencję wartości (zwykle dziennik poleceń) nawet wtedy, gdy niektóre węzły ulegną awarii lub wiadomości będą opóźnione, o ile większość węzłów będzie aktywna i potrafi ze sobą komunikować.

Raft, opublikowany przez Diego Ongaro i Johna Ousterhousta w 2014 roku, został zaprojektowany wyraźnie jako zrozumiała alternatywa dla Paxos, która jest dowodowo poprawna, ale słynie z bycia trudną do zrozumienia. Raft rozkłada konsensus na trzy oddzielne podproblemy – wybór lidera, replikacja dziennika i bezpieczeństwo – każdy z nich może być rozumiany w dużej mierze niezależnie.

Każą węzeł jest zawsze w dokładnie jednym z trzech stanów

Kierownik → pasywny; odpowiada na żądania RPC od lidera lub kandydata; stan domyślny Kandydat → aktywnie kampaniuje o głosy po upływie czasu wyboru Lider → jedyny węzeł, który obecnie akceptuje zapisy klientów i replikuje je Kierownicy, którzy nic nie słyszą przed upływem czasu wyboru, stają się Kandydatami. Normalnie tylko jeden Kandydat wygrywa i staje się Liderem dla tego okresu. Czas jest podzielony na okresy, monotonicznie rosnące liczby całkowite, które działają jako zegar logiczny. Maksymalnie jeden lider może zostać wybrany na każdy okres – to egzekwuje się po prostu dlatego, że węzeł rzuca maksymalnie jeden głos w każdym okresie, zgodnie z zasadą „pierwszy cofnął”, więc kandydat musi uzyskać większość głosów wśród tej samej grupy wyborców, aby wygrać, a dwóch kandydatów nie może obu wygrać większości tego samego zbioru wyborców.

Follower   → passive; responds to RPCs from a leader or candidate; default state
Candidate  → actively campaigning for votes after an election timeout
Leader     → the one node currently accepting client writes and replicating them

Followers who hear nothing before their election timeout expires become Candidates.
Exactly one Candidate normally wins and becomes Leader for that term.

Wybór lidera: losowe opóźnienia jako decydujący czynnik

Postępujący obserwator, który nie otrzymał sygnału serca (heartbeat) od aktualnego lidera w czasie trwania jego wyboru, zakłada, że lider zniknął, zwiększa wartość terminu, głosuje na siebie i prosi o głosy od wszystkich innych węzłów. Jednym z inteligentnych, choć celowo ukrytych, elementów jest to, że opóźnienie nie jest stałe – jest losowo wybierane z zakresu (w artykule używany zakres 150-300 ms) przez każdy węzeł:

electionTimeout = random(150ms, 300ms) // ponowne ustawienie w każdym cyklu resetowania // Dlaczego losowość ma znaczenie: // Jeśli wszystkie obserwatory używałyBY takiego samego stałego opóźnienia, wszystkie by wycofały się jednocześnie, wszyscy staliBY się kandydatami naraz, podzielilibY głosowanie równo i powtarCALIBY to w nieskończoność bez tego, że ktokolwiek zdobyłBY większość. // Losowość oznacza, że timer jednego węzła prawie zawsze uruchamia SIĘ pierwszy, staje SIĘ kandydatem zanim inni zauważą, i zwykle wygrywa od razu. Jeśli jednak zdarzy się rozdzielone głosowanie (dwie kandydatury wycofują się blisko siebie i dzielą obserwatorów), termin po prostu wygasa bez zwycięzcy, a każdy węzeł ustawia świeże losowe opóźnienie na kolejny termin – rozdzielone głosy są rzadkie w praktyce i samorozwiązują się w ciągu jednej lub dwóch dodatkowych rund, a nie stanowią źródła długotrwałej niedostępności.

electionTimeout = random(150ms, 300ms)   // re-rolled every time it resets

// why randomness matters:
// if every follower used the SAME fixed timeout, all of them would time out
// simultaneously, all become candidates at once, split the vote evenly,
// and repeat forever with no leader ever winning a majority.
// randomizing means one node's timer almost always fires first, it becomes
// a candidate before the others notice, and usually wins outright.

Replikacja logów: większość quorum, nie jednolita zgoda

Po wybraniu lidera, jest to jedyny węzeł, który akceptuje polecenia od klientów. Dodaje każde polecenie do swojego własnego dziennika i wysyła je równolegle do wszystkich węzłów-śladowców za pomocą RPC AppendEntries. Kluczowe jest, że lider uznaje wpis za zatwierdzony – bezpieczny, trwały, gwarantujący przetrwanie w przypadku zmiany lidera – tak szybko, jak tylko większość węzłów (w tym on sam) go zapisała, a nie wszystkich:

Grupa 5 węzłów → potrzebuje 3 potwierdzeń do zatwierdzenia wpisu (większość = 3 z 5) Grupa 3 węzłów → potrzebuje 2 potwierdzeń do zatwierdzenia wpisu (większość = 2 z 3) // Dlatego klastry Raft używają rozmiarów nieparzystych: 3, 5, 7 – nawet rozmiar klastra nie zapewnia dodatkowej odporności na awarie, // ponieważ większość wymaga tego samego liczby ocalałych w obu przypadkach. To quorum większości jest mechanizmem, który pozwala klastrowi kontynuować postęp, nawet jeśli niewielka liczba węzłów jest niedostępna lub uległa awarii. Klastr 5-węzłowy toleruje 2 jednoczesne awarie i nadal dokonywa zapisów, ponieważ 3 węzły stanowią większość. Dlatego też klastry Raft są tworzone z węzłów o rozmiarach nieparzystych: klastr 4-węzlów nadal tylko toleruje 1 awarię (potrzebujesz 3 z 4 dla większości, tak samo jak potrzebujesz 2 z 3), więc czwarty węzeł nie wnosi nic poza zbędnym szumem sieciowym.

cluster of 5 nodes → needs 3 acknowledgments to commit an entry (majority = 3 of 5)
cluster of 3 nodes → needs 2 acknowledgments to commit an entry (majority = 2 of 3)

// this is why Raft clusters use ODD sizes: 3, 5, 7 — an even-sized cluster
// buys no extra fault tolerance over the next odd size down, because a
// majority requires the same number of survivors either way

Dlaczego martwa lider może cicho nadpisywać zapisy uznane za trwałe?

Subtelny aspekt argumentu bezpieczeństwa: co zapobiega sytuacji, w której węzeł odłączony podczas wyboru lidera, przeoczył kilka zatwierdzonych wpisów i później ponownie nawiązuje połączenie, stając się liderem i próbując nadpisać historię, do której klienci już wiedzieli, że jest trwała? Odpowiedź Rafta to ograniczenie wyborów – kandydat w swoim żądaniu głosowania (RequestVote RPC) zawiera indeks i numer terminu jego ostatniego wpisu w dzienniku, a wyborca odmawia udzielenia głosu kandydatom, których dziennik jest mniej aktualny niż jego własny. Ponieważ zatwierdzenie wpisu wymagało już większości, a wygrana w wyborach również wymaga większości głosów, te dwie większości muszą się pokrywać przynajmniej w jednym węźle – zgodnie z zasadą gołębia i żerdzi – więc każdy węzeł zdolny do wygranej w wyborach jest gwarantowany posiadaniem wszystkich wcześniej zatwierdzonych wpisów. Martwy kandydat nie może w ogóle zdobyć większości głosów.

Podziały: mniejsza grupa poprawnie odmawia zapisywania danych

Rozłączenie sieci, które dzieli klastr 5-węzłowy na grupę liczącą 3 i drugą grupę liczącą 2, jest najjasniejszym przykładem całego projektu. Grupa licząca 3 nadal posiada większość: może wybrać lidera (jeśli jeszcze go nie ma) i kontynuować normalne wprowadzanie nowych wpisów. Grupa licząca 2 nie może utworzyć większości z 5 – każdy węzeł w niej, który wycofa się i uruchomi wybór lidera, będzie stale zwiększał termin i prosił o głosy, ale nigdy nie zebrałby 3 głosów potrzebnych do zostania działającym liderem, dlatego mniejsza grupa poprawnie przestaje akceptować zapisywania danych, zamiast ryzykować dwa liderów, którzy będą się nie zgadzać. Po uzupełnieniu się podziału, stare lub niezapisane wpisy mniejszej grupy są po prostu nadpisywane przez AppendEntries z lidera większości, a log konwerguje do jednej spójnej historii.

Jest to Raft wymieniający dostępność na spójność podczas podziału (w języku CAP-theorem jest to system CP): zamiast pozwolić obu stronom rozszczepionego klastra kontynuować akceptację zapisów i ryzykować niemożliwą do rozwiązania konflikt, mniejsza grupa przestaje obsługiwać zapytania, dopóki nie połączy się z większością. Jest to celowe, zasadnicze rozwiązanie – nie jest to błąd – i dokładnie odzwierciedla zachowanie symulacji na tej stronie, gdy podział lub usunięcie węzłów zostaną uruchomione: obserwuj, jak mniejsza grupa zawiesza się, podczas gdy większa grupa nadal wybiera liderów i wprowadza wpisy.

Często zadawane pytania

Wypróbuj na żywo

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