Teorema CAP - CAP theorem

În informatică teoretică , teorema CAP , numită și teorema lui Brewer după informaticianul Eric Brewer , afirmă că orice magazin de date distribuit poate oferi doar două dintre următoarele trei garanții:

Coerență
Fiecare citire primește cea mai recentă scriere sau o eroare.
Disponibilitate
Fiecare solicitare primește un răspuns (fără erori), fără garanția că conține cea mai recentă scriere.
Toleranță partiție
Sistemul continuă să funcționeze în ciuda unui număr arbitrar de mesaje care au fost abandonate (sau întârziate) de rețeaua dintre noduri.

Atunci când se produce o defecțiune a partiției de rețea, trebuie decis dacă

  • anulați operațiunea și astfel reduceți disponibilitatea, dar asigurați coerența sau
  • continuați operațiunea și astfel asigurați disponibilitatea, dar incoerența riscului.

Astfel, dacă există o partiție de rețea, trebuie să alegeți între consistență și disponibilitate. Rețineți că consistența definită în teorema CAP este destul de diferită de consistența garantată în tranzacțiile bazei de date ACID .

Eric Brewer susține că conceptul „doi din trei” des folosit poate fi oarecum înșelător, deoarece proiectanții de sistem trebuie să sacrifice consecvența sau disponibilitatea doar în prezența partițiilor, dar că în multe sisteme partițiile sunt rare.

Explicaţie

Niciun sistem distribuit nu este ferit de eșecurile rețelei, prin urmare partiționarea rețelei trebuie în general tolerată. În prezența unei partiții, una rămâne apoi cu două opțiuni: consistență sau disponibilitate . Atunci când alegeți consistența față de disponibilitate, sistemul va returna o eroare sau o expirare dacă anumite informații nu pot fi garantate că sunt actualizate din cauza partiționării de rețea. Atunci când alegeți disponibilitatea peste consistență, sistemul va procesa întotdeauna interogarea și va încerca să returneze cea mai recentă versiune disponibilă a informațiilor, chiar dacă nu poate garanta că este actualizată din cauza partiționării de rețea.

CAP este adesea înțeleasă greșit ca fiind o alegere în orice moment, dintre care una dintre cele trei garanții să o abandoneze. De fapt, alegerea este între consistență și disponibilitate numai atunci când se întâmplă o partiție de rețea sau o eroare. Atunci când nu există eșecuri de rețea, atât disponibilitatea, cât și consistența pot fi satisfăcute.

CAP a fost folosit de mulți furnizori de baze de date NoSQL ca o justificare pentru a nu furniza consistență ACID tranzacțională, susținând că teorema CAP „dovedește” că este imposibil să se asigure scalabilitate și consistență ACID în același timp. Cu toate acestea, o privire mai atentă la teorema CAP și, în special, la formalizarea de către Gilbert & Lynch, relevă faptul că teorema CAP nu se referă deloc la scalabilitate, ci doar la disponibilitate (A în CAP).

Sistemele de baze de date proiectate având în vedere garanțiile tradiționale ACID, cum ar fi RDBMS, aleg consistența față de disponibilitate, în timp ce sistemele concepute în jurul filosofiei BASE , obișnuite în mișcarea NoSQL , de exemplu, aleg disponibilitatea în locul consistenței.

PACELC teorema se bazează pe PAC afirmând că , chiar și în absența partiționare, există un alt compromis între latență și consecvență.

Istorie

Potrivit Universității din California, informaticianul Berkeley, Eric Brewer , teorema a apărut pentru prima dată în toamna anului 1998. A fost publicată ca principiul CAP în 1999 și prezentată ca o presupunere de către Brewer la Simpozionul 2000 privind principiile de calcul distribuit (PODC). În 2002, Seth Gilbert și Nancy Lynch de la MIT au publicat o dovadă formală a conjecturii lui Brewer, făcând din aceasta o teoremă .

În 2012, Brewer și-a clarificat unele dintre pozițiile sale, inclusiv de ce conceptul adesea folosit „doi din trei” poate fi oarecum înșelător, deoarece proiectanții de sistem trebuie să sacrifice consecvența sau disponibilitatea doar în prezența partițiilor; există tehnici de gestionare și recuperare a partițiilor. Brewer a remarcat, de asemenea, diferita definiție a consistenței utilizată în teorema CAP față de definiția utilizată în ACID .

O teoremă similară care afirmă compromisul între consistență și disponibilitate în sisteme distribuite a fost publicată de Birman și Friedman în 1996. Rezultatul Birman și Friedman a limitat această limită inferioară la operațiuni care nu fac naveta.

Tehnologia Blockchain sacrifică consistența disponibilității și toleranței partiției, dar se realizează prin validarea între noduri în timp, având impresia rezultată că teorema nu este validă.

Vezi si

Referințe

linkuri externe