C.A.P. věta

CAP teorém ( také známý jako Brewerův teorém ) je heuristický výrok, že v žádné implementaci distribuovaného počítání nelze poskytnout více než dvě z následujících tří vlastností :

Zkratka CAP v názvu věty je tvořena z prvních písmen anglických názvů těchto tří vlastností.

Princip navrhl profesor UC Berkeley Eric Brewer v červenci 2000 [1] [2] a následně si získal širokou popularitu a uznání mezi specialisty na distribuované počítače [3] [4] . Koncept NoSQL , v jehož rámci jsou vytvářeny distribuované netransakční systémy pro správu databází , často používá tento princip jako zdůvodnění nevyhnutelnosti selhání konzistence dat [5] [6] [7] . Nicméně, mnoho vědců [8] a praktiků [9] kritizuje teorém CAP pro jeho volný výklad a dokonce nespolehlivost ve smyslu, ve kterém je běžný v komunitě.

Odůvodnění

V roce 2002 vybrali Seth Gilbert a Nancy Lynch z Massachusetts Institute of Technology formální modely asynchronního a synchronního distribuovaného počítání, které ukazují naplnění teorému CAP při absenci synchronizace (společné hodiny) v uzlech distribuovaného systému a zásadní možnost kompromisu v částečně synchronních systémech [10] . V této práci "konzistence" ve smyslu věty CAP koreluje se splněním prvních dvou požadavků ACID  - atomicity a konzistence . V budoucnu mnoho odborníků z praxe odkazovalo na tuto práci jako na důkaz CAP teorému [4] [11] [3] .

Důsledky

Z pohledu CAP teorému spadají distribuované systémy v závislosti na dvojici prakticky podporovaných vlastností ze tří možných do tří tříd - CA, CP, AP.

V systému třídy CA jsou data konzistentní a dostupná napříč všemi uzly a zároveň obětují robustnost rozdělení na oddíly. Takové systémy jsou možné na základě technologického softwaru, který podporuje transakční schopnost ve smyslu ACID , příkladem takových systémů mohou být řešení založená na systémech správy klastrovaných databází nebo distribuované adresářové službě LDAP [12] .

Systém třídy CP v každém okamžiku poskytuje holistický výsledek a je schopen fungovat za podmínek úpadku, ale dosahuje toho na úkor dostupnosti: nemusí reagovat na požadavek. Odolnost vůči rozdělení do sekcí vyžaduje duplikaci změn ve všech uzlech systému, v souvislosti s tím se uvádí praktická účelnost použití distribuovaných pesimistických zámků v takových systémech pro zachování integrity [13] .

V systému třídy AP není integrita zaručena, jsou však splněny podmínky pro přístupnost a odolnost vůči rozdělení. Přestože systémy tohoto druhu byly známy již dávno před formulací principu CAP (například distribuované webové mezipaměti nebo DNS ) [14] , rostoucí obliba řešení s touto sadou vlastností je spojena právě s rozšířením teorému CAP . Většina systémů NoSQL tedy zásadně nezaručuje integritu dat a jako motiv takového omezení odkazuje na teorém CAP [5] . Úkolem při budování AP systémů je poskytnout nějakou prakticky vhodnou úroveň integrity dat, v tomto smyslu se o AP systémech říká, že jsou „nakonec konzistentní “ [ 15] nebo „slabě konzistentní“ ( angl  . slabě konzistentní ) [16] .  

ZÁKLADNÍ architektura

V druhé polovině roku 2000 byl formulován přístup pro budování distribuovaných systémů, ve kterých nejsou plně splněny požadavky na integritu a dostupnost, nazývaný zkratka BASE (z anglického  Basically Available, Soft-state, Eventually konzistentní  - základní dostupnost, nestabilní stavu, konzistence), zatímco tento přístup je přímo protichůdný k ACID [17] . Základní dostupnost se týká přístupu k návrhu aplikace tak, že selhání v některých uzlech vede k odmítnutí služby pouze pro malou část relací při zachování dostupnosti ve většině případů [18] . Volatilní stav znamená schopnost obětovat dlouhodobé ukládání stavu relace (jako jsou mezivýsledky výběrů, informace o navigaci, kontext), přičemž se soustředí na vydávání aktualizací pouze pro kritické operace. Konzistence, která je nakonec v některých případech interpretována jako možnost nekonzistence dat, ale při zajištění shody v prakticky předvídatelné době je věnována značná část nezávislého výzkumu [19] [20] .

