Paxos (informatyka)

Paxos to rodzina protokołów do rozwiązywania konsensusu w sieci zawodnych lub zawodnych procesorów. Konsensus to proces uzgadniania jednego wyniku wśród grupy uczestników. Ten problem staje się trudny, gdy uczestnicy lub ich komunikacja mogą napotkać awarie.

Protokoły konsensusu są podstawą podejścia opartego na replikacji maszyny stanowej w przetwarzaniu rozproszonym , zgodnie z sugestią Leslie Lamport i badaniem przeprowadzonym przez Freda Schneidera . Replikacja maszyny stanowej to technika przekształcania algorytmu w odporną na błędy, rozproszoną implementację. Techniki ad-hoc mogą pozostawiać nierozwiązane ważne przypadki niepowodzeń. Podejście oparte na zasadach zaproponowane przez Lamport i in. zapewnia bezpieczne prowadzenie wszystkich spraw.

Protokół Paxos został po raz pierwszy przedłożony w 1989 r. I nazwany na cześć fikcyjnego systemu konsensusu legislacyjnego używanego na wyspie Paxos w Grecji, gdzie Lamport napisał, że parlament musi funkcjonować, „mimo że ustawodawcy nieustannie wędrują do izby parlamentarnej iz niej”. Został on później opublikowany jako artykuł w czasopiśmie w 1998 roku.

Rodzina protokołów Paxos obejmuje spektrum kompromisów między liczbą procesorów, liczbą opóźnień wiadomości przed poznaniem uzgodnionej wartości, poziomem aktywności poszczególnych uczestników, liczbą wysłanych wiadomości i rodzajami awarii. Chociaż żaden deterministyczny protokół konsensusu odporny na błędy nie może zagwarantować postępu w sieci asynchronicznej (wynik udowodniony w artykule Fischera , Lyncha i Patersona ), Paxos gwarantuje bezpieczeństwo (spójność), a warunki, które mogłyby uniemożliwić mu postęp, są trudne do sprowokować.

Paxos jest zwykle używany tam, gdzie wymagana jest trwałość (na przykład do replikacji pliku lub bazy danych ), w których ilość trwałego stanu może być duża. Protokół próbuje czynić postępy nawet w okresach, gdy pewna ograniczona liczba replik nie odpowiada. Istnieje również mechanizm usunięcia trwale uszkodzonej repliki lub dodania nowej repliki.

Historia

Temat poprzedza protokół. W 1988 roku Lynch , Dwork i Stockmeyer zademonstrowali możliwość rozwiązania konsensusu w szerokiej rodzinie systemów „częściowo synchronicznych”. Paxos ma silne podobieństwa do protokołu używanego do uzgadniania w „replikacji ze znacznikiem widoku”, opublikowanej po raz pierwszy przez Okiego i Liskova w 1988 r., w kontekście transakcji rozproszonych. Niezależnie od tej wcześniejszej pracy, Paxos oferował szczególnie elegancki formalizm i zawierał jeden z najwcześniejszych dowodów bezpieczeństwa dla odpornego na błędy rozproszonego protokołu konsensusu.

Rekonfigurowalne maszyny stanowe mają silne powiązania z wcześniejszymi pracami nad niezawodnymi protokołami multiemisji grupowej, które obsługują dynamiczne członkostwo w grupach, na przykład praca Birmana w 1985 i 1987 r. Nad wirtualnie synchronicznym protokołem gbcast . Jednak gbcast jest niezwykły pod względem wspierania trwałości i rozwiązywania problemów z partycjonowaniem. Większość niezawodnych protokołów multiemisji nie ma tych właściwości, które są wymagane do implementacji modelu replikacji maszyny stanowej. Kwestia ta została omówiona w artykule Lamporta , Malkhi i Zhou.

Protokoły Paxos należą do teoretycznej klasy rozwiązań problemu sformalizowanego jako jednolita zgodność z awariami awarii. Dolne granice tego problemu zostały udowodnione przez Keidar i Shraer. Derecho, biblioteka oprogramowania C++ do replikacji maszyn stanowych w skali chmury, oferuje protokół Paxos, który został zintegrowany z samozarządzanym członkostwem wirtualnie synchronicznym. Protokół ten odpowiada granicom optymalności Keidara i Shraera i skutecznie odwzorowuje nowoczesne zdalne centrum danych DMA (RDMA) (ale używa protokołu TCP, jeśli RDMA nie jest dostępny).

Założenia

Aby uprościć prezentację Paxos, wyjaśniono następujące założenia i definicje. Techniki poszerzania stosowalności są znane w literaturze i nie są omówione w tym artykule.

Procesory

Procesory działają z dowolną prędkością.
Procesory mogą ulegać awariom.
Procesory ze stabilną pamięcią masową mogą ponownie dołączyć do protokołu po awarii (zgodnie z modelem odzyskiwania po awarii).
Podmioty przetwarzające nie działają w zmowie, nie kłamią ani w żaden inny sposób nie próbują podważyć protokołu. (Oznacza to, że awarie bizantyjskie nie występują. Zobacz bizantyjskie Paxos , aby znaleźć rozwiązanie, które toleruje awarie wynikające z arbitralnego/złośliwego zachowania procesów).

Sieć

Procesory mogą wysyłać komunikaty do dowolnego innego procesora.
Wiadomości są wysyłane asynchronicznie i ich dostarczenie może zająć dużo czasu.
Wiadomości mogą zostać utracone, zmienione lub zduplikowane.
Wiadomości są dostarczane bez korupcji. (Oznacza to, że awarie bizantyjskie nie występują. Zobacz bizantyjskie Paxos , aby znaleźć rozwiązanie, które toleruje uszkodzone wiadomości wynikające z arbitralnego/złośliwego zachowania kanałów przesyłania wiadomości).

Liczba procesorów

$innymi$ algorytm konsensusu może poczynić postępy przy użyciu $słowy$ pomimo jednoczesnej awarii dowolnych liczba nie- wadliwych procesów musi być ściśle większa niż liczba wadliwych procesów. Jednak przy użyciu rekonfiguracji można zastosować protokół, który przetrwa dowolną liczbę całkowitych awarii, o ile nie więcej niż F ulegnie awarii jednocześnie. W przypadku protokołów Paxos te rekonfiguracje mogą być obsługiwane jako osobne konfiguracje .

Role

Paxos opisuje działania procesorów według ich ról w protokole: klient, akceptant, proponujący, uczeń i lider. W typowych implementacjach pojedynczy procesor może pełnić jednocześnie jedną lub więcej ról. Nie wpływa to na poprawność protokołu — zwykle łączy się role, aby poprawić opóźnienie i/lub liczbę komunikatów w protokole.

Klient: Klient wysyła żądanie do systemu rozproszonego i czeka na odpowiedź . Na przykład żądanie zapisu do pliku na rozproszonym serwerze plików.
Akceptujący (wyborcy): Akceptanci działają jako odporna na błędy „pamięć” protokołu. Akceptanci są gromadzeni w grupach zwanych kworami. Każda wiadomość wysłana do Akceptanta musi zostać wysłana do Kworum Akceptantów. Każda wiadomość otrzymana od Akceptanta jest ignorowana, chyba że otrzymano kopię od każdego Akceptanta w Kworum.
Proponujący: Proponujący opowiada się za żądaniem klienta, próbując przekonać Akceptantów do wyrażenia zgody i działając jako koordynator, aby posunąć protokół do przodu, gdy wystąpią konflikty.
Uczący się: Uczący się działają jako czynnik replikacji protokołu. Po uzgodnieniu żądania Klienta przez Akceptantów, Uczeń może podjąć działania (tj. wykonać żądanie i wysłać odpowiedź do klienta). Aby poprawić dostępność przetwarzania, można dodać dodatkowych uczniów.
Lider: Paxos wymaga wyróżniającego się Wnioskodawcy (zwanego liderem), aby osiągnąć postęp. Wiele procesów może wierzyć, że są liderami, ale protokół gwarantuje postęp tylko wtedy, gdy jeden z nich zostanie ostatecznie wybrany. Jeśli dwa procesy uważają, że są liderami, mogą zablokować protokół, ciągle proponując sprzeczne aktualizacje. Jednak właściwości bezpieczeństwa są nadal zachowane.

Kworum

Kwora wyrażają właściwości bezpieczeństwa (lub spójności) Paxos poprzez zapewnienie, że przynajmniej część procesorów, które przeżyły, zachowa wiedzę o wynikach.

Kwora definiuje się jako podzbiory zbioru Akceptantów, w taki sposób, że dowolne dwa Kwora mają co najmniej jednego członka. Zazwyczaj Kworum to dowolna większość uczestniczących Akceptantów. Na przykład, biorąc pod uwagę zbiór Akceptantów {A,B,C,D}, Kworum większościowe składałoby się z dowolnych trzech Akceptantów: {A,B,C}, {A,C,D}, {A,B,D} , {B,C,D}. Mówiąc bardziej ogólnie, Akceptantom można przypisać dowolne dodatnie wagi; w takim przypadku Kworum można zdefiniować jako dowolny podzbiór Akceptantów o łącznej wadze większej niż połowa łącznej wagi wszystkich Akceptantów.

Numer oferty i uzgodniona wartość

Każda próba określenia uzgodnionej wartości v odbywa się z propozycjami, które mogą, ale nie muszą zostać zaakceptowane przez Akceptantów. Każda oferta jest indywidualnie numerowana dla danego Oferenta. Tak więc np. każda propozycja może mieć postać (n, v) , gdzie n jest unikalnym identyfikatorem propozycji, a v jest rzeczywistą proponowaną wartością. Wartość odpowiadająca ponumerowanej propozycji może być obliczona w ramach działania protokołu Paxos, ale nie musi.

Właściwości bezpieczeństwa i żywotności

Aby zagwarantować bezpieczeństwo (zwane również „spójnością”), Paxos definiuje trzy właściwości i zapewnia, że pierwsze dwie są zawsze utrzymywane, niezależnie od wzorca awarii:

Trafność (lub nietrywialność ): Tylko proponowane wartości mogą być wybrane i nauczone.
Zgodność (lub spójność lub bezpieczeństwo ): Dwóch różnych uczniów nie może nauczyć się różnych wartości (lub nie może być więcej niż jedna zdecydowana wartość)
Zakończenie (lub żywotność): Jeśli zaproponowano wartość C, to w końcu uczeń L nauczy się pewnej wartości ( jeśli wystarczająca liczba procesorów nie ulegnie awarii).

Zauważ, że Paxos nie gwarantuje zakończenia, a zatem nie ma właściwości liveness. Potwierdza to wynik niemożliwości Fischera Lyncha Patersona (FLP), który stwierdza, że protokół spójności może mieć tylko dwa z nich: bezpieczeństwo , żywotność i odporność na uszkodzenia . Ponieważ Paxos ma na celu zapewnienie odporności na awarie i gwarantuje bezpieczeństwo, nie może również zagwarantować żywotności.

Typowe wdrożenie

W większości wdrożeń Paxos każdy uczestniczący proces działa w trzech rolach; Proponujący, akceptujący i uczący się. Zmniejsza to znacznie złożoność wiadomości, bez utraty poprawności:

W Paxos klienci wysyłają polecenia do lidera. Podczas normalnej pracy lider odbiera polecenie klienta, przypisuje mu nowy numer polecenia $,$ a następnie rozpoczyna $instancję$ konsensusu, wysyłając komunikaty do zestawu procesów ^{akceptujących}

Łącząc role, protokół „zapada się” w wydajne wdrożenie w stylu klient-główny-replika, typowe dla społeczności baz danych. Zaletą protokołów Paxos (w tym implementacji z połączonymi rolami) jest gwarancja ich właściwości bezpieczeństwa .

Typowy przepływ komunikatów implementacji jest omówiony w sekcji Multi-Paxos .

Podstawowy Paxos

Ten protokół jest najbardziej podstawowym z rodziny Paxos. Każda „instancja” (lub „wykonanie”) podstawowego protokołu Paxos decyduje o pojedynczej wartości wyjściowej. Protokół przebiega przez kilka rund. Udana runda składa się z 2 faz: fazy 1 (która jest podzielona na części a i b ) oraz fazy 2 (która jest podzielona na części a i b ). Zobacz poniżej opis faz. Pamiętaj, że zakładamy model asynchroniczny, więc np. procesor może być w jednej fazie, a drugi w innej.

Faza 1

Faza 1a: Przygotowanie

Proponujący tworzy wiadomość, którą nazywamy „Przygotuj”, oznaczoną numerem n . Zauważ, że n nie jest wartością, którą należy zaproponować i być może uzgodnić, ale tylko liczbą, która jednoznacznie identyfikuje tę początkową wiadomość przez wnioskodawcę (do wysłania do akceptantów). Liczba n musi być większa niż jakakolwiek liczba użyta w którymkolwiek z poprzednich komunikatów dotyczących przygotowania przez tego oferenta. Następnie wysyła Przygotowania zawierający n co najmniej do Kworum Akceptantów . Należy zauważyć, że Prepare zawiera tylko liczbę n (to znaczy nie musi zawierać np. proponowanej wartości, często oznaczanej przez v ). Proponujący decyduje o tym, kto jest w Kworum ^{[ w jaki sposób? ]} . Proponujący nie powinien inicjować Paxos, jeśli nie może komunikować się przynajmniej z Kworum Akceptantów.

Faza 1b: Obietnica

Każdy z akceptantów czeka na wiadomość przygotowania od któregokolwiek z oferentów . Jeśli Akceptant otrzyma komunikat Przygotowania, Akceptant musi spojrzeć na numer identyfikacyjny n właśnie otrzymanego komunikatu Przygotowania . Istnieją dwa przypadki.

Jeżeli n jest większe niż każdy poprzedni numer oferty otrzymany od któregokolwiek z Oferentów przez Akceptanta, to Akceptant musi odesłać Oferentowi wiadomość, którą nazywamy „Obietnicą”, aby zignorować wszystkie przyszłe oferty o numerze niższym niż n . Jeżeli Akceptant zaakceptował propozycję w pewnym momencie w przeszłości, musi podać numer poprzedniej propozycji, powiedzmy m , i odpowiednią zaakceptowaną wartość, powiedzmy w , w swojej odpowiedzi dla Wnioskodawcy.

W przeciwnym razie (tj. n jest mniejsze lub równe jakiemukolwiek poprzedniemu numerowi propozycji otrzymanemu od jakiegokolwiek Wnioskodawcy przez Akceptanta) Akceptant może zignorować otrzymaną propozycję. W tym przypadku nie musi odpowiadać, aby Paxos zadziałał. Jednak ze względu na optymalizację wysłanie odpowiedzi odmownej ( Nack ) poinformuje wnioskodawcę, że może przerwać próbę osiągnięcia konsensusu z propozycją rz .

