Programming Languages Hacks

Importanti regole per linguaggi di programmazione rilevanti come Java, C, C++, C#…

  • Subscribe

  • Lettori

    I miei lettori abituali

  • Twitter

Il Teorema CAP – il motivo del NOSQL?

Posted by Ricibald on July 25th, 2013

Il teorema CAP, noto anche come teorema di Brewer, afferma che è impossibile per un sistema informatico distribuito fornire simultaneamente tutte e tre le seguenti garanzie (le 3 CAP):

  • Consistency (tutti i nodi vedono gli stessi dati nello stesso momento)
  • Availability (ogni richiesta riceverà una risposta)
  • Partition Tolerance (il sistema continua a funzionare nonostante arbitrarie perdite di messaggi)

Secondo il teorema, un sistema distribuito è in grado di soddisfare al massimo due di queste garanzie allo stesso tempo, ma non tutte e tre. Da semplice congettura nata nel 2000, la teoria è stata dimostrata formalmente nel 2002 assurgendolo a teorema vero e proprio.

Il concetto di per sé è abbastanza chiaro: se vogliamo avere dati geograficamente distribuiti siamo costretti a sacrificare o la Consistency o la Availability.

La globalizzazione informatica e l’esigenza di trattare Big Data spinge a scalare orizzontalmente i dati usando macchine consumer replicandole a livello geografico per ragioni di economicità, scalabilità, disponibilità, reattività.

Stanno quindi avanzando modelli di memorizzazione che non si basano sul classico modello ACID (Atomicity, Consistency, Isolation, Durability) degli RDBMS, OODBMS, Cluster, Caching bensì si basano sul nuovo modello BASE (Basically Available Soft-state services with Eventual-consistency) che rilassa il concetto di consistenza a una consistenza eventuale (applicabile solo nei dati non critici).

Dimostrazione pratica del teorema

Il principio di esclusione legato al teorema CAP dipende dal meccanismo di replica delle informazioni.

In reti locali ad alta velocità tra i vari nodi si può usare la replica pessimistica senza degrado di performance. In tale replica la scrittura sul nodo A non è considerata conclusa finquando tutte le repliche non sono concluse tramite una transazione distribuita two-phase commit. Poiché la scalabilità sarà possibile solo su rete locale allora si sacrifica la Partition Tolerance ma si garantisce Consistency e Availability.

Se viceversa i nodi sono distribuiti su reti non affidabili e a bassa velocità in tal caso si deve usare la replica ottimistica promettendo che prima o poi la replica sarà fatta mediante un processo asincrono. In questo caso il nodo B potrebbe quindi in un certo momento temporale non avere ancora ricevuto la replica aggiornata dal nodo A. Se una richiesta arriva a B in queste condizioni allora il nodo può scegliere di:

  • restituire il dato potenzialmente obsoleto (si sacrifica la Consistency)
  • rispondere con un errore (si sacrifica la Availability)

Nella pratica è un problema?

Il teorema CAP è in realtà valido solo quando i vincoli iniziali non possono essere rilassati: se sono costretto a garantire che rispondano sempre gli stessi nodi in qualsiasi momento allora è per forza valido. Se invece posso permettermi brevi downtime di partizioni allora posso ottenere tutte le 3 CAP. Infatti un bilanciatore potrebbe implementare stratagemmi come quello di isolare le partizioni che ancora non hanno il dato replicato. In questo modo sarebbe possibile ottenere un db cluster replicato geograficamente.

Attenzione però in tal caso a mantenere un rapporto tra i nodi replicati e quelli ancora non replicati, altrimenti la Consistency non è comunque garantita. Date infatti le seguenti variabili:

  • N: n° di nodi coinvolti dalla replica
  • W: n° di repliche che devono confermare la ricezione dell’update prima che l’update si possa considerare concluso
  • R: n° di repliche che verranno contemporaneamente contattate al momento della read per essere sicuri della correttezza del dato

Se vale:

  • W + R > N allora la C di CAP è garantita
  • W + R <= N allora la C di CAP non è sacrificata e avremo una eventual consistency

Quindi se ho un dato replicato in 3 nodi di cui almeno 2 repliche garantite e devo leggere da 2 repliche allora 4 > 3, avrò una strong consistency.

Il mio db è già replicato anche in Cina… funziona e non sapevo tutto questo!

Una cosa è il backup, un’altra è la Partition Tolerance. Una cosa è un db di pochi GB un’altra è un Big Data di TB di dati. Il modello BASE si applica soprattutto su dati geograficamente distribuiti che devono:

  • ottenere la minima latenza geografica possibile
  • avere un disaster recovery senza interruzioni di servizio

Potremmo pensare che il problema non ci riguarda e sono temi ad appannaggio solo di siti miliardari come facebook, ma in realtà ci riguarda da vicino. Con l’avvento del cloud i costi variano di molto se si utilizza o meno un datastore ACID o BASE. Nel caso di database BASE (MongoDB o altri), infatti, i provider cloud possono ottenere un’importante economia di scala abbattendo notevolmente i costi e riducendo di conseguenza le relative spese per il cliente finale (noi!).

In Azure ad esempio il costo di un SQL Server è piuttosto alto, mentre i costi di un Table Storage sono ridicoli per TB (!) di dati. Il costo estremamente ridotto potrebbe spingere diverse realtà quindi a convergere verso un modello di consistenza più rilassato per essere più competitivi sul mercato.

One Response to “Il Teorema CAP – il motivo del NOSQL?”

  1. data|recovery|drive|services|computer|undelete|fix|repair|rescue|retrieve|clicking|format|recovery|backup|ide|sata|scsi|tape Says:

    It’s really a great and helpful piece of info. I am glad that you simply shared this helpful information with us. Please stay us up to date like this. Thank you for sharing.

Leave a Reply

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>