Najlepsza odpowiedź
Ten artykuł zawiera uderzająco jasne wyjaśnienie i dowód: http://pdos.csail.mit.edu/6.824/papers/paxos-simple.pdf
W tym miejscu postaram się przedstawić jasne podsumowanie:
Celem Algorytm Paxos służy pewnej liczbie rówieśników do osiągnięcia porozumienia co do wartości. Paxos gwarantuje, że jeśli jeden partner uważa, że jakaś wartość została uzgodniona przez większość, większość nigdy nie zgadzają się na inną wartość. Protokół został zaprojektowany w taki sposób, że każda umowa musi być przez większość węzłów. Wszelkie przyszłe próby osiągnięcia porozumienia, jeśli zakończą się powodzeniem, muszą również przejść przez co najmniej jeden z tych węzłów. Zatem: Każdy węzeł, który proponuje po podjęciu decyzji, musi komunikuje się z węzłem w większości. Protokół gwarantuje, że nauczy się poprzedniej ag polegał na wartości z tej większości.
Oto jak to działa:
Załóżmy, że mamy 3 węzły, A, B i C. A chciałby zaproponować wartość „Foo.”
Algorytm działa w 3 fazach. Na każdym etapie należy uzyskać potwierdzenie z większości węzłów.
Najpierw mamy fazę przygotowawczą. A wysyła żądanie przygotowania do A, B i C. Paxos opiera się na numerach sekwencji do osiągnąć swoje gwarancje. Żądanie przygotowania żąda od węzła obietnicy: „Nigdy nie przyjmuję propozycji o numerze kolejnym niższym niż w żądaniu przygotowania”. Węzły odpowiadają, podając dowolną wartość, na którą wcześniej wyraziły zgodę (jeśli dotyczy). (Jest to niezwykle ważne): Węzeł A musi zaproponować otrzymaną wartość z najwyższym numerem kolejnym. Ta akcja zapewnia gwarancję zachowania wcześniej uzgodnionych wartości.
Następnie mamy fazę akceptacji. A wysyła żądanie akceptacji do A, B i C. Żądanie akceptacji brzmi: „ Czy akceptujesz foo? ” Jeśli towarzyszący numer sekwencyjny nie jest niższy od tego, co wcześniej obiecał węzeł lub zażądał, aby węzeł poprzednio zaakceptował, zaakceptuje nową wartość i numer kolejny.
Jeśli węzeł A odbiera akceptuje od w przypadku większości węzłów wartość jest określana. Ta runda Paxos nigdy nie zgodzi się na inną wartość.
Trzecia faza nie jest absolutnie konieczna, ale ma kluczowe znaczenie optymalizacja w każdym produkcyjnym wdrożeniu Paxos. Gdy A otrzyma większość zaakceptowanych, wysyła zdecydowane wiadomości do A, B i C. Te komunikaty informują wszystkich rówieśników, że wartość została wybrana, i przyspieszają zakończenie procesu decyzyjnego.
Bez tej wiadomości pozostali partnerzy musieliby spróbować zaproponować wartość, którą można by nauczyć się o umowie. W fazie przygotowawczej dowiedzieliby się o wcześniej uzgodnionej wartości. Gdy umowa została doprowadzona do zawarcia, węzeł rozpoznałby umowę.
Omówiłem tutaj kilka kluczowych kwestii:
- Wszystkie numery sekwencji muszą być monotonicznie rosnące i unikalne dla każdego węzła . Oznacza to, że A i B nie mogą jednocześnie wysłać wiadomości o numerze kolejnym k. Wszystkie wiadomości przesyłane w protokole zawierają numery sekwencyjne. Węzeł musi śledzić najwyższe żądanie akceptacji, które widział, a także najwyższą wartość, jaką obiecał w fazie przygotowania.
- Warunki niepowodzenia. Jest całkiem możliwe, że runda Paxos się nie powiedzie. W przypadku awarii jeden węzeł po prostu próbuje zaproponować ponownie z wyższym numerem kolejnym.
- Warunki zakończenia. Wersja Paxosa, którą opisałem, niekoniecznie musi się zakończyć. Kilka poprawek jest wymaganych do formalnego potwierdzenia wypowiedzenia.
Odpowiedź
Ponieważ Paxos osiąga konsensus, może być również używany do replikowania zapisów w rozproszonej bazie danych, ponieważ może zagwarantować spójną kolejność zdarzeń we wszystkich węzłach w grupie. Chubby by Google używa Paxos do udostępniania bardzo spójnych plików. To stąd wynika zamieszanie. Jaka jest zatem relacja między synchronizacją widoków i paxos, jeśli obie mogą być używane do replikacji?
Mała historia: Lamport wprowadził koncepcję replikacji maszyny stanowej na początku lat 80-tych. Replikacja maszyny stanów oznacza, że system dostarcza zdarzenia w tej samej kolejności do wszystkich węzłów i są one przetwarzane deterministycznie, co gwarantuje spójne stany we wszystkich węzłach w grupie. Jednak w momencie wprowadzenia tej koncepcji wiązało się to z różnego rodzaju założeniami, w tym synchronizacją sieci.Tak więc replikacja maszyny stanowej pozostała jedynie narzędziem teoretycznym bez praktycznego zastosowania. W tym miejscu wprowadzono synchronizację widoków, która miała na celu osiągnięcie spójności przy braku takich założeń. Celem było posiadanie praktycznego systemu zapewniającego takie gwarancje.
Publikacja Paxosa nastąpiła w trakcie prac nad synchronizacją widoków. Paxos może osiągnąć replikację maszyny stanu, ponieważ repliki mogą teraz uzgadniać kolejność wykonywania żądań klientów przy użyciu tego algorytmu konsensusu. Paxos nie założył sieci synchronicznej ani awarii. Paxos dostarczył również protokół członkostwa w grupie. Różnice, które teraz pozostały między synchronizacją widoków a Paxos, dotyczyły tylko sposobu formułowania abstrakcji. Obie zapewniają dynamiczne członkostwo i podobnie radzą sobie z awariami. Różnice są tak naprawdę tylko w modelu. Niektóre różnice, które można podkreślić, to:
- Virtual Synchrony ma prosty protokół członkostwa w grupie w porównaniu z Paxos. Virtual Synchrony uruchamia członkostwo w grupie jako oddzielną usługę.
- Paxos może robić postępy w niektórych przypadkach partycji, na których wirtualne bloki synchronizacji.
- Virtual Synchrony jest szybsza niż współczesne Paxos.
Oba systemy ewoluowały i są zbieżne . W obecnej sytuacji bardzo trudno jest narysować jakiekolwiek znaczące różnice między nimi.
Lalith jasno wyjaśnia protokół Virtual Synchrony i słusznie wskazuje, że Paxos lub każdy inny wariant konsensusu może być używany w synchronizacji widoku. Paxos oprócz konsensusu zapewnia członkostwo w grupie i inne funkcje, które już zapewnia Wirtualna synchronizacja. Ponieważ zarówno wirtualna synchronizacja, jak i Paxos zapewniają te same gwarancje i zostały opracowane mniej więcej w tym samym czasie, specyfikacja wirtualnej synchronizacji nie wykorzystuje Paxos do konsensusu. Jednak model wirtualnej synchronizacji używa całkowicie uporządkowanego protokołu wysyłania (znanego również jako ABCAST) w celu uzyskania emisji atomowej i innego protokołu do aktualizacji widoków grup. Można je postrzegać jako wariant konsensusu używa.
Warto zauważyć, że model wykonawczy ISIS-2 łączy model Paxos z modelem wirtualnej synchronizacji, nie dla konsensusu, ale dla uwzględnienia członkostwa w grupie jako oddzielnej usługi w Paxos. To sprawia, że Paxos jest szybszy w przypadkach, gdy członkostwo nie zmienia się dynamicznie. Łącząc Virtual Synchrony i Paxos, ISIS2 jest w stanie pominąć pewne kroki, które muszą wykonać typowe Paxos. Zasadniczo Paxos i Virtual Synchrony to różne modele, które zapewniają tę samą funkcjonalność i można je łączyć ze sobą w celu uzyskania wariantów lub optymalizacji.