Poznámky

  1. ↑ Brewer, 2000 .
  2. ↑ Gilbert, Lynch, 2002 , Na konferenci PODC 2000 Brewer ve své pozvané přednášce vyslovil následující domněnku: Je nemožné, aby webová služba poskytovala následující tři záruky: • Konzistence • Dostupnost • Tolerance oddílů, str. 55.
  3. ↑ 1 2 White Paper Beating the CAP Theorem  (anglicky) ( PDF )  (odkaz není k dispozici) . genedb.com (17. dubna 2011). Získáno 7. června 2011. Archivováno z originálu 28. června 2011.
  4. ↑ 1 2 Browne, Julian Brewer's CAP Theorem  ( 11. ledna 2009). Získáno 7. června 2011. Archivováno z originálu 1. srpna 2012.
  5. ↑ 1 2 Brewer, 2010 , Návrháři velkoplošných systémů, ve kterých jsou síťové oddíly považovány za nevyhnutelné, vědí, že nemohou mít zároveň dostupnost a konzistenci, a proto mohou nyní ospravedlnit slabší konzistenci. Vzestup hnutí „NoSQL“ („Nejen SQL“) je výrazem této svobody, str. 335.
  6. ↑ Rice, 2011 , Tato domněnka je nyní běžně známá jako CAP teorém a je jedním z hlavních argumentů, proč tradiční relační databáze, které poskytují silné ACID záruky (atomové transakce, transakční konzistence a izolace a techniky trvanlivosti dat) nemohou poskytnout obě oblasti tolerance a dostupnost vyžadovaná rozsáhlými distribuovanými aplikacemi, str. 49.
  7. ↑ Kuznetsov, 2011 , Vážnější „teoretický“ základ pro vývoj NoSQL, ve kterém jsou obecně přijímané užitečné vlastnosti systémů správy dat obětovány dostupnosti těchto systémů, je takzvaný „teorém CAP“, který poprvé formuloval Eric Sládek, p. 191.
  8. ↑ Kuznetsov, 2011 , Slovo teorém uzavírám do uvozovek, protože výrok s názvem Brewer nemohu rozpoznat jako teorém z důvodu nedostatku jasného a alespoň trochu formálního vyjádření problému ... ale všeobecně se má za to, že to znamená nemožnost podporovat v jednom distribuovaném systému správy dat vlastnosti konzistence dat (Consistency), dostupnosti (Availability) a odolnosti vůči oddělení sítě (Partitioning), str. 191-192.
  9. ↑ Rice, 2011 , Proč je tedy mnoho předních sociálních sítí (Facebook, MySpace, Twitter), webových stránek elektronického obchodu (hotelové rezervační systémy a nákupní stránky) a velkých bankovních aplikací stále implementováno pomocí tradičních databázových systémů, jako je MySQL? (Facebook, Twitter) nebo SQL Server (MySpace, Choice Hotels International, Bank Itau) namísto použití nových systémů NoSQL? … Odpověď na vysoké úrovni je, že architektura aplikace stále zvažuje stejné kompromisy, které vyžaduje teorém CAP, str. padesáti.
  10. ↑ Gilbert, Lynch, 2002 , V asynchronním modelu, kdy nejsou k dispozici žádné hodiny, je výsledek nemožnosti dosti silný: není možné poskytnout konzistentní data, dokonce ani umožnit vrácení zastaralých dat, když se zprávy ztratí. V částečně synchronních modelech je však možné dosáhnout praktického kompromisu mezi konzistencí a dostupností. 59.
  11. ↑ Grigorik, 2010 , Problém je, že teorém CAP navržený Ericem Brewerem a později dokázaný Sethem Gilbertem a Nancy Lynchovou ukazuje, že dohromady tyto tři požadavky nelze splnit současně.
  12. ↑ Carter, 2011 , Některé systémy CA zahrnují: databáze jednoho místa, klastrové databáze a LDAP.
  13. ↑ Demidov, 2010 , CP (denial of service) je přístup s duplikací, přísnou ACID konzistencí a synchronní replikací změn pomocí metody pesimistického blokování.
  14. ↑ Carter, 2011 , Některé AP systémy zahrnují: Web caching systémy a Domain Name System (DNS).
  15. ↑ Carter, 2011 , Případná konzistence – provedení operace čtení může klientovi poskytnout zastaralá data, ale všechny zápisy se nakonec rozšíří celým systémem.
  16. ↑ Grigorik, 2010 , CAP implikuje slabou konzistenci.
  17. ↑ Pritchett, 2008 , Pokud ACID poskytuje volbu konzistence pro dělené databáze, jak místo toho dosáhnete dostupnosti? Jedna odpověď je BASE (základně dostupná, měkký stav, případně konzistentní). BASE je diametrálně odlišný od ACID.
  18. ↑ Pritchett, 2008 , Dostupnost BASE je dosažena podporou částečných selhání bez úplného selhání systému. Zde je jednoduchý příklad: pokud jsou uživatelé rozděleni na pět databázových serverů, BASE design podporuje vytváření operací takovým způsobem, že selhání uživatelské databáze postihne pouze 20 procent uživatelů na daném hostiteli.
  19. ↑ Stonebreaker, 2010 .
  20. ↑ Vogels, 2008 .

Literatura