Bezkonfliktowe replikowane typy danych (CRDT) vs Paxos lub Raft

Myślę, że ten facet wie o czym mówi:

Blog

Video

Wnioski o systemach rozproszonych

Crdt i Paxos mają różne cele i są wykorzystywane w różnych scenariuszach. Mają one wspólnego, że pomagają programistom radzić sobie z współbieżnością / replikacją. Crdt są typami danych, które asume równoczesne aktualizacje będą występować. Paxos jest protokołem, który wymusza ich przyzwyczajenie, wymuszając na nich całkowity porządek. Zobaczmy to bardziej szczegółowo.

Powiedzmy, że mamy replikowany zbiór, który jest replikowany w dwóch różnych miejscach.

Korzystanie z Paxos gwarantuje, że zapisuje do zestawu będą wykonywane przez każdą replikę w tej samej kolejności. Ogólnie rzecz biorąc, gwarantuje to, że wszystkie repliki zgadzają się co do tego, jak ewoluuje Stan zestawu.

Jeśli na przykład user1 wykonuje update1 w replika1, dodaje element 1 do replikowanego zestawu, a jednocześnie user2 wykonuje update2, dodaje element2 w replika2, Paxos sprawi, że repliki zgodzą się na daną kolejność tych aktualizacji lub ewentualnie zgodzą się na wybór jednej z dwóch aktualizacji i odrzucenie replik. drugi, w zależności od tego, jak go używasz i co chcesz osiągnąć. Jeśli wynikiem programu Paxos jest, powiedzmy, że update1 jest przed update2, każda replika zaktualizuje zestaw w tej kolejności. W konsekwencji, użytkownicy czytający zestaw jednocześnie z tymi aktualizacjami mogą obserwować, niezależnie od tego ,gdzie (w jakiej replice) czytają, tylko następujące stany zestawu (zakładając, że zestaw był pusty na początku):

{} (pusty zestaw)

{element1}

{element1, element2}

Ponadto stany te można zobaczyć tylko w tej Kolejności, co oznacza, że gdy stan zbioru wynosi {element1, element2} (przy każdej replice), żaden kolejny odczyt nie zwróci {} lub {element1}.

Pozytywna strona: ten zbiór jest prosty do rozumowania, ponieważ jest odpowiednikiem zbioru, który nie jest replikowany.

Negatywna strona: Niedostępność: jeśli repliki nie mogą ze sobą rozmawiać( partycja sieciowa), twój zestaw nie może zostać zaktualizowany, ponieważ nie może być umowy. Niski wydajność, wysokie opóźnienia: umowa wymaga synchronizacji replik przed wysłaniem odpowiedzi do klienta. Powoduje to opóźnienie proporcjonalne do opóźnienia między replikami.

Crdt mają słabsze Gwarancje. Zestaw CRDT nie jest odpowiednikiem sekwencyjnego, jednokrotnego. Wynika z tego, że nie ma porozumienia ani całkowitej kolejności w jaki sposób repliki są aktualizowane.

CRDTs gwarantuje, że jeśli obie repliki zestawu mają te same aktualizacje (niezależnie od kolejności, w jakiej widzą ich), wówczas będą one wykazywały ten sam stan; repliki będą się zbieżne.

W naszym przykładzie dwóch użytkowników wykonujących aktualizacje jednocześnie, system, który nie uruchamia systemu Paxos, aby zlecić operacje na zestawie (dzieje się tak np. przy ewentualnej lub przyczynowej spójności), pozwoli replica1 dodać element1, podczas gdy replica2 dodaje element2

Więc stan w replika1 będzie: {element1}

A stan w replika2 będzie: {element2}

W tym momencie repliki / align = "left" / Później, gdy repliki się zsynchronizują, będą wymieniać swoje aktualizacje, w końcu wykazując ten stan:

Stan w replika1 będzie: {element1, element2}

Stan w replika2 będzie: {element2, element1}

W tym momencie repliki się zbiegły.

Użytkownicy czytający zestaw jednocześnie z tymi aktualizacjami mogą obserwować, w zależności od tego ,gdzie (w jakiej replice) czytają, następujące stany zestawu (zakładając, że zestaw był pusty w początek): {]}

{} (pusty zestaw)

{element1} (jeśli czytają z replika1)

{element2} (jeśli czytają z replika2)

{element1, element2}

{element2, element1}

Strona ujemna: trudno jest rozumować o tym zestawie, ponieważ pokazuje stany, które nie mogą wystąpić w zestawie sekwencyjnym. W naszym przykładzie zaobserwowaliśmy tylko przypadek dwóch równoległych dodawań do zbioru, co jest proste. Równoczesne dodawanie i usuwanie są bardziej złożone, istnieje wiele typy danych o różnych problemach:

