Teorema CAP
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 (copy-consistency): tutti i nodi vedano gli stessi dati nello stesso momento
- Disponibilità (availability): la garanzia che ogni richiesta riceva una risposta su ciò che è riuscito o fallito
- Tolleranza di partizione (partitioning): il sistema continua a funzionare nonostante arbitrarie perdite di messaggi o malfunzionamenti
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
modificaL'enunciato del teorema venne ideato dall'informatico statunitense Eric Brewer all'Università della California - Berkeley nell'autunno del 1998.[4] Venne pubblicato nel 1999 come "principio CAP"[5] e successivamente presentato come congettura dallo stesso Brewer al simposio Principles of Distributed Computing (PODC) che ebbe luogo nel 2000.[6] Nel 2002, Seth Gilbert e Nancy Lynch del MIT pubblicarono una dimostrazione formale della congettura di Brewer, facendola assurgere al rango di 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 alla 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- ^ a b Lynch e Gilbert, pp. 51-59.
- ^ (EN) Brewer's CAP Theorem, su julianbrowne.com. URL consultato il 2 marzo 2010.
- ^ (EN) Brewers CAP theorem on distributed systems, su royans.net. URL consultato il 16 novembre 2012 (archiviato dall'url originale il 12 aprile 2011).
- ^ Brewer, 2012, pp. 23-29.
- ^ Brewer, 1999, pp. 174-178.
- ^ (EN) Eric Brewer, Towards Robust Distributed Systems (PDF), su cs.berkeley.edu, Università di Berkeley.
Bibliografia
modifica- (EN) Armando Fox e Eric Brewer, Harvest, Yield and Scalable Tolerant Systems, Proc. 7th Workshop Hot Topics in Operating Systems (HotOS 99), IEEE CS, 1999, pp. 174–178, DOI:10.1109/HOTOS.1999.798396.
- (EN) Nancy Lynch e Seth Gilbert, Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services (PDF), in ACM SIGACT News, vol. 33, n. 2, 2002 (archiviato dall'url originale il 22 novembre 2011).
- (EN) Eric Brewer, CAP twelve years later: How the 'rules' have changed, in Computer, vol. 45, n. 2, 2012, DOI:10.1109/MC.2012.37.
Voci correlate
modificaCollegamenti esterni
modifica- (EN) Daniel Abadi, Problems with CAP, and Yahoo's little known NoSQL system, su dbmsmusings.blogspot.com.
- (EN) A Simple introduction to CAP theorem, su ksat.me. URL consultato il 28 gennaio 2012 (archiviato dall'url originale il 17 maggio 2012).
