Een geïllustreerd bewijs van de Cap-stelling

de Cap-stelling is een fundamentele stelling in gedistribueerde systemen die stelt dat elk gedistribueerd systeem maximaal twee van de volgende drie eigenschappen kan hebben.

• consistentie
• beschikbaarheid
• Partitietolerantie

deze gids vat de specificatie van Gilbert en Lynch en het bewijs van de Cap-stelling samen met afbeeldingen!

Wat is de Cap-stelling?

de stelling van CAP stelt dat een gedistribueerd systeem NIET gelijktijdig consistent, beschikbaar en partitietolerant kan zijn. Klinkt eenvoudig genoeg, maar wat betekent het om consistent te zijn? beschikbaar? partitie tolerant? Wat bedoel je precies met een gedistribueerd systeem?

in deze paragraaf zullen we een eenvoudig gedistribueerd systeem introduceren en uitleggen wat het betekent dat dat systeem beschikbaar, consistent en partitie tolerant is. Voor een formele beschrijving van het systeem en de drie eigenschappen, verwijzen wij u naar het artikel van Gilbert en Lynch.

een gedistribueerd systeem

laten we eens kijken naar een zeer eenvoudig gedistribueerd systeem. Ons systeem bestaat uit twee servers, $G_1$ en $G_2$. Beide servers houden dezelfde variabele bij, $v$, waarvan de waarde aanvankelijk $v_0$is. $G_1$ en $G_2$ kunnen met elkaar communiceren en kunnen ook met externe clients communiceren. Zo ziet ons systeem eruit.

een client kan vragen om te schrijven en te lezen vanaf elke server. Wanneer een server een verzoek ontvangt, voert deze alle gewenste berekeningen uit en reageert vervolgens op de client. Bijvoorbeeld, hier is hoe een schrijven eruit ziet.

en zo ziet een lezing eruit.

nu dat we ons systeem hebben opgericht, laten we eens gaan over wat het betekent dat het systeem consistent, beschikbaar en partitie tolerant is.

consistentie

hier is hoe Gilbert en Lynch consistentie beschrijven.

elke leesbewerking die begint nadat een schrijfbewerking is voltooid, moet die waarde teruggeven, of het resultaat van een latere schrijfbewerking

in een consistent systeem.zodra een client een waarde naar een server schrijft en een antwoord krijgt, verwacht hij die waarde (of een frissere waarde) terug te krijgen van een server waarvan hij leest.

hier is een voorbeeld van een inconsistent systeem.

onze cliënt schrijft $v_1$ naar $G_1$ en$ G_1 $ erkent, maar wanneer het leest van $G_2$, krijgt het verouderde gegevens: $v_0$.

aan de andere kant is hier een voorbeeld van een consistent systeem.

in dit systeem repliceert $G_1$ zijn waarde naar $G_2$ alvorens een bevestiging naar de client te sturen. Dus, wanneer de client leest van $G_2$, krijgt het de meest up-to-date waarde van $v$: $v_1$.

beschikbaarheid

zo beschrijven Gilbert en Lynch beschikbaarheid.

elk verzoek dat door een niet-falend knooppunt in het systeem wordt ontvangen, moet resulteren in een antwoord

In een Beschikbaar systeem.als onze client een verzoek naar een server stuurt en de server niet gecrasht is, moet de server uiteindelijk reageren op de client. De server mag de verzoeken van de client niet negeren.

partitie tolerantie

zo beschrijven Gilbert en Lynch partities.

het netwerk mag willekeurig veel berichten verliezen die van het ene knooppunt naar het andere worden verzonden

dit betekent dat alle berichten $G_1$ en $G_2$ die naar elkaar worden verzonden, kunnen worden verwijderd. Als alle berichten werden gedropt, dan zou ons systeem er zo uitzien.

ons systeem moet ondanks willekeurige netwerkpartities correct kunnen functioneren om partitie tolerant te zijn.

het bewijs

nu we vertrouwd zijn met de notie van consistentie, beschikbaarheid en partitie tolerantie, kunnen we bewijzen dat een systeem niet alle drie tegelijk kan hebben.

Neem voor tegenstrijdigheid aan dat er wel een systeem bestaat dat consistent, beschikbaar en partitie tolerant is. Het eerste wat we doen is ons systeem partitioneren. Het ziet er zo uit.

vervolgens hebben we onze klant verzoek dat $v_1$ worden geschreven naar $G_1$. Omdat ons systeem beschikbaar is, moet $G_1$ reageren. Omdat het netwerk echter gepartitioneerd is, kan $G_1$ zijn gegevens niet repliceren naar $G_2$. Gilbert en Lynch noemen deze fase van uitvoering $\alpha_1$.

vervolgens hebben we onze klant een leesverzoek naar $G_2$. Nogmaals, omdat ons systeem beschikbaar is, moet $G_2$ reageren. En omdat het netwerk gepartitioneerd is, kan $G_2$ zijn waarde niet bijwerken vanaf $G_1$. Het geeft $v_0$terug. Gilbert en Lynch noemen deze fase van uitvoering $\alpha_2$.

$G_2$ geeft $v_0$ terug aan onze cliënt nadat de cliënt reeds $v_1$ naar $G_1$had geschreven. Dit is inconsistent.

we namen aan dat er een consistent, beschikbaar, partitie tolerant systeem bestond, maar we hebben zojuist aangetoond dat er een uitvoering bestaat voor een dergelijk systeem waarin het systeem inconsistent werkt. Zo ‘ n systeem bestaat dus niet.