Quantum Computing Fundamentals

Dlaczego zgoda na jedną wartość jest trudna

Poszczególne serwery baz danych nigdy nie muszą się ze sobą kłócić. Pięć serwerów robi to, a nawet więcej. Każde serwer ma własny, niezmienniczy dziennik poleceń i konsensus jest gwarancją, że wszystkie poprawne serwery wykonują te same polecenia w tym samym czasie, nawet jeśli sieć między nimi opóźnia, odrzuca lub przesuwa kolejność wiadomości, a każdy węzeł może ulec awarii bez ostrzeżenia. Formalnie protokół konsensusu musi spełniać trzy właściwości: zgodność (żaden dwa poprawne węzły nie podejmuje innej decyzji), ważność (zdana wartość faktycznie została zaproponowana przez kogoś) i zakończenie (każdy poprawny węzeł ostatecznie podejmuje decyzję). Wynik FLP z 1985 roku udowodnił, że żaden deterministyczny algorytm nie może zagwarantować wszystkich trzech w czystej sieci asynchronicznej — rzeczywiste systemy unikają tego dzięki wygaszaczom czasowym i losowaniu, kosztem teoretycznej gwarancji za zmianą na praktycznie zawsze działającą.

demo na żywo · powiązana symulacja● LIVE

Platforma: jeden lider, jedna księga, jedno termin w czasie

Platforma, zaprojektowana przez Ongaro i Ousterhout w 2014 roku, została wyraźnie zbudowana, aby była łatwiejsza do rozumowania niż wcześniejszy protokół Paxos, przy jednoczesnym zapewnieniu tych samych gwarancji bezpieczeństwa. Każdego serwera dotyczy jeden z trzech stanów – obserwator, kandydat lub lider, a czas jest podzielony na monotonicznie rosnące terminy, z których każdy ma maksymalnie jednego lidera. Wszystkie polecenia klientów przepływają przez aktualnego lidera, który dodaje je do swojej własnej księgi i następnie replikuje je do obserwatorów za pomocą wywołań zdalnych AppendEntries, oznaczone terminem, w którym zostały zapisane.

Wybór lidera z losowymi timeoutami

Śledacze oczekują regularnego sygnału tętna od lidera. Jeśli nie otrzymają go przed upływem losowego timeoutu (zazwyczaj 150-300 ms), śledacz zakłada, że lider zniknął, podnosi numer terminu, staje się kandydatem, głosuje za siebie i prosi każdego sąsiada o głos:

grant_vote(candidate) = candidate.term >= self.currentTerm AND self.votedFor w {null, candidate.id} AND candidate.log jest co najmniej tak aktualny jak self.log

// kandydat wygrywający większość staje się liderem dla tego terminu // i natychmiast wysyła sygnały tętna w celu tłumienia kolejnych wyborów Losowanie timeoutu to cała sztuczka: jeśli każdy śledacz czekałby identyczny okres czasu, wszyscy zaczęliby wybory jednocześnie i podzieliliby głos na zawsze. Dzięki losowanym timeoutom, jeden śledacz prawie zawsze pierwszy wysyła sygnał i zbiera większość zanim ktokolwiek zauważy, że lider zniknął. Termin działa jako zegar logiczny — wszelkie wiadomości zawierające przestarzały numer terminu są odrzucane natychmiast, co zapobiega korupcji logu przez starygo, tymczasowo odłączonego lidera po ponownym nawiązaniu połączenia.

grant_vote(candidate) =
  candidate.term  >= self.currentTerm
  AND self.votedFor in {null, candidate.id}
  AND candidate.log is at least as up-to-date as self.log

// a candidate that wins a majority becomes leader for that term
// and immediately sends heartbeats to suppress further elections

Replikacja i zasada komitetu

Wpis staje się zafirmowany i bezpieczny do zastosowania w maszynie stanów, dopiero po potwierdzeniu przez lidera, że został on zapisany na większości serwerów – dla klastra o 5 węzłach oznacza to lidera plus dwa obserwatory. To jedno wytyczne sprawia, że Raft toleruje ⌊(n-1)/2⌋ awarii: klaster o 5 węzłach przetrwa dwie jednoczesne awarie, ponieważ jakiekolwiek dwie większości z trzech węzłów spośród pięciu musi się przecinać w przynajmniej jednym węźle, więc nowo wybrany lider nigdy nie może "zapomnieć" wartości, którą już wcześniej zaakceptowała większość.

