Ett illustrerat bevis på CAP-satsen

CAP-satsen är en grundläggande sats i distribuerade system som säger att alla distribuerade system kan ha högst två av följande tre egenskaper.

• konsistens
• tillgänglighet
• Partitionstolerans

denna guide kommer att sammanfatta Gilbert och Lynchs specifikation och bevis på CAP-satsen med bilder!

Vad är CAP-satsen?

CAP-satsen säger att ett distribuerat system inte samtidigt kan vara konsekvent, tillgängligt och partitionstolerant. Låter enkelt nog, men vad betyder det att vara konsekvent? tillgänglig? partitionstolerant? Heck, vad exakt menar du ens med ett distribuerat system?

i det här avsnittet introducerar vi ett enkelt distribuerat system och förklarar vad det betyder för att systemet ska vara tillgängligt, konsekvent och partitionstolerant. För en formell beskrivning av systemet och de tre egenskaperna, se Gilbert och Lynchs papper.

ett distribuerat System

låt oss överväga ett mycket enkelt distribuerat system. Vårt system består av två servrar, $G_1$ och $G_2$. Båda dessa servrar håller reda på samma variabel, $v$, vars värde initialt är $v_0$. $G_1$ och $G_2$ kan kommunicera med varandra och kan också kommunicera med externa klienter. Så här ser vårt system ut.

en klient kan begära att skriva och läsa från vilken server som helst. När en server tar emot en begäran utför den alla beräkningar den vill ha och svarar sedan på klienten. Till exempel, här är vad en skrivning ser ut.

så här ser en läsning ut.

nu när vi har fått vårt system etablerat, låt oss gå igenom vad det betyder för systemet att vara konsekvent, tillgängligt och partitionstolerant.

konsistens

så här beskriver Gilbert och Lynch konsistens.

varje läsoperation som börjar efter att en skrivoperation har slutförts måste returnera det värdet eller resultatet av en senare skrivoperation

i ett konsekvent system, när en klient skriver ett värde till en server och får ett svar, förväntar den sig att få det värdet (eller ett fräschare värde) tillbaka från vilken server den läser från.

här är ett exempel på ett inkonsekvent system.

vår klient skriver $v_1$ till $G_1$ och $G_1$ erkänner, men när det läser från $G_2$ blir det inaktuella data: $v_0$.

å andra sidan är här ett exempel på ett konsekvent system.

i det här systemet replikerar $G_1$ sitt värde till $G_2$ innan du skickar en bekräftelse till klienten. Således, när klienten läser från $G_2$, får den det mest aktuella värdet på $v$: $v_1$.

tillgänglighet

så här beskriver Gilbert och Lynch tillgänglighet.

varje begäran som tas emot av en icke-misslyckad nod i systemet måste resultera i ett svar

i ett tillgängligt system, om vår klient skickar en begäran till en server och servern inte har kraschat, måste servern så småningom svara på klienten. Servern får inte ignorera klientens förfrågningar.

Partitionstolerans

så här beskriver Gilbert och Lynch partitioner.

nätverket kommer att tillåtas att förlora godtyckligt många meddelanden som skickas från en nod till en annan

detta innebär att alla meddelanden $G_1$ och $G_2$ skicka till varandra kan tappas. Om alla meddelanden tappades skulle vårt system se ut så här.

vårt system måste kunna fungera korrekt trots godtyckliga nätverkspartitioner för att vara partitionstoleranta.

beviset

nu när vi har bekantat oss med begreppet konsistens, tillgänglighet och partitionstolerans kan vi bevisa att ett system inte samtidigt kan ha alla tre.

Antag för motsägelse att det finns ett system som är konsekvent, tillgängligt och partitionstolerant. Det första vi gör är att partitionera vårt system. Det ser ut så här.

därefter har vi vår kundbegäran att $v_1$ skrivs till $G_1$. Eftersom vårt system är tillgängligt måste $G_1$ svara. Eftersom nätverket är partitionerat kan $G_1$ dock inte replikera sina data till $G_2$. Gilbert och Lynch kallar denna fas av utförandet $ \ alpha_1$.

därefter har vi vår klient utfärda en läsförfrågan till $G_2$. Återigen, eftersom vårt system är tillgängligt, måste $G_2$ svara. Och eftersom nätverket är partitionerat kan $G_2$ inte uppdatera sitt värde från $G_1$. Den returnerar $v_0$. Gilbert och Lynch kallar denna fas av utförandet $ \ alpha_2$.

$G_2 $ returnerar $v_0$ till vår klient efter att klienten redan hade skrivit $v_1$ till $G_1$. Detta är inkonsekvent.

vi antog ett konsekvent, tillgängligt, partitionstolerant system existerade, men vi visade bara att det finns en exekvering för ett sådant system där systemet fungerar inkonsekvent. Således finns inget sådant system.