Wyobraźmy sobie więc. W pokoju jest zamkniętych 5 kotów i aby obudzić właściciela, muszą to wszyscy między sobą uzgodnić, ponieważ drzwi mogą otworzyć tylko wtedy, gdy pięć z nich się o nie opiera. Jeśli jeden z kotów jest kotem Schrödingera, a pozostałe koty nie wiedzą o jego decyzji, pojawia się pytanie: „Jak oni mogą to zrobić?”
W tym artykule w prosty sposób opowiem Państwu o teoretycznym składniku świata systemów rozproszonych i zasadach ich działania. Przyjrzę się także powierzchownie głównej idei leżącej u podstaw Paxos.
Kiedy programiści korzystają z infrastruktur chmurowych, różnych baz danych i pracują w klastrach składających się z dużej liczby węzłów, mają pewność, że dane będą kompletne, bezpieczne i zawsze dostępne. Ale gdzie są gwarancje?
Zasadniczo gwarancje, które posiadamy, są gwarancjami dostawcy. W dokumentacji są one opisane następująco: „Ta usługa jest w miarę niezawodna, ma określoną SLA, nie martw się, wszystko będzie działać dystrybucyjnie tak, jak tego oczekujesz.”
Zwykle wierzymy w najlepsze, bo mądrzy goście z dużych firm zapewniali nas, że wszystko będzie dobrze. Nie zadajemy sobie pytania: dlaczego w ogóle to może działać? Czy istnieje jakieś formalne uzasadnienie poprawności działania takich systemów?
Niedawno poszedłem do i był bardzo zainspirowany tym tematem. Wykłady w szkole bardziej przypominały zajęcia z rachunku różniczkowego niż coś związanego z systemami komputerowymi. Ale właśnie w ten sposób pewnego razu udowodniono najważniejsze algorytmy, z których korzystamy na co dzień, nawet o tym nie wiedząc.
Większość nowoczesnych systemów rozproszonych wykorzystuje algorytm konsensusu Paxos i jego różne modyfikacje. Najfajniejsze jest to, że ważność i w zasadzie samą możliwość istnienia tego algorytmu można udowodnić po prostu za pomocą długopisu i papieru. W praktyce algorytm stosowany jest w dużych systemach działających na ogromnej liczbie węzłów w chmurach.
Lekka ilustracja tego, co zostanie omówione dalej: zadanie dwóch generałówSpójrzmy na rozgrzewkę .
Mamy dwie armie – czerwoną i białą. W oblężonym mieście stacjonują białe oddziały. Oddziały czerwone dowodzone przez generałów A1 i A2 rozmieszczone są po dwóch stronach miasta. Zadaniem rudych jest zaatakowanie białego miasta i zwycięstwo. Jednak armia każdego czerwonego generała z osobna jest mniejsza niż armia białej.
Warunki zwycięstwa czerwonych: obaj generałowie muszą atakować w tym samym czasie, aby mieć przewagę liczebną nad białymi. Aby to zrobić, generałowie A1 i A2 muszą dojść do porozumienia. Jeśli każdy zaatakuje osobno, rudzielcy przegrają.
Aby osiągnąć porozumienie, generałowie A1 i A2 mogą wysyłać do siebie posłańców przez terytorium białego miasta. Posłaniec może skutecznie dotrzeć do sojuszniczego generała lub zostać przechwycony przez wroga. Pytanie: czy istnieje taka sekwencja komunikacji między rudowłosymi generałami (kolejność wysyłania posłańców z A1 do A2 i odwrotnie z A2 do A1), w której mają gwarancję wyrażenia zgody na atak o godzinie X. Tutaj: gwarancje oznaczają, że obaj generałowie będą mieli jednoznaczne potwierdzenie, że sojusznik (inny generał) na pewno zaatakuje w wyznaczonym czasie X.
Załóżmy, że A1 wysyła posłańca do A2 z wiadomością: „Atakujmy dzisiaj o północy!” Generał A1 nie może zaatakować bez potwierdzenia ze strony Generała A2. Jeżeli przybył posłaniec z A1, to generał A2 wysyła potwierdzenie z komunikatem: „Tak, zabijmy dziś białych”. Ale teraz generał A2 nie wie, czy jego posłaniec przybył, czy nie, nie ma gwarancji, czy atak będzie równoczesny. Teraz Generał A2 ponownie potrzebuje potwierdzenia.
Jeśli bliżej opiszemy ich komunikację, stanie się jasne, że niezależnie od tego, ile jest cykli wymiany wiadomości, nie ma sposobu, aby zagwarantować, że obaj generałowie otrzymali wiadomości (zakładając, że którykolwiek z komunikatorów może zostać przechwycony).
Problem dwóch generałów jest świetną ilustracją bardzo prostego systemu rozproszonego, w którym istnieją dwa węzły z zawodną komunikacją. Oznacza to, że nie mamy 100% gwarancji, że są zsynchronizowane. Podobne problemy zostaną omówione dopiero w szerzej w dalszej części artykułu.
Wprowadzamy koncepcję systemów rozproszonych
System rozproszony to grupa komputerów (zwanych dalej węzłami), które mogą wymieniać wiadomości. Każdy indywidualny węzeł jest pewnego rodzaju autonomiczną jednostką. Węzeł może samodzielnie przetwarzać zadania, ale aby komunikować się z innymi węzłami, musi wysyłać i odbierać komunikaty.
Jak dokładnie realizowane są komunikaty, jakie protokoły są stosowane – w tym kontekście nas to nie interesuje. Ważne jest, aby węzły systemu rozproszonego mogły wymieniać między sobą dane poprzez wysyłanie komunikatów.
Sama definicja nie wygląda na bardzo skomplikowaną, jednak musimy wziąć pod uwagę, że system rozproszony posiada szereg atrybutów, które będą dla nas istotne.
Atrybuty systemów rozproszonych
- Konkurencja – możliwość jednoczesnego lub jednoczesnego wystąpienia zdarzeń w systemie. Co więcej, zdarzenia zachodzące w dwóch różnych węzłach będziemy uważać za potencjalnie współbieżne, o ile nie będziemy mieli jasnej kolejności występowania tych zdarzeń. Ale z reguły tego nie mamy.
- Brak zegara globalnego. Nie mamy jasnego porządku wydarzeń ze względu na brak zegara globalnego. W zwykłym świecie ludzi jesteśmy przyzwyczajeni do tego, że zegary i czas mamy absolutnie. Wszystko się zmienia, jeśli chodzi o systemy rozproszone. Nawet ultraprecyzyjne zegary atomowe mają dryf i mogą zaistnieć sytuacje, w których nie będziemy w stanie stwierdzić, które z dwóch zdarzeń miało miejsce jako pierwsze. Dlatego też nie możemy polegać na czasie.
- Niezależna awaria węzłów systemu. Jest jeszcze jeden problem: coś może pójść nie tak po prostu dlatego, że nasze węzły nie trwają wiecznie. Dysk twardy może ulec awarii, maszyna wirtualna w chmurze może zostać ponownie uruchomiona, sieć może migać, a wiadomości zostaną utracone. Co więcej, mogą wystąpić sytuacje, w których węzły działają, ale jednocześnie działają przeciwko systemowi. Ostatnia klasa problemów otrzymała nawet osobną nazwę: problem . Najpopularniejszym przykładem systemu rozproszonego, w którym występuje ten problem, jest Blockchain. Ale dzisiaj nie będziemy rozważać tej szczególnej klasy problemów. Nas będą interesować sytuacje, w których może zawieść po prostu jeden lub więcej węzłów.
- Modele komunikacji (modele przesyłania wiadomości) pomiędzy węzłami. Ustaliliśmy już, że węzły komunikują się poprzez wymianę komunikatów. Istnieją dwa dobrze znane modele przesyłania wiadomości: synchroniczny i asynchroniczny.
Modele komunikacji pomiędzy węzłami w systemach rozproszonych
Model synchroniczny – wiemy na pewno, że istnieje skończona znana delta czasu, podczas której wiadomość na pewno dotrze z jednego węzła do drugiego. Jeżeli ten czas minął i wiadomość nie dotarła, to śmiało możemy powiedzieć, że węzeł uległ awarii. W tym modelu mamy przewidywalny czas oczekiwania.
Model asynchroniczny – w modelach asynchronicznych uważamy, że czas oczekiwania jest skończony, ale nie ma takiej delty czasu, po upływie której możemy zagwarantować, że węzeł ulegnie awarii. Te. Czas oczekiwania na wiadomość z węzła może być dowolnie długi. Jest to ważna definicja i porozmawiamy o tym dalej.
Pojęcie konsensusu w systemach rozproszonych
Zanim formalnie zdefiniujemy pojęcie konsensusu, rozważmy przykład sytuacji, w której jest on nam potrzebny, a mianowicie - Replikacja maszyny stanowej.
Mamy trochę rozproszonego dziennika. Chcielibyśmy, aby był on spójny i zawierał identyczne dane na wszystkich węzłach systemu rozproszonego. Gdy jeden z węzłów pozna nową wartość, którą zamierza zapisać do dziennika, jego zadaniem staje się udostępnienie tej wartości wszystkim pozostałym węzłom, dzięki czemu dziennik zostanie zaktualizowany we wszystkich węzłach, a system przejdzie do nowego, spójnego stanu. W tym przypadku ważne jest, aby węzły były między sobą zgodne: wszystkie węzły zgadzają się, że zaproponowana nowa wartość jest poprawna, wszystkie węzły akceptują tę wartość i tylko w tym przypadku każdy może zapisać nową wartość do dziennika.
Innymi słowy: żaden z węzłów nie sprzeciwił się temu, że posiada bardziej istotne informacje, a proponowana wartość była błędna. Zgoda między węzłami i zgoda co do jednej poprawnej akceptowanej wartości jest konsensusem w systemie rozproszonym. Następnie porozmawiamy o algorytmach, które pozwalają zagwarantować, że system rozproszony osiągnie konsensus.
Bardziej formalnie algorytm konsensusu (lub po prostu algorytm konsensusu) możemy zdefiniować jako pewną funkcję, która przenosi system rozproszony ze stanu A do stanu B. Co więcej, stan ten jest akceptowany przez wszystkie węzły i wszystkie węzły mogą go potwierdzić. Jak się okazuje, zadanie to wcale nie jest tak banalne, jak mogłoby się wydawać na pierwszy rzut oka.
Właściwości algorytmu konsensusu
Algorytm konsensusu musi mieć trzy właściwości, aby system mógł nadal istnieć i mieć pewien postęp w przechodzeniu od stanu do stanu:
- Umowa – wszystkie poprawnie działające węzły muszą przyjmować tę samą wartość (w artykułach właściwość ta nazywana jest także właściwością bezpieczeństwa). Wszystkie węzły, które obecnie funkcjonują (nie zawiodły i nie straciły kontaktu z innymi) muszą dojść do porozumienia i zaakceptować jakąś ostateczną wspólną wartość.
Ważne jest, aby zrozumieć, że węzły w systemie rozproszonym, które rozważamy, chcą się zgodzić. Oznacza to, że mówimy teraz o systemach, w których coś może po prostu zawieść (na przykład jakiś węzeł ulega awarii), ale w tym systemie zdecydowanie nie ma węzłów, które celowo działają przeciwko innym (zadanie bizantyjskich generałów). Dzięki tej właściwości system pozostaje spójny.
- Integrość — jeśli wszystkie poprawnie działające węzły oferują tę samą wartość v, co oznacza, że każdy poprawnie działający węzeł musi zaakceptować tę wartość v.
- Zakończenie – wszystkie poprawnie działające węzły ostatecznie przyjmą określoną wartość (właściwość żywotności), co pozwala algorytmowi na postęp w systemie. Każdy poprawnie działający węzeł prędzej czy później musi przyjąć ostateczną wartość i potwierdzić ją: „Dla mnie ta wartość jest prawdziwa, zgadzam się z całym systemem”.
Przykład działania algorytmu konsensusu
Chociaż właściwości algorytmu mogą nie być całkowicie jasne. Dlatego zilustrujemy na przykładzie, przez jakie etapy przechodzi najprostszy algorytm konsensusu w systemie z synchronicznym modelem powiadamiania, w którym wszystkie węzły funkcjonują zgodnie z oczekiwaniami, komunikaty nie giną i nic się nie psuje (czy to się naprawdę dzieje?).
- Wszystko zaczyna się od propozycji małżeństwa (Zaproponuj). Załóżmy, że klient połączył się z węzłem o nazwie „Węzeł 1” i rozpoczął transakcję przekazując do węzła nową wartość – O. Od tej chwili będziemy nazywać „Węzeł 1” oferta. Jako wnioskodawca „Węzeł 1” musi teraz powiadomić cały system, że ma świeże dane, i wysyła komunikaty do wszystkich pozostałych węzłów: „Patrz! Przyszło mi do głowy znaczenie „O” i chcę je zapisać! Proszę potwierdzić, że zapiszesz również „O” w swoim dzienniku.”
- Kolejnym etapem jest głosowanie na proponowaną wartość (Głosowanie). Po co to jest? Może się zdarzyć, że inne węzły otrzymały nowsze informacje i posiadają dane dotyczące tej samej transakcji.
Kiedy węzeł „Węzeł 1” wysyła swoją propozycję, pozostałe węzły sprawdzają w swoich dziennikach dane dotyczące tego zdarzenia. Jeśli nie ma sprzeczności, węzły ogłaszają: „Tak, nie mam innych danych na temat tego zdarzenia. Wartość „O” to najnowsza informacja, na którą zasługujemy.”W każdym innym przypadku węzły mogą odpowiedzieć na „Węzeł 1”: „Słuchaj! Mam nowsze dane dotyczące tej transakcji. Nie „O”, ale coś lepszego.”
Na etapie głosowania węzły podejmują decyzję: albo wszystkie przyjmują tę samą wartość, albo jeden z nich głosuje przeciw, wskazując, że ma nowsze dane.
- Jeśli runda głosowania przebiegła pomyślnie i wszyscy byli za, system przechodzi do nowego etapu – Zaakceptowania wartości. „Węzeł 1” zbiera wszystkie odpowiedzi z innych węzłów i raportuje: „Wszyscy zgodzili się na wartość „O”! Teraz oficjalnie ogłaszam, że „O” to nasze nowe znaczenie, takie samo dla wszystkich! Zapisz to w swojej książeczce, nie zapomnij. Zapisz to w swoim dzienniku!”
- Pozostałe węzły wysyłają potwierdzenie (Accepted), że zapisali wartość „O”, w tym czasie nie pojawiło się nic nowego (rodzaj zatwierdzenia dwufazowego). Po tym znaczącym wydarzeniu uważamy, że rozdzielona transakcja została sfinalizowana.
Zatem algorytm konsensusu w prostym przypadku składa się z czterech kroków: zaproponować, głosować (głosować), akceptować (akceptować), potwierdzać akceptację (akceptować).
Jeśli na którymś etapie nie udało nam się dojść do porozumienia, algorytm rozpoczyna się od nowa, uwzględniając informacje przekazane przez węzły, które odmówiły potwierdzenia zaproponowanej wartości.
Algorytm konsensusowy w systemie asynchronicznym
Wcześniej wszystko szło gładko, bo mówiliśmy o modelu przesyłania wiadomości synchronicznych. Wiemy jednak, że we współczesnym świecie jesteśmy przyzwyczajeni do robienia wszystkiego asynchronicznie. Jak podobny algorytm działa w systemie z asynchronicznym modelem powiadamiania, gdzie uważamy, że czas oczekiwania na odpowiedź od węzła może być dowolnie długi (swoją drogą awarię węzła można też traktować jako przykład, gdy węzeł może odpowiadać przez dowolnie długi czas).
Skoro już wiemy, jak w zasadzie działa algorytm konsensusu, pytanie do dociekliwych czytelników, którym udało się dotrzeć tak daleko: ile węzłów w systemie N węzłów z asynchronicznym modelem komunikatów może ulec awarii, aby system nadal mógł osiągnąć konsensus?
Prawidłowa odpowiedź i uzasadnienie znajdują się za spoilerem.Poprawna odpowiedź to: 0. Jeśli choć jeden węzeł w systemie asynchronicznym ulegnie awarii, system nie będzie w stanie osiągnąć konsensusu. Twierdzenie to znajduje potwierdzenie w dobrze znanym w niektórych kręgach twierdzeniu FLP (1985, Fischer, Lynch, Paterson, link do oryginału na końcu artykułu): „Niemożność osiągnięcia rozproszonego konsensusu w przypadku awarii przynajmniej jednego węzła .”
Chłopaki, w takim razie mamy problem, jesteśmy przyzwyczajeni do tego, że wszystko jest asynchroniczne. I oto jest. Jak dalej żyć?
Rozmawialiśmy tylko o teorii, o matematyce. Co oznacza „nie da się osiągnąć konsensusu”, przekładając z języka matematycznego na nasz - inżynieria? Oznacza to, że „nie zawsze da się to osiągnąć”, tj. Są przypadki, w których nie da się osiągnąć konsensusu. Co to za przypadek?
Jest to dokładnie naruszenie opisanej powyżej właściwości żywotności. Nie mamy wspólnego porozumienia, a system nie może mieć postępu (nie może zostać ukończony w skończonym czasie) w przypadku, gdy nie mamy odpowiedzi ze wszystkich węzłów. Ponieważ w systemie asynchronicznym nie mamy przewidywalnego czasu odpowiedzi i nie możemy wiedzieć, czy węzeł uległ awarii, czy po prostu potrzebuje dużo czasu na reakcję.
Ale w praktyce możemy znaleźć rozwiązanie. Niech nasz algorytm będzie mógł działać długo w przypadku awarii (potencjalnie może działać w nieskończoność). Ale w większości sytuacji, gdy większość węzłów działa poprawnie, będziemy mieli postęp w systemie.
W praktyce mamy do czynienia z częściowo synchronicznymi modelami komunikacji. Synchronizację częściową rozumiemy następująco: w ogólnym przypadku mamy model asynchroniczny, ale formalnie wprowadza się pewne pojęcie „czasu globalnej stabilizacji” określonego momentu.
Ta chwila może nie nadejść długo, ale pewnego dnia musi nadejść. Zadzwoni wirtualny budzik i od tego momentu możemy przewidzieć deltę czasową, po której nadejdą wiadomości. Od tego momentu system przechodzi z asynchronicznego na synchroniczny. W praktyce mamy do czynienia właśnie z takimi systemami.
Algorytm Paxos rozwiązuje problemy konsensusu
to rodzina algorytmów rozwiązujących problem konsensusu dla systemów częściowo synchronicznych, z zastrzeżeniem możliwości awarii niektórych węzłów. Autorem Paxos jest . Formalny dowód na istnienie i poprawność algorytmu zaproponował w 1989 roku.
Ale dowód okazał się wcale nie trywialny. Pierwsza publikacja ukazała się dopiero w 1998 roku (33 strony) opisująca algorytm. Jak się okazało, był on niezwykle trudny do zrozumienia i w 2001 roku opublikowano wyjaśnienie artykułu, które zajęło 14 stron. Objętość publikacji podana jest po to, aby pokazać, że tak naprawdę problem konsensusu wcale nie jest prosty, a za takimi algorytmami kryje się ogrom pracy najmądrzejszych ludzi.
Co ciekawe, sam Leslie Lamport zauważył w swoim wykładzie, że w drugim artykule objaśniającym znajduje się jedno stwierdzenie, jedna linijka (nie sprecyzował, która), którą można różnie interpretować. Z tego powodu duża liczba nowoczesnych wdrożeń Paxos nie działa całkowicie poprawnie.
Szczegółowa analiza pracy Paxosa zajęłaby więcej niż jeden artykuł, dlatego postaram się bardzo krótko przekazać główną ideę algorytmu. W linkach na końcu mojego artykułu znajdziesz materiały umożliwiające dalsze zgłębienie tego tematu.
Role w Paxos
Algorytm Paxos ma koncepcję ról. Rozważmy trzy główne (istnieją modyfikacje z dodatkowymi rolami):
- Wnioskodawcy (można również użyć terminów: liderzy lub koordynatorzy). To oni dowiadują się o jakiejś nowej wartości od użytkownika i przejmują rolę lidera. Ich zadaniem jest uruchomienie rundy propozycji nowej wartości i koordynacja dalszych działań węzłów. Co więcej, Paxos pozwala na obecność kilku przywódców w określonych sytuacjach.
- Akceptanci (wyborcy). Są to węzły, które głosują za przyjęciem lub odrzuceniem określonej wartości. Ich rola jest bardzo istotna, gdyż od nich zależy decyzja: do jakiego stanu system przejdzie (lub nie) po kolejnym etapie algorytmu konsensusu.
- Uczniowie. Węzły, które po prostu akceptują i zapisują nową zaakceptowaną wartość, gdy zmieni się stan systemu. Nie podejmują decyzji, po prostu otrzymują dane i mogą je przekazać użytkownikowi końcowemu.
Jeden węzeł może łączyć kilka ról w różnych sytuacjach.
Pojęcie kworum
Zakładamy, że mamy system N węzły A z nich maksimum F węzły mogą ulec awarii. Jeśli węzły F zawiodą, musimy przynajmniej mieć 2F+1 węzły akceptorowe.
Jest to konieczne, abyśmy zawsze mieli większość, nawet w najgorszej sytuacji, „dobrych” węzłów, które działają poprawnie. To jest F+1 „dobre” węzły, które się zgodziły, a ostateczna wartość zostanie zaakceptowana. W przeciwnym razie może dojść do sytuacji, w której nasze różne grupy lokalne nabiorą różnych znaczeń i nie będą mogły dojść do porozumienia między sobą. Dlatego też, aby wygrać głosowanie, potrzebujemy większości absolutnej.
Ogólna koncepcja działania algorytmu konsensusu Paxos
Algorytm Paxos składa się z dwóch dużych faz, które z kolei są podzielone na dwa etapy:
- Faza 1a: Przygotowanie. W fazie przygotowawczej lider (wnioskodawca) informuje wszystkie węzły: „Rozpoczynamy nową fazę głosowania. Mamy nową rundę. Numer tej rundy to n. Teraz zaczniemy głosować.” Na razie po prostu zgłasza początek nowego cyklu, ale nie zgłasza nowej wartości. Zadaniem tego etapu jest zainicjowanie nowej rundy i poinformowanie wszystkich o jej unikalnym numerze. Okrągła liczba jest ważna, musi być wartością większą niż wszystkie poprzednie liczby głosów wszystkich poprzednich liderów. Bo to dzięki okrągłej liczbie pozostałe węzły w systemie zrozumieją, jak aktualne są dane lidera. Jest prawdopodobne, że inne węzły mają już wyniki głosowania ze znacznie późniejszych rund i po prostu powiedzą liderowi, że jest opóźniony.
- Faza 1b: Obietnica. Kiedy węzły akceptorowe otrzymają numer nowego etapu głosowania, możliwe są dwa wyniki:
- Liczba n nowego głosowania jest większa niż liczba wszelkich poprzednich głosów, w których brał udział akceptujący. Następnie akceptujący składa liderowi obietnicę, że nie będzie już brał udziału w głosowaniu o liczbie mniejszej niż n. Jeśli akceptant już na coś głosował (czyli przyjął już jakąś wartość w drugiej fazie), to do swojej obietnicy dołącza zaakceptowaną wartość i liczbę głosów, w których brał udział.
- W przeciwnym razie, jeśli akceptujący wie już o głosie o wyższej liczbie, może po prostu zignorować etap przygotowawczy i nie odpowiadać liderowi.
- Faza 2a: Akceptacja. Lider musi poczekać na odpowiedź kworum (większość węzłów w systemie) i w przypadku otrzymania wymaganej liczby odpowiedzi ma dwie możliwości rozwoju wydarzeń:
- Część akceptantów przesłała wartości, na które już głosowali. W tym przypadku lider wybiera wartość spośród głosów o maksymalnej liczbie. Nazwijmy tę wartość x i wyślemy do wszystkich węzłów wiadomość typu: „Akceptuj (n, x)”, gdzie pierwsza wartość to liczba głosowania z własnego kroku Propozycji, a druga wartość to to, dla czego wszyscy się zebrali, tj. wartość, na którą faktycznie głosujemy.
- Jeżeli żaden z akceptantów nie przesłał żadnych wartości, a jedynie obiecał głosować w tej turze, lider może zaprosić ich do głosowania na ich wartość, wartość, dla której w pierwszej kolejności został liderem. nazwijmy to y. Wysyła do wszystkich węzłów wiadomość typu: „Akceptuj (n, y)”, podobnie jak w poprzednim przypadku.
- Faza 2b: Zaakceptowano. Co więcej, węzły akceptacyjne po otrzymaniu od lidera komunikatu „Akceptuj(...)” zgadzają się z nim (wysyłają do wszystkich węzłów potwierdzenie, że zgadzają się z nową wartością) tylko wtedy, gdy nie obiecały jakiegoś (innego) ) lidera do udziału w głosowaniu z okrągłą liczbą n' > n, w przeciwnym razie zignorują prośbę o potwierdzenie.
Jeżeli większość węzłów odpowiedziała liderowi i wszystkie potwierdziły nową wartość, wówczas nową wartość uważa się za zaakceptowaną. Brawo! Jeśli większość nie zostanie osiągnięta lub pojawią się węzły, które odmówiły przyjęcia nowej wartości, wszystko zaczyna się od nowa.
Tak działa algorytm Paxos. Każdy z tych etapów ma wiele subtelności, praktycznie nie braliśmy pod uwagę różnego rodzaju awarii, problemów wielu liderów i wielu innych, ale celem tego artykułu jest jedynie wprowadzenie czytelnika w świat przetwarzania rozproszonego na wysokim poziomie.
Warto również zaznaczyć, że Paxos nie jest jedyny w swoim rodzaju, istnieją inne algorytmy, np. , ale to temat na inny artykuł.
Linki do materiałów do dalszych badań
Poziom początkujący:
- , Preethi Kasireddy, artykuł na blogu na Medium
- , Adi Kancherla, artykuł na blogu Medium
- , Ittai Abraham, blog
- , Ittai Abraham, artykuł na blogu
Poziom Leslie Lamporta:
- , Fischer, Lynch i Paterson, artykuł badawczy, 1985
- , Leslie Lamport, artykuł badawczy, 1998
- , Leslie Lamport, artykuł badawczy, 2001
Źródło: www.habr.com