Teorema C.A.P

Teorema CAP (cunoscută și ca teorema lui Brewer ) este o declarație euristică conform căreia nu pot fi furnizate mai mult de două dintre următoarele trei proprietăți în orice implementare a calculului distribuit :

Acronimul CAP din numele teoremei este format din primele litere ale numelor englezești ale acestor trei proprietăți.

Principiul a fost propus de profesorul UC Berkeley Eric Brewer în iulie 2000 [1] [2] și ulterior a câștigat o mare popularitate și recunoaștere în rândul specialiștilor în calculul distribuit [3] [4] . Conceptul NoSQL , în cadrul căruia sunt create sisteme de gestionare a bazelor de date non- tranzacționale distribuite , utilizează adesea acest principiu ca rațiune pentru inevitabilitatea eșecului de consistență a datelor [5] [6] [7] . Cu toate acestea, mulți oameni de știință [8] și practicieni [9] critică teorema CAP pentru interpretarea ei liberă și chiar lipsa de încredere în sensul în care este comună în comunitate.

Justificări

În 2002, Seth Gilbert și Nancy Lynch de la Massachusetts Institute of Technology au selectat modele formale de calcul distribuit asincron și sincron, care arată îndeplinirea teoremei CAP în absența sincronizării (ceasul comun) la nodurile unui sistem distribuit și posibilitatea fundamentală a unui compromis în sistemele parțial sincrone [10 ] . În această lucrare, „coerența” în sensul teoremei CAP este corelată cu îndeplinirea primelor două cerințe de ACID  - atomicitate și consistență . În viitor, mulți practicieni s-au referit la această lucrare ca pe o dovadă a teoremei CAP [4] [11] [3] .

Consecințele

Din punctul de vedere al teoremei CAP, sistemele distribuite, în funcție de o pereche de proprietăți suportate practic, din trei posibile, se încadrează în trei clase - CA, CP, AP.

Într-un sistem de clasă CA, datele sunt consistente și disponibile pe toate nodurile, sacrificând în același timp robustețea partiționării. Astfel de sisteme sunt posibile bazate pe software tehnologic care suportă tranzacționalitatea în sensul ACID , exemple de astfel de sisteme pot fi soluții bazate pe sisteme de management al bazelor de date în cluster sau un serviciu de directoare distribuit LDAP [12] .

Un sistem de clasă CP oferă în fiecare moment un rezultat holistic și este capabil să funcționeze în condiții de degradare, dar realizează acest lucru în detrimentul disponibilității: este posibil să nu răspundă unei cereri. Reziliența la împărțirea în secțiuni necesită duplicarea modificărilor în toate nodurile sistemului, în legătură cu aceasta, se remarcă oportunitatea practică a utilizării încuietorilor pesimiste distribuite în astfel de sisteme pentru a menține integritatea [13] .

Într-un sistem de clasă AP, integritatea nu este garantată, dar sunt îndeplinite condițiile de accesibilitate și rezistență la partiționare. Deși sisteme de acest fel au fost cunoscute cu mult înainte de formularea principiului CAP (de exemplu, cache-urile web distribuite sau DNS ) [14] , popularitatea tot mai mare a soluțiilor cu acest set de proprietăți este asociată tocmai cu răspândirea teoremei CAP. . Astfel, majoritatea sistemelor NoSQL în mod fundamental nu garantează integritatea datelor și se referă la teorema CAP ca motiv pentru o astfel de restricție [5] . Sarcina în construirea sistemelor AP este de a oferi un nivel practic de integritate a datelor, în acest sens, despre sistemele AP se spune că sunt „eventual consistente ” [ 15] sau „slab consistent” ( ing  . slab consistent ) [16] .  

Arhitectura BASE

În a doua jumătate a anilor 2000, a fost formulată o abordare pentru construirea de sisteme distribuite în care cerințele de integritate și disponibilitate nu sunt pe deplin îndeplinite, numită acronimul BASE (din engleză  Basicically Available, Soft-state, Eventually consistent  - disponibilitate de bază, instabil). stare, consistență în cele din urmă), în timp ce această abordare este direct opusă ACID [17] . Disponibilitatea de bază se referă la o abordare a proiectării unei aplicații astfel încât o defecțiune în unele noduri duce la o refuz de serviciu doar pentru o mică parte a sesiunilor, menținând în același timp disponibilitatea în majoritatea cazurilor [18] . Starea volatilă implică capacitatea de a sacrifica stocarea pe termen lung a stării sesiunii (cum ar fi rezultatele intermediare ale selecțiilor, informații despre navigare, context), concentrându-se în același timp pe comiterea actualizărilor doar pentru operațiunile critice. Consecvența, care în cele din urmă este interpretată ca posibilitatea de inconsecvență a datelor în unele cazuri, dar în timp ce se asigură acordul într-un timp practic previzibil, o cantitate semnificativă de cercetări independente este dedicată [19] [20] .

