Teorema CAP
En informàtica teòrica, el teorema CAP, també conegut com a teorema de Brewer, formula que és impossible garantir simultàniament les tres característiques següents en una aplicació distribuïda: [1][2][3]
- Consistència (tots els nodes veuen la mateixa dada al mateix temps)
- Disponibilitat (la garantia que cada petició a un node rep una resposta de si ha tingut èxit o a fallat)
- Tolerància a la partició (el sistema continua operant malgrat la partició arbitrària a causa d'errors en la xarxa)
El 2012 Brewer va aclarir alguna de les seves posicions com que el concepte "dos de tres" ("two out of three") pot ser malentès o pot induir a error i també el perquè de la definició de consistència CAP divergeix respecte a la de ACID.[4]
Història
El teorema va ser formulat per primer cop per l'informàtic Eric Brewer de la Universitat de Califòrnia durant la tardor de 1998.[4] Va ser publicat com a principi CAP a l'any següent i va ser presentat per Brewer com a conjectura en el Symposium on Principles of Distributed Computing (PODC) de l'any 2000.[5][6] El 2002, Seth Gilbert i Nancy Lynch del MIT van publicar una demostració formal de la conjectura de Brewer, fet que la convertia en teorema.[1] Tanmateix, aquest darrer punt ha estat criticat.[7]
Explicació
No hi ha cap sistema distribuït a prova de fallades de xarxa, per tant la tolerància a la partició -errors de xarxa- generalment ha de ser tolerada. En presència d'una partició, s'ha d'escollir una de les dues opcions: consistència o disponibilitat.
A l'hora d'escollir consistència sobre disponibilitat, el sistema retornarà un error, o un temps d'espera indeterminat, si no es pot garantir, a causa de la partició de la xarxa, que la informació estigui actualitzada a tots els nodes.
En triar la disponibilitat per sobre de la consistència, el sistema sempre processarà la consulta i intentarà retornar la versió més recent disponible de la informació, encara que no pugui garantir que estigui actualitzada a tots els nodes, a causa de la partició de la xarxa.
En absència de partició, tant la disponibilitat com la consistència es poden satisfer.
Referències
- 1 2 Seth Gilbert and Nancy Lynch, “Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services”, ACM SIGACT News, Volume 33 Issue 2 (2002), pg. 51-59.
- ↑ "Brewer's CAP Theorem", julianbrowne.com, Retrieved 02-Mar-2010
- ↑ "Brewers CAP theorem on distributed systems" Arxivat 2016-02-04 a Wayback Machine., royans.net
- 1 2 Eric Brewer, “CAP twelve years later: How the "rules" have changed”, IEEE Explore, Volume 45, Issue 2 (2012), pg. 23-29.
- ↑ Armando Fox and Eric Brewer, “Harvest, Yield and Scalable Tolerant Systems”, Proc. 7th Workshop Hot Topics in Operating Systems (HotOS 99), IEEE CS, 1999, pg. 174-178.
- ↑ Eric Brewer, "Towards Robust Distributed Systems"
- ↑ Mark Burgess, "Deconstructing the `CAP theorem' for CM and DevOps"
Enllaços externs
- "A plain english introduction to CAP Theorem" Arxivat 2012-05-17 a Wayback Machine. Explains CAP and eventual consistency using examples.
- "Consistency Models in Non-Relational Databases" Arxivat 2015-05-10 a Wayback Machine. Explains CAP Theorem and eventual consistency in distributed environments.
- "Problems with CAP, and Yahoo's little known NoSQL system" Discusses PACELC, an alternative to CAP.
- "Returning Transactions to Distributed Data Stores" Arxivat 2014-02-23 a Wayback Machine. Discusses the CAP Theorem as it applies to NoSQL systems.
- "You can't sacrifice partition tolerance, by Codahale" Discusses practical implications of CAP Theorem in real world systems.