Faza 2

Faza 2a: Zaakceptuj

Jeśli Proponujący otrzymuje Obietnice od Kworum Akceptujących, musi ustawić wartość v dla swojej propozycji. Jeśli jacyś Akceptanci wcześniej zaakceptowali jakąkolwiek propozycję, to prześlą swoje wartości do Wnioskodawcy, który teraz musi ustawić wartość swojej propozycji, v , na wartość związaną z najwyższym numerem propozycji zgłoszonym przez Akceptantów, nazwijmy to z . Jeżeli żaden z Akceptantów do tej pory nie zaakceptował propozycji, to Proponujący może wybrać wartość, którą pierwotnie chciał zaproponować, powiedzmy x .

Proponujący wysyła wiadomość Akceptuj , (n, v) , do Kworum Akceptantów z wybraną wartością dla swojej propozycji, v, oraz numerem propozycji n (który jest taki sam jak numer zawarty w komunikacie Przygotowania wysłanym wcześniej do Akceptantów). Tak więc Akceptuj to albo (n, v=z) albo, w przypadku, gdy żaden z Akceptantów wcześniej nie zaakceptował wartości, (n, v=x) .

Ten komunikat Akceptuj należy interpretować jako „prośbę”, jak w przypadku „Zaakceptuj tę propozycję, proszę!”.

Faza 2b: Zaakceptowano

Jeśli Akceptant otrzyma wiadomość Akceptuj, (n, v) od Wnioskodawcy, musi ją zaakceptować wtedy i tylko wtedy, gdy nie obiecał już (w fazie 1b protokołu Paxos) rozpatrywania tylko propozycji mających identyfikator większy niż n .

Jeżeli Akceptant nie zobowiązał się już (w Fazie 1b) do rozpatrywania wyłącznie propozycji o identyfikatorze większym niż n , powinien zarejestrować wartość v (z właśnie otrzymanego komunikatu Akceptuj ) jako zaakceptowaną wartość (Protokołu) i wysłać Przyjęty wiadomość do Wnioskodawcy i każdego Uczestnika (którymi zazwyczaj mogą być sami Wnioskodawcy).

W przeciwnym razie może zignorować komunikat Akceptuj lub żądanie.

Należy zauważyć, że konsensus zostaje osiągnięty, gdy większość Akceptantów zaakceptuje ten sam numer identyfikacyjny (zamiast tej samej wartości ). Ponieważ każdy identyfikator jest unikalny dla Wnioskodawcy i tylko jedna wartość może zostać zaproponowana dla każdego identyfikatora, wszyscy Akceptanci, którzy akceptują ten sam identyfikator, akceptują tę samą wartość. Fakty te skutkują kilkoma sprzecznymi z intuicją scenariuszami, które nie mają wpływu na poprawność: Akceptanci mogą zaakceptować wiele wartości , wartość może osiągnąć większość wśród Akceptantów (z różnymi identyfikatorami) tylko po to, by później zostać zmieniona , oraz Akceptujący mogą nadal akceptować propozycje po uzyskaniu przez identyfikator większości . Jednak protokół Paxos gwarantuje, że konsensus jest trwały, a wybrana wartość niezmienna.

Kiedy rundy się nie powiodą

Rundy kończą się niepowodzeniem, gdy wielu oferentów wysyła sprzeczne komunikaty dotyczące przygotowania lub gdy oferent nie otrzyma kworum odpowiedzi ( obietnica lub akceptacja ). W takich przypadkach należy rozpocząć kolejną rundę z wnioskiem o wyższym numerze.

Paxos może być użyty do wyboru lidera

Zauważ, że Proponujący w Paxos może zaproponować „Jestem liderem” (lub na przykład „Propozytor X jest liderem”). Ze względu na zgodę i gwarancje ważności Paxos, jeśli zostanie zaakceptowany przez Kworum, Proponujący jest teraz znany jako lider wszystkich innych węzłów. To zaspokaja potrzeby wyboru lidera, ponieważ istnieje jeden węzeł wierzący, że jest liderem i jeden węzeł, o którym wiadomo, że jest liderem przez cały czas.

Graficzne przedstawienie przepływu komunikatów w podstawowym Paxos

Poniższe diagramy przedstawiają kilka przypadków/sytuacji zastosowania protokołu Basic Paxos. Niektóre przypadki pokazują, jak protokół Basic Paxos radzi sobie z awarią pewnych (redundantnych) komponentów systemu rozproszonego.

Zauważ, że wartości zwracane w komunikacie Obietnicy są „null” przy pierwszym składaniu propozycji (ponieważ żaden Akceptant nie zaakceptował wcześniej wartości w tej rundzie).

Podstawowe Paxos bez awarii

Na poniższym diagramie znajduje się 1 Klient, 1 Proponujący, 3 Akceptantów (tj. wielkość Kworum wynosi 3) i 2 Uczniów (reprezentowanych przez 2 pionowe linie). Diagram ten przedstawia przypadek pierwszej rundy, która zakończyła się sukcesem (tj. żaden proces w sieci nie zawodzi).

Tutaj V jest ostatnim z (Va, Vb, Vc).

Przypadki błędów w podstawowym Paxos

Najprostsze przypadki błędów to awaria Akceptanta (kiedy Kworum Akceptantów pozostaje przy życiu) oraz awaria zbędnego Ucznia. W takich przypadkach protokół nie wymaga „odzyskiwania” (tj. nadal się udaje): nie są wymagane żadne dodatkowe rundy ani komunikaty, jak pokazano poniżej (na dwóch kolejnych diagramach/przypadkach).

Podstawowe Paxos, gdy Akceptor zawiedzie

Na poniższym diagramie jeden z Akceptantów w Kworum ulega awarii, więc rozmiar Kworum wynosi 2. W tym przypadku podstawowy protokół Paxos nadal działa pomyślnie.

Klient Proponujący Akceptujący Uczeń | | | | | | | X-------->| | | | | | Żądanie | X--------->|->|->| | | Przygotuj(1) | | | | ! | | !! PONIEŚĆ PORAŻKĘ !! | |<---------X--X | | Obietnica(1,{Va, Vb, null}) | X--------->|->| | | Zaakceptuj!(1,V) | |<---------X--X--------->|->| Zaakceptowano(1,V) |<---------------------------------X--X Odpowiedź | | | | | |

Podstawowy Paxos, gdy zbędny uczeń zawiedzie

W poniższym przypadku jeden z (zbędnych) uczniów zawodzi, ale podstawowy protokół Paxos nadal działa.

Klient Proponujący Akceptujący Uczestnik | | | | | | | X-------->| | | | | | Żądanie | X--------->|->|->| | | Przygotuj(1) | |<---------X--X--X | | Obietnica(1,{Va,Vb,Vc}) | X--------->|->|->| | | Zaakceptuj!(1,V) | |<---------X--X--X------>|->| Zaakceptowano(1,V) | | | | | | ! !! PONIEŚĆ PORAŻKĘ !! |<---------------------------------X Odpowiedź | | | | | |

Podstawowy Paxos, gdy Proponujący zawiedzie

W tym przypadku Proponujący nie udaje się po zaproponowaniu wartości, ale przed osiągnięciem porozumienia. W szczególności kończy się niepowodzeniem w trakcie komunikatu Akceptuj, więc tylko jeden Akceptant Kworum otrzymuje wartość. W międzyczasie wybierany jest nowy Lider (Proponujący) (ale nie jest to szczegółowo pokazane). Zwróć uwagę, że w tym przypadku są 2 rundy (rundy przebiegają pionowo, od góry do dołu).

Klient Proponujący Akceptujący Uczeń | | | | | | | X----->| | | | | | Żądanie | X------------>|->|->| | | Przygotuj(1) | |<------------X--X--X | | Obietnica(1,{Va, Vb, Vc}) | | | | | | | | | | | | | | !! Lider zawodzi podczas transmisji !! | X------------>| | | | | Zaakceptuj!(1,V) | ! | | | | | | | | | | | | !! NOWY LIDER!! | X--------->|->|->| | | Przygotuj(2) | |<---------X--X--X | | Obietnica(2,{V, null, null}) | X--------->|->|->| | | Zaakceptuj!(2,V) | |<---------X--X--X------>|->| Zaakceptowano(2,V) |<---------------------------------X--X Odpowiedź | | | | | | |

Podstawowy Paxos w przypadku konfliktu wielu Proponujących

Najbardziej złożonym przypadkiem jest sytuacja, w której wielu Wnioskodawców uważa się za Liderów. Na przykład obecny lider może upaść i później odzyskać siły, ale pozostali wnioskodawcy już ponownie wybrali nowego lidera. Odzyskany lider jeszcze się tego nie nauczył i próbuje rozpocząć jedną rundę w konflikcie z obecnym liderem. Na poniższym diagramie pokazane są 4 nieudane rundy, ale może być ich więcej (zgodnie z sugestią na dole diagramu).

Klient Proponujący Akceptujący Uczestnik | | | | | | | X----->| | | | | | Żądanie | X------------>|->|->| | | Przygotuj(1) | |<------------X--X--X | | Obietnica(1,{null,null,null}) | ! | | | | | !! PORAŻKA LIDERA | | | | | | | !! NOWY LIDER (wie, że ostatnia liczba to 1) | X--------->|->|->| | | Przygotuj(2) | |<---------X--X--X | | Obietnica(2,{null,null,null}) | | | | | | | | !! STARY LIDER wraca do zdrowia | | | | | | | | !! STARY LIDER próbuje 2, odmowa | X------------>|->|->| | | Przygotuj(2) | |<------------X--X--X | | Nak(2) | | | | | | | | !! STARY LIDER próbuje 3 | X------------>|->|->| | | Przygotuj(3) | |<------------X--X--X | | Obietnica(3,{null,null,null}) | | | | | | | | !! NOWY LIDER proponuje, odrzuca | | X--------->|->|->| | | Zaakceptuj!(2,Va) | | |<---------X--X--X | | Nak(3) | | | | | | | | !! NOWY LIDER próbuje 4 | | X--------->|->|->| | | Przygotuj(4) | | |<---------X--X--X | | Obietnica(4,{null,null,null}) | | | | | | | | !! STARY LIDER proponuje, odrzuca | X------------>|->|->| | | Zaakceptuj!(3,Vb) | |<------------X--X--X | | Nack(4) | | | | | | | | ... i tak dalej ...

Podstawowy Paxos, w którym Akceptant akceptuje Dwie Różne Wartości

W poniższym przypadku jeden Oferent uzyskuje akceptację wartości V1 przez jednego Akceptanta przed porażką. Nowy Proponujący przygotowuje Akceptantów, którzy nigdy nie zaakceptowali V1, umożliwiając mu zaproponowanie V2. Następnie V2 jest akceptowany przez wszystkich Akceptantów, włączając w to tego, który początkowo zaakceptował V1.

Uczestnik akceptujący oferenta | | | | | | | X--------->|->|->| | | Przygotuj(1) |<--------X--X--X | | Obietnica(1,{null,null,null}) x--------->| | | | | Akceptuj!(1,V1) | | X------------>|->| Zaakceptowano(1,V1)! | | | | | | !! PONIEŚĆ PORAŻKĘ !! | | | | | | X--------->|->| | | Przygotuj(2) |<--------X--X | | Obietnica(2,{null,null}) X------>|->|->| | | Zaakceptuj!(2,V2) |<------X--X--X------>|->| Zaakceptowano(2,V2) | | | | | |

Podstawowy Paxos, w którym większość z wieloma identyfikatorami jest niewystarczająca

W poniższym przypadku jeden Oferent uzyskuje akceptację wartości V1 jednego Akceptanta przed porażką. Nowy Proponujący przygotowuje Akceptantów, którzy nigdy nie zaakceptowali V1, umożliwiając mu zaproponowanie V2. Ten Proponujący jest w stanie skłonić jednego Akceptanta do zaakceptowania V2 przed niepowodzeniem. Nowy Proponujący znajduje większość obejmującą Akceptanta, który zaakceptował V1 i musi go zaproponować. Proponującemu udaje się pozyskać dwóch Akceptantów, aby go zaakceptowali, zanim poniesie porażkę. W tym momencie trzech akceptantów zaakceptowało V1, ale nie dla tego samego identyfikatora. Na koniec nowy Wnioskodawca przygotowuje większość, która nie widziała największego zaakceptowanego identyfikatora. Wartość związana z największym identyfikatorem w tej większości to V2, więc musi go zaproponować. Ten Proponujący nakłania następnie wszystkich Akceptantów do zaakceptowania V2, osiągając konsensus.

Uczestnik akceptujący oferenta | | | | | | | | | | | X--------------->|->|->|->|->| | | Przygotuj(1) |<---------------X--X--X--X--X | | Obietnica(1,{null,null,null,null,null}) x--------------->| | | | | | | Akceptuj!(1,V1) | | | | X--->|->| Zaakceptowano(1,V1)! | | | | | | | | | | !! PONIEŚĆ PORAŻKĘ !! | | | | | | | | | | X--------------->|->|->|->| | | Przygotuj(2) |<---------------X--X--X--X | | Obietnica(2,{null,null,null,null}) X--------------->| | | | | | Zaakceptuj!(2,V2) | | | | X--------------->|->| Zaakceptowano(2,V2) ! | | | | | | | | | !! PONIEŚĆ PORAŻKĘ !! | | | | | | | | | X--------->|---->|->|->| | | Przygotuj(3) |<--------X-----X--X--X | | Obietnica(3,{V1,null,null,null}) X--------------->|->| | | | Akceptuj!(3,V1) | | | | X--X--------->|->| Zaakceptowano(3,V1) ! | | | | | | | | !! PONIEŚĆ PORAŻKĘ !! | | | | | | | | X------>|->|------->| | | Przygotuj(4) |<------X--X--|--|--X | | Obietnica(4,{V1(1),V2(2),null}) X------>|->|->|->|->| | | Zaakceptuj!(4,V2) | X--X--X--X--X------>|->| Zaakceptowany(4,V2)

Podstawowy Paxos, w którym nowi wnioskodawcy nie mogą zmienić istniejącego konsensusu