A comprehensive study of Convergent and Commutative Replicated Data Types

Pozytywna strona: Wysoka dostępność: jeśli repliki nie mogą ze sobą rozmawiać( partycja sieciowa), twój zestaw może zostać zaktualizowany. Repliki zostaną zsynchronizowane, gdy się połączą. Wysoka Wydajność, niskie opóźnienia: repliki natychmiast odpowiadają klientom i synchronizują się w tle, po udzieleniu odpowiedzi klientowi.

Jest błąd w przykładzie CRDT Treedoc. Każdy węzeł wymaga disambiguatora w przypadku, gdy dwa systemy wstawiają jednocześnie ten sam klucz.

Po tym zdarzeniu nie jest już możliwe, aby systemy wstawiały między wpisy, które mają identyczne klucze, ale różne disambiguatory, ponieważ wymaga to, aby system wstawił inny identyczny klucz, ale kontrolujący kolejność disambiguatorów. Disambiguatory nie są gęste, więc nie zawsze jest to możliwe. Jeśli disambiguators były jeszcze inne drzewo, można rozwiązać jeden problem, ale potem trzeba inny mechanizm rozwiązywania konfliktów głębiej w dół ... itd.

Ten niezapowiedziany problem, plus fakt, że musisz zrobić dwufazowy commit, aby uporządkować metadane, sprawia, że myślę, że CRDTs są nadal w toku.

Mamy wiele metryk:

• throughput (CRDT i Paxos są takie same, ponieważ wszystkie żądania są replikowane na wszystkich replikach bez względu na CRDT lub Paxos);
• opóźnienie (CRDT jest lepszy niż Paxos, ponieważ zapisuje do mniejszej liczby replik);
• niezawodność (CRDT jest słabszy niż Paxos, ponieważ zapisuje do mniejszej liczby replik (mniejszej niż większość), co może spowodować utratę stanu);
• konsystencja (CRDT jest słabszy niż Paxos, ponieważ pozwala na jednoczesny zapis bez punktu synchronizacji (zasadniczo bez nakładających się replik), podczas gdy zapis Paxos zawsze wymaga nakładających się replik do serializacji).

Moja sugestia jest taka, że powinniśmy używać Paxos, gdy repliki znajdują się niedaleko od siebie (np. w centrum danych), i używać CRDT, gdy partycjonowanie sieci jest normalne (np. odłączony telefon komórkowy).

Komentarz do odpowiedzi użytkownika @ btilly:

Pytanie w temacie związane jest z różnymi modelami spójności, a tym samym wzorcami projektowymi:

• CRDT odnosi się do ewentualnej spójności rodziny algorytmów,
• rodzina algorytmów PAXOS odnosi się do silnej spójności / Linerizability (synchronizacja klienta z serwerem,),
• jest odpowiednikiem PAXOS w sposób algorytmiczny i spójny, ale uważa się go za łatwiejszy do wdrożenie.

CRDT i Paxos to bardzo różne rzeczy i o ich zastosowaniu należy decydować w oparciu o wymagania Twojej architektury. Uważam, że najlepszym sposobem radzenia sobie z tym jest przegląd przypadków użycia, w których algorytmy te zostały z powodzeniem zastosowane.

Użyj wzorców:

PAXOS używany głównie w systemach własnościowych wspierających infrastrukturę systemów (np. Chubby), lub do implementacji synchronizacji w rozproszonych systemach bazodanowych, takich jak BigTable, Datastore, Spinaker, Spanner itp.

Tratwa jest bardziej popularna w projektach infrastrukturalnych OSS, takich jak ETCD, Consul, ...

(nie pamiętam na czym bazują CockroachDB i TiDB)

Istnieje również BFT, ale jest używany mniej.

P. S. PAXOS != ZooKeeper. ZooKeeper używa innego algorytmu nazywany ZAB i nie jest replikowaną maszyną stanową, ale replikowaną maszyną migawkową z pojedynczym pisarzem i zrelaksowanym modelem odczytu. Google opiera się na Paxos, ale jest zastrzeżony.

P. s. S. ciekawe jak PAXOS ewoluuje przez te wszystkie lata. W ciągu ostatnich 20 lat wynaleziono wiele wariantów obsługujących różne optymalizacje przypadków krawędzi, wielkości kworum i rekonfiguracji klastra.

Kiedy jest to właściwe. Jednak PaxOS nie jest tak źle, ponieważ jego przepustowość jest zazwyczaj taka sama jak w przypadku CRDT, nie wspominając o tym, że niezawodność jest znacznie wyższa (CRDT może spowodować utratę stanu), a jego opóźnienie nie jest tak złe, ponieważ wymaga tylko większości odpowiedzi replik zamiast wszystkich.