Jakie jest uzasadnienie twierdzenia CAP?

21

http://en.wikipedia.org/wiki/CAP_theorem

http://www.cs.berkeley.edu/~brewer/cs262b-2004/PODC-keynote.pdf

Myślę, że nie jest to bardzo proste, dlaczego tylko dwa z nich

  1. Konsystencja
  2. Dostępność
  3. Tolerancja podziału

może pomieścić dla dowolnego systemu rozproszonej bazy danych. Ta hipoteza została udowodniona, ale czy istnieje łatwiejszy sposób, aby zrozumieć, dlaczego prawdopodobnie tak się dzieje?

Nie szukam dowodu, tylko dobry sposób na zrozumienie, dlaczego to twierdzenie może mieć sens. Jakie jest uzasadnienie?

Lazer
źródło

Odpowiedzi:

23

OK, wyobraźmy sobie, że masz rozproszoną bazę danych. Załóżmy, że masz węzeł w Oregonie i jeden w Kalifornii. Teoria CAP mówi, że napotkasz problemy podczas konfigurowania tego typu bazy danych.

Na przykład, jeśli przeszukujesz dane z jednej bazy danych, muszą one być takie same jak dane w drugiej bazie danych. Gwarantuje to, że dowolna wartość, którą posiadasz w jednej bazie danych, gwarantuje, że będzie w drugiej ( spójność teorii CAP). W ten sposób można zaktualizować dane w jednej bazie danych i przeszukać je w innej, uzyskując te same wyniki.

Komputer aktualizujący dane w stanie Oregon przesyła dane do Kalifornii

Gdy aktualizujemy dane w węźle Oregon, dane są wysyłane do węzła Kalifornii, dzięki czemu bazy danych są spójne. Aby naprawdę zachować spójność, musimy upewnić się, że obie bazy danych otrzymają aktualizację, zanim jedno z nich będzie mogło naprawdę zapisać dane (zatwierdzanie dwufazowe przy użyciu transakcji rozproszonych). Innymi słowy, jeśli baza danych w Kalifornii z jakiegoś powodu nie może zapisać danych (np. Awaria dysku twardego), wówczas baza danych w Oregonie nie zapisze danych i zawiedzie transakcję.

Problem z rozproszonymi transakcjami, jak powyższy, pojawia się, gdy chcemy mieć wysoką dostępność. W powyższym scenariuszu proces synchronizacji obu baz danych jest procesem bardzo powolnym. (Wyobraź sobie, że musimy wysyłać dane z Oregonu do Kalifornii, upewnić się, że tam dotrą, upewnij się, że obie bazy danych mają blokady danych itp.) To powoduje poważne problemy, gdy chcemy, aby system był szybki i reagował nawet podczas czasy wysokiego popytu. (To jest dostępność twierdzenia CAP).

Zwykle w celu zapewnienia wysokiej dostępności używamy replikacji zamiast transakcji rozproszonych. Zamiast więc zagwarantować, że Kalifornia może zaakceptować dane, po prostu przechowujemy je w węźle Oregon, a następnie wysyłamy dane do Kalifornii, gdy się do nich zbliżymy. Gwarantuje to, że zawsze możemy przechowywać dane, niezależnie od tego, czy Kalifornia jest gotowa do przechowywania danych, czy nie.

Węzeł Oregon aktualizuje dane, podczas gdy Kalifornia je odczytuje.  Później dane są przenoszone do Kalifornii

Poprawia to dostępność, ale kosztem spójności. Zobacz, jeśli ktoś zaktualizuje dane w Oregonie, a następnie ktoś (w tym samym czasie) odczyta dane w Kalifornii, nie otrzyma nowych danych - bazy danych nie są już spójne. W rzeczywistości nie będą spójne, dopóki Oregon nie wyśle ​​danych do Kalifornii!

Tak więc jest to kompromis pomiędzy dostępnością a vs.

Tolerancja podziału na partie to trzeci aspekt teorii WPR. W tym kontekście partycjonowanie polega na tym, że baza danych (lub inny system rozproszony) może zostać podzielona na osobne sekcje i nadal działać poprawnie.

Powstaje pytanie, co się stanie, gdy obie bazy danych będą działały poprawnie, ale połączenie z Oregonu do Kalifornii zostanie zerwane?

Oregon jest aktualizowany podczas odczytywania węzła Kalifornii.  Sieć między węzłami jest zerwana.

Jeśli aktualizujemy bazę danych w stanie Oregon, musimy przenieść dane do Kalifornii w ten czy inny sposób (transakcja rozproszona lub replikacja). Jeśli jednak połączenie między nimi zostanie przerwane, system zostanie podzielony na partycje, a bazy danych nie będą już ze sobą połączone.

Kiedy tak się stanie, możesz przestać zezwalać na aktualizacje (w celu zachowania spójności) kosztem dostępności lub pozwolić na aktualizacje (w celu utrzymania dostępności) kosztem spójności.

Jak widać, tolerancja partycji tworzy bezpośrednie kompromisy między spójnością a dostępnością.


Jest oczywiście więcej niż to, ale to kilka przykładów, w jaki sposób te trzy główne aspekty systemów rozproszonych działają przeciwko sobie i przeciw sobie. Wyjaśnienie Juliana Browne'a dotyczące teorii CAP jest doskonałym miejscem do zdobycia dodatkowych informacji.

Richard
źródło
Powiązana odpowiedź Remusa Rusanu.
Nick Chammas,
Z ładniejszym obrazem!
Richard