Teorema CAP

El teorema CAP (también conocido como teorema de Brewer ) es una declaración heurística de que no se pueden proporcionar más de dos de las siguientes tres propiedades en cualquier implementación de computación distribuida :

El acrónimo CAP en el nombre del teorema se forma a partir de las primeras letras de los nombres en inglés de estas tres propiedades.

El principio fue propuesto por el profesor de UC Berkeley , Eric Brewer , en julio de 2000 [1] [2] y, posteriormente, ganó gran popularidad y reconocimiento entre los especialistas en computación distribuida [3] [4] . El concepto NoSQL , dentro del cual se crean los sistemas de administración de bases de datos no transaccionales distribuidas , a menudo utiliza este principio como justificación para la inevitabilidad de fallas en la consistencia de los datos [5] [6] [7] . Sin embargo, muchos científicos [8] y profesionales [9] critican el teorema CAP por su interpretación vaga e incluso por su falta de fiabilidad en el sentido en que es común en la comunidad.

Justificaciones

En 2002, Seth Gilbert y Nancy Lynch del Instituto Tecnológico de Massachusetts seleccionaron modelos formales de computación distribuida asíncrona y síncrona, que muestran el cumplimiento del teorema CAP en ausencia de sincronización (reloj común) en los nodos de un sistema distribuido y el posibilidad fundamental de compromiso en sistemas parcialmente síncronos [10 ] . En este trabajo, la "consistencia" en el sentido del teorema CAP se correlaciona con el cumplimiento de los dos primeros requisitos de ACID  : atomicidad y consistencia . En el futuro, muchos profesionales se refirieron a este trabajo como una prueba del teorema CAP [4] [11] [3] .

Consecuencias

Desde el punto de vista del teorema CAP, los sistemas distribuidos, dependiendo de un par de propiedades prácticamente admitidas, de tres posibles, se dividen en tres clases: CA, CP, AP.

En un sistema de clase CA, los datos son coherentes y están disponibles en todos los nodos, al tiempo que se sacrifica la solidez por el particionamiento. Dichos sistemas son posibles basados ​​en software tecnológico que soporte la transaccionalidad en el sentido de ACID , ejemplos de tales sistemas pueden ser soluciones basadas en sistemas de gestión de bases de datos en clúster o un servicio de directorio distribuido LDAP [12] .

Un sistema de clase CP proporciona en todo momento un resultado holístico y es capaz de funcionar en condiciones de descomposición, pero lo logra a expensas de la disponibilidad: es posible que no responda a una solicitud. La resiliencia a la división en secciones requiere la duplicación de cambios en todos los nodos del sistema, en relación con esto, se observa la conveniencia práctica de usar bloqueos pesimistas distribuidos en tales sistemas para mantener la integridad [13] .

En un sistema de clase AP no se garantiza la integridad, pero se cumplen las condiciones de accesibilidad y resistencia a la partición. Aunque los sistemas de este tipo se conocen mucho antes de la formulación del principio CAP (por ejemplo, cachés web distribuidos o DNS ) [14] , la creciente popularidad de las soluciones con este conjunto de propiedades está asociada precisamente con la difusión del teorema CAP. . Por lo tanto, la mayoría de los sistemas NoSQL fundamentalmente no garantizan la integridad de los datos y se refieren al teorema CAP como el motivo de tal restricción [5] . La tarea en la construcción de sistemas AP es proporcionar algún nivel práctico de integridad de datos, en este sentido, se dice que los sistemas AP son "eventualmente consistentes " [ 15] o "débilmente consistentes" ( eng  . débilmente consistentes ) [16] .  

Arquitectura BASE

En la segunda mitad de la década de 2000, se formuló un enfoque para construir sistemas distribuidos en los que los requisitos de integridad y disponibilidad no se cumplen por completo, llamado el acrónimo BASE (del inglés  Basically Available, Soft-state, Eventualmente consistente  - disponibilidad básica, inestable). estado, coherencia en última instancia), mientras que este enfoque se opone directamente a ACID [17] . La disponibilidad básica se refiere a un enfoque para diseñar una aplicación de modo que una falla en algunos nodos conduzca a una denegación de servicio solo para una pequeña parte de las sesiones mientras se mantiene la disponibilidad en la mayoría de los casos [18] . El estado volátil implica la capacidad de sacrificar el almacenamiento a largo plazo del estado de la sesión (como resultados intermedios de selecciones, información sobre navegación, contexto), mientras se concentra en enviar actualizaciones solo a operaciones críticas. Coherencia, que en última instancia se interpreta como la posibilidad de inconsistencia de los datos en algunos casos, pero al tiempo que garantiza un acuerdo en un tiempo prácticamente previsible, se dedica una cantidad significativa de investigación independiente a [19] [20] .

