O dovadă ilustrată a teoremei CAP

Teorema CAP este o teoremă fundamentală în sistemele distribuite care afirmă că orice sistem distribuit poate avea cel mult două dintre următoarele trei proprietăți.

• consistență
• disponibilitate
• toleranță partiție

acest ghid va rezuma Gilbert și Lynch CAIETUL DE SARCINI și dovada teoremei capac cu imagini!

care este teorema CAP?

teorema PAC afirmă că un sistem distribuit nu poate fi simultan consecvent, disponibil și tolerant la partiție. Sună destul de simplu, dar ce înseamnă să fii consecvent? disponibil? partition tolerant? La naiba, ce vrei să spui cu un sistem distribuit?

în această secțiune, vom introduce un sistem distribuit simplu și vom explica ce înseamnă ca acel sistem să fie disponibil, consecvent și tolerant la partiții. Pentru o descriere formală a sistemului și a celor trei proprietăți, vă rugăm să consultați hârtia lui Gilbert și Lynch.

un sistem distribuit

să luăm în considerare un sistem distribuit foarte simplu. Sistemul nostru este compus din două servere, $g_1$ și $g_2$. Ambele servere urmăresc aceeași variabilă, $v$, a cărei valoare este inițial $v_0$. $G_1 $ și $g_2$ pot comunica între ei și pot comunica și cu clienți externi. Iată cum arată sistemul nostru.

un client poate solicita să scrie și să citească de pe orice server. Când un server primește o cerere, efectuează orice calcule pe care le dorește și apoi răspunde clientului. De exemplu, iată cum arată o scriere.

și iată cum arată o citire.

acum că ne-am stabilit sistemul, să trecem în revistă ce înseamnă ca sistemul să fie consecvent, disponibil și tolerant la partiții.

consistență

Iată cum descriu Gilbert și Lynch consistența.

orice operație de citire care începe după finalizarea unei operații de scriere trebuie să returneze acea valoare sau rezultatul unei operații de scriere ulterioare

într-un sistem consecvent, odată ce un client scrie o valoare oricărui server și primește un răspuns, se așteaptă să obțină acea valoare (sau o valoare mai proaspătă) înapoi de la orice server de pe care citește.

Iată un exemplu de sistem inconsistent.

clientul nostru scrie $v_1$ la $g_1 $ și $g_1$ recunoaște, dar când citește de la $g_2$, primește date învechite: $v_0$.

pe de altă parte, iată un exemplu de sistem consecvent.

în acest sistem, $g_1 $ își reproduce valoarea la $g_2 $ înainte de a trimite o confirmare Clientului. Astfel, atunci când clientul citește de la $g_2$, acesta obține cea mai actualizată valoare a $v$: $v_1$.

disponibilitate

Iată cum descriu Gilbert și Lynch disponibilitatea.

fiecare solicitare primită de un nod care nu eșuează în sistem trebuie să aibă ca rezultat un răspuns

într-un sistem disponibil, dacă clientul nostru trimite o solicitare către un server și serverul nu s-a prăbușit, atunci serverul trebuie să răspundă în cele din urmă clientului. Serverul nu are voie să ignore solicitările clientului.

toleranță partiție

Iată cum Gilbert și Lynch descrie partiții.

rețelei i se va permite să piardă în mod arbitrar multe mesaje trimise de la un nod la altul

aceasta înseamnă că orice mesaje $g_1$ și $g_2$ trimise unul altuia pot fi abandonate. Dacă toate mesajele ar fi fost abandonate, atunci sistemul nostru ar arăta așa.

sistemul nostru trebuie să poată funcționa corect în ciuda partițiilor de rețea arbitrare pentru a fi tolerant la partiții.

dovada

acum că ne-am familiarizat cu noțiunea de consistență, disponibilitate și toleranță la partiție, putem dovedi că un sistem nu le poate avea simultan pe toate trei.

presupunem pentru contradicție că există un sistem care este consecvent, disponibil și tolerant la partiție. Primul lucru pe care îl facem este partiționarea sistemului nostru. Se pare ca acest lucru.

apoi, avem cererea clientului nostru ca $v_1$ să fie scris în $g_1$. Deoarece sistemul nostru este disponibil, $g_1$ trebuie să răspundă. Deoarece rețeaua este partiționată, cu toate acestea, $g_1$ nu poate reproduce datele sale la $g_2$. Gilbert și Lynch numesc această fază de execuție $ \ alpha_1$.

apoi, avem clientul nostru emite o cerere de citire la $g_2$. Din nou, deoarece sistemul nostru este disponibil, $g_2$ trebuie să răspundă. Și din moment ce rețeaua este partiționată, $g_2$ nu își poate actualiza valoarea de la $g_1$. Se întoarce $v_0$. Gilbert și Lynch numesc această fază de execuție $ \ alpha_2$.

$G_2 $ returnează$ v_0 $ clientului nostru după ce clientul a scris deja $v_1$ la $g_1$. Acest lucru este inconsistent.

am presupus că există un sistem consecvent, disponibil, tolerant la partiție, dar tocmai am arătat că există o execuție pentru orice astfel de sistem în care sistemul acționează inconsecvent. Astfel, nu există un astfel de sistem.