Twierdzenie CAP

4.1 Spójność dotycząca Brewera

Zacznijmy od tego, że Eric Brewer nie jest i nigdy nie twierdził, że jest ekspertem od baz danych. Należy do środowiska systemów rozproszonych, a jego słynna prelekcja, w której pojawiło się „twierdzenie” CAP, została wygłoszona na konferencji „Principles of Distributed Computing”. (Nawiasem mówiąc, dziesięć lat później, w 2010 roku, ponownie wygłosił zaproszony referat na tej samej konferencji i w tym referacie podał w szczególności szereg przykładów systemów rozproszonych, których rozwój uwzględniał „ twierdzenie" CAP.) W tym zakresie posiada własną interpretację terminów używanych w dziedzinie baz danych.

W szczególności określenie „natychmiastowa spójność” oznacza, że ​​po otrzymaniu przez użytkownika powiadomienia z systemu o pomyślnym zakończeniu jakiejś operacji aktualizacji danych, wynik tej operacji staje się natychmiast widoczny dla wszystkich obserwatorów.

Spójność ewentualna oznacza, że ​​jeśli przez odpowiednio długi czas do systemu nie będą wprowadzane żadne nowe operacje aktualizacji danych, to można oczekiwać, że wyniki wszystkich poprzednich operacji aktualizacji danych ostatecznie rozprzestrzenią się na wszystkie węzły systemu, a dane wszystkich replik zostaną spójny (najwyraźniej należy to rozumieć jako „wszystkie repliki będą miały ten sam stan”.

Mając na uwadze to poczucie spójności, „twierdzenie” Brewera można uznać za całkiem zrozumiałe i oczywiste: w dowolnym systemie rozproszonym ze współdzielonymi danymi można jednocześnie zapewnić tylko dwie dowolne właściwości sieci: spójność, dostępność i tolerancję partycji. Pod tym względem Brewer porównuje nawet zestaw właściwości ACID z proponowanym przez siebie zestawem właściwości BASE (zasadniczo dostępny, stan miękki, konsystencja ostateczna - dostępność w większości przypadków; stan niestabilny; konsystencja końcowa). Ale ten sprzeciw, moim zdaniem, jest nieuzasadniony, ponieważ w pierwszym przypadku mówimy o logicznych cechach transakcji, aw drugim - o fizycznych właściwościach systemów rozproszonych.

4.2 Dowód „twierdzenia”

Wielu uważa, że ​​„twierdzenie” Brewera zostało formalnie udowodnione. Rzeczywiście, artykuł Setha Gilberta i Nancy Lynch wprowadza pewne (prawie) definicje formalne, w kontekście których „twierdzenie” naprawdę staje się twierdzeniem i zostaje udowodnione. Zobaczmy jednak, jak określa się te trzy właściwości systemu rozproszonego, z których zgodnie z „twierdzeniem” Brewera tylko dwie właściwości mogą być obsługiwane jednocześnie.

Spójność nazywana jest konsystencją atomową lub konsystencją możliwą do linearyzacji (konsystencja atomowa lub linearyzowalna), która jest właściwością systemu, którego wszystkie poszczególne obiekty danych są atomowe (linearyzowalne). Z kolei obiekt atomowy to obiekt z kilkoma operacjami, tak że wywołanie operacji i odebranie danych odpowiedzi następuje niejako natychmiastowo, tj. obiekt nie akceptuje wywołania następnej operacji, dopóki poprzednia operacja nie zostanie całkowicie zakończona. Kolejność, w jakiej operacje są odbierane, musi być taka, że ​​jeśli operacja typu odczytu nadejdzie po wykonaniu jakiejś operacji typu zapisu, wówczas operacja odczytu musi zwrócić wartość zapisaną przez tę lub późniejszą operację zapisu.

System rozproszony jest zawsze dostępny, jeśli trzeba odpowiedzieć na każde żądanie otrzymane przez węzeł, który nie uległ awarii. Odporność systemu na partycję sieci modeluje się jako zachowanie żywotności systemu w przypadku utraty dowolnej liczby komunikatów przesyłanych z jednego węzła do drugiego.

Na podstawie tych definicji Hilbert i Lynch formułują następujące twierdzenie (w modelu sieci asynchronicznej nie ma zegara, a węzły powinny podejmować decyzje tylko na podstawie odebranych komunikatów i lokalnych obliczeń):

W modelu sieci asynchronicznej nie jest możliwe zaimplementowanie obiektu danych do odczytu/zapisu, który gwarantuje dostępność i właściwości spójności atomowej dla wszystkich prawidłowych wykonań (w tym tych, które powodują utratę komunikatów).

To twierdzenie jest naprawdę po prostu formalnie udowodnione metodą „przez sprzeczność”. W dalszej części artykułu dochodzi do wniosku, że:

W modelu sieci asynchronicznej nie jest możliwe zaimplementowanie obiektu danych do odczytu/zapisu, który gwarantowałby właściwości dostępności dla wszystkich prawidłowych wykonań i spójność atomową dla prawidłowych wykonań, w których komunikaty nie są tracone.

Ponadto prawdziwość głównego twierdzenia jest udowodniona dla częściowo synchronicznego modelu sieci, w którym każdy węzeł ma zegar, którego pokazany czas narasta w tym samym tempie, ale które nie są zsynchronizowane, tj. może pokazywać różne czasy w tym samym rzeczywistym momencie. Pokazano, że dla tego przypadku nie wyprowadza się podobnej konsekwencji, a zatem dla sieci częściowo synchronicznych jest więcej możliwości organizowania systemów rozproszonych o „dobrych” właściwościach.

Tak, w pewnym sensie (niekoniecznie tak, jak zamierzał Brewer) można uznać, że Gilbert i Lynch udowodnili, że niemożliwe jest jednoczesne zapewnienie właściwości spójności atomowej, dostępności i tolerancji partycji sieci w pojedynczym systemie rozproszonym. Ale co to ma wspólnego z transakcjami bazodanowymi w ogóle, a transakcjami ACID w szczególności?

4.3 Transakcje ACID

Oto, co pisze o tym Julian Browne w swojej notatce na temat dyskusji nad „twierdzeniem” CAP:

W swoim dowodzie Hilbert i Lynch używają terminu atomowość zamiast terminu spójność, co ma większy sens z technicznego punktu widzenia, ponieważ, ściśle mówiąc, spójność w znaczeniu ACID odnosi się do idealnych właściwości transakcji bazodanowych i oznacza, że ​​nie dane staną się trwałe, jeśli naruszą pewne wcześniej ustalone ograniczenia. Ale jeśli założymy, że z góry ustalonym ograniczeniem systemów rozproszonych jest zakaz obecności kilku różnych wartości dla tego samego elementu danych, to moim zdaniem tę wadę w abstrakcji spójności można uznać nieistotne (poza tym, gdyby Brewer użył terminu atomowość, to pojawiłoby się twierdzenie AAP, którego nazwa byłaby wyjątkowo niewygodna do wymówienia).

To jest napisane niezbyt poważnie, ale szczerze. I faktycznie, wymogu spójności atomowej nie należy mieszać z wymogami spójności transakcyjnej w sensie ACID. Ograniczenia integralności bazy danych są logicznymi wymaganiami biznesowymi. Pochodzą z logiki domeny aplikacji. Wymóg spójności atomowej jest zupełnie innego rodzaju. Jest to wymóg implementacyjny, który mieści się w kategorii tradycyjnie określanej w branży baz danych jako spójność fizyczna (na przykład podczas wykonywania dowolnej operacji zmiany indeksu wszystkie bloki odpowiedniego drzewa B+ muszą zawierać prawidłowe wartości i być połączone prawidłowymi referencjami) ).

A oto, co dość poważnie piszą w swojej notatce przedstawiciele społeczności bazodanowej Daniel Abadi i Alexander Thomson:

...wymaganie dostępności skalowalnych systemów transakcyjnych staje się coraz bardziej krytyczne, a jest to zazwyczaj realizowane poprzez replikację i automatyczne przekierowanie żądań w przypadku awarii jednego z węzłów. Dlatego twórcy aplikacji oczekują, że gwarancje spójności systemów ACID (pierwotnie polegające na lokalnej obsłudze niezmienników zdefiniowanych przez użytkownika) zostaną rozszerzone, aby zapewnić silną spójność (aby wszystkie repliki tych samych danych w danym momencie były identycznymi kopiami, tj. ta spójność przypadku jest implikowana w sensie CAP/PACELC.

Innymi słowy, spójność Brewera nie ma nic wspólnego ze spójnością ACID, ale to w systemach nastawionych na zapewnienie wysokiej dostępności poprzez replikację danych pożądane jest utrzymanie silnej spójności replik. Nie jest to właściwość ACID, ale techniczna (fizyczna) cecha masowo równoległego DBMS, która ułatwia tworzenie aplikacji.

Według Michaela Stonebreakera kluczem do zbudowania wysokiej jakości nowoczesnego DBMS jest właściwy wybór kompromisów technicznych. Przy wyborze konkretnego rozwiązania inżynierskiego należy wziąć pod uwagę wiele czynników – wymagania przyszłych użytkowników, prawdopodobieństwo wystąpienia różnych sytuacji awaryjnych itp., a nie kierować się dogmatycznie jakimikolwiek ogólnymi teoretycznymi wytycznymi (w tym „twierdzeniem” CAP).

Stonebreaker uważa, że ​​w dziedzinie transakcyjnych równoległych systemów baz danych porzucenie spójności Brewera na rzecz wspierania wysokiej dostępności i tolerancji partycji sieciowych jest kiepskim kompromisem, ponieważ (a) spójność replik jest bardzo użyteczną cechą systemu; (b) transakcyjne masowo równoległe DBMS nie potrzebują klastrów z bardzo dużą liczbą węzłów, więc sytuacje podziału sieci są mało prawdopodobne; (c) system może łatwo stać się niedostępny, nie z powodu podziału sieci, ale na przykład z powodu regularnie występujących błędów oprogramowania.

Tak więc wysoka aktywność przedstawicieli obozu NoSQL (czyt. NoACID), którzy często odwołują się do „twierdzenia” Brewera, nie jest związana z teoretyczną niemożnością zbudowania masowo równoległych transakcyjnych DBMS obsługujących transakcje ACID, ale z faktem, że uproszczone systemy które obsługują nie tylko transakcje ACID, ale także spójność replik, są tworzone łatwiej i szybciej. Ze względu na swoją uproszczoną organizację są zdolne do bardzo szybkiego przetwarzania danych, co dla niektórych aplikacji jest ważniejsze niż wszelkie wygody związane z technologią baz danych.

Zobaczmy, jak społeczność baz danych odpowiada na to wyzwanie.