Ilustrowany dowód twierdzenia CAP

twierdzenie CAP jest podstawowym twierdzeniem w systemach rozproszonych, które stwierdza, że każdy system rozproszony może mieć co najwyżej dwie z następujących trzech właściwości.

• spójność
• dostępność
• tolerancja partycji

ten przewodnik podsumuje specyfikację Gilberta i Lyncha oraz dowód twierdzenia o CAP za pomocą zdjęć!

co to jest twierdzenie CAP?

twierdzenie CAP mówi, że system rozproszony nie może być jednocześnie spójny, dostępny i tolerancyjny dla partycji. Brzmi prosto, ale co to znaczy być konsekwentnym? dostępny? partycja tolerancyjna? Co dokładnie masz na myśli mówiąc o systemie rozproszonym?

w tej sekcji przedstawimy prosty system rozproszony i wyjaśnimy, co oznacza dla niego dostępność, spójność i tolerancja partycji. Formalny opis systemu i trzech właściwości znajduje się w artykule Gilberta i Lyncha.

system rozproszony

rozważmy bardzo prosty system rozproszony. Nasz system składa się z dwóch serwerów, $g_1$ i $g_2$. Oba te serwery śledzą tę samą zmienną, $v$, której wartość początkowo wynosi $v_0$. $G_1$ i $g_2$ mogą komunikować się ze sobą, a także komunikować się z klientami zewnętrznymi. Oto jak wygląda nasz system.

klient może zażądać zapisu i odczytu z dowolnego serwera. Kiedy serwer otrzymuje żądanie, wykonuje dowolne obliczenia, które chce, a następnie odpowiada klientowi. Na przykład, oto jak wygląda zapis.

a oto jak wygląda odczyt.

teraz, gdy mamy już nasz system ustanowiony, przejdźmy nad tym, co to znaczy, aby system był spójny, dostępny i tolerancyjny dla partycji.

konsystencja

Oto jak Gilbert i Lynch opisują konsystencję.

każda operacja odczytu, która rozpoczyna się po zakończeniu operacji zapisu, musi zwrócić tę wartość lub wynik późniejszej operacji zapisu

w spójnym systemie, gdy klient zapisze wartość do dowolnego serwera i otrzyma odpowiedź, spodziewa się odzyskać tę wartość (lub świeższą wartość) z dowolnego serwera, z którego odczytuje.

oto przykład niespójnego systemu.

nasz klient zapisuje $v_1$ do $G_1$ i $g_1$ potwierdza, ale gdy czyta z $G_2$, otrzymuje przestarzałe dane: $v_0$.

z drugiej strony, oto przykład spójnego systemu.

w tym systemie, $G_1$ replikuje swoją wartość do $G_2$ przed wysłaniem potwierdzenia do klienta. Tak więc, gdy klient odczytuje z $G_2$, otrzymuje najbardziej aktualną wartość $v$: $v_1$.

dostępność

Oto jak Gilbert i Lynch opisują dostępność.

każde żądanie otrzymane przez niezaliczony węzeł w systemie musi skutkować odpowiedzią

w dostępnym systemie, jeśli nasz klient wyśle żądanie do serwera, a serwer nie zawiesił się, serwer musi ostatecznie odpowiedzieć na klienta. Serwer nie może ignorować żądań klienta.

tolerancja partycji

Oto jak Gilbert i Lynch opisują partycje.

sieć będzie mogła utracić dowolnie wiele wiadomości wysyłanych z jednego węzła do drugiego

oznacza to, że wszelkie wiadomości $g_1$ i $g_2$ wysyłane do siebie mogą zostać odrzucone. Gdyby wszystkie wiadomości były odrzucane, nasz system wyglądałby tak.

nasz system musi być w stanie działać poprawnie pomimo arbitralnych partycji sieciowych, aby był odporny na partycje.

dowód

teraz, gdy zapoznaliśmy się z pojęciem spójności, dostępności i tolerancji partycji, możemy udowodnić, że system nie może jednocześnie mieć wszystkich trzech.

Przyjmij za sprzeczność, że istnieje system, który jest spójny, dostępny i tolerancyjny dla partycji. Pierwszą rzeczą, którą robimy, jest partycjonowanie naszego systemu. Wygląda tak.

następnie nasz klient prosi o zapisanie $v_1$ do $G_1$. Ponieważ nasz system jest dostępny, $G_1$ musi odpowiedzieć. Ponieważ jednak sieć jest partycjonowana, $g_1$ nie może replikować swoich danych do $G_2$. Gilbert i Lynch nazywają tę fazę egzekucji $ \ alpha_1$.

następnie nasz klient wysyła żądanie odczytu do $G_2$. Ponownie, ponieważ nasz system jest dostępny, $G_2$ musi odpowiedzieć. A ponieważ sieć jest partycjonowana, $g_2$ nie może zaktualizować jej wartości z $g_1$. Zwraca $v_0$. Gilbert i Lynch nazywają tę fazę egzekucji $ \ alpha_2$.

$G_2$ zwraca$ v_0 $ do naszego Klienta po tym, jak klient napisał już $v_1$ do $G_1$. To jest niespójne.

założyliśmy, że istnieje spójny, dostępny, tolerujący partycje system, ale po prostu pokazaliśmy, że istnieje wykonanie dla każdego takiego systemu, w którym system działa niezgodnie. Tak więc taki system nie istnieje.