Zatrolený CAP

S tím jak se šíří cloudové šílenství, čím dál tím víc lidí naráží do CAP teorému. Mě i mé kolegy nevyjímaje. Tak jsem si řekl, že si to tu vyjasním.

CAP teorém zjednodušeně říká, že distribuovaný systém, nemůže splňovat všechny tři následující vlastnosti:

  1. Consistency – konzistence – všichni klienti vidí stejná data
  2. Availability – dostupnost – každý klient může vždy číst i zapisovat
  3. Partition tolerance – odolnost vůči rozdělení – systém funguje i když se rozpadne na víc nezávislých častí

Jak sami vidíte, není to zrovna moc exaktně definováno. Co to znamená, že systém funguje při rozpadu na víc částí? Čert ví. Často se také liší definice jednotlivých vlastností. Ale nevadí, že je to vágní. I tak je důležité je mít tu větu neustále na mysli, když se pokoušíte o distribuovaný systém.

Pro jednoduchost si představme, že máme dva databázové servery, kterým budeme říkat třeba Anička a Bohouš. Takže máme Aničku a Bohouše a samozřejmě chceme, aby klienti mohli zapisovat a číst přes oba dva. Taky chceme, aby Anička poznala, že se Bohouš rozbil, a vzala to na chvíli místo něj. No a pak jsou tu tak samozřejmé požadavky, že je snad ani nemusíme zmiňovat. Jako třeba, že se nám nesmí ztrácet data. Když něco zapíšeme, chceme, aby to tam zůstalo. A samozřejmě potřebujeme, aby to všechno jelo tak rychle, jak je jen možné. To se snad rozumí samo sebou.

Problém je, že to nejde.

V první řadě nedokážeme zajistit konzistenci, pokud se provádí zápis přes víc serverů. Nebo přesněji, nedokážeme to pokud chceme změny provádět rychle. Kvůli konzistenci musíme totiž zajistit, že nepřijmeme konfliktní zápisy. Jako třeba pokus o současné převedení peněz z jednoho účtu. Pokud to provede zároveň pro různé požadavky Anička i Pepík tak nakonec může účet skončit v mínusu, i když je to zakázané.

Tento problém se obvykle řeší tak, že všechny změny provádí jen jeden server. Ten už si dokáže ohlídat, jestli se někdo nesnaží dostat do mínusu. Nebo musíme dělat něco jako distribuované transakce, což je nejen pomalejší, ale stejně to zatíží všechny servery, takže se to ani nevyplatí.

Tím pádem můžeme zjednodušeně říci, že pokud vyžadujeme konzistenci, všechny zápisy musí jít přes jeden server. Třeba přes Aničku. Stačí to aby se zajistila konzistence? Přijde na to. Pokud klienti čtou z Bohouše, tak mohou vidět stará data. Pokud se jedná o milisekundy, tak se vždycky můžeme vymlouvat, že ten zápis proběhl až potom, co začali číst. Potíže nastanou, když je zpoždění větší nebo když něco zapíšu na jednom serveru a pak to na tom druhém ještě nevidím. Oboje jsou to řešitelné problémy. Třeba tak, že Bohouš pozná, že má stará data, a v takovém případě přepošle požadavky na Aničku.

Skvělé, takže jsem vyřešili konzistenci, co ostatní požadavky? Dostupnost? Brnkačka. Bohouš pozná, že Anička odpadla a vezme práci za ní. Tak to obvykle řeší klasické relační databáze. Tak v čem je problém?

Samozřejmě, že v té odolnosti vůči rozdělení. Když se nám rozpadne spojení mezi oběma servery, můžou si oba myslet, že je ten druhý spinká a začnou přijímat zápisy. Což nám rozbije konzistenci. Tento problém se před pár lety nemusel řešit. Oba servery obvykle byly spojeny superrychlým superspolehlivým spojením, takže byl rozpad clusteru nepravděpodobný. Dnes ale žijeme v době superlevného superšitoidního cloudu, takže se sít rozpadne několikrát za týden.

Co s tím? Třeba MongoDB to řeší tak, že nás nutí mít lichý počet serverů. Přijímat zápisy pak může jenom ten, co vidí většinu nodů v clusteru. Takže Anička s Bohoušem musí pozvat Cecilku a zapisovat bude jen ten, co vidí alespoň jednoho dalšího. Pokud se síť rozpadne, servery se rozhlédnou a pokud vidí alespoň jeden jiný server, tak se s ním dohodnou, kdo z nich bude zapisovat.

