Protokół konsensu Paxos: Jak rozproszone systemy osiągają zgody na jedno wartość

Problem: Zgodność w Niepewnych Warunkach

Serce obliczeń rozproszonych kryje się w trudnym wyzwaniu: jak kilka niezależnych maszyn, połączonych niestabilną siecią, może osiągnąć zgodność na dokładnie jedno wartość, gdy każda z nich może zatrzymać się bez ostrzeżenia i każde wiadomości mogą zniknąć bez ostrzeżenia? To problem konsensusu rozproszonego, a jego znaczenie jest niezwykle duże w praktyce. Bazy danych muszą zgodnie ustalić porządek transakcji, usługi blokujące muszą zgodnie ustalić właściciela bloku i kopie zapasowe dzienników muszą zgodnie ustalić tę samą sekwencję poleceń. Proste podejścia, takie jak wybór jednego koordynatora i zaufanie do niego całkowicie, się rozpadają w chwili, gdy ten koordynator zatrzymuje się lub staje się niewykonwalny. Poprawna protokół konsensusu musi tolerować awarie węzłów i opóźnienia w sieciach, jednocześnie gwarantując dwa cechy: bezpieczeństwo, co oznacza, że system nigdy nie zgodnie ustala dwie różne wartości, oraz żywotność, co oznacza, że osiąga zgodność, jeśli wystarczająco dużo elementów systemu jest w worku. Paxos był pierwszym protokołem dowodzonym na to, że rozwiązuje ten problem, a jego kluczowa myśl polega na tym, że zgodność nie wymaga, aby każdy węzeł odpowiedział, tylko większości. Tylko jedna taka idea, że nadmiarowe majorie zawsze mają co najmniej wspólnego członka, jest to, co pozwala całości systemu funkcjonować nawet wtedy, gdy niektóre jego części są niewykonwalne lub wolne.

Znajdźysz Zawodników: Proposery, Akceptatorów i Uczniów

Paxos przypisuje każdemu z uczestniczących węzłom jedno lub więcej z trzech roli. Proposer to węzeł, który chce uzyskać zaakceptowanie wartości, na przykład żądanie klienta do wpisania nowego elementu do reperkusyjnego dziennika. Akceptator jest węzłem, który głosuje na propozycje; akceptatory tworzą trwałą pamięć systemu i muszą zachować swoje obietnice nawet po ponownych uruchomieniach. Uczniem jest węzeł, który chce tylko dowiedzieć się, która wartość została w końcu wybrana, bez udziału w głosowaniu samodzielnie. W rzeczywistych zastosowaniach pojedynczy fizyczny serwer często odgrywa wiele roli naraz, działając zarówno jako proposer i akceptator. Rozdzielenie roli jest to, co sprawia, że Paxos tak elastyczny: każdy węzeł może próbować zaproponować wartość w dowolnym momencie, wielu proposerów może konkurencje jednocześnie, a protokoł nadal zbiega się do jednego zwycięzcy. Akceptatory nigdy nie koordynują się bezpośrednio ze sobą; odpowiadają tylko proposerom, co sprawia komunikację prostą i unika potrzeby niewytrzymalnego, zawsze włącznego lidera. Ta konstrukcja oznacza również, że system degradowa się łagodnie. Jeśli proposer upadnie pośrodku rundy, inny proposer może prosto rozpocząć nową rundę z wyższym numerem propozycji i kontynuować gdzie zostawiły to akceptatory, nie spowodując uszkodzenia tego, co już zapisali.

Faza 1: Przygotowanie i Gwarancja

Każdy runde Paxosa zaczyna się od propozycji o unikatowo numerowanym numerze, a te monotonicznie rosnące numery propozycji są mecanizmem rozstrzygającym konflikty między konkurencyjnymi propozentami. W Fazie 1 propozent wybiera numer propozycji n wyższy niż żaden z poprzednich i wysyła prośbę o przygotowanie z tym numerem do większości akceptantów. Każdy akceptant, który otrzyma tę prośbę, porównuje n z najwyższym numerem propozycji, którą już gwarantował. Jeśli n jest wyższe, akceptant zobowiązuje się nigdy nie przyjmować żadnej przyszłej propozycji o niższym numerze i odpowiada tym samym, wraz z wartością najwyższego numeru propozycji, którą już gwarantował, jeśli taka istnieje. Jeśli n nie jest wyższe, akceptant prosty ignoruje lub odmawia prośby. Ta fazę można uznać za przeszukanie: propozent sprawdza, czy sytuacja jest bezpieczna i, kluczowo, odkrywa, czy pewna wcześniejsza propozycja może być już przyjęta przez część większości. To krok odkrywania zapobiega wnikliwemu nadpisaniu wartości, której inny propozent mógł częściowo przyjąć. Propozent ma wystarczającą informację, aby bezpiecznie przejść do fazy 2 i rzeczywistej propozycji wartości, tylko po słuchnięciu gwarancji od większości akceptantów.

Faza 2: Akceptacja i Zatwierdzone

Zbrojny większością propozycji, przedstawiciel wejdzie w Fazę 2. Musi wybierać wartość do zaproponowania z przemyśleniem: jeśli którykolwiek akceptator z Fazy 1 zgłosił już zaakceptowaną wartość, przedstawiciel jest zobowiązany do przyjęcia wartości z najbardziej numeryzowanej takiej zgody, a nie podstawienia swojej. Ta reguła stanowi kluczowy element bezpieczeństwa Paxos, zapewniając, że wartość już w drodze do wyboru nie może być bezgłośnie zastąpiona. Następnie przedstawiciel wysyła żądanie akceptacji, zawierające swój numer propozycji n i wybraną wartość, do tej samej większości akceptatorów. Każdy akceptator akceptuje żądanie i rejestruje wartość, chyba że odmawiająco zgodził się w odpowiedzi na przygotowanie o wyższej numeracji od innej przedstawicielki, ignorować propozycje numeryzowane n lub niższe. Jeśli przedstawiciel otrzyma akceptację większością akceptatorów, wartość jest oficjalnie zatwierdzona, choć inne węzły mogą nadal o niej nie wiedzieć. Nauczyciele dowiadują się o wybranej wartości albo bezpośrednio od akceptatorów, lub poprzez uprzednio wyznaczony nauczyciel, który agreguje i rozprzestrzenia wynik. Ponieważ wartość może być zatwierdzona tylko po uzyskaniu pełnej większości akceptacji, a każda dwie wielkości większości zawsze się nadmiarują, jest matematycznie niemożliwe dla dwóch różnych wartości, aby obu doszły do akceptacji większościowej.

Dlaczego kwalifikacje większościowe gwarantują bezpieczeństwo, a Paxos w rzeczywistości

Powstańca mocu większościowych kwalifikacji jest tak silna z powodu prostej przecięcia zbiorów: dla dowolnej grupy węzłów, dwa podzbory zawierające więcej niż połowę członków są gwarantowane do zawierać co najmniej jeden wspólny węzeł. Ten wspólny węzeł widział obie rundy i gwarantuje ich zgodność, ponieważ nie przyjmie propozycji o niższym numerze po zobowiązań do przestrzegania propozycji o wyższym numerze. Ta własność zachowuje się nawet podczas podziału sieci, ponieważ na najwyżej jednej stronie podzielonego systemu może znajdować się większość, więc tylko jedna strona może osiągnąć postępy, a druga trzyma się do momentu zwracania się po powrocie komunikacji. Ta wymiana, przewagując bezpieczeństwo nad dostępnością podczas podziału, jest dokładnie to, co teoria CAP przewiduje dla systemów zgodnych. Idee Paxosa okazały się tak podstawowe, że wpłynęły na dekadę infrastruktury. Usługa blokująca Chubby Google opisana w popularnym 2006 roku dokumencie używała logu skopiowanego z Paxosa do utrzymania zgodności danych blokujących i konfiguracyjnych między centrami danych, a Chubby z kolei wpłynęła na inspirację do ZooKeepera. W ostatnim czasie algorytm konsensusowy Raft został zaprojektowany jako bardziej zrozumiały zastępca Paxosa, a systemy takie jak etcd, który obsługuje Kubernetes, są oparte na Raft. Dwa różne pakowania, mekanizmy wyboru lidera i kopii logów Rafta przeprowadzają swoją pochodzenie intelektualne bezpośrednio do Paxosa, co sprawia, że jest słusznie nazwać Paxosa przodka całej rodziny współczesnych systemów konsensusowych.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz The Paxos Consensus Protocol: How Distributed Systems Agree on One Value i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.