W poniższym przypadku jeden Oferent uzyskuje akceptację wartości V1 dwóch Akceptantów przed porażką. Nowy Proponujący może rozpocząć kolejną rundę, ale obecnie nie jest możliwe, aby ten Proponujący przygotował większość, która nie obejmuje co najmniej jednego Akceptanta, który zaakceptował V1. W związku z tym, mimo że Wnioskodawca nie widzi istniejącego konsensusu, jedyną opcją Wnioskodawcy jest zaproponowanie uzgodnionej już wartości. Nowi wnioskodawcy mogą stale zwiększać identyfikator, aby ponownie uruchomić proces, ale konsensusu nigdy nie można zmienić.

Uczestnik akceptujący oferenta | | | | | | | X--------->|->|->| | | Przygotuj(1) |<--------X--X--X | | Obietnica(1,{null,null,null}) x--------->|->| | | | Akceptuj!(1,V1) | | X--X--------->|->| Zaakceptowano(1,V1)! | | | | | | !! PONIEŚĆ PORAŻKĘ !! | | | | | | X--------->|->| | | Przygotuj(2) |<--------X--X | | Obietnica(2,{V1,null}) X------>|->|->| | | Zaakceptuj!(2,V1) |<------X--X--X------>|->| Zaakceptowano(2,V1) | | | | | |

Multi-Paxos

Typowe wdrożenie Paxos wymaga ciągłego strumienia uzgodnionych wartości działających jako polecenia dla rozproszonej maszyny stanów. Jeśli każde polecenie jest wynikiem pojedynczego wystąpienia podstawowego protokołu Paxos , spowodowałoby to znaczne obciążenie.

Jeśli lider jest względnie stabilny, faza 1 staje się zbędna. W ten sposób możliwe jest pominięcie fazy 1 dla przyszłych wystąpień protokołu z tym samym liderem.

Aby to osiągnąć, numer rundy I jest dołączany wraz z każdą wartością, która jest zwiększana w każdej rundzie przez tego samego Lidera. Multi-Paxos zmniejsza bezawaryjne opóźnienie wiadomości (propozycja do nauki) z 4 opóźnień do 2 opóźnień.

Graficzne przedstawienie przepływu wiadomości w Multi-Paxos

Multi-Paxos bez awarii

Na poniższym diagramie pokazano tylko jedną instancję (lub „wykonanie”) podstawowego protokołu Paxos, z początkowym Liderem (Proponującym). Zauważ, że Multi-Paxos składa się z kilku instancji podstawowego protokołu Paxos.

Klient Proponujący Akceptujący Uczestnik | | | | | | | --- Pierwsze żądanie --- X-------->| | | | | | Żądanie | X--------->|->|->| | | Przygotuj(N) | |<---------X--X--X | | Obietnica(N,I,{Va,Vb,Vc}) | X--------->|->|->| | | Akceptuj!(N,I,V) | |<---------X--X--X------>|->| Zaakceptowano(N,I,V) |<---------------------------------X--X Odpowiedź | | | | | | |

gdzie V = ostatni z (Va, Vb, Vc).

Multi-Paxos, gdy można pominąć fazę 1

W tym przypadku kolejne instancje podstawowego protokołu Paxos (reprezentowane przez I+1 ) używają tego samego lidera, więc faza 1 (z tych kolejnych instancji podstawowego protokołu Paxos), która składa się z podfaz Przygotowania i Obietnicy, jest pomijany. Należy pamiętać, że Lider powinien być stabilny, tzn. nie powinien się zawieszać ani zmieniać.

Klient Proponujący Akceptujący Uczestnik | | | | | | | --- Śledzenie żądań --- X-------->| | | | | | Żądanie | X--------->|->|->| | | Zaakceptuj!(N,I+1,W) | |<---------X--X--X------>|->| Zaakceptowano(N,I+1,W) |<---------------------------------X--X Odpowiedź | | | | | | |

Multi-Paxos, gdy role są zwinięte

Powszechne wdrażanie Multi-Paxos polega na zwróceniu roli Proponujących, Akceptujących i Uczących się do „Serwerów”. Ostatecznie więc są tylko „klienci” i „serwery”.

Poniższy diagram przedstawia pierwszą „instancję” podstawowego protokołu Paxos, w której role Wnioskodawcy, Akceptanta i Ucznia są zwinięte do jednej roli, zwanej „Serwerem”.

Serwery klienckie | | | | --- Pierwsze żądanie --- X-------->| | | Żądanie | X->|->| Przygotuj(N) | |<-X--X Obietnica(N, I, {Va, Vb}) | X->|->| Akceptuj!(N, I, Vn) | X<>X<>X Zaakceptowano(N, I) |<--------X | | odpowiedź | | | |

Multi-Paxos, gdy role się załamują, a lider jest stabilny

W kolejnych instancjach podstawowego protokołu Paxos, z tym samym liderem co w poprzednich instancjach podstawowego protokołu Paxos, można pominąć fazę 1.

Serwery klienckie X-------->| | | Żądanie | X->|->| Zaakceptuj!(N,I+1,W) | X<>X<>X Zaakceptowano(N,I+1) |<--------X | | odpowiedź | | | |

optymalizacje

Można przeprowadzić szereg optymalizacji, aby zmniejszyć liczbę wymienianych komunikatów, poprawić wydajność protokołu itp. Kilka z tych optymalizacji przedstawiono poniżej.

„Możemy zapisywać wiadomości kosztem dodatkowego opóźnienia wiadomości, mając jednego wyróżnionego ucznia, który informuje pozostałych uczniów, gdy dowie się, że wybrano wartość. Akceptanci wysyłają następnie Zaakceptowane wiadomości tylko do wyróżniającego się ucznia. W większości aplikacji role lidera i wyróżniającego się ucznia są wykonywane przez ten sam procesor.

„Lider może wysłać swoje Przygotuj i Zaakceptuj! wiadomości tylko do kworum akceptujących. Tak długo, jak wszyscy akceptujący w tym kworum pracują i mogą komunikować się z liderem i uczniami, osoby akceptujące spoza kworum nie muszą nic robić.

„Akceptanci nie dbają o wybraną wartość. Po prostu odpowiadają na komunikaty Przygotuj i Zaakceptuj!, aby zapewnić, że pomimo niepowodzeń można wybrać tylko jedną wartość. Jeśli jednak akceptant dowie się, jaka wartość została wybrana, może przechowywać wartość w stabilnym magazynie i usuń wszelkie inne zapisane tam informacje.Jeśli akceptant otrzyma później komunikat Przygotuj lub Zaakceptuj! wiadomości, zamiast wykonywać swoją akcję Faza1b lub Faza2b, może po prostu poinformować lidera o wybranej wartości.

„Zamiast wysyłać wartość v, lider może wysłać skrót v do niektórych akceptantów w swoich komunikatach Akceptuj!. Uczeń dowie się, że v jest wybrany, jeśli otrzyma komunikaty Zaakceptowane dla v lub jego skrót od kworum akceptantów, i co najmniej jedna z tych wiadomości zawiera zamiast skrótu v. Jednak lider może otrzymać Obietnicę komunikaty, które przekazują mu hash wartości v, której musi użyć w swojej akcji Fazy 2a, bez podawania rzeczywistej wartości v. Jeśli tak się stanie, lider nie może wykonać swojej akcji Fazy 2a, dopóki nie skomunikuje się z jakimś procesem, który zna v”

. Wnioskodawca może wysłać swoją propozycję tylko do lidera, a nie do wszystkich koordynatorów. Wymaga to jednak, aby wynik algorytmu wyboru lidera został przekazany oferentom, co może być kosztowne. Może więc lepiej pozwolić wnioskodawcy na przesłanie wniosku do wszystkich koordynatorów. (W takim przypadku tylko sami koordynatorzy muszą wiedzieć, kto jest liderem.)

„Zamiast wysyłania zaakceptowanych wiadomości przez każdego ucznia do każdego ucznia, osoby akceptujące mogą wysyłać swoje zaakceptowane wiadomości do lidera, a lider może informować uczniów, kiedy wartość została wybrana. Powoduje to jednak dodatkowe opóźnienie wiadomości. Na koniec

obserwuj tę fazę 1 jest zbędny w rundzie 1. Lider rundy 1 może rozpocząć rundę wysyłając Akceptuj ! wiadomość o dowolnej proponowanej wartości."

Tanie Paxos

Cheap Paxos rozszerza podstawowy Paxos , aby tolerował awarie F z procesorami głównymi F+1 i procesorami pomocniczymi F poprzez dynamiczną rekonfigurację po każdej awarii.

To zmniejszenie wymagań dotyczących procesora odbywa się kosztem żywotności; jeśli zbyt wiele głównych procesorów ulegnie awarii w krótkim czasie, system musi zostać zatrzymany, dopóki procesory pomocnicze nie będą mogły ponownie skonfigurować systemu. W okresach stabilnych procesory pomocnicze nie biorą udziału w protokole.

„Przy tylko dwóch procesorach p i q jeden procesor nie jest w stanie odróżnić awarii drugiego procesora od awarii medium komunikacyjnego. Potrzebny jest trzeci procesor. Jednak ten trzeci procesor nie musi uczestniczyć w wyborze sekwencji poleceń. Musi podjąć działanie tylko w przypadku awarii p lub q, po czym nic nie robi, podczas gdy p lub q nadal samodzielnie obsługuje system.Trzeci procesor może być zatem mały/wolny/tani lub procesor przeznaczony głównie do innych zadań ”.

Przepływ wiadomości: Tanie Multi-Paxos

Przykład dotyczący trzech akceptorów głównych, jednego akceptora pomocniczego i kworum wynoszącego trzy, pokazujący awarię jednego głównego procesora i późniejszą rekonfigurację:

{ Akceptujący } Proponujący Główny pomocniczy uczestnik | | | | | | -- Faza 2 -- X----------->|->|->| | | Akceptuj!(N,I,V) | | | ! | | --- PONIEŚĆ PORAŻKĘ! --- |<-----------X--X--------------->| Zaakceptowano(N,I,V) | | | | | -- Wykryto awarię (tylko 2 akceptowane) -- X----------->|->|------->| | Akceptuj!(N,I,V) (prześlij ponownie, włącz Aux) |<-----------X--X--------X------> | Zaakceptowano(N,I,V) | | | | | -- Rekonfiguracja : Kworum = 2 -- X----------->|->| | | Akceptuj!(N,I+1,W) (Aux nie bierze udziału) |<------------X--X--------------->| Zaakceptowano(N,I+1,W) | | | | |

Szybki Paxos

Fast Paxos uogólnia Basic Paxos , aby zredukować opóźnienia wiadomości od końca do końca. W Basic Paxos opóźnienie komunikatu od żądania klienta do uczenia wynosi 3 opóźnienia komunikatu. Fast Paxos dopuszcza 2 opóźnienia wiadomości, ale wymaga, aby (1) system składał się z 3f+1 akceptorów, aby tolerować do f błędów (zamiast klasycznego 2f+1) oraz (2) aby Klient wysyłał swoje żądanie do wielu miejsc docelowych .

Intuicyjnie, jeśli lider nie ma żadnej wartości do zaproponowania, klient może wysłać Akceptuj ! wiadomość bezpośrednio do Akceptantów. Akceptanci reagowaliby tak jak w Basic Paxos, wysyłając Zaakceptowane wiadomości do lidera i każdego Ucznia osiągając dwa opóźnienia wiadomości od Klienta do Ucznia.

Jeśli lider wykryje kolizję, rozwiązuje ją, wysyłając polecenie Akceptuj! wiadomości do nowej rundy, które są Akceptowane jak zwykle. Ta skoordynowana technika odzyskiwania wymaga czterech opóźnień wiadomości od Klienta do Uczestnika.

Ostateczna optymalizacja ma miejsce, gdy lider określa z góry technikę odzyskiwania, umożliwiając Akceptantom samodzielne wykonanie odzyskiwania po kolizji. W związku z tym nieskoordynowane usuwanie kolizji może wystąpić w przypadku trzech opóźnień komunikatów (i tylko dwóch opóźnień komunikatów, jeśli wszyscy uczniowie są również akceptantami).

Przepływ wiadomości: Fast Paxos, bez konfliktów

Lider Klienta Akceptant Uczeń | | | | | | | | | X--------->|->|->|->| | | Dowolny(N,I,Odzyskiwanie) | | | | | | | | X---->|->|->|->| | | Zaakceptuj!(N,I,W) | |<---------X--X--X--X------>|->| Zaakceptowano(N,I,W) |<-----------------------------------X--X Odpowiedź(W) | | | | | | | |

Przepływ wiadomości: Fast Paxos, sprzeczne propozycje

Sprzeczne propozycje ze skoordynowanym odzyskiwaniem. Uwaga: protokół nie określa sposobu obsługi odrzuconego żądania klienta.

Lider Klienta Akceptant Uczeń | | | | | | | | | | | | | | | | | | | | | | | | | | | !! Równoległe sprzeczne propozycje | | | | | | | | | !! otrzymane w innej kolejności | | | | | | | | | !! przez Akceptantów | X--------------?|-?|-?|-?| | | Zaakceptuj!(N,I,V) X-----------------?|-?|-?|-?| | | Zaakceptuj!(N,I,W) | | | | | | | | | | | | | | | | | | !! Akceptanci nie zgadzają się co do wartości | | |<-------X--X->|->|----->|->| Zaakceptowano(N,I,V) | | |<-------|<-|<-X--X----->|->| Zaakceptowano(N,I,W) | | | | | | | | | | | | | | | | | | !! Wykryj kolizję i odzyskaj | | X------->|->|->|->| | | Zaakceptuj!(N+1,I,W) | | |<-------X--X--X--X----->|->| Zaakceptowano(N+1,I,W) |<---------------------------------X--X Odpowiedź (W) | | | | | | | | |

Sprzeczne propozycje z nieskoordynowanym odzyskiwaniem.

Lider Klienta Akceptant Uczeń | | | | | | | | | | | X------->|->|->|->| | | Dowolny(N,I,Odzyskiwanie) | | | | | | | | | | | | | | | | | | !! Równoległe sprzeczne propozycje | | | | | | | | | !! otrzymane w innej kolejności | | | | | | | | | !! przez Akceptantów | X--------------?|-?|-?|-?| | | Zaakceptuj!(N,I,V) X-----------------?|-?|-?|-?| | | Zaakceptuj!(N,I,W) | | | | | | | | | | | | | | | | | | !! Akceptanci nie zgadzają się co do wartości | | |<-------X--X->|->|----->|->| Zaakceptowano(N,I,V) | | |<-------|<-|<-X--X----->|->| Zaakceptowano(N,I,W) | | | | | | | | | | | | | | | | | | !! Wykryj kolizję i odzyskaj | | |<-------X--X--X--X----->|->| Zaakceptowano(N+1,I,W) |<---------------------------------X--X Odpowiedź (W) | | | | | | | | |

