Teorema CAP

Da Wikipedia, l'enciclopedia libera.

In informatica teorica, 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:[1][2]

  • Coerenza (tutti i nodi vedono gli stessi dati nello stesso momento)
  • Disponibilità (la garanzia che ogni richiesta riceva una risposta su ciò che sia riuscito o fallito)
  • Tolleranza di partizione (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.[3]

Storia[modifica | modifica wikitesto]

Il teorema è iniziato come una congettura matematica fatta all'Università della California, Berkeley, dallo scienziato informatico Eric Brewer al simposio Principles of Distributed Computing (PODC) che ha avuto luogo nel 2000.[4] Nel 2002, Seth Gilbert e Nancy Lynch del MIT hanno pubblicato una dimostrazione formale della congettura di Brewster, assurgendolo a teorema.[1]

Il teorema CAP, come dimostrato da Gilbert e Lynch, è un po' più limitato di quello che Brewer aveva in mente. Il teorema stabilisce uno scenario in cui viene presentato un servizio replicato con due richieste in conflitto che arrivano in luoghi distinti nel momento in cui il collegamento tra di loro è fallito. L'obbligo di fornire la disponibilità nonostante gli errori di partizionamento, porta i servizi a rispondere; almeno una di queste risposte sarà necessariamente in contrasto con ciò che un servizio che implementa una vera e propria replica semantica one-copy avrebbe fatto. I ricercatori vanno poi avanti per dimostrare che altre forme di consistenza sono realizzabili, tra cui una proprietà che chiamano coerenza t-eventuale. Così il teorema non esclude la fattibilità della coerenza di un sistema distribuito, e non dice nulla circa il cloud in sé o sulla scalabilità.

Al contrario, come Eric Brewer ha posto la domanda, CAP è spesso volto ad escludere la consistenza per i servizi in esecuzione in alta elasticità di primo livello di un moderno sistema di cloud computing. A questi servizi è richiesto generalmente di essere stateless o di mantenere solo un soft-state (dati memorizzati nella cache), e di essere reattivi anche se servizi ad un livello più interno sono temporaneamente inaccessibili. CAP, in questo senso, usa "A" per indicare immediatamente reattivo, e "P" per dire "anche se un guasto impedisce al primo livello di servizio di connettersi ad una risorsa necessaria". In effetti, sacrifichiamo la coerenza per ottenere risposte più veloci in modo più scalabile.

Si noti che il partizionamento in sé in realtà non entra in questa interpretazione estensiva del teorema CAP. Infatti, non c'è un teorema CAP per lo scenario effettivamente visto in cui la disponibilità simmetrica in caso di guasto del partizionamento non sia normalmente richiesta. Ci sono due ragioni per questo: la prima, le piattaforme cloud dispongono di reti ridondanti ad alta disponibilità e normalmente non sono affette da questi guasti. In secondo luogo, se uno di questi eventi molto rari di partizionamento si verificasse, sarebbe molto probabile tagliare fuori alcune piccole porzioni della replica, non solo dalle altre componenti del cloud ma anche dai loro client esterni, ovviando la necessità di disponibilità.

Il teorema CAP è spesso citato come una giustificazione per l'utilizzo di modelli di consistenza più deboli. Popolare tra questi è BASE, acronimo di Basically Available Soft-state (services with) Eventual consistency ((Servizi con) consistenza effettiva, soft-state, fondamentalmente disponibile). In sintesi, la metodologia BASE è caratterizzata da una elevata disponibilità per i servizi di primo livello, lasciando un qualche tipo di meccanismo di pulizia di fondo per risolvere i problemi creati da azioni ottimistiche che poi risultano avere violato la consistenza.

Note[modifica | modifica wikitesto]

  1. ^ a b Nancy Lynch and Seth Gilbert, “Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services”, ACM SIGACT News, Volume 33 Issue 2 (2002), pg. 51-59.
  2. ^ "Brewer's CAP Theorem", julianbrowne.com, Retrieved 02-Mar-2010
  3. ^ "Brewers CAP theorem on distributed systems", royans.net
  4. ^ Eric Brewer, "Towards Robust Distributed Systems"

Collegamenti esterni[modifica | modifica wikitesto]

informatica Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica