Una dimostrazione illustrata del Teorema CAP

Il Teorema CAP è un teorema fondamentale nei sistemi distribuiti che afferma che qualsiasi sistema distribuito può avere al massimo due delle seguenti tre proprietà.

• Consistenza
• Disponibilità
• Tolleranza della partizione

Questa guida riassume le specifiche di Gilbert e Lynch e la dimostrazione del teorema CAP con le immagini!

Qual è il teorema CAP?

Il teorema CAP afferma che un sistema distribuito non può essere simultaneamente coerente, disponibile e tollerante alle partizioni. Sembra abbastanza semplice, ma cosa significa essere coerenti? disponibile? partizione tollerante? Diamine, cosa intendi esattamente con un sistema distribuito?

In questa sezione, introdurremo un semplice sistema distribuito e spiegheremo cosa significa per quel sistema essere disponibile, coerente e tollerante alle partizioni. Per una descrizione formale del sistema e delle tre proprietà, si prega di fare riferimento al documento di Gilbert e Lynch.

Un sistema distribuito

Consideriamo un sistema distribuito molto semplice. Il nostro sistema è composto da due server, G G_1 and e G G_2.. Entrambi questi server tengono traccia della stessa variabile, v v v, il cui valore è inizialmente v v_0.. $G_1 and e G G_2 can possono comunicare tra loro e possono anche comunicare con client esterni. Ecco come appare il nostro sistema.

Un client può richiedere di scrivere e leggere da qualsiasi server. Quando un server riceve una richiesta, esegue tutti i calcoli che desidera e quindi risponde al client. Ad esempio, ecco come appare una scrittura.

Ed ecco come appare una lettura.

Ora che abbiamo stabilito il nostro sistema, esaminiamo cosa significa che il sistema sia coerente, disponibile e tollerante alle partizioni.

Coerenza

Ecco come Gilbert e Lynch descrivono la coerenza.

qualsiasi operazione di lettura che inizia dopo il completamento di un’operazione di scrittura deve restituire quel valore, o il risultato di un’operazione di scrittura successiva

In un sistema coerente, una volta che un client scrive un valore su qualsiasi server e ottiene una risposta, si aspetta di ottenere quel valore (o un valore più fresco) da

Ecco un esempio di un sistema incoerente.

il Nostro cliente scrive $v_1$ a $G_1$ e $G_1$ riconosce, ma quando legge da $G_2$, si ottiene i dati non aggiornati: $v_0$.

D’altra parte, ecco un esempio di un sistema coerente.

In questo sistema, $G_1 repl replica il suo valore in G G_2 before prima di inviare un riconoscimento al client. Così, quando il client legge da $G_2$, si ottiene il più aggiornato valore di $v$: $v_1$.

Disponibilità

Ecco come Gilbert e Lynch descrivono la disponibilità.

ogni richiesta ricevuta da un nodo non in errore nel sistema deve comportare una risposta

In un sistema disponibile, se il nostro client invia una richiesta a un server e il server non si è arrestato in modo anomalo, il server deve infine rispondere al client. Al server non è consentito ignorare le richieste del client.

Tolleranza partizione

Ecco come Gilbert e Lynch descrivono le partizioni.

alla rete sarà permesso di perdere arbitrariamente molti messaggi inviati da un nodo all’altro

Ciò significa che tutti i messaggi send G_1 send e send G_2 send inviati l’uno all’altro possono essere eliminati. Se tutti i messaggi venivano eliminati, il nostro sistema sarebbe simile a questo.

Il nostro sistema deve essere in grado di funzionare correttamente nonostante le partizioni di rete arbitrarie per essere tollerante alle partizioni.

La dimostrazione

Ora che abbiamo familiarizzato con la nozione di coerenza, disponibilità e tolleranza della partizione, possiamo dimostrare che un sistema non può avere simultaneamente tutti e tre.

Supponiamo per contraddizione che esista un sistema coerente, disponibile e tollerante alle partizioni. La prima cosa che facciamo è partizionare il nostro sistema. Sembra questo.

Successivamente, abbiamo la richiesta del nostro cliente che v v_1 be sia scritto su G G_1.. Poiché il nostro sistema è disponibile, must G_1 must deve rispondere. Poiché la rete è partizionata, tuttavia, $G_1 cannot non può replicare i suoi dati in G G_2.. Gilbert e Lynch chiamano questa fase di esecuzione alph \ alpha_1$.

Successivamente, abbiamo il nostro cliente emettere una richiesta di lettura a G G_2$. Di nuovo, dal momento che il nostro sistema è disponibile, must G_2 must deve rispondere. E poiché la rete è partizionata, $G_2 cannot non può aggiornare il suo valore da G G_1.. Restituisce v v_0.. Gilbert e Lynch chiamano questa fase di esecuzione alph \ alpha_2..

$G_2$ restituisce $v_0$ ai nostri client dopo che il cliente aveva già scritto $v_1$ a $G_1$. Questo è incoerente.

Abbiamo ipotizzato che esistesse un sistema coerente, disponibile e tollerante alle partizioni, ma abbiamo appena dimostrato che esiste un’esecuzione per qualsiasi sistema in cui il sistema agisce in modo incoerente. Pertanto, non esiste un tale sistema.