Teorema CAP

  El Teorema CAP, inicialmente llamado como la conjetura CAP, recibió el estatus de teorema cuando se proporcionó una prueba matemática del concepto,  [1]  

 CAP (Consistency, Availability, Partition Tolerance) establece que en un sistema distribuido, se puede cumplir como máximo con dos de estas propiedades: consistencia, disponibilidad y  tolerancia de partición. 

Consistencia

 En cuanto al concepto de consistencia en aplicaciones distribuidas, por ejemplo, si una empresa usa un servidor de base de datos de respaldo, cuando un usuario actualiza la cuenta de un cliente, esos mismos cambios se realizarían en el servidor de respaldo.

Esto requeriría que la base de datos escribiera los datos dos veces: una vez en el disco usado por el servidor primario y luego una vez más en el disco usado por el servidor de respaldo en una operación conocida como confirmación de dos fases, ver la Figura 1.

1. Consistencia. Adaptado de [2]

Mientras se ejecuta la confirmación de dos fases, se bloquean otras consultas a los datos. Los datos actualizados no estarán disponibles hasta que finalice la confirmación de dos fases. Esto favorece la coherencia sobre la disponibilidad de los datos.

Disponibilidad

La disponibilidad de datos se ilustra en el ejemplo del carro de compras de comercio electrónico [2],  donde es posible tener una copia de seguridad de los datos contenidos en el carro y que no este sincronizada con la copia principal. Los datos seguirían estando disponibles si el servidor primario falla, pero los datos del servidor de respaldo serian inconsistentes con los datos del servidor primario si el servidor primario falla antes de actualizar el servidor de respaldo.  Ver la Figura 2.

2. Disponbilidad. Adaptado de [2]

Tolerancia a la Partición.

El ejemplo mas simple de tolerancia de partición es cuando el sistema continúa funcionando incluso si las máquinas involucradas en la prestación del servicio pierden la capacidad de comunicarse entre sí debido a que un enlace de red se cae (ver  Figura 3).

 

3. Tolerancia a la partición . Adaptado de [3]

 Relación entre conceptos del Teorema CAP

La Figura 4 esquematiza los conceptos asociados al Teorema CAP y la relación entre ellos. Allí se resalta los puntos de intersección entre las propiedades definidas en el teorema, por ejemplo, CA es la intersección para los sistemas que cumplan la propiedad de consistencia y disponibilidad,  CP son los sistemas con las propiedades de consistencia y tolerancia a la partición, y  AP  para las propiedades de disponibilidad y tolerancia a la partición.

4.Relación entre Conceptos del Teorema CAP. Adaptado de [3]. 

Noten que la intersección entre los tres conceptos  no esta definida en la Figura 4.  El principio  CAP establece que no es posible construir un sistema distribuido que garantice los tres conceptos: consistencia, disponibilidad y tolerancia a la partición. Se pueden lograr uno o dos de ellos, pero no los tres simultáneamente. Al utilizar un sistema distribuidos se debe tener en cuenta cuales principios puede garantizar, de acuerdo a su diseño. Esto se ilustra en la Figura 5.

5. Significado del Teorema CAP. Adaptado de[4]

En el contexto de una aplicación de red social global, o un sistema de comercio electrónico mundial, la solución deseada es mantener la disponibilidad incluso si se sacrifica cierta consistencia entre los usuarios. Por otra parte, en el sistema financiero mundial, requiere  mantener la consistencia de los datos sobre la disponibilidad de los mismos, por tanto las actualizaciones podrían requerir mas tiempo para su ejecución. En la Figura,  5 se muestra las propiedades del Teorema CAP y los tipos de aplicaciones que cumplen con estas propiedades.

 

Bibliografia:

1. Eric A. Brewer. “Towards Robust Distributed Systems”. In: PODC ’00 (2000), pages 7–. DOI: 10.1145/343477.343502. 
2. Dan Sullivan. NoSQL for Mere Mortals. Pearson, 2015. 
3. Christina J. Hogan Thomas A. Limoncelli Strata R. Chalup. The Practice of Cloud System Administration: Designing and Operating Large Distributed Systems. Volume 2. Addison Wesley, 2014. ISBN: 032194318X.  
4. Ganesh Chandra Deka. NoSQL: Database for Storage and Retrieval of Data in Cloud. CRC Press, 2017.
5. Paulo Veríssimo and Luís Rodrigues. Distributed Systems for System Architects. Advances in Distributed Computing and Middleware Ser. 1. Springer, 2012. ISBN: 9781461356660.