Notas

  1. ↑ Cervecero, 2000 .
  2. ↑ Gilbert, Lynch, 2002 , En PODC 2000, Brewer, en una charla invitada, hizo la siguiente conjetura: es imposible que un servicio web brinde las siguientes tres garantías: • Coherencia • Disponibilidad • Tolerancia de partición, p. 55.
  3. ↑ 1 2 White Paper Superando el teorema CAP  (inglés) ( PDF )  (enlace no disponible) . genedb.com (17 de abril de 2011). Consultado el 7 de junio de 2011. Archivado desde el original el 28 de junio de 2011.
  4. ↑ 1 2 Browne, Teorema CAP de Julian Brewer  ( 11 de enero de 2009). Consultado el 7 de junio de 2011. Archivado desde el original el 1 de agosto de 2012.
  5. ↑ 1 2 Brewer, 2010 , Los diseñadores de sistemas de área amplia, en los que las particiones de red se consideran inevitables, saben que no pueden tener tanto disponibilidad como coherencia y, por lo tanto, ahora pueden justificar una coherencia más débil. El surgimiento del movimiento “NoSQL” (“Not Only SQL”) es una expresión de esta libertad, p. 335.
  6. ↑ Rice, 2011 , Esta conjetura ahora se conoce comúnmente como el teorema CAP y es uno de los principales argumentos por los que la base de datos relacional tradicional que proporciona sólidas garantías ACID (transacciones atómicas, consistencia y aislamiento transaccional y técnicas de durabilidad de datos) no puede proporcionar tanto la partición tolerancia y disponibilidad requeridas por aplicaciones distribuidas a gran escala, pág. 49.
  7. ↑ Kuznetsov, 2011 , Una base "teórica" ​​más seria para los desarrollos NoSQL, en los que las propiedades útiles generalmente aceptadas de los sistemas de gestión de datos se sacrifican por la disponibilidad de estos sistemas, es el llamado "teorema CAP", formulado por primera vez por Eric cervecero, pág. 191.
  8. ↑ Kuznetsov, 2011 , adjunto la palabra teorema entre comillas, ya que no puedo reconocer el enunciado llamado Brewer como un teorema debido a la falta de un enunciado claro y al menos levemente formal del problema... pero se cree ampliamente que significa la imposibilidad de soportar en un sistema de gestión de datos distribuidos las propiedades de consistencia de los datos (Consistencia), disponibilidad (Availability) y resistencia a la separación de la red (Particionamiento), p. 191-192.
  9. ↑ Rice, 2011 Entonces, ¿por qué muchos de los principales sitios de redes sociales (Facebook, MySpace, Twitter), sitios web de comercio electrónico (sistemas de reservas de hoteles y sitios de compras) y grandes aplicaciones bancarias aún se implementan utilizando sistemas de bases de datos tradicionales como MySQL? (Facebook, Twitter) o SQL Server (MySpace, Choice Hotels International, Bank Itaú) en lugar de utilizar los nuevos sistemas NoSQL? … La respuesta de alto nivel es que la arquitectura de la aplicación todavía está sopesando las mismas compensaciones requeridas por el teorema CAP, p. cincuenta.
  10. ↑ Gilbert, Lynch, 2002 , En un modelo asíncrono, cuando no hay relojes disponibles, el resultado de imposibilidad es bastante fuerte: es imposible proporcionar datos consistentes, incluso permitiendo que se devuelvan datos obsoletos cuando se pierden los mensajes. Sin embargo, en modelos parcialmente síncronos es posible lograr un compromiso práctico entre consistencia y disponibilidad, p. 59.
  11. ↑ Grigorik, 2010 , El problema es que el teorema CAP propuesto por Eric Brewer y luego demostrado por Seth Gilbert y Nancy Lynch muestra que estos tres requisitos juntos son imposibles de lograr al mismo tiempo.
  12. ↑ Carter, 2011 , Algunos sistemas de CA incluyen: bases de datos de sitio único, bases de datos de clúster y LDAP.
  13. ↑ Demidov, 2010 , CP (denegación de servicio) es un enfoque con duplicación, consistencia ACID estricta y replicación síncrona de cambios mediante el método de bloqueo pesimista.
  14. ↑ Carter, 2011 , Algunos sistemas AP incluyen: sistemas de almacenamiento en caché web y el sistema de nombres de dominio (DNS).
  15. ↑ Carter, 2011 , Coherencia eventual: realizar una operación de lectura puede proporcionar datos obsoletos al cliente, pero todas las escrituras finalmente se propagarán por todo el sistema.
  16. ↑ Grigorik, 2010 , CAP implica consistencia débil.
  17. ↑ Pritchett, 2008 , Si ACID proporciona la opción de coherencia para las bases de datos particionadas, ¿cómo lograr la disponibilidad en su lugar? Una respuesta es BASE (básicamente disponible, estado suave, eventualmente consistente). BASE es diametralmente opuesto a ACID.
  18. ↑ Pritchett, 2008 , La disponibilidad de BASE se logra mediante la compatibilidad con fallas parciales sin una falla total del sistema. Aquí hay un ejemplo simple: si los usuarios se dividen en cinco servidores de base de datos, el diseño BASE fomenta las operaciones de elaboración de tal manera que una falla en la base de datos del usuario afecta solo al 20 por ciento de los usuarios en ese host en particular.
  19. ↑ Rompepiedras, 2010 .
  20. ↑ Vogels, 2008 .

Literatura