Skvělé, to vypadá, jako kdybychom měli splněné všechny tři podmínky. Ha, hloupá CAP věta vyvrácena. Nebo ne? Bohužel ne. Tím, že jsme si zajistili odolnost vůči rozpadnutí jsme se připravili o dostupnost. Pokud totiž žádný server nevidí většinu clusteru nebude zapisovat nikdo z nich. Sakra.

Pokud máme nespolehlivou síť, tak si prostě musíme vybrat mezi případnou nekonzistencí, která hrozí třeba u MySQL nebo nedostupností, která hrozí u MongoDB. Prostě a zkrátka, pokud se spolu servery nemůžou domluvit, tak jich buď může zapisovat víc nebo žádný.

Zajímavá varianta je, rovnou se vzdát konzistence. To dělá třeba CouchDB. Pokud dojde v konfliktu v datech, tak to jednoduše uloží jako různé verze jednoho dokumentu a řešení hodí na někoho jiného. Buď na aplikaci nebo rovnou na uživatele. Tím pádem nemají problém v tom zajistit dostupnost a odolnost vůči síťovým problémům. Takže třeba můžou mít offline kopii, která se po připojení do online režimu automaticky sesynchronizuje.

Mám dojem, že jsem vyčerpal nejen vás, ale i všechny možnosti. Nebo jsem na něco zapomněl? Nezmínil jsem sharding. Ale sharding nám v podstatě jenom zajistí rozpad jednoho distribuvaného systému na víc nezávislých. Tím si sice rozložíme zátěž, ale CAP teorém nám to neobejde. Na ten budeme nadále narážet v rámci jednotlivých shardů. Hmm, už mě nic nenapadá, tak vás jen poprosím. Nepokoušejte se psát systémy, které jsou konzistentní, stále dostupné a vydrží rozpad sítě. Opravdu to nejde.

Odkazy:

Jak si MongDB replica set volí mastera

Pěkné přirovnání na CAP teorém

Obrazový průvodce NoSQL systémy

Vyvrácení CAP teorému

7 Responses to “Zatrolený CAP”

  1. LubosCZ Says:

    O CAP teorému jsem toho zatím moc neslyšel, tak díky za uvedení. Nějak jsem to tušil, ale nevěděl, že to má jméno. 🙂 S ohledem na to, že od chlapců z GooData to není první článek o Mongu a replikacích, tak se zdá, že Vás něco trápí... Trochu mně to s těmi nereláčními DB stroji přijde jako návrat na stromy. To, že nejde jednoduše udělat join, dobrá. Ale řešit ještě chod na více instancí na tak nízké úrovní, mně překvapuje.

  2. Ondrej Says:

    CAP je dohad(!) ktory vyzera ze je spravny. Cele je to pekne vysvetlene to originalnom prispevku:
    C - je vlastne atomicita -> vsetky potvrdene zmeny su vyditelne kazdemu klientovy
    A - system vzdy odpovie -> volanie neskonci chybou ale volanie moze trvat lubovolne dlho
    P - Pokial nenastane totalny vypadok siete tak ziadna ina chyba nesmie system znefunkcnit

    Takto definovany CAP je skutocne "pick two".

    Cassandra si vymyslela "eventual consistency", Hyperdex ma CAP ak je v systeme menej ako F chyb a chyby su na menej ako F nodoch. atd...

  3. Lukáš Křečan Says:

    @LubosCZ Popravdě řečeno, s Mongem ty problémy nemáme. Snažíme se je řešit na MySQL, kde potřebujeme měnit ta samá data na víc datových centrech pokud možno konzistentně. Kdybychom to měli v Mongu, tak bychom měli půlku starostí vyřešenou.

  4. banter Says:

    Do odkazů bych ještě doplnil http://www.julianbrowne.com/article/viewer/brewers-cap-theorem

  5. lzap Says:

    Pekne. Shitoidni cloud 🙂

  6. Přemysl Čončka Says:

    K tomu vynikající článek na téma "You Can’t Sacrifice Partition Tolerance" od Coda Hale, architekta infrastruktury Yammeru.

  7. Stanislav Poljovka Says:

    Prehladne rozdelenie NoSQL databaz na zaklade CAP teoremu a datovemu modelu je na http://blog.nahurst.com/visual-guide-to-nosql-systems