Teorema CAP
PAC Teorema sau COP, de asemenea , cunoscut sub numele de numele teorema Brewer , spune că este imposibil pe un sistem de calculator pentru calcul distribuit pentru a se asigura în același timp (adică atât sincron ) după trei constrângeri:
-
Consistență ( consistență în engleză): toate nodurile din sistem văd exact aceleași date în același timp;
-
Disponibilitate ( Disponibilitate în limba engleză): garantează că toate întrebările sunt răspunse;
-
Partiționarea toleranței ( Partition Tolerance English): nu se blochează mai puțin decât o defecțiune totală a rețelei ar trebui să împiedice sistemul să răspundă corect (sau: dacă fragmentarea în subrețele, fiecare trebuie să poată funcționa autonom).
Atenție : în această definiție, termenul „partiționare” nu trebuie înțeles în sensul că, într-o bază de date, un obiect poate fi împărțit în mai multe destinații de stocare, ci ca mașini distincte (în general numite noduri) care posedă fiecare o parte a datelor astfel încât, singur, setul de noduri face posibilă reconstituirea tuturor datelor bazei.
Conform acestei teoreme, un sistem distribuit de calcul / stocare poate garanta la un moment dat T doar două dintre aceste constrângeri, dar nu pe toate trei.
Istoric
Teorema pleacă de la o presupunere afirmată de informaticianul Eric Brewer de la Universitatea din California la Berkeley în timpul Simpozionului privind principiile de calcul distribuit (PODC). În 2002, Seth Gilbert și Nancy Lynch de la MIT au publicat o dovadă formală a verificabilității conjecturii lui Brewer și au făcut din aceasta o teoremă stabilită.
Ilustrații vectoriale
- Fie A și B doi utilizatori ai sistemului, fie N1 și N2 două noduri ale sistemului. Dacă A modifică o valoare pe N1, atunci pentru ca B să vadă această valoare pe N2 este necesar să așteptați până când N1 și N2 sunt sincronizate. Dacă N1 și N2 trebuie să servească întotdeauna ca valori consistente, atunci există un timp incompresibil între începutul scrierii, sincronizare și următoarea lectură. Pe un sistem foarte încărcat și foarte mare, acest timp incompresibil va influența considerabil disponibilitatea și rezistența la fragmentare. Există, evident, tehnici de optimizare de această dată, dar cu cât sistemul este mai mare, cu atât este mai dificil de redus.
- Exemplu de arbitraj implicat de teorema CAP: doi utilizatori care efectuează aceeași căutare pe același motor de căutare pot obține rezultate diferite, dar putem considera că acest dezavantaj este mai puțin grav decât să nu aibă deloc rezultate.
Referințe
-
(în) [PDF] Lynch, Nancy și Seth Gilbert, „ Conjectura lui Brewer și fezabilitatea unor servicii web consistente, disponibile, tolerante la partiții. »În ACM SIGACT News , v. 33 N ° 2, 2002, p. 51-59.
-
(în) julianbrowne.com: Teorema Brewer's CAP. Accesat la 2 martie 2010.
-
(en) royans.net: Teorema Brewers CAP este sisteme distribuite.
-
(în) Eric Brewer, „ Către sisteme distribuite robuste ” , la Universitatea Berkeley .
-
http://davidmasclet.gisgraphy.com/post/2010/06/09/10-minutes-pour-comprendre...NoSQL
linkuri externe