Teorema CAP
En Ciencias de la computación, el teorema CAP, también llamado Conjetura de Brewer, enuncia que es imposible para un sistema de cómputo distribuido garantizar simultáneamente:[1][2]
- La consistencia (Consistency), es decir, cualquier lectura recibe como respuesta la escritura más reciente o un error.
- La disponibilidad (Availability), es decir, cualquier petición recibe una respuesta no errónea, pero sin la garantía de que contenga la escritura más reciente.
- La tolerancia al particionado (Partition Tolerance), es decir, el sistema sigue funcionando incluso si un número arbitrario de mensajes son descartados (o retrasados) entre nodos de la red.
Según el teorema, un sistema no puede asegurar más de dos de estas tres características simultáneamente.[3]
Historia
El teorema comenzó como una conjetura, presentada por Eric Brewer, de la Universidad de Berkeley en el año 2000 durante el Simposio de Principios de Computación Distribuida (PODC, en inglés).[4] En 2002, Seth Gilbert y Nancy Lynch, del MIT, publicaron una demostración formal de la conjetura, convirtiéndola en un teorema.[1]
Explicación
Ningún sistema distribuido está a salvo de las fallas de la red, por lo tanto , la partición de la red generalmente tiene que ser tolerada. En presencia de una partición, una se queda con dos opciones: consistencia o disponibilidad . Al elegir la consistencia sobre la disponibilidad, el sistema devolverá un error o un tiempo de espera si no se puede garantizar que la información particular esté actualizada debido a la partición de la red. Al elegir la disponibilidad sobre la coherencia, el sistema siempre procesará la consulta e intentará devolver la versión disponible más reciente de la información, incluso si no puede garantizar que esté actualizada debido a la partición de la red.
En ausencia de falla de la red, es decir, cuando el sistema distribuido se está ejecutando normalmente, se puede satisfacer tanto la disponibilidad como la consistencia.
Con frecuencia, la CAP se malinterpreta como si uno tuviera que elegir abandonar una de las tres garantías en todo momento. De hecho, la elección es realmente entre la consistencia y la disponibilidad solo cuando ocurre una partición de red o falla; en cualquier otro momento, no hay que hacer concesiones. Bases de datos relacionales como YugabyteDB, CockroachDB, LeanXcale, NuoDB o Google Spanner son ejemplos de esta falacia.
Los sistemas de base de datos diseñados teniendo en cuenta las garantías tradicionales de ACID , como RDBMS, eligen la consistencia sobre la disponibilidad, mientras que los sistemas diseñados en torno a la filosofía BASE , comunes en el movimiento NoSQL , por ejemplo, eligen la disponibilidad sobre la consistencia.
Muchos proveedores de bases de datos NoSQL han utilizado el teorema CAP como justificación para no proporcionar consistencia ACID transaccional, alegando que el teorema CAP "demuestra" que es imposible proporcionar escalabilidad y consistencia ACID al mismo tiempo. Sin embargo, un examen más detallado del teorema CAP y, en particular, de la formalización de Gilbert y Lynch, revela que el teorema CAP no se refiere en absoluto a la escalabilidad, sino sólo a la disponibilidad (la A de CAP).[5]
El teorema de CAPELC se basa en CAP al afirmar que, incluso en ausencia de partición, se produce otra compensación entre la latencia y la consistencia.
Ejemplos
Según satisfagan unos criterios u otros, podemos encontrar:
- AP: Cassandra, CouchDB MongoDB .
- CP: Paxos.
- CA: RDBMS.
Referencias
- ↑ 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.
- ↑ "Brewer's CAP Theorem", julianbrowne.com, Retrieved 02-Mar-2010
- ↑ "Brewers CAP theorem on distributed systems" Archivado el 12 de abril de 2011 en Wayback Machine., royans.net
- ↑ Eric Brewer, "Towards Robust Distributed Systems"
- ↑ «Understanding the CAP Theorem and its No Relationship to Scalability – LeanXcale» (en inglés estadounidense). Consultado el 18 de abril de 2022.
Enlaces externos
- "Problems with CAP, and Yahoo's little known NoSQL system" by Daniel Abadi
- "CAP equivalent for analytics"
- [https://web.archive.org/web/20120623022526/https://web.archive.org/web/20120623022526/http://dbpedias.com/wiki/NoSQL:Consistency_Models_in_Non-Relational_Databases Archivado el 23 de junio de 2012 en Wayback Machine. "Consistency Models in Non-Relational Databases"] by Guy Harrison: Una buena descripción del Teorema del CAP, de la Consistencia Eventual y de cómo se pueden tratar los problemas de consistencia en entornos distribuidos.
Datos: Q856032