Note

  1. ↑ Berărie, 2000 .
  2. ↑ Gilbert, Lynch, 2002 , La PODC 2000, Brewer, într-o discuție invitată, a făcut următoarea presupunere: este imposibil ca un serviciu web să ofere următoarele trei garanții: • Consistență • Disponibilitate • Toleranță la partiție, p. 55.
  3. ↑ 1 2 Cartea albă Beating the CAP Theorem  (engleză) ( PDF )  (link nu este disponibil) . genedb.com (17 aprilie 2011). Consultat la 7 iunie 2011. Arhivat din original pe 28 iunie 2011.
  4. ↑ 1 2 Browne, Teorema CAP a lui Julian Brewer  ( 11 ianuarie 2009). Consultat la 7 iunie 2011. Arhivat din original la 1 august 2012.
  5. ↑ 1 2 Brewer, 2010 , Proiectanții sistemelor de suprafață largă, în care partițiile de rețea sunt considerate inevitabile, știu că nu pot avea atât disponibilitate, cât și consistență și, astfel, pot justifica acum o consistență mai slabă. Ascensiunea mișcării „NoSQL” („Nu numai SQL”) este o expresie a acestei libertăți, p. 335.
  6. ↑ Rice, 2011 , Această presupunere este acum cunoscută sub numele de teorema CAP și este unul dintre principalele argumente pentru care bazele de date relaționale tradiționale care oferă garanții puternice ACID (tranzacții atomice, consistență și izolare tranzacțională și tehnici de durabilitate a datelor) nu pot oferi atât partiția. toleranța și disponibilitatea cerute de aplicațiile distribuite pe scară largă, p. 49.
  7. ↑ Kuznetsov, 2011 , O bază „teoretică” mai serioasă pentru dezvoltările NoSQL, în care proprietățile utile general acceptate ale sistemelor de management al datelor sunt sacrificate pentru disponibilitatea acestor sisteme, este așa-numita „teoremă CAP”, formulată pentru prima dată de Eric. Berărie, p. 191.
  8. ↑ Kuznetsov, 2011 , încadrez cuvântul teorema între ghilimele, deoarece nu pot recunoaște afirmația numită Brewer ca teoremă din cauza lipsei oricărei enunțuri clare și cel puțin ușor formale a problemei... dar se crede că înseamnă imposibilitatea suportării într-un singur sistem de management al datelor distribuit a proprietăților de consistență a datelor (Consistență), disponibilitate (Disponibilitate) și rezistență la separarea rețelei (Partiționare), p. 191-192.
  9. ↑ Rice, 2011 , Deci, de ce multe dintre cele mai importante site-uri de rețele sociale (Facebook, MySpace, Twitter), site-uri web de comerț electronic (sisteme de rezervare la hoteluri și site-uri de cumpărături) și aplicații bancare mari sunt încă implementate folosind sisteme tradiționale de baze de date, cum ar fi MySQL (Facebook, Twitter) sau SQL Server (MySpace, Choice Hotels International, Bank Itau) în loc să folosiți noile sisteme NoSQL? … Răspunsul la nivel înalt este că arhitectura aplicației încă cântărește aceleași compromisuri cerute de teorema CAP, p. cincizeci.
  10. ↑ Gilbert, Lynch, 2002 , Într-un model asincron, când nu sunt disponibile ceasuri, rezultatul imposibilității este destul de puternic: este imposibil să se furnizeze date consistente, permițând chiar returnarea datelor învechite atunci când mesajele sunt pierdute. Cu toate acestea, în modelele parțial sincrone este posibil să se realizeze un compromis practic între consistență și disponibilitate, p. 59.
  11. ↑ Grigorik, 2010 , Problema este, teorema CAP propusă de Eric Brewer și demonstrată ulterior de Seth Gilbert și Nancy Lynch, arată că împreună, aceste trei cerințe sunt imposibil de realizat în același timp.
  12. ↑ Carter, 2011 , Unele sisteme CA includ: baze de date cu un singur site, baze de date cluster și LDAP.
  13. ↑ Demidov, 2010 , CP (denial of service) este o abordare cu duplicare, consistență strictă a ACID și replicare sincronă a modificărilor folosind metoda blocării pesimiste.
  14. ↑ Carter, 2011 , Some AP Systems includ: Web caching systems and the Domain Name System (DNS).
  15. ↑ Carter, 2011 , Consecvență eventuală – efectuarea unei operații de citire poate oferi clientului date învechite, dar toate scrierile se vor propaga în cele din urmă prin întregul sistem.
  16. ↑ Grigorik, 2010 , CAP Implica Weak Consistency.
  17. ↑ Pritchett, 2008 , Dacă ACID oferă opțiunea de consistență pentru bazele de date partiționate, atunci cum obțineți disponibilitatea în schimb? Un răspuns este BASE (disponibil în principiu, stare soft, eventual consistent). BASE este diametral opusă cu ACID.
  18. ↑ Pritchett, 2008 , Disponibilitatea BASE este atinsă prin suportarea defecțiunilor parțiale fără defecțiuni totale ale sistemului. Iată un exemplu simplu: dacă utilizatorii sunt împărțiți pe cinci servere de baze de date, designul BASE încurajează operațiunile de creare, astfel încât o defecțiune a bazei de date a utilizatorilor să afecteze doar 20% dintre utilizatorii de pe gazda respectivă.
  19. ↑ Stonebreaker, 2010 .
  20. ↑ Vogels, 2008 .

Literatură