Twierdzenie CAP (ang. CAP theorem) mówi, że system rozproszony — czyli baza działająca na wielu maszynach naraz — w momencie awarii sieci może utrzymać tylko jedną z dwóch własności: spójność (Consistency) albo dostępność (Availability). Trzecia litera, odporność na podział sieci (Partition tolerance), nie jest tak naprawdę wyborem — to rzeczywistość, z którą musisz żyć, bo kable się rwą, a pakiety gubią. Sformułował je Eric Brewer w 2000 roku, a formalnie udowodnili Seth Gilbert i Nancy Lynch w 2002.
Rozbijmy te trzy litery na konkrety. C oznacza, że każdy odczyt zwraca najświeższy zapis — nikt nie zobaczy starych danych. A to gwarancja, że każde zapytanie dostanie odpowiedź (nie błąd, nie timeout). P to zdolność systemu do dalszej pracy, gdy część węzłów straci ze sobą kontakt.
Dlaczego musisz wybierać
Sztuczka polega na tym, że tak naprawdę wybierasz tylko w trakcie podziału sieci (partition). Gdy wszystko działa, masz i spójność, i dostępność — bez problemu. Ale kiedy dwa centra danych przestają się słyszeć, system musi zdecydować: albo odrzuca zapisy, żeby dane się nie rozjechały (wybiera CP), albo przyjmuje je dalej, ryzykując, że dwa węzły będą miały różne wersje prawdy (wybiera AP). Trzeciej drogi nie ma — to nie kwestia lepszego sprzętu, tylko fizyki i logiki.
Przykład z praktyki
MongoDB to klasyk obozu CP. Gdy primary node traci kontakt z resztą replica set, przestaje przyjmować zapisy i odpala wybory nowego primary — przez kilka sekund baza woli powiedzieć „nie da rady” niż zapisać niespójne dane. Z drugiej strony Apache Cassandra stawia na AP: zapis przyjmie zawsze, a o poziomie spójności decydujesz per zapytanie. Ustawiasz to przez consistency level, np.:
CONSISTENCY QUORUM;
Im wyżej (np. ALL), tym bliżej spójności, ale tym łatwiej o niedostępność, gdy węzły padną. To dosłownie pokrętło CAP w twoich rękach.
Częste mity
Najczęstszy błąd to myślenie „wybieram dwie z trzech jak z menu”. Nie — P jest dane z góry w każdym realnym systemie rozproszonym, więc prawdziwy wybór toczy się między C a A. Drugi mit: „baza CA istnieje”. Owszem, ale tylko na jednej maszynie, gdzie podziału sieci po prostu nie ma — i wtedy CAP cię nie dotyczy. Trzeci: ludzie traktują CAP zero-jedynkowo, a w praktyce systemy stroją to płynnie (patrz consistency level Cassandry). Dlatego powstało rozszerzenie PACELC, które dorzuca pytanie o trade-off między latencją a spójnością, gdy sieć działa normalnie.
Pojęcia powiązane: eventual consistency, ACID, BASE, teoremat PACELC, replikacja danych, partycjonowanie, quorum, systemy rozproszone.