Koncepcja CAP: wybierz dwie, ale P nie jest opcjonalne

Zasada CAP zaproponowana przez Erica Brownera mówi, że magazyn danych rozproszony może zapewnić maksymalnie dwa z następujących cech: spójność (każde odczytanie widzi najnowszy zapis), dostępność (każdy żądanie otrzymuje odpowiedź) i tolerancję na błędy sieciowe (system działa dalej, gdy sieć się rozszczepia). Ponieważ w rzeczywistych sieciach występują awarie, rezygnowanie z tolerancji na błędy nie jest poważnym wyborem, więc praktyczny wybór sprowadza się do CP kontra AP. Raft i Paxos to przykłady systemów CP: podczas awarii mniejszościowa strona odmawia akceptowania zapisów zamiast ryzykować, że dwa liderzy dokonają sprzecznych zapisów – celowe poświęcenie dostępności w celu zapewnienia trwałości i poprawności każdego zaakceptowanego zapisu.

Przerywające błędy w porównaniu z błędami Byzancja

Raft zakłada awarię w postaci zatrzymania pracy (crash-stop failures): wadliwy węzeł po prostu przestaje odpowiadać, nigdy nie wysyła uszkodzonych lub sprzecznych komunikatów. To założenie pozwala na tolerancję f błędów przez 2f+1 replik. Tolerancja błędów Byzancja całkowicie odrzuca to założenie i zakłada, że wadliwy węzeł może zachowywać się dowolnie, w tym fałszować wiadomości różnym peerom – co wymaga 3f+1 replik oraz podpisy kryptograficzne, aby tolerować ten sam f błędów. Dlatego też protokoły BFT takie jak PBFT i HotStuff są zarezerwowane dla blockchainów i innych środowisk adversarialnych, a nie dla zwykłej wewnętrznej infrastruktury, takiej jak etcd lub warstwa metadanych KRaft Kafka.

Często zadawane pytania

Dlaczego Raft wykorzystuje losowe interwały wyborów zamiast ustalonego?

Jeśli każdy podrzędny serwer czekał dokładnie taki sam czas, to wszyscy by się stali kandydatami jednocześnie po każdym awarii lidera, podzieliliby głos za każdym razem i nigdy by się nie zbiegli. Losowe wyciąganie czasu oczekiwania każdego podrzędnego serwera z zakresu, np. 150-300 ms, oznacza, że prawie zawsze jeden z nich wycofa się jako pierwszy, poprosi o głosy zanim ktokolwiek inny rozpocznie wybór i wygra większość w jednym okręgu.

Co dokładnie wymusza twierdzenie CAP?

Podczas rzeczywistej awarii sieci można zagwarantować tylko dwie z cech: spójność, dostępność i tolerancję na podziały. Ponieważ podziały rzeczywiście występują, tolerancja na podziały nie jest opcjonalna – prawdziwy wybór dotyczy spójności czy dostępności. Raft i Paxos są systemami CP: mniejsza strona podziału przestaje akceptować zapisy zamiast ryzykować obsługę przestarzałych lub sprzecznych danych, poświęcając dostępność, aby każdy zatwierdzony zapis był trwały i prawidłowy.

Jakie jest różnice między tolerancją na awarie po zwarciu a tolerancją na awarie byzantyjskie?

Algorytmy odporne na awarie po zwarciu, takie jak Raft, zakładają, że uszkodzony węzeł po prostu przestaje odpowiadać – nigdy nie wysyła zniekształconych, sprzecznych lub złych wiadomości. Tolerancja na awarie byzantyjskie zakłada, że uszkodzony węzeł może zachowywać się dowolnie, w tym kłamać różnym peerom, co wymaga 3f+1 replik do tolerowania f uszkodzonych węzłów zamiast 2f+1 w Raft, plus dodatkowe rundy kryptograficznego podpisywania wiadomości – dodane koszty sprawiają, że BFT jest zarezerwowane dla blockchainów i środowisk adversarialnych, a nie zwykłej wewnętrznej infrastruktury.

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz the simulation i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.

▶ Otwórz symulację the simulation