Przepływ wiadomości: Fast Paxos z nieskoordynowanym odzyskiwaniem, zwinięte role

(połączone role akceptanta/ucznia)

Serwery klienckie | | | | | | | | X->|->|->| Dowolny(N,I,Odzyskiwanie) | | | | | | | | | | | | !! Równoległe sprzeczne propozycje | | | | | | !! otrzymane w innej kolejności | | | | | | !! przez Serwery | X--------?|-?|-?|-?| Zaakceptuj!(N,I,V) X-----------?|-?|-?|-?| Zaakceptuj!(N,I,W) | | | | | | | | | | | | !! Serwery nie zgadzają się co do wartości | | X<>X->|->| Zaakceptowano(N,I,V) | | |<-|<-X<>X Zaakceptowano(N,I,W) | | | | | | | | | | | | !! Wykryj kolizję i odzyskaj | | X<>X<>X<>X Zaakceptowano(N+1,I,W) |<-----------X--X--X--X Odpowiedź(W) | | | | | |

Uogólniony Paxos

Uogólniony konsensus bada związek między operacjami replikowanej maszyny stanów a protokołem konsensusu, który ją implementuje. Główne odkrycie dotyczy optymalizacji Paxos, gdy sprzeczne propozycje można zastosować w dowolnej kolejności. tj. gdy proponowane operacje są operacjami przemiennymi dla maszyny stanowej. W takich przypadkach obie sprzeczne operacje mogą zostać zaakceptowane, unikając opóźnień wymaganych do rozwiązania konfliktów i ponownego zaproponowania odrzuconych operacji.

Ta koncepcja jest dalej uogólniana na stale rosnące sekwencje operacji przemiennych, z których niektóre są znane jako stabilne (a zatem mogą być wykonywane). Protokół śledzi te sekwencje, zapewniając, że wszystkie proponowane operacje jednej sekwencji są ustabilizowane, zanim pozwoli na to, aby jakakolwiek operacja niezgodna z nimi stała się stabilna.

Przykład

Aby zilustrować uogólniony Paxos, poniższy przykład pokazuje przepływ komunikatów między dwoma współbieżnie działającymi klientami i replikowaną maszyną stanów realizującą operacje odczytu/zapisu w dwóch odrębnych rejestrach A i B.

Tabela przemienności
	Czytać)	Napisać)	Odczyt (B)	Napisz (B)
Odczyt(A)
Zapis(A)
Odczyt(B)
Zapis(B)

Zauważ, że w tej tabeli wskazuje operacje, które są nieprzemienne.

Możliwa sekwencja operacji:

<1:Odczyt(A), 2:Odczyt(B), 3:Zapis(B), 4:Odczyt(B), 5:Odczyt(A), 6:Zapis(A)>

Ponieważ 5:Read(A) dojeżdża zarówno z 3:Write(B) jak i 4:Read(B) , jedna możliwa permutacja równoważna poprzedniej kolejności jest następująca:

<1:Odczyt(A), 2:Odczyt(B), 5:Odczyt(A), 3:Zapis(B), 4:Odczyt(B), 6:Zapis(A)>

W praktyce dojazdy występują tylko wtedy, gdy operacje są proponowane jednocześnie.

Przepływ wiadomości: uogólniony Paxos (przykład)

Nie pokazano odpowiedzi. Uwaga: skróty komunikatów różnią się od poprzednich przepływów komunikatów ze względu na specyfikę protokołu, patrz pełna dyskusja.

Lider Klienta Akceptant Uczeń | | | | | | | | !! Nowy lider rozpoczyna rundę | | X----->|->|->| | | Przygotuj(N) | | |<-----X- X- X | | Obietnica(N,null) | | X----->|->|->| | | Faza2Start(N,null) | | | | | | | | | | | | | | | | !! Równoczesne propozycje dojazdów | X------- ?|----?|-?|-?| | | Zaproponuj(OdczytA) X-----------?|----?|-?|-?| | | Zaproponuj(OdczytB) | | X------X-------------->|->| Zaakceptowano (N, ) | | |<--------X--X-------->|->| Zaakceptowano (N, ) | | | | | | | | | | | | | | | | !! Brak konfliktu, obie akceptowane | | | | | | | | stabilny = | | | | | | | | | | | | | | | | !! Równoległe sprzeczne propozycje X-----------?|----?|-?|-?| | | Zaproponować( ) | X--------?|-----?|-?|-?| | | Zaproponuj(OdczytB) | | | | | | | | | | X------X-------------->|->| Zaakceptowano (N, . ) | | |<--------X--X-------->|->| Zaakceptowano (N, . ) | | | | | | | | | | | | | | | | !! Wykryto konflikt, lider wybiera | | | | | | | | porządek przemienny: | | | | | | | | V = | | | | | | | | | | X----->|->|->| | | Faza2Start(N+1,V) | | |<-----X- X- X-------->|->| Zaakceptowano(N+1,V) | | | | | | | | stabilny = . | | | | | | | | | | | | | | | | | | | | | | | | !! Więcej sprzecznych propozycji X-----------?|----?|-?|-?| | | Zaproponuj(ZapiszA) | X--------?|-----?|-?|-?| | | Zaproponuj(OdczytA) | | | | | | | | | | X------X-------------->|->| Zaakceptowany(N+1, . ) | | |<--------X- X-------->|->| Zaakceptowany(N+1, . ) | | | | | | | | | | | | | | | | !! Lider wybiera kolejność: | | | | | | | | W = | | | | | | | | | | X----->|->|->| | | Faza2Start(N+2,W) | | |<-----X- X- X-------->|->| Zaakceptowano(N+2,W) | | | | | | | | stabilny = . | | | | | | | | . | | | | | | | | | | | | | | | |

Wydajność

Powyższy przepływ komunikatów pokazuje nam, że Generalized Paxos może wykorzystać semantykę operacji, aby uniknąć kolizji, gdy zawiedzie spontaniczne uporządkowanie sieci. Dzięki temu protokół jest w praktyce szybszy niż Fast Paxos. Jednak w przypadku kolizji Generalized Paxos potrzebuje dwóch dodatkowych podróży w obie strony, aby odzyskać siły. Sytuację tę ilustrują operacje WriteB i ReadB w powyższym schemacie.

W ogólnym przypadku takie podróże w obie strony są nieuniknione i wynikają z faktu, że podczas rundy można przyjąć wiele poleceń. To sprawia, że protokół jest droższy niż Paxos, gdy konflikty są częste. Mamy nadzieję, że możliwe są dwa możliwe udoskonalenia Generalized Paxos, aby skrócić czas regeneracji.

Po pierwsze, jeśli koordynator jest częścią każdego kworum akceptantów (mówi się, że runda N jest wyśrodkowana ), a następnie, aby dojść do siebie w rundzie N+1 po kolizji w rundzie N, koordynator pomija fazę 1 i proponuje w fazie 2 kolejność, którą zaakceptował jako ostatnią podczas rundy N. Zmniejsza to koszt powrotu do zdrowia do jednej podróży w obie strony.
Po drugie, jeśli obie rundy N i N+1 korzystają z unikalnego i identycznego wyśrodkowanego kworum, gdy akceptor wykryje kolizję w rundzie N, spontanicznie proponuje w rundzie N+1 sekwencję, w której obie (i) sekwencje zaakceptowane w rundzie N są sufiksowane przez koordynator i (ii) największy niekonfliktowy prefiks, który zaakceptował w rundzie N. Na przykład, jeśli koordynator i akceptant zaakceptowali odpowiednio w rundzie N I , akceptant zaakceptuje spontanicznie w rundzie N+1. W tej odmianie kosztem odzyskiwania jest opóźnienie pojedynczego komunikatu, co jest oczywiście optymalne. Zauważ tutaj, że użycie unikalnego kworum w rundzie nie szkodzi żywotności. Wynika to z faktu, że każdy proces w tym kworum jest kworum odczytu dla fazy przygotowania następnych rund.

bizantyjski Paxos

Paxos można również rozszerzyć o wspieranie arbitralnych niepowodzeń uczestników, w tym kłamstwa, fabrykowania wiadomości, zmowy z innymi uczestnikami, selektywnego nieuczestniczenia itp. Tego typu niepowodzenia nazywane są niepowodzeniami bizantyjskimi , od rozwiązania spopularyzowanego przez Lamporta.

Bizantyjski Paxos wprowadzony przez Castro i Liskov dodaje dodatkową wiadomość (Verify), która ma na celu rozpowszechnianie wiedzy i weryfikację działań innych procesorów:

Przepływ wiadomości: bizantyjski Multi-Paxos, stan ustalony

Klient Proponujący Akceptujący Uczestnik | | | | | | | X-------->| | | | | | Żądanie | X--------->|->|->| | | Akceptuj!(N,I,V) | | X<>X<>X | | Sprawdź(N,I,V) - ROZSYŁANIE | |<---------X--X--X------>|->| Zaakceptowano(N,V) |<---------------------------------X--X Odpowiedź(V) | | | | | | |

Szybki bizantyjski Paxos wprowadzony przez Martina i Alvisiego eliminuje to dodatkowe opóźnienie, ponieważ klient wysyła polecenia bezpośrednio do akceptantów.

Uwaga Zaakceptowana wiadomość w Fast Byzantine Paxos jest wysyłana do wszystkich Akceptantów i wszystkich Uczniów, podczas gdy Fast Paxos wysyła Zaakceptowane wiadomości tylko do Uczniów):

Przepływ wiadomości: szybki bizantyjski Multi-Paxos, stan ustalony

Uczestnik akceptujący klienta | | | | | | X----->|->|->| | | Akceptuj!(N,I,V) | X<>X<>X------>|->| Zaakceptowano(N,I,V) - BROADCAST |<---------------------------------X--X Odpowiedź(V) | | | | | |

Scenariusz awarii jest taki sam dla obu protokołów; Każdy uczeń czeka na otrzymanie identycznych wiadomości F+1 od różnych akceptantów. Jeśli tak się nie stanie, sami Akceptanci również będą tego świadomi (ponieważ wymieniali między sobą komunikaty w rundzie rozgłoszeniowej), a właściwi Akceptanci ponownie wyemitują uzgodnioną wartość:

Przepływ wiadomości: Fast Bizantine Multi-Paxos, awaria

Uczestnik akceptujący klienta | | | ! | | !! Jeden Akceptor jest uszkodzony X----->|->|->! | | Akceptuj!(N,I,V) | X<>X<>X------>|->| Zaakceptowano(N,I,{V,W}) - BROADCAST | | | ! | | !! Uczniowie otrzymują 2 różne polecenia | | | ! | | !! Prawidłowo Akceptanci zauważają błąd i wybierają | X<>X<>X------>|->| Zaakceptowano(N,I,V) - BROADCAST |<---------------------------------X--X Odpowiedź(V) | | | ! | |

Dostosowanie Paxos do sieci RDMA

Wraz z pojawieniem się bardzo szybkich, niezawodnych sieci centrów danych, które obsługują zdalne DMA ( RDMA ), pojawiło się duże zainteresowanie optymalizacją Paxos w celu wykorzystania odciążania sprzętu, w którym karta interfejsu sieciowego i routery sieciowe zapewniają niezawodność i kontrolę przeciążenia w warstwie sieci, uwalniając CPU hosta do innych zadań. Biblioteka Derecho C++ Paxos to implementacja Paxos typu open source, która eksploruje tę opcję.

Derecho oferuje zarówno klasyczny Paxos, z trwałością danych w pełnych sekwencjach zamykania/ponownego uruchamiania, jak i pionowy Paxos (atomowa multiemisja), do replikacji w pamięci i synchronizacji maszyny stanu. Protokoły Paxos używane przez Derecho musiały zostać dostosowane, aby zmaksymalizować asynchroniczne przesyłanie danych i usunąć inne źródła opóźnień na ścieżce krytycznej lidera. Dzięki temu Derecho może utrzymać pełną dwukierunkową szybkość transmisji danych RDMA. W przeciwieństwie do tego, chociaż tradycyjne protokoły Paxos można migrować do sieci RDMA, po prostu mapując operacje wysyłania wiadomości do natywnych operacji RDMA, pozostawia to opóźnienia w obie strony na ścieżce krytycznej. W szybkich sieciach RDMA nawet niewielkie opóźnienia mogą być wystarczająco duże, aby uniemożliwić wykorzystanie pełnego potencjału przepustowości.

Wykorzystanie produkcyjne Paxos

Google używa algorytmu Paxos w swojej usłudze rozproszonej blokady Chubby , aby zachować spójność replik w przypadku awarii. Chubby jest używany przez Bigtable , który jest obecnie w produkcji w Google Analytics i innych produktach.
Google Spanner i Megastore używają algorytmu Paxos wewnętrznie.
Usługa replikacji OpenReplica wykorzystuje Paxos do utrzymywania replik dla systemu otwartego dostępu, który umożliwia użytkownikom tworzenie obiektów odpornych na błędy. Zapewnia wysoką wydajność dzięki jednoczesnym rundom i elastyczność dzięki dynamicznym zmianom członkostwa.
IBM rzekomo używa algorytmu Paxos w swoim produkcie IBM SAN Volume Controller do implementacji odpornej na awarie maszyny wirtualnej ogólnego przeznaczenia, używanej do uruchamiania komponentów konfiguracyjnych i kontrolnych usług wirtualizacji pamięci masowej oferowanych przez klaster. ( Oryginalny artykuł badawczy MIT i IBM )
Microsoft używa Paxos w usłudze zarządzania klastrami Autopilot firmy Bing oraz w Windows Server Failover Clustering.
WANdisco wdrożyło Paxos w swojej technologii replikacji Active-Active DConE.
XtreemFS wykorzystuje oparty na Paxos algorytm negocjacji dzierżawy do odpornej na błędy i spójnej replikacji danych plików i metadanych.
Heroku używa Doozerda , który implementuje Paxos dla swojego spójnego rozproszonego magazynu danych.
Ceph używa Paxos jako części procesów monitorowania, aby uzgodnić, które OSD działają iw klastrze.
Clustrix używa Paxos do rozstrzygania transakcji rozproszonych .
Neo4j HA implementuje Paxos, zastępując Apache ZooKeeper z wersji 1.9
Apache Cassandra NoSQL używa Paxos tylko do funkcji lekkich transakcji
Amazon Elastic Container Services używa Paxos do utrzymania spójnego widoku stanu klastra
Amazon DynamoDB używa algorytmu Paxos do wyboru lidera i osiągania konsensusu .

Zobacz też

Linki zewnętrzne