Ilustrovaný Důkaz CAP Teorém

SZP Věta je zásadní věta v distribuovaných systémů, které státy jakýkoliv distribuovaný systém může mít maximálně dvě z těchto tří vlastností.

• konzistence
• dostupnost
• tolerance oddílů

Tato příručka shrnuje specifikaci Gilberta a Lynche a důkaz věty CAP s obrázky!

co je věta CAP?

věta CAP uvádí, že distribuovaný systém nemůže být současně konzistentní, dostupný a tolerantní k oddílům. Zní to dost jednoduše, ale co to znamená být konzistentní? k dispozici? oddíl tolerantní? Sakra, co přesně myslíte distribuovaným systémem?

V této části představíme jednoduchý distribuovaný systém, a vysvětlit, co to znamená pro tento systém k dispozici, v souladu, a oddíl tolerantní. Formální popis systému a tří vlastností naleznete v dokumentu Gilberta a Lynche.

distribuovaný systém

uvažujme o velmi jednoduchém distribuovaném systému. Náš systém se skládá ze dvou serverů, $G_1$ a $G_2$. Oba tyto servery sledují stejnou proměnnou $v$, jejíž hodnota je zpočátku $v_0$. $G_1$ a $G_2$ mohou komunikovat mezi sebou a mohou také komunikovat s externími klienty. Takhle vypadá náš systém.

klient může požádat o zápis a čtení z libovolného serveru. Když server obdrží požadavek, provede všechny výpočty, které chce, a poté odpoví klientovi. Například, zde je to, jak vypadá zápis.

a tady je to, co čtení vypadá.

Teď, že jsme dostali náš systém založen, pojďme na to, co to znamená pro systém musí být konzistentní, k dispozici, a oddíl tolerantní.

konzistence

zde je návod, jak Gilbert a Lynch popisují konzistenci.

žádné operace čtení, které začíná po operaci zápisu dokončí se musí vrátit, že hodnoty, nebo výsledek později psát provoz

V konzistentní systém, jakmile klient zapíše hodnotu na server a dostane odpověď, že očekává, že se dostat, že hodnotu (nebo čerstvější) hodnoty zpět z jakéhokoliv serveru se to čte.

zde je příklad nekonzistentního systému.

Náš klient píše, $v_1$, $G_1$ a $G_1$ uznává, ale když to čte z $G_2$, to bude zastaralé údaje: $v_0$.

na druhé straně je zde příklad konzistentního systému.

V tomto systému, $G_1$ kopíruje její hodnotu na $G_2$ před odesláním potvrzení klienta. Když tedy klient čte z $G_2$, získá nejaktuálnější hodnotu $v$: $v_1$.

dostupnost

zde je návod, jak Gilbert a Lynch popisují dostupnost.

každou žádost, kterou obdrží non-selhání uzlu v systému musí vyústit v reakci

k dispozici V systému, pokud náš klient odešle požadavek na server a server má nehavarované, pak server se nakonec musí reagovat na klienta. Server nesmí ignorovat požadavky klienta.

tolerance oddílů

zde je návod, jak Gilbert a Lynch popisují oddíly.

síť bude umožněno přijít libovolně mnoho zpráv odeslaných z jednoho uzlu do druhého.

To znamená, že všechny zprávy, $G_1$ a $G_2$ posílat jeden druhému může být zrušen. Pokud by byly všechny zprávy zrušeny, náš systém by vypadal takto.

náš systém musí být schopen správně fungovat i přes libovolné síťové oddíly, aby byl tolerantní k oddílům.

Důkaz

Teď, když jsme seznámili se s pojmem konzistence, dostupnost, a partition tolerance, můžeme dokázat, že systém nemůže zároveň mít všechny tři.

Předpokládejme pro rozpor, že existuje systém, který je konzistentní, dostupný a tolerantní k oddílům. První věc, kterou uděláme, je rozdělit náš systém. Vypadá to takto.

dále máme požadavek klienta, aby $v_1$ byl zapsán na $G_1$. Vzhledem k tomu, náš systém je k dispozici, $G_1$ musí reagovat. Vzhledem k tomu, že síť je rozdělena, $G_1$ nemůže replikovat svá data na $G_2$. Gilbert a Lynch nazývají tuto fázi provádění $ \ alpha_1$.

dále máme náš klient vydat read request na $G_2$. Znovu, protože náš systém je k dispozici, $G_2$ musí reagovat. A protože síť je rozdělena, $G_2$ nemůže aktualizovat svou hodnotu z $G_1$. Vrací $v_0$. Gilbert a Lynch nazývají tuto fázi provádění $ \ alpha_2$.

$G_2$ vrací $v_0$ našemu klientovi poté, co klient již napsal $v_1$ na $G_1$. To je nekonzistentní.

Jsme předpokládali, že konzistentní, k dispozici, oddíl tolerantní systém existoval, ale jen jsme ukázali, že existuje provedení pro jakýkoli takový systém, ve kterém systém působí nekonzistentně. Žádný takový systém tedy neexistuje.