Et illustreret bevis på CAP-sætningen

CAP-sætningen er en grundlæggende sætning i distribuerede systemer, der angiver, at ethvert distribueret system højst kan have to af følgende tre egenskaber.

• konsistens
• tilgængelighed
• Partitionstolerance

denne vejledning opsummerer Gilbert og Lynchs specifikation og bevis for CAP-sætningen med billeder!

Hvad er CAP-sætningen?

CAP-sætningen siger, at et distribueret system ikke samtidig kan være konsistent, tilgængeligt og partitionstolerant. Lyder simpelt nok, men hvad betyder det at være konsekvent? tilgængelig? partition tolerant? Heck, hvad mener du endda med et distribueret system?

i dette afsnit introducerer vi et simpelt distribueret system og forklarer, hvad det betyder for det system at være tilgængeligt, konsistent og partitionstolerant. For en formel beskrivelse af systemet og de tre egenskaber henvises til Gilbert og Lynchs papir.

et distribueret System

lad os overveje et meget simpelt distribueret system. Vores system består af to servere, $G_1$ og $G_2$. Begge disse servere holder styr på den samme variabel, $v$, hvis værdi oprindeligt er $v_0$. $G_1$ og $G_2$ kan kommunikere med hinanden og kan også kommunikere med eksterne klienter. Sådan ser vores system ud.

en klient kan anmode om at skrive og læse fra enhver server. Når en server modtager en anmodning, udfører den alle beregninger, den ønsker, og reagerer derefter på klienten. For eksempel, her er hvordan en skrivning ser ud.

og her er hvordan en læsning ser ud.

nu hvor vi har fået vores system etableret, lad os gå over, hvad det betyder for systemet at være konsistent, tilgængeligt og partitionstolerant.

konsistens

sådan beskriver Gilbert og Lynch konsistens.

enhver læseoperation, der begynder, efter at en skrivehandling er afsluttet, skal returnere denne værdi eller resultatet af en senere skrivehandling

i et ensartet system, når en klient skriver en værdi til en server og får et svar, forventer den at få den værdi (eller en friskere værdi) tilbage fra enhver server, den læser fra.

her er et eksempel på et inkonsekvent system.

vores klient skriver $v_1$ til $G_1$ og$ G_1 $ anerkender, men når det læser fra $G_2$, bliver det forældede data: $v_0$.

på den anden side er her et eksempel på et konsistent system.

i dette system replikerer $G_1$ sin værdi til $G_2$, før du sender en bekræftelse til klienten. Således, når klienten læser fra $G_2$, får den den mest opdaterede værdi på $v$: $v_1$.

tilgængelighed

sådan beskriver Gilbert og Lynch tilgængelighed.

hver anmodning modtaget af en ikke-svigtende node i systemet skal resultere i et svar

i et tilgængeligt system, hvis vores klient sender en anmodning til en server, og serveren ikke er gået ned, skal serveren til sidst svare på klienten. Serveren må ikke ignorere klientens anmodninger.

Partitionstolerance

sådan beskriver Gilbert og Lynch partitioner.

netværket får lov til at miste vilkårligt mange meddelelser sendt fra en node til en anden

dette betyder, at alle meddelelser $G_1$ og $G_2$ send til hinanden kan tabes. Hvis alle meddelelser blev droppet, ville vores system se sådan ud.

vores system skal kunne fungere korrekt på trods af vilkårlige netværkspartitioner for at være partitionstolerant.

beviset

nu hvor vi har kendskab til begrebet konsistens, tilgængelighed og partitionstolerance, kan vi bevise, at et system ikke samtidig kan have alle tre.

Antag for modsigelse, at der findes et system, der er konsistent, tilgængeligt og partitionstolerant. Den første ting, vi gør, er at opdele vores system. Det ser sådan ud.

Dernæst har vi vores klient anmodning om, at $v_1$ skrives til $G_1$. Da vores system er tilgængeligt, skal $G_1$ svare. Da netværket er opdelt, kan $G_1$ imidlertid ikke replikere sine data til $G_2$. Gilbert og Lynch kalder denne fase af udførelsen $ \ alpha_1$.

Dernæst har vi vores klient udstede en læse anmodning til $G_2$. Igen, da vores system er tilgængeligt, skal $G_2$ svare. Og da netværket er opdelt, kan $G_2$ ikke opdatere sin værdi fra $G_1$. Det returnerer $v_0$. Gilbert og Lynch kalder denne fase af udførelsen $ \ alpha_2$.

$G_2 $ returnerer $v_0$ til vores klient, efter at klienten allerede havde skrevet $v_1$ til $G_1$. Dette er inkonsekvent.

vi antog, at der eksisterede et konsistent, tilgængeligt, partitionstolerant system, men vi viste bare, at der findes en udførelse for ethvert sådant system, hvor systemet virker inkonsekvent. Således findes der ikke noget sådant system.