Twierdzenie CAP u progu dorosłości

Większość osób pracujących w branży IT słyszała zapewne o twierdzeniu CAP (CAP theorem), które Eric Brewer ogłosił w 1999. Od tego czasu stało się ono standardem myślenia o architekturze aplikacji rozproszonych. Niedawno natknąłem się na interesujący artykuł CAP theorem revisited autorstwa urodzonego w Wielkiej Brytanii fizyka i informatyka Marka Burgessa, w którym przygląda się on ponownie twierdzeniu CAP, dowodzi braku jego matematycznych podstaw i proponuje całkiem interesującą alternatywę. Lektura artykułu Burgessa skłoniła mnie też do przeczytania kilku innych opracowań, które odnoszą się do CAP ze współczesnej perspektywy.

Burgess uważa, że twierdzenie CAP jest po prostu błędne. Swoją argumentację rozpoczyna od stwierdzenia, że w związku z brakiem matematycznego dowodu (istnieje wszakże szczegółowe wyjaśnienie autorstwa Setcha Gilberta i Nancy Lynch) nie jest ono twierdzeniem, a raczej domysłem. Autor używa również teorii względności by dowieść, że zignorowanie przez CAP upływającego czasu czyni je błędnym. Ostatecznie, zamiast trzymać się CAP, proponuje alternatywne rozwiązanie, Promise Theory, kładące nacisk na autonomię każdego agenta (czy też węzła) i jego odpowiedzialność za wyłącznie swoje działania.

Wspomniany artykuł Gilberta i Lynch jest próbą nakreślenia bardziej precyzyjnych ram dla CAP. Autorzy dostarczają znacznie bardziej precyzyjnych definicji dla wszystkich trzech komponentów, a także uwzględniają upływ czasu oraz asynchroniczność połączeń sieciowych. Artykuł dostarcza wielu ciekawych informacji, jednakże również mu brakuje matematycznego dowodu. Burgess twierdzi, że brak tegoż jest jedną z głównych słabości CAP.

Wg szczególnej teorii względności Einsteina dwa zdarzenia, które mają miejsce w dwóch różnych miejscach nie mogą być jednoczesne. Ich jednoczesność albo kolejność zależy od położenia obserwatora i kierunku jego ruchu. Jeśli zastosujemy względność jednoczesności do CAP to okaże się, że w rozproszonym systemie (którego elementy są rozrzucone w przestrzeni z samej jego natury) nie możemy mówić o jednoczesności, a co za tym idzie spójności, z absolutnego punktu widzenia.

Z tej perspektywy Burgess próbuje zdefiniować trzy komponenty CAP możliwie najprecyzyjniej. W pierwszej kolejności próbuje uwzględnić upływający czas. Dostępność staje się możliwością obiecania, że odpowiedź na każde odebrane żądanie zostanie odesłana przed upływem określonego czasu – jest to jedyna prosta definicja wg Burgessa. Spójność, jako że zależy od dotrzymania obietnic przez inne węzły systemu, nie jest czymś, co może zostać lekkomyślnie obiecane. Według autora jedynie spójność ostateczna (eventual consistency) może zostać obiecana, albowiem nie jest możliwe zapewnienie natychmiastowej spójności w działającym systemie – potrzebny jest czas na osiągnięcie przez niego równowagi.

Najbardziej niejasna okazuje się jednak definicja odporności na awarie sieci (partition tolerance). Jest ona możliwa do sformułowania, ale definicja (obietnica dostarczenia prawidłowej odpowiedzi przed upływem określonego czasu nawet, jeśli odpowiedź jest zależna od informacji znajdujących się w niedostępnej części sieci) wydaje się być niepraktyczna i wymagałaby sporo pracy w celu przygotowania odpowiedzi, która byłaby prawidłowa tylko dla fragmentu systemu działającego w obrębie tej samej dostępnej części sieci.

Twierdzenie CAP widziane z tej perspektywy wydaje się faktycznie być błędne bardzo trudno bowiem określić jasne granice jego składowych. Burgess zwraca też uwagę na to, że CAP całkowicie ignoruje końcowego użytkownika informacji i uważa, że ten czynnik ma w tej chwili zasadniczy wpływ na oderwanie twierdzenia od otaczającej rzeczywistości. W celu przybliżenia swojej koncepcji autor przywołuje przykład gita i continuous deployment. Używając gita tworzymy wiele niespójnych środowisk, gałęzi, które mogą (ale nie muszą) zostać ze sobą w pewnym momencie połączone. Jeśli dodamy do tego continuous deployment, to ujrzymy proces stopniowego przenoszenia zmian (z lokalnego środowiska programisty przez środowisko testowe aż po produkcję). Łączenie gałęzi prowadzi do ponownego osiągnięcia równowagi przez system, ale jest to proces, który trwa pewien czas. Co więcej nie powinien być przeprowadzany za każdym razem, gdy pojawi się zmiana powodująca naruszenie spójności – w przeciwnym wypadku bardzo szybko doprowadzilibyśmy całą aplikację do niestabilności wdrażając każdą pojedynczą zmianę na produkcję.

Trzymając się dalej analogii z gitem należy uznać, że proces osiągania równowagi przez system powinien być zainicjowany z wewnątrz, a nie narzucony z zewnątrz. Gałąź istniejąca w repozytorium jest utrzymywana w zgodności poprzez pobieranie informacji o zmianach z zewnątrz, a nie przez odbieraniu komunikatów z centralnego węzła odpowiedzialnego za nadzór na spójnością całego systemu. Zadaniem lokalnego węzła (w tym wypadku programisty) jest zadecydowanie kiedy powinien on zweryfikować swoją spójność z pozostałymi węzłami; niektóre zmiany mogą nie mieć znaczenia albo mogą zostać zintegrowane później.

Burgess uważa, że systemy opierające się na wysyłaniu komunikatów (w których istnieje jeden wszystkowiedzący węzeł odpowiedzialny za utrzymanie spójności) nie są w stanie określić czy cały system jest spójny. Z kolei w systemach których składowe są autonomiczne każdy węzeł odpowiada za swoją własną spójność i jako jedyny może określić czy jest spójny. Ta właśnie myśl wydaje się być kluczowym wnioskiem autora.

Trzymanie się koncepcji Burgessa przy projektowaniu systemów rozproszonych może bardzo ułatwić nam pracę. Zamiast tworzyć scentralizowane aplikacje, których bardzo istotną słabością jest uzależnienie od możliwości odebrania komunikatów z głównego węzła (bądź klastra węzłów) powinniśmy skupić się na niezależności poszczególnych węzłów i pozwolić na osiąganie przez nie równowagi przez wzajemną komunikację. Nawet jeśli taki system nie będzie przez cały czas spójny, to osiągnie on ostatecznie równowagę zachowując jednocześnie wysoką dostępność.

Dalsze zgłębianie Promise Theory i współczesnych zastrzeżeń wobec CAP warto zacząć od artykułu Burgessa i przejrzenia listy źródeł na jego końcu. Szczególnie godne uwagi wydają się być artykuł Brewera na temat CAP napisany dwanaście lat po ogłoszeniu twierdzenia i proponowana przez Abadiego alternatywa bądź rozszerzenie CAP – PACELC.

(See English version: CAP theorem revisited)