El teorema de CAP

Los que sigais de cerca el mundillo de NoSQL seguramente habreís escuchado, cuando se comentan las características de implementación de estas bases de datos, que los desarrolladores han tenido que escoger entre garantizar consistencia o garantizar disponibilidad, siempre sacrificando una de ellas. Esta dicotomía es debida al teorema de CAP 1, que lanzado inicialmente como una conjetura 2 en el año 2000 por Eric Brewer (motivo por el cual al teorema se le conoce formalmente como teorema de Brewer), y posteriormente probado formalmente en el 2002 3, establece que:

Un sistema de datos compartidos pude asegurar como mucho dos de estas tres propiedades: Consistencia, Disponibilidad y Tolerancia a particiones.

El problema con este teorema es que la definición es muy simple (y por tanto, fácil de recordar), y ha provocado y sigue provocando muchas confusiónes, entre otras cosas porque se cambia el significado real de las propiedades (por ejemplo, tolerancia a particiones a veces se aplica a particionar los datos funcionalmente en diferentes ubicaciones). Así pués, recordemos antes de nada el significado de estas tres propiedades según la definición del teorema (y recordad que estamos hablando de sistemas distribuidos):

  • Consistencia: un conjunto de operaciones se deben ejecutar al mismo tiempo, o dicho de otra forma, un sistema es consistente si una modificación se aplica a todos los nodos en el mismo tiempo lógico y, por tanto, cuando se recupera la información, todos los nodos devuelven el mismo resultado. Es lo que se conoce como consistencia atomica o estricta (“Linearizability” en inglés)
  • Disponibilidad: cualquier petición recibida en un nodo del sistema debe obtener una respuesta, aunque falle el resto de los nodos.
  • Tolerancia a particiones: una petición debe ser procesada por el sistema incluso si se pierden de forma arbitraria mensajes entre alguno o todos los nodos del sistema, es decir, si un nodo se separa de la red (porque pierde conectividad, …), el sistema seguirá disponible.

Por lo tanto, siguiendo el teorema, un sistema distribuido solamente podrá asegurarnos:

  • CP: el sistema ejecutará las operaciones de forma consistente, aunque se pierda la comunicación entre nodos (partición del sistema), pero no se asegura que el sistema responda (disponibilidad).
  • AP: el sistema siempre responderá a las peticiones, aunque se pierda la comunicación entre nodos (partición del sistema). Los datos procesados pueden no ser consistentes.
  • CA: el sistema siempre responderá a las peticiones y los datos procesados serán consistentes. En este caso no se permite una perdida de comunicación entre nodos (partición del sistema).

Vamos a poner un ejemplo práctico para que se entienda mejor. Imaginemonos que tenemos un sistema de datos que mantiene la información almacenada en 3 nodos {A, B, C}, y en un momento concreto un cliente lanza una petición de escritura, pero debido a un fallo de red se pierda la comunicación entre algunos nodos, y por tanto el sistema se particiona en 2, por ejemplo {A, B} y {C}:

  • En un sistema CP, para garantizar la consistencia debemos asegurarnos que la operación se realiza en los 3 nodos al mismo tiempo. Como el sistema se ha particionado (y sigue vivo ya que toleramos las particiones), si la petición se procesa por el nodo {C} será imposible replicarla en los nodos {A, B}. Ante esta situación, el nodo {C} deberá rechazar la escritura hasta que se deshaga la partición (ya que sino no podría garantizar consistencia), lo que da lugar a indisponibilidad.
  • En un sistema AP, nos importa más la disponibilidad, por lo que aunque haya una partición del sistema, la petición se procesará igualmente. En este caso, el sistema no nos puede garantizar la consistencia, ya que no sabe si la información procesada por un nodo (por ejemplo, {C}) ha sido replicada al resto de nodos ({A, B}).
  • En el caso de un sistema CA, el tema se complica un poco más. Si el sistema no esta particionado, cualquier operación se procesará y replicará al resto de nodos. Ahora bien, si el sistema se particiona, entonces el sistema debería fallar, ya que no podremos garantizar la consistencia de la operación, y si falla, entonces no podemos garantizar disponibilidad, por lo que estaríamos delante del mismo caso que un sistema CP. Resumiendo, que este tipo de sistema es bastante improbable, ya que para que funcione es necesario que la comunicación entre nodos siempre esté en perfecto estado (improbable), o en su defecto, tolerar las particiones como en un sistema CP.

A partir de este ejemplo, podemos ver la razón por la que las implementaciones de bases de datos distribuidas (tanto las tradicionales como las NoSQL) se vean obligadas a escoger entre consistencia (CP) o disponibilidad (AP), pero jamas podrán escoger las dos (CA), a no ser claro está que solo haya un nodo o que todos los nodos residan en la misma caja física (pero entonces no serian distribuidas). Me reservo otra entrada para explicar que tipo de solución implementan los distintos servidores distribuidos que hay en el mercado y, oh, sorpresa, algunas incluso logran garantizar las 3. ¿Sabeis cómo?

1 La palabra CAP viene determinada por las iniciales de las 3 propiedades (en inglés): Consistency, Availability, Partition tolerance.

2 La presentación original de E. Brewer: “Towards Robust Distributed Systems” (PDF).

3 La prueba formal del teorema: “Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services” (PDF).

Comments

Comment by CM on 2011-08-26 03:06:43 +0000

¿Cómo se garantizan las 3? De verdad existe la forma de hacerlo?

Comment by ferdy on 2011-09-22 23:01:40 +0000

CM, según el teorema, no se pueden garantizar las 3. Para lidiar con este problema se suele recurrir a la Eventual Consistency. En cuanto tenga tiempo, escribiré una entrada sobre esto.

Comment by PaEs on 2012-12-24 03:57:09 +0000

Hola Amigo! podrías darme un ejemplo más claro de un sistema CP?

Mi duda es que si el sistema es Tolerante a Particiones, como puede ser al mismo tiempo consistente??. Si es tolerante a particiones entonces no se garantiza que los datos sean replicados a todos los nodos (porque la comunicación puede fallar), por lo tanto no hay consistencia.

En el ejemplo de sistema CP ponés:

“Ante esta situación, el nodo {C} deberá rechazar la escritura hasta que se deshaga la partición (ya que sino no podría garantizar consistencia)”

Da a entender que para que el sistema sea consistente no debe haber particiones.. por lo tanto un sistema CP es improbable.

Comment by Sergio on 2016-01-14 15:26:50 +0000

Es consistente, porque no deja realizar la escritura o lectura…

Lo que no tiene es disponibilidad, hasta que se termine el particionamiento.

Comment by Sergio Gabriel on 2017-07-02 01:36:20 +0000

El caso de CA sucede en los RDBMS tradicionales (Consistency, Availability), pero en el caso de una arquitectura de replicación el RDBMS no podría más que garantizar la consistencia eventual. Sería interesante hacer un análisis de qué propiedad se va cumpliendo en los diferentes escenarios, alta disponibilidad con replicación síncrona, asíncrona, maestro-esclavo y multi maestro.

Muy buen artículo!

Saludos.

Sergio Gabriel

Corrientes – Argentina

Publicado en General | Etiquetado

¡Hola mundo!

Hacia tiempo que tenia habilitado este blog (básicamente para hacer pruebas con los plugins de WordPress), y hoy me he decidido a sacarle un poco de provecho.

Como algunos ya sabeis, solía escribir en otro blog (SDLC Blog), en inglés (por aquello de llegar a un público más amplio) y enfocado el mundo de las metodologias y herramientas de desarrollo de aplicaciones (que es de lo que trabajaba hasta ahora). Ahora quiero disponer de un espacio donde pueda vomitar mis reflexiones sin estar atado ni a una tematica ni a un idioma en concreto. De ahí que aproveche este blog para hablar de mis cosillas, de tecnologia, de internet, de escalabilidad, de lenguajes de programación, … vaya, de lo que me de la gana. Espero no aburriros demasiado.

Pués ahí queda es, ¡Hola Mundo!

Publicado en General