Cos'è il teorema CAP?

Questa è puramente la mia nozione e comprensione del teorema CAP. Da quando è uscito inizialmente, ha avuto una discreta evoluzione. Le persone hanno identificato alcuni difetti, caveat, e per quanto ne so, non c'è una singola spiegazione timbrata del teorema. Di seguito il mio tentativo di spiegarlo parlando di alcuni concetti di sistema distribuito che circondano il teorema.

Il teorema CAP di Eric Brewer _originariamente_ afferma che qualsiasi sistema distribuito con dati condivisi è probabile che ci sia tensione tra le seguenti proprietà sistemiche:

1. Consistenza - Tutte le repliche sono in sincronia e mantengono lo stesso stato di qualsiasi oggetto in qualsiasi punto del tempo. Conosciuto anche come consistenza sequenziale.
   
2. Disponibilità - Una richiesta alla fine verrà completata con successo. Una richiesta di lettura/scrittura su qualsiasi nodo del sistema non sarà mai rifiutata finché quel particolare nodo è attivo e funzionante.
   
3. Tolleranza alla partizione della rete - Quando la rete che collega i nodi va giù, il sistema continuerà a funzionare anche se alcuni/tutti i nodi non possono più comunicare tra loro.
   

Alternativamente, il teorema afferma che è possibile per il sistema soddisfare qualsiasi due ma non tutte le proprietà menzionate sopra.

Diciamo che il sistema è composto da 2 nodi interconnessi con la rete.

Se un dato è memorizzato solo nel nodo N1, allora quel nodo avrà sempre lo stato coerente di quel dato perché tutti gli aggiornamenti sono sempre serializzati sullo stesso nodo. Quindi, otteniamo la consistenza "C".

Supponiamo che i dati al nodo N1 siano replicati al nodo N2, ed entrambe le repliche sono sempre sincronizzate mantenendo copie coerenti dei dati in qualsiasi momento. Questo implica che un aggiornamento che avviene nel nodo N1 si propagherà atomicamente al nodo N2 e viceversa. Quindi, una richiesta di lettura/ricezione di un elemento di dati su una qualsiasi delle repliche (N1 o N2) non restituirà mai una copia vecchia o non aggiornata dei dati. Il nostro sistema raggiunge di nuovo la coerenza "C".

Ora che abbiamo capito brevemente la "C" del teorema CAP, assumiamo che il nostro sistema distribuito di due nodi N1 e N2 sia progettato e implementato in modo che i dati siano replicati su entrambi i nodi, e il sistema mantenga una copia coerente dei dati.

Detto questo, diciamo che la rete che collega entrambi i nodi va giù (la rete viene partizionata), ma entrambi i nodi N1 e N2 sono attivi e funzionano bene.

Come avrà questo impatto sulle operazioni generali del sistema? Gli aggiornamenti che avvengono sul nodo N1 non possono più raggiungere il nodo N2 e viceversa. Se ora :

1. Entrambe le repliche continuano a servire le richieste di aggiornamento per un elemento di dati, e poiché il sistema è partizionato in rete, questi aggiornamenti non possono più essere propagati all'altra replica. Così entrambe le repliche divergono, e finiscono per mantenere copie conflittuali o incoerenti dell'elemento di dati. Quindi, il sistema non possiede più la proprietà di coerenza ("C"). Qui abbiamo scelto la disponibilità ("A"), e abbiamo continuato a servire le operazioni in un ambiente disconnesso. In altre parole, abbiamo preferito la disponibilità "A" alla consistenza "C", e tollerato le partizioni di rete "P". Quindi, il sistema fornisce le proprietà "A" e "P" del teorema CAP.

O

2. Una delle repliche (diciamo N2) smette di servire le richieste di lettura/scrittura quando rileva che la rete che collega il sistema è partizionata. Questo significa che il sistema tratta il nodo N1 come non più disponibile, e qualsiasi richiesta su questo nodo sarà rifiutata. In questo caso, preserviamo la proprietà di consistenza poiché tutti gli aggiornamenti saranno serializzati solo sul nodo N1, e non c'è possibilità di divergenza di replica poiché l'altra replica non servirà alcuna richiesta. Si noti che N2 non dovrebbe servire nemmeno una richiesta di lettura/acquisizione in quanto finirebbe per restituire la vecchia/copia vecchia dei dati. Quindi, questo tipo di sistema fornisce la consistenza "C" al costo della disponibilità "A", e come prima tolleriamo le partizioni di rete "P".

O

3. Entrambe le repliche N1 e N2 smettono di servire le richieste di aggiornamento, ma continuano a fornire operazioni di lettura/ricezione. In questo caso, il sistema è disponibile per le operazioni di lettura, ma non per gli aggiornamenti. Anche qui preserviamo la consistenza "C" al costo della disponibilità "A", e tolleriamo le partizioni di rete "P".

In tutti i punti precedenti, è stata una scelta tra "C" e "A". Dalla letteratura che ho letto e capito, sento che è quasi sempre il caso che il trade-off sia tra "C" e "A". La tolleranza di partizione "P" non è veramente una scelta. La considero come una proprietà di base utilizzata per il trade-off tra consistenza e disponibilità, e di conseguenza progettare il sistema.

Se la rete viene partizionata, non conosco un modo in cui il sistema può essere sia coerente "C" che disponibile "A".

"Le repliche nel sistema non sono in grado di comunicare tra loro, ma il sistema è fortemente coerente, il che richiede che le repliche propaghino le modifiche l'una all'altra attraverso la rete, ma questo non può avvenire perché la rete è partizionata".

Quindi, la coerenza forte (C) e la disponibilità (A) non possono coesistere insieme.

La discussione precedente implica anche che "C", "A", e "P" non possono essere raggiunti insieme nel sistema distribuito con dati condivisi, e questo è in accordo con il teorema.

La nozione di coerenza si è anche evoluta portando a sistemi con modelli deboli o eventualmente coerenti. Per esempio, in DynamoDB, gli aggiornamenti possono avvenire sulle repliche in caso di guasto della rete. La sincronizzazione delle repliche in background viene effettuata utilizzando gli alberi di Merkle per ripristinare la coerenza tra i dati mantenuti nelle repliche. Questo significa che gli aggiornamenti alla fine si propagano a tutte le repliche e quindi il sistema è "alla fine coerente". Significa effettivamente che tutte e tre le proprietà "C", "A" e "P" sono fornite dall'archivio dati. Tuttavia, la nozione e la definizione di "C" è molto diversa.