En informática teórica , el teorema CAP , también llamado teorema de Brewer en honor al científico informático Eric Brewer , establece que es imposible que un almacén de datos distribuido proporcione simultáneamente más de dos de las siguientes tres garantías: [1] [2] [3 ]
- Consistencia : cada lectura recibe la escritura más reciente o un error
- Disponibilidad : cada solicitud recibe una respuesta (sin error), sin la garantía de que contiene la escritura más reciente
- Tolerancia de partición : el sistema continúa funcionando a pesar de que la red descarta (o retrasa) una cantidad arbitraria de mensajes entre los nodos
Cuando ocurre una falla en la partición de red, deberíamos decidir
- Cancelar la operación y así disminuir la disponibilidad pero asegurar la consistencia
- Continuar con la operación y así proporcionar disponibilidad pero riesgo de inconsistencia
El teorema de CAP implica que, en presencia de una partición de red, se debe elegir entre consistencia y disponibilidad. Tenga en cuenta que la coherencia tal como se define en el teorema CAP es bastante diferente de la coherencia garantizada en las transacciones de la base de datos ACID . [4]
Eric Brewer sostiene que el concepto de "dos de tres" que se usa con frecuencia puede ser algo engañoso porque los diseñadores de sistemas solo necesitan sacrificar la consistencia o disponibilidad en presencia de particiones, y que en muchos sistemas las particiones son raras. [5] [6]
Explicación
Ningún sistema distribuido está a salvo de las fallas de la red, por lo que la partición de la red generalmente debe tolerarse. [7] [8] En presencia de una partición, uno se queda con dos opciones: consistencia o disponibilidad . Al elegir la coherencia sobre la disponibilidad, el sistema devolverá un error o un tiempo de espera si no se puede garantizar que una determinada información 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 más reciente disponible 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 está funcionando normalmente, se puede satisfacer tanto la disponibilidad como la consistencia.
Con frecuencia se malinterpreta el CAP como si uno tuviera que optar por abandonar una de las tres garantías en todo momento. De hecho, la elección es realmente entre consistencia y disponibilidad solo cuando ocurre una partición de red o falla; en cualquier otro momento, no es necesario hacer concesiones. [9] [10]
Los sistemas de bases de datos diseñados con las garantías ACID tradicionales en mente, como RDBMS, eligen la consistencia sobre la disponibilidad, mientras que los sistemas diseñados en torno a la filosofía BASE , común en el movimiento NoSQL , por ejemplo, eligen la disponibilidad sobre la consistencia. [5]
El teorema de PACELC se basa en CAP al afirmar que incluso en ausencia de partición, se produce otra compensación entre latencia y consistencia.
Historia
Según el científico informático Eric Brewer de la Universidad de California, Berkeley , el teorema apareció por primera vez en otoño de 1998. [5] Fue publicado como el principio CAP en 1999 [11] y presentado como una conjetura por Brewer en el Simposio de 2000 sobre principios de distribución distribuida. Computación (PODC). [12] En 2002, Seth Gilbert y Nancy Lynch del MIT publicaron una prueba formal de la conjetura de Brewer, convirtiéndola en un teorema . [1]
En 2012, Brewer aclaró algunas de sus posiciones, incluida la razón por la que el concepto de "dos de tres" que se utiliza con frecuencia puede ser algo engañoso porque los diseñadores de sistemas solo necesitan sacrificar la coherencia o la disponibilidad en presencia de particiones; existen técnicas de gestión y recuperación de particiones. Brewer también señaló la diferente definición de consistencia utilizada en el teorema de CAP en relación con la definición utilizada en ACID . [5] [6]
Birman y Friedman publicaron en 1996 un teorema similar que establece el equilibrio entre consistencia y disponibilidad en sistemas distribuidos. [13] El resultado de Birman y Friedman restringió este límite inferior a las operaciones sin desplazamiento.
La tecnología Blockchain sacrifica la consistencia por la disponibilidad y la tolerancia a la partición, pero se logra mediante la validación entre los nodos a lo largo del tiempo con la impresión resultante de que el teorema no es válido. [14]
Ver también
- Falacias de la computación distribuida
- Teorema de PACELC
- Paxos (informática)
- Balsa (informática)
Referencias
- ^ a b Seth Gilbert y Nancy Lynch, "La conjetura de Brewer y la viabilidad de servicios web consistentes, disponibles y tolerantes a la partición" , ACM SIGACT News , Volumen 33 Número 2 (2002), pág. 51–59. doi : 10.1145 / 564585.564601 .
- ^ "Teorema de CAP de cervecero" , julianbrowne.com, obtenido el 02 de marzo de 2010
- ^ "Teorema de CAP de los cerveceros en sistemas distribuidos" , royans.net
- ↑ Liochon, Nicolas. "La confusa redacción de CAP y ACID" . Este largo plazo . Consultado el 1 de febrero de 2019 .
- ^ a b c d Eric Brewer, "CAP doce años después: cómo han cambiado las 'reglas'" , Computadora , Volumen 45, Número 2 (2012), pág. 23-29. doi : 10.1109 / MC.2012.37 .
- ^ a b Carpenter, Jeff; Hewitt, Eben (julio de 2016). "Cassandra: The Definitive Guide, 2nd Edition [Libro]" . www.oreilly.com . Consultado el 21 de diciembre de 2020 .
En febrero de 2012, Eric Brewer proporcionó una perspectiva actualizada sobre su teorema CAP [...] Brewer ahora describe el axioma “2 de 3” como algo engañoso. Señala que los diseñadores solo necesitan sacrificar la consistencia o la disponibilidad en presencia de particiones, y que los avances en las técnicas de recuperación de particiones han hecho posible que los diseñadores alcancen altos niveles de consistencia y disponibilidad.
- ^ Kleppmann, Martin (18 de septiembre de 2015). "Una crítica del teorema CAP" . arXiv : 1509.05393 . Código Bibliográfico : 2015arXiv150905393K . doi : 10.17863 / CAM.13083 . S2CID 1991487 . Consultado el 24 de noviembre de 2019 . Cite journal requiere
|journal=
( ayuda ) - ^ Martin, Kleppmann. "Por favor, deje de llamar a las bases de datos CP o AP" . Blog de Martin Kleppmann . Consultado el 24 de noviembre de 2019 .
- ^ "Explicando mejor el teorema CAP" . DZone Big Data . Consultado el 2 de septiembre de 2016 .
- ^ Abadi, Daniel (23 de abril de 2010). "DBMS Musings: problemas con CAP, y poco conocido sistema NoSQL de Yahoo" . Reflexiones DBMS . Consultado el 23 de enero de 2018 .
- ^ Armando Fox y Eric Brewer, "Cosecha, rendimiento y sistemas tolerantes escalables", Proc. 7º Taller Temas de actualidad en sistemas operativos (HotOS 99) , IEEE CS, 1999, pág. 174-178. doi : 10.1109 / HOTOS.1999.798396
- ^ Eric Brewer, "Hacia sistemas distribuidos robustos"
- ^ Ken Birman y Roy Friedman, " Consistencia comercial para la disponibilidad en sistemas distribuidos ", abril de 1996. hdl : 1813/7235 .
- ^ Bashir, Imran. (2018). Dominando blockchain . Birmingham, Inglaterra: Packt Publishing. pag. 41. ISBN 978-1-78883-904-4 .
enlaces externos
- CAP Doce años después: cómo las "reglas" han cambiado el artículo de Brewer de 2012 sobre CRDT (tipos de datos replicados sin conflictos)
- Spanner, TrueTime y el teorema CAP
- Una crítica del teorema CAP
- Deje de llamar a las bases de datos CP o AP Kleppmann en el blog de 2015 correspondiente a la publicación de "Una crítica del teorema de CAP"