SoftWare Samuraj: CAP Theorem

Byl jsem teď na pracovním pohovoru. Byl první a zatím ne poslední. Mám z toho takový dost rozpačitý pocit, ale o tom napíšu někdy příště. Zmiňuju to proto, že jsem z toho minimálně vytěžil téma článku.

O co šlo? Bylo mi na závěr pohovoru doporučeno, že pokud bych postoupil do druhého kola, tak bych si měl určitě nastudovat CAP Theorem.

Beru to jako příležitost a jelikož jsem zrovna četl výborný článek Techniques for Efficiently Learning Programming Languages, volím formu blog postu. A rovnou na rovinu říkám, že CAP Theorem je pro mne... ehm, theorem, teoretické tvrzení, se kterým nemám praktickou zkušenost. Takže budu rád, pokud mne v komentářích opravíte, nebo doplníte.

CAP Theorem à la Wikipedia

Začněme definicí z Wikipedie: CAP Theorem říká, že "pro distribuovaný počítačový systém je nemožné poskytovat simultáně více, než dvě ze tří následujících garancí:"

Konzistence (Consistency) - systém vrátí při každém čtení poslední zápis.
Dostupnost (Availability) - systém vrátí pro každý požadavek odpověď, nicméně bez garance, že jde o poslední zápis.
Tolerance rozdělení (Partition Tolerance) - systém zpracovává informace navzdory tomu, že došlo k rozdělení sítě (network partition), způsobené chybou komunikace mezi sub-systémy.

Wikipedia dále říká, že "žádný distribuovaný systém není imunní proti síťovému selhání, tudíž rozdělení sítě musí být tolerováno. V případě rozdělení, tak nastává volba mezi konzistencí a dostupností."

Zároveň je potřeba zdůraznit, že "volba mezi konzistencí a dostupností nastává pouze tehdy, pokud dojde k rozdělení; v ostatních případech není potřeba dělat kompromis."

Tolik tedy Wikipedia. Samozřejmě, Wikipedia je skvělý začátek, kde začít hledat informace. Ale pak je lepší jít trochu blíže ke zdroji.

CAP Theorem originál

CAP Theorem byl původně prezentován Ericem Brewerem v roce 2000 na konferenci Principles of Distributed Computing, jako součást jeho key note Toward Robust Distributed Systems.

CAP Theorem, původní slide (zdroj: Toward Robust Distributed Systems)

Brewer tehdy prezentoval i další věci, které ho ke CAP Theoremu dovedly, a které nám dnes již přijdou samozřejmé. Třeba, že persistence v distribuovaném systému je složité téma, nebo rozdíl mezi ACID a BASE přístupem.

ACID vs. BASE (zdroj: Toward Robust Distributed Systems)

Pro mne nejzajímavější myšlenka celé key note zazní už na začátku: "Klasické distribuované systémy se zaměřují na výpočet, ne na data. To je ŠPATNĚ, výpočet je ta jednoduchá část."

Persistent State is HARD (zdroj: Toward Robust Distributed Systems)

CAP Theorem vědecky

Brewer tehdy ve své key note prezentoval CAP problém, jako theorem, tvrzení bez (matematického) důkazu (tedy přesněji jako doměnku - conjecture). Důkaz platnosti theoremu na sebe nechal čekat dva roky, kdy dva vědci z MIT - Seth Gilbert a Nancy Lynch - prokázali platnost theoremu, pomocí formálního modelu, ve své tezi Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services.

Při čtení tohoto dokumentu můžeme vidět určitý posun v chápání daného problému. Jednak se zde už nemluví o distribuovaných systémech, ale o webových službách. A pak je celý problém a jeho popis pozvednut na vyšší, abstraktnější úroveň. Za zmínku stojí asi hlavně dva modely, na kterých je důkaz postaven.

První model používá asynchronní síťový model, který nemá žádné hodiny (synchronizaci času) a jednotlivé síťové uzly se tak musejí rozhodovat pouze na základě přijatých zpráv a lokálních výpočtů.

Druhý model se více blíží reálnému světu - v částečně synchronním modelu (partially synchronous model) má každý node své hodiny, které mají všechny stejné tempo. Hodiny nicméně nejsou synchronizovány, takže můžou ukazovat různé hodnoty pro stejný reálný čas.

V závěrečném hodnocení modelů se píše: "V asynchronním modelu, kdy nejsou dostupné žádné hodiny, je nemožnost výsledku (impossibility result) velmi silná: je nemožné poskytovat konzistentní data a to i tehdy, pokud povolíme návrat zastaralých dat v případě ztracených zpráv. Ovšem v případě částečně synchronních modelů je možné dosáhnout praktického kompromisu mezi konzistencí a dostupností. Většina dnešních real-world systémů je nucena pracovat způsobem, kdy vrací maximum dat po většinu času.”

CAP Theorem Re-visited

Naše povídání by nebylo úplné, kdybychom se nepodívali, jak to bylo dál - už jsme všichni velcí kluci a holky a víme, že žádné "žili šťastně až do smrti" neexistuje.

Ke CAP Theoremu se po 12 letech vrátil sám Eric Brewer v obsáhlém článku CAP Twelve Years Later: How the "Rules" Have Changed. Je to zajímavé čtení. Brewer tam - nijak překvapivě - říká, CAP Theorem byl velmi často nepochopen.

Vezměme si například důkaz, zmíněný v předešlé sekci - sice je formálně a matematicky správný, ale je postaven jen... na dvou nodech. To přece není realita systémů, kterých se CAP týká.

Jak říká Brewer: "Designéři systému by neměli slepě obětovat konzistenci, nebo dosupnost, pokud existuje rozdělení." Především je potřeba revidovat tvrdé pravidlo "2 ze 3". Jak v článku opakovaně zaznívá, vztah jednotlivých CAP aspektů je spektrum, nikdy to není binární. (Mimochodem, pokud jste si nevšimli, podívejte se ještě jednou výše na patičku slidu ACID vs. BASE - zaznělo to už tenkrát.)

Převážná část článku je věnována strategiím, jak řešit rozdělení sítě a následné zotavení se. Například jednou z možností zotavení jsou kompenzace, klasický nástroj dlouho-trvajících transakcí. Další možností je rekonciliace pomocí verzovacích vektorů (version vector). Někdy každá část partition použije různou strategii a tedy akcentuje jiný aspekt, tj. někdy dostupnost, jindy konzistenci.

Zotavení se z rozdělení (zdroj: CAP Twelve Years Later)

Co si z toho odnáším?

Bylo zábavné se teoreticky zorientovat v (momentálně) odlehlé oblasti mého oboru. Rád čtu a přemýšlím nad věcmi a zpracovat si to formou psaní je fajn. Na druhou stranu, nosnost a rozsáhlost dané oblasti pro mne zatím není tak přitažlivá, abych se pustil do nějakého praktického výzkumu. I když bych se třeba rád podíval na NoSQL databáze, které hodně těží z BASE principu.

Takže? Na pohovoru to už příště budu sypat z rukávu. A taky se budu trochu kritickým okem dívat na ty, co se budou ptát... už nebudou v takové převaze. A brát to trochu s nadhledem - svět není černobílý... je to spektrum.