A CAP tétel illusztrált bizonyítéka

a CAP tétel az elosztott rendszerek alapvető tétele, amely kimondja, hogy bármely elosztott rendszernek a következő három tulajdonság közül legfeljebb kettő lehet.

• következetesség
• elérhetőség
• partíció tolerancia

ez az útmutató összefoglalja Gilbert és Lynch specifikáció és bizonyíték a CAP tétel képekkel!

mi a CAP tétel?

a CAP tétel kimondja, hogy egy elosztott rendszer nem lehet egyszerre konzisztens, elérhető és partíció toleráns. Elég egyszerűnek hangzik, de mit jelent következetesnek lenni? elérhető? partíció toleráns? Heck, pontosan mit is jelent az elosztott rendszer?

ebben a részben bemutatunk egy egyszerű elosztott rendszert, és elmagyarázzuk, mit jelent az, hogy a rendszer elérhető, konzisztens és partíció-toleráns. A rendszer és a három tulajdonság hivatalos leírását lásd Gilbert és Lynch tanulmányában.

elosztott rendszer

Vegyünk egy nagyon egyszerű elosztott rendszert. A rendszer két szerverből áll, $G_1$ és $G_2$. Mindkét szerver ugyanazt a változót követi nyomon, $v$, amelynek értéke kezdetben $v_0$. $G_1$ és $G_2$ kommunikálhatnak egymással és kommunikálhatnak külső ügyfelekkel is. Így néz ki a rendszerünk.

az ügyfél bármely szerverről kérhet írást és olvasást. Amikor egy szerver kérést kap, elvégzi a kívánt számításokat, majd válaszol az ügyfélnek. Például itt van, hogy néz ki egy írás.

így néz ki egy olvasmány.

most, hogy létrehoztuk a rendszerünket, nézzük át, mit jelent a rendszer következetessége, elérhetősége és partíció toleranciája.

konzisztencia

így írja le Gilbert és Lynch a következetességet.

minden olyan olvasási műveletnek, amely egy írási művelet befejezése után kezdődik, vissza kell adnia ezt az értéket, vagy egy későbbi írási művelet eredménye

következetes rendszerben, ha az ügyfél egy értéket ír egy kiszolgálóra, és választ kap, elvárja, hogy ezt az értéket (vagy egy frissebb értéket) visszakapja bármely kiszolgálótól, amelyről olvas.

íme egy példa egy következetlen rendszerre.

ügyfelünk $v_1$ – t ír $ G_1$ – ra és $G_1$ nyugtázza, de amikor $G_2$ – ról olvas, elavult adatokat kap: $v_0$.

másrészt itt van egy példa a következetes rendszerre.

ebben a rendszerben a $G_1$ megismétli az értékét $G_2$ – ra, mielőtt nyugtát küldene az ügyfélnek. Így, amikor az ügyfél $G_2$ – ból olvas, a legfrissebb értéket kapja $v$: $v_1$.

elérhetőség

így írja le Gilbert és Lynch az elérhetőséget.

a rendszer nem hibás csomópontjától kapott minden kérésnek

választ kell eredményeznie egy rendelkezésre álló rendszerben, ha az ügyfél kérést küld egy szervernek, és a szerver nem összeomlott, akkor a szervernek végül válaszolnia kell az ügyfélnek. A szerver nem hagyhatja figyelmen kívül az ügyfél kéréseit.

partíciós tolerancia

így írja le Gilbert és Lynch a partíciókat.

a hálózat önkényesen elveszítheti az egyik csomópontról a másikra küldött üzeneteket

ez azt jelenti, hogy a $G_1$ és $G_2$ egymásnak küldött üzenetek eldobhatók. Ha az összes üzenetet eldobnák, akkor a rendszerünk így nézne ki.

rendszerünknek képesnek kell lennie arra, hogy az önkényes hálózati partíciók ellenére megfelelően működjön, hogy partíció toleráns legyen.

a bizonyíték

most, hogy megismertük a konzisztencia, a rendelkezésre állás és a partíciós tolerancia fogalmát, be tudjuk bizonyítani, hogy egy rendszerben nem lehet egyszerre mindhárom.

tegyük fel az ellentmondás kedvéért, hogy létezik olyan rendszer, amely következetes, elérhető és partíció toleráns. Az első dolog, amit csinálunk, a rendszerünk particionálása. Így néz ki.

ezután ügyfelünk azt kéri, hogy $v_1$ legyen írva $G_1$ – ra. Mivel a rendszerünk elérhető, a $G_1$ – nak válaszolnia kell. Mivel azonban a hálózat particionálva van, a $G_1$ nem tudja megismételni az adatait $G_2$ – ra. Gilbert és Lynch ezt a végrehajtási fázist $\alpha_1$ – nak nevezik.

ezután ügyfelünk olvasási kérelmet ad ki $G_2$ – ra. Ismét, mivel a rendszerünk elérhető, a $G_2$ – nak válaszolnia kell. Mivel a hálózat particionálva van, a $G_2$ nem tudja frissíteni az értékét $G_1$ – ról. Visszatér $v_0$. Gilbert és Lynch ezt a végrehajtási fázist $\alpha_2$ – nak nevezik.

$G_2$ $v_0$ – t ad vissza ügyfelünknek, miután az ügyfél már $ v_1$ – t írt $G_1$ – ra. Ez következetlen.

feltételeztük, hogy létezik egy következetes, elérhető, partíció toleráns rendszer, de csak megmutattuk, hogy létezik olyan végrehajtás minden ilyen rendszer számára, amelyben a rendszer következetlenül működik. Ilyen rendszer tehát nem létezik.