CAP teorém

Pokud začneme hlouběji uvažovat nad distribuovanými systémy, je dobré znát jejich limity. CAP teorém patří mezi ty nejzákladnější a nejjednodušší vůbec. Jestliže chceme kryptografickou svobodu nejen přijmout, ale i plně pochopit, je nezbytné se někdy zabývat těmito, na první pohled nudnými, záležitostmi, jako jsou matematicko-informatické důkazy.

Úvod

CAP teorém formalizuje některé užitečné limity spolehlivosti distribuovaných systémů. Protože kryptosítě jsou distribuované systémy (a vlastně vše, o čem se v rámci rubriky Kryptografie bavíme, také), je velmi užitečné znát jejich limity. Pro tento článek vám stačí znát, co je to DLT. Po přečtení budete vyzbrojeni zhruba pěti procenty vědomostí nutných pro pochopení tzv. shardingu na Ethereu 2.0 (kryptoměně pro chytré smlouvy).

CAP trilema

CAP teorém je věta z oblasti teoretické informatiky. Je nazývána též Brewerův teorém podle Erica Brewera, který ji popsal v roce 1999. Řekl, že u distribuovaného datového úložiště (DLT) nelze splnit více než dvě z následujících garancí:

  • Konzistentnost (Consistency): při každém čtení obdržíme nejnovější zápis nebo chybu (souvisí s problémem dvojitého utracení a DLT vůbec)
  • Dostupnost (Aviability): každý požadavek obdrží nechybovou odpověď, ale bez garance, že obsahuje nejnovější zápis
  • Odolnost vůči přerušení (Partition tolerance): systém pokračuje v operování bez ohledu na arbitrární počet zpráv zasílaných nebo zpožďovaných uzly sítě

Pokud dojde k přerušení (výpadku části sítě), měli bychom se rozhodnout:

  • Zrušit operaci a tím snížit dostupnost, ale zajistit konzistenci
  • Pokračovat v operaci a zajistit tak dostupnost, ale podstoupit riziko nesrovnalosti (nekonzistence)

CAP teorém znamená, že při přerušení v síti je třeba si vybrat mezi konzistencí a dostupností. Odolnost vůči přerušení logicky nemůžeme obětovat, protože pak by distribuované úložiště při rozdělení sítě nefungovalo vůbec (tj. v praxi nemůžeme připustit, že k přerušení nedojde).

Přerušení sítě znamená její rozklad na relativně nezávislé podsítě (network split) následkem selhání síťového zařízení. Ukažme si to na příkladu.

Rozdělení distribuované sítě

Jak se může síť rozdělit? Představte si, že si založíte vlastní banku a máte dva bankomaty (ATM). S bankomaty můžete jako uživatel provést tři operace: vložit peníze, vybrat peníze a zkontrolovat stav účtu. Navíc nechcete, aby se bilance dostala do záporu.

Kopie bilance účtů si u sebe uchovává každý z nich. Pokud zákazník k některému z nich přijde a vybere si (nebo vloží) peníze, tak se bilance aktualizuje i na druhém z ATM.

Může nastat pár nepříznivých situací. Zaprvé, zákazník přijde k ATM a on nebude fungovat. S tím toho aktivně moc nenaděláme, možná na něj vyvěsíme cedulku, že je mimo provoz, a máme hotovo. A zadruhé, což je horší, nebude fungovat druhý z ATM. To znamená přerušení sítě těchto dvou ATM. Zde přichází do hry CAP teorém – musíme si vybrat mezi konzistentností a dostupností.

Pokud zvolíme konzistentní design, odmítne ATM obsloužit zákazníka, protože to není bezpečné. Na druhém ATM by se totiž bilance nemusela aktualizovat. Pokud zvolíme dostupný design, tak ATM obslouží zákazníka, ale může nastat problém s aktualizací dat na druhém ATM (data budou navzájem nekonzistentní). Při volbě dostupnosti nad konzistencí tak systém vždy zpracuje dotaz a pokusí se vrátit nejnovější dostupnou verzi informací, i když nemůže zaručit, že je aktuální kvůli síťovému rozdělení.

Zdroj: Cryptographics

CAP teorém v reálném světě

Ve skutečném světě ale mluvíme o stupních dostupnosti a konzistence, přičemž mezi tím můžeme dělat tradeoffy.

Např. částečně dostupný design zmíněného ATM by vypadal jako:

  • Vklady: ano
  • Výběry: ne
  • Info o bilanci: orientační

Nebo takto:

  • Vklady: ano
  • Výběry: malé a méně časté (ano, bilance se může dostat do záporu, ale ne příliš hodně a moc rychle)
  • Info o bilanci: orientační

Samozřejmě, pokud mám síť, kde k přerušení nedochází, nemusíme tento tradeoff činit.

V případě, že ale např. vyžadujeme operaci v odpojeném off-line režimu zařízení (tj. Google Docs Documents, obecně cloudová služba), rozhodně budeme tento tradeoff činit (systém, který umožní vysokou dostupnost na úkor konzistence mezi cloudem a vaším zařízením – pak budete muset vyřešit, jak data později synchronizovat).

Vysvětlení

Konzistentnost systému

Konzistentnost systému – když každý uzel poskytuje nejnovější stav systému

Pokud nemá systém nejnovější stav, neposkytne žádnou odpověď. Konzistentnost systému říká, že žádné dva uzly sítě nebudou mít různý stav v libovolném čase a že žádný uzel nevrátí prošlý stav (outdated).

Dostupnost systému

Dostupnost systému – každý uzel má nepřetržitý přístup k zápisu a čtení stavu

Dostupný systém mi umožní dělat aktualizace a obdržet stav systému bez zpoždění. Dostupnost mi slibuje to, co se má stát – umožnit čtení a zápis stavu. Zápis stavu byl v případě banky vklad nebo výběr.

Odolnost vůči přerušení

Odolnost vůči přerušení – schopnost dvou a více uzlů v síti navzájem komunikovat

O odolnosti systému vůči přerušení můžete přemýšlet jako o neomezené latenci sítě, což znamená, že se zpráva nikdy nedostane následkem síťového zpoždění ke svému příjemci. Odolnost vůči přerušení nám říká, že síť nepřestane fungovat i za přítomnosti přerušení mezi síťovými spojeními.

Důkaz

Důkaz není třeba provádět, protože vysvětlení teorému je zcela intuitivní.

Zdroje

Wikipedia – CAP teorém (úvod)

Wikipedia – rozdělení sítě

Youtube (Distributed Systems Course) – příklad

Youtube (Blockchain at BerkeleyX) – vysvětlení

Cryptographics – náhled

Napsat komentář

Tato stránka používá Akismet k omezení spamu. Podívejte se, jak vaše data z komentářů zpracováváme..