Paxos w swoim sercu jest bardzo prosty

algorytm Paxos, przedstawiony w prostym języku angielskim, jest bardzo prosty. — Leslie Lamport 2001

spróbuję wyjaśnić pojedynczy dekret Paxos w sposób, miejmy nadzieję, że jest łatwy do zrozumienia.

do dziś, IMO, Wykład Johna Ousterhouta na temat Paxos nadal jest najlepszy. Materiał w tym poście w dużym stopniu zapożycza z wykładu Prof. Ousterhouta. Za zgodą Johna Ousterhouta, użyłem kilku jego slajdów, aby wyjaśnić Paxos.

konsensus

Paxos jako protokół próbuje rozwiązać problem konsensusu. Mówiąc po angielsku, próbuje rozwiązać problem, że system wybierze tylko jedną wartość, gdy jeden lub więcej serwerów może zaproponować inną wartość(wartości).

przykład prawdziwego świata byłby czymś w rodzaju wyborów. Ludzie mogą głosować na innego prezydenta. Ale tylko jeden prezydent może być wybrany.

Paxos jest przeznaczony do radzenia sobie z fail-stop/crash (non-Byzantine) i opóźnienia/utraty wiadomości. Istnieje również wymóg żywotności, aby pewna proponowana wartość była ostatecznie wybierana tak długo, jak działa większość serwerów. Ma to na celu uniknięcie nieciekawych rozwiązań, takich jak never-accept-any-value. Jeśli nic nie zrobisz, nie zrobisz nic złego. Podobnie, nie chcesz, aby więcej niż jeden prezydent został wybrany i chcesz mieć prezydenta w końcu tak długo, jak ludzie głosują.

na marginesie, szczerze mówiąc, myślę, że próba wykorzystania głosowania jako przykładu do wyjaśnienia Paxos w oryginalnym dokumencie Parlamentu w niepełnym wymiarze godzin jest bardzo naturalna. Ale jakoś nie zadziałało zbyt dobrze. Lamport również sam powiedział w wywiadzie, że jest to totalna porażka, co jest niefortunne.

pojedynczy akceptor

Screen-Shot-2018-11-13-at-11.17.43-PM
w przypadku klastra serwerów 2F+1, co się stanie, jeśli zawsze zrobimy jedno określone pole, aby zaakceptować propozycje. I każda propozycja zaakceptowana przez tę skrzynkę zostanie wybrana.

problem w tym podejściu polega na tym, że pojedynczy down box może sprawić, że usługa będzie niedostępna. Ale wymóg mówi, że usługa musi być uruchomiona tak długo, jak działa większość serwerów (w tym przypadkuF+1).

zauważ, że jest to efektywnie pojedynczy model replikacji. I właśnie dlatego przestoje są nieuniknione przy replikacji master-slave.

Quorum

więc jeśli posiadanie jednego akceptora nie działa, może powinniśmy poczekać, aż wiele serwerów zaakceptuje propozycję, zanim zażądamy wybrania wartości.

ile?

jeśli akceptory są stałe i jest to <=F, ponownie, nie tolerujemy F awarii serwerów. Jeśli akceptorami mogą być dowolne serwery i jest to <=F, w klastrze serwerów 2F+1, możemy mieć dwie różne propozycje przechodzące do dwóch rozłącznych zestawów akceptorów powodujących wybranie dwóch wartości.

więc liczba akceptorów musi być >=F+1. Ponieważ mniej akceptorów tym lepiej, po prostu wybierzmy F+1. I może to być dowolny F+1 serwer w klastrze.

mamy już pewne postępy! Jeśli jakaś propozycja zostanie zaakceptowana przez serwery F+1, zostanie wybrana.

przyjmowanie propozycji

teraz zobaczmy, jak akceptanci powinni zdecydować, czy przyjąć propozycję, czy nie.

akceptujesz tylko pierwszą propozycję?
Screen-Shot-2018-11-13-at-11.17.27-PM

to by nie zadziałało, ponieważ nigdy nie możemy mieć żadnej wartości wybranej jak w powyższym przypadku. To narusza wymóg żywotności.

nie ma sensu mówić “przyjmij drugą propozycję” czy coś w tym stylu, bo nigdy nie wiadomo, czy kiedykolwiek będzie druga propozycja.

więc musimy zaakceptować pierwszą propozycję, ale może nie tylko pierwszą.

przyjmujesz wszystkie propozycje?
Screen-Shot-2018-11-13-at-11.31.11-PM
naruszałoby to wymagania bezpieczeństwa, ponieważ możemy w końcu wybrać więcej niż jedną wartość.

Core

oto trik, który moim zdaniem jest najciekawszą częścią Paxos.

po wybraniu wartości przyszłe propozycje muszą zaproponować taką samą wartość.

oznacza to, że potrzebny byłby protokół dwufazowy. W pierwszej fazie wnioskodawcy muszą dowiedzieć się, czy jakakolwiek wartość została już wybrana. I zaproponować w drugiej fazie.

jeśli jesteś weteranem systemu rozproszonego, musisz już zauważyć jedno słowo kluczowe w poprzedniej instrukcji. I to jest “przyszłość”. Sprawdziłem czas i porządek wcześniej. System rozproszony polega na zamawianiu. “przyszłość” oznacza tutaj uporządkowanie (relacja happen-before). Musimy więc zamówić wszystkie propozycje. Następnie w poniższym przykładzie możemy odrzucić red, ponieważ wiemy, że blue jest wybrana, a red jest starą propozycją.

Screen-Shot-2018-11-13-at-11.39.37-PM

numer do głosowania

łatwym sposobem na zamówienie propozycji jest posiadanie unikalnego numeru do głosowania dla każdej propozycji w postaci <seq_id, server_id>. W celu zagwarantowania zamówienia, seq_id musi być utrzymane cross crash / restart. Musi więc być trwale przechowywany lokalnie.

Paxos

teraz wszyscy jesteśmy skonfigurowani do opisania prawdziwego dwufazowego protokołu Paxos. Pierwszą fazę nazwiemy fazą prepare, a drugą fazą accept. prepare Faza służy dwóm celom w jednej podróży w obie strony.

  1. dowiedz się o dowolnej wartości, która już została wybrana
  2. uniemożliwiaj akceptantom akceptowanie starszych propozycji (bardzo podobnie jak krok rezerwowy w dwufazowym zatwierdzaniu)

Screen-Shot-2018-11-13-at-11.53.52-PM
akceptor musi trwale przechowywać kilka rzeczy

  • minProposal
  • acceptedProposal
  • acceptedValue
    odnotuj, ĹĽe zamiast” nadawaÄ ‡ do wszystkich serwerĂłw”, powinno byÄ ‡ “nadawaÄ ‡ do co najmniej serwerĂłw F+1”. A wnioskodawca powinien wysłać wiadomość accept na ten sam zestaw serwerów F+1, co w fazie przygotowania.

przyjrzyjmy się uważnie każdemu etapowi.

Faza przygotowania

w tej fazie wnioskodawca stara się uzyskać od akceptanta obietnicę, że nie przyjmie żadnych propozycji starszych niż jego. Jednocześnie akceptanci poinformują wnioskodawców, jakie wartości zostały już przyjęte do tej pory.

w krokach 3 i 4 wnioskodawca zmieni swój wniosek na najnowszy zaakceptowany wniosek od akceptantów, z którymi rozmawiał. Wydaje się to być bardzo konserwatywne, ponieważ można dostać zaakceptowaną propozycję, która nie jest wybrana, a wnioskodawca kończy rezygnację z propozycji. Ale to w porządku, ponieważ zależy nam tylko na konsensusie. W pierwszej fazie trudno jest wnioskującemu dowiedzieć się, czy wybrano wartość, czy nie. Zaakceptowana wartość może nie zostać wybrana. Ale wybrana wartość musi zostać zaakceptowana przez większość serwerów! A akceptanci odrzucają starsze propozycje (krok 6). Przy dwóch niezmiennikach wiemy, że ostatni zaakceptowany wniosek powrócił do wniosku w fazie pierwszej albo został już wybrany, albo w tej chwili nie wybrano żadnej wartości. Tak czy inaczej, można bezpiecznie zaproponować tę wartość.

po co śledzić minProposal?
w fazie przygotowania mogą być dwie propozycje wyścigowe, a nic nie zostało jeszcze zaakceptowane. Oznacza to, że obaj przejdą do fazy akceptacji. Dzięki całkowitemu zamówieniu wszystkich propozycji i wymaganiu F+1, co najmniej jeden akceptant zobaczy nowszą propozycję i odrzuci wiadomość accept z przegranej / starszej propozycji. Niezmiennikiem jest tutaj minProposal >= acceptedProposal.

Screen-Shot-2018-11-14-at-12.28.11-AM

jest to prawdopodobnie najciekawszy przypadek, ponieważ drugi wnioskodawca nie widział poprzedniej zaakceptowanej wartości i nie wybrano wartości w fazie przygotowania. W takim przypadku zostanie wysłana accept(Y) na inne serwery. Ponieważ S3 obiecał, że przyjmie propozycje dopiero później niż 4.5, odrzuca X. Jeśli nie będziemy śledzić minProposal, X zostanie zaakceptowane przez S3. Wtedy zarówno X, jak i Y zostałyby zaakceptowane przez trzy serwery i uznane za wybrane, co narusza wymagania bezpieczeństwa.

proszę bardzo. To jest pojedynczy dekret Paxos. To powiedziawszy, wdrożenie Paxos okazało się bardzo trudne.

  1. Paxos made simple https://lamport.azurewebsites.net/pubs/paxos-simple.pdf ↩︎

  2. Sejm na pół etatu https://lamport.azurewebsites.net/pubs/lamport-paxos.pdf ↩︎

  3. Paxos made live https://www.cs.utexas.edu/users/lorenzo/corsi/cs380d/papers/paper2-1.pdf ↩︎

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany.