ET Illustrert Bevis På CAP-Teoremet
CAP-Teoremet Er et grunnleggende teorem i distribuerte systemer som sier at ethvert distribuert system kan ha maksimalt to av følgende tre egenskaper.
- Konsistens
- Tilgjengelighet
- Partisjonstoleranse
denne veiledningen vil oppsummere Gilbert og Lynchs spesifikasjon og bevis på CAP-Teoremet med bilder!
Hva er CAP-Teoremet?
CAP-teoremet sier at et distribuert system ikke samtidig kan være konsistent, tilgjengelig og partisjonstolerant. Høres enkelt nok, men hva betyr det å være konsekvent? tilgjengelig? partisjon tolerant? Heck, hva mener du selv med et distribuert system?
i denne delen introduserer vi et enkelt distribuert system og forklarer hva det betyr for at systemet skal være tilgjengelig, konsistent og partisjonstolerant. For en formell beskrivelse av systemet og de tre egenskapene, se Gilbert Og Lynchs papir.
Et Distribuert System
la oss vurdere et veldig enkelt distribuert system. Vårt system består av to servere, $G_1$ og $G_2$. Begge disse serverne holder styr på samme variabel, $v$, hvis verdi er i utgangspunktet $v_0$. $G_1$ Og $G_2$ kan kommunisere med hverandre og kan også kommunisere med eksterne kunder. Slik ser vårt system ut.
en klient kan be om å skrive og lese fra hvilken som helst server. Når en server mottar en forespørsel, utfører den alle beregninger den ønsker og svarer deretter til klienten. For eksempel, her er hva en skrive ser ut.
Her er hvordan en lesning ser ut.
Nå som vi har fått systemet vårt etablert, la oss gå over hva det betyr for systemet å være konsistent, tilgjengelig og partisjonstolerant.
Konsistens
Slik Beskriver Gilbert og Lynch konsistens.
enhver leseoperasjon som begynner etter at en skriveoperasjon er fullført, må returnere den verdien, eller resultatet av en senere skriveoperasjon
I et konsistent system, når en klient skriver en verdi til en hvilken som helst server og får et svar, forventer den å få den verdien (eller en ferskere verdi) tilbake fra hvilken som helst server den leser fra.
her er et eksempel på et inkonsekvent system.
vår klient skriver $v_1$ til $G_1$ og $G_1$ anerkjenner, men når Den leser fra $G_2$, blir den foreldet data: $v_0$.
på den annen side er her et eksempel på et konsistent system.
i dette systemet replikerer $G_1$ verdien til $G_2$ før du sender en bekreftelse til klienten. Når klienten leser fra $G_2$, får den den mest oppdaterte verdien av $v$: $v_1$.
Tilgjengelighet
Slik Beskriver Gilbert og Lynch tilgjengelighet.
hver forespørsel mottatt av en ikke-sviktende node i systemet må resultere i et svar
i et tilgjengelig system, hvis vår klient sender en forespørsel til en server og serveren ikke har krasjet, må serveren til slutt svare på klienten. Serveren har ikke lov til å ignorere klientens forespørsler.
Partisjonstoleranse
Slik Beskriver Gilbert Og Lynch partisjoner.
nettverket vil få lov til å miste vilkårlig mange meldinger sendt fra en node til en annen
dette betyr at eventuelle meldinger $G_1$ og$ G_2 $ send til hverandre kan bli droppet. Hvis alle meldingene ble droppet, ville systemet vårt se slik ut.
Vårt system må kunne fungere riktig til tross for vilkårlige nettverkspartisjoner for å være partisjonstolerant.
Beviset
Nå som vi har kjent oss med begrepet konsistens, tilgjengelighet og partisjonstoleranse, kan vi bevise at et system ikke samtidig kan ha alle tre.
Anta for motsetning at det eksisterer et system som er konsistent, tilgjengelig og partisjonstolerant. Det første vi gjør er å partisjonere systemet vårt. Det ser slik ut.
Deretter har vi vår klientforespørsel om at $v_1$ skrives til $G_1$. Siden vårt system er tilgjengelig, må $G_1$ svare. Siden nettverket er partisjonert, kan $G_1$ ikke replikere dataene til $G_2$. Gilbert Og Lynch kaller denne fasen av utførelse $ \ alpha_1$.
Deretter har vi vår klient utstedt en leseforespørsel til $G_2$. Igjen, siden systemet vårt er tilgjengelig, må $G_2$ svare. Og siden nettverket er partisjonert, kan $G_2$ ikke oppdatere verdien fra $G_1$. Den returnerer $v_0$. Gilbert Og Lynch kaller denne fasen av utførelse $\alpha_2$.
$G_2 $ returnerer $v_0 $ til vår klient etter at klienten allerede hadde skrevet $v_1$ til $G_1$. Dette er inkonsekvent.
vi antok at et konsekvent, tilgjengelig, partisjonstolerant system eksisterte, men vi viste bare at det eksisterer en utførelse for et slikt system der systemet virker inkonsekvent. Dermed eksisterer ikke et slikt system.