Teorema CAP: qué es y qué significa en bases de datos distribuidas

Teorema CAP: qué es y qué significa en bases de datos distribuidas
Índice
  1. Qué significa cada letra
  2. Enunciado
  3. La idea de la demostración
  4. Por qué «elige dos de tres» es engañoso
  5. Sistemas CP y sistemas AP
    1. Ejemplo: quórums de lectura y escritura
  6. PACELC: lo que pasa cuando no hay partición
  7. Errores frecuentes al hablar de CAP
  8. Historia
  9. Preguntas frecuentes
    1. ¿Qué es el teorema CAP?
    2. ¿Qué significan C, A y P?
    3. ¿Por qué se llama también teorema de Brewer?
    4. ¿Existen bases de datos CA?
    5. ¿Qué es PACELC?
  10. Fuentes

Actualizado el

El teorema CAP dice que un sistema de datos distribuido en varias máquinas no puede garantizar a la vez tres cosas: que todos los nodos devuelvan siempre el dato más reciente (consistencia), que todo nodo que funcione responda siempre (disponibilidad) y que el sistema siga funcionando aunque la red pierda mensajes entre nodos (tolerancia a particiones). Como en una red real las particiones ocurren, la consecuencia práctica es esta: cuando la red se parte, hay que elegir entre consistencia y disponibilidad.

Qué significa cada letra

Las definiciones precisas son las de la demostración formal de 2002, y conviene usarlas tal cual, porque las palabras tienen aquí un sentido más estricto que en el lenguaje corriente:

LetraPropiedadDefinición en el teorema
CConsistencia (consistency)Toda lectura devuelve el valor de la escritura más reciente o un error. El sistema se comporta como si hubiera una sola copia de los datos (lo que técnicamente se llama linealizabilidad).
ADisponibilidad (availability)Toda petición que llega a un nodo que no ha fallado recibe una respuesta (que no sea un error), aunque no sea la más reciente.
PTolerancia a particiones (partition tolerance)El sistema sigue funcionando aunque la red pierda o retrase un número arbitrario de mensajes entre nodos.

Un aviso importante: la C de CAP no es la C de ACID. En las transacciones ACID, «consistencia» significa que se respetan las reglas de integridad de la base de datos (claves, restricciones); en CAP significa que todas las réplicas parecen una sola.

Enunciado

En un sistema distribuido con datos replicados, en una red asíncrona donde se pueden perder mensajes, es imposible implementar un objeto de lectura y escritura que garantice a la vez consistencia (linealizable) y disponibilidad en todas las ejecuciones, incluidas aquellas en las que hay particiones de red.

La idea de la demostración

La prueba es corta y se entiende con solo dos nodos.

  1. Hay dos nodos, N1 y N2, cada uno con una copia del dato v, que vale inicialmente v0.
  2. Se produce una partición: ningún mensaje pasa de un nodo al otro.
  3. Un cliente escribe v = v1 en N1. Si el sistema es disponible, N1 tiene que aceptar la escritura y responder, aunque no pueda avisar a N2.
  4. Otro cliente lee v en N2. Si el sistema es disponible, N2 tiene que responder, y lo único que conoce es v0.
  5. La lectura devuelve v0 después de que se escribiera v1: el sistema no es consistente.

Para ser consistente, N2 tendría que esperar o devolver un error, y entonces no sería disponible. No hay salida: con la red partida, C y A son incompatibles.

Por qué «elige dos de tres» es engañoso

El teorema se suele resumir como «de C, A y P, elige dos». El propio Brewer explicó en 2012 que esa forma de decirlo siempre fue engañosa. Las razones:

  • P no es opcional. En un sistema repartido en varias máquinas, la red puede fallar; no se puede «elegir» que no haya particiones. Un sistema «CA» solo tiene sentido si está en una sola máquina o si se acepta que deje de funcionar cuando la red falla.
  • La elección solo se plantea durante una partición. Mientras la red funciona, se pueden tener consistencia y disponibilidad. Las particiones son poco frecuentes, así que no hay motivo para renunciar a C o a A cuando no las hay.
  • No es todo o nada. Un mismo sistema puede tomar decisiones distintas para distintas operaciones o datos, y hay grados intermedios de consistencia.

Sistemas CP y sistemas AP

Con esa precisión, la clasificación útil es qué hace cada sistema cuando hay una partición:

  • CP (consistencia ante particiones): los nodos que no pueden confirmar que tienen el dato más reciente rechazan la petición o esperan. Es lo que se quiere en un saldo bancario, en el inventario de un producto con pocas unidades o en un servicio de bloqueos y coordinación.
  • AP (disponibilidad ante particiones): todos los nodos siguen respondiendo, aunque algunos con datos atrasados, y las copias se reconcilian cuando la red se recupera (consistencia eventual). Es aceptable en un carrito de la compra, un contador de «me gusta» o un DNS.

Ejemplo: quórums de lectura y escritura

Muchas bases de datos replicadas guardan cada dato en N nodos y permiten configurar cuántos deben confirmar una escritura (W) y cuántos se consultan en una lectura (R). Si R + W > N, cualquier conjunto de nodos leídos y cualquier conjunto de nodos escritos tienen al menos un nodo en común, y la lectura ve la última escritura.

  • Con N = 3, W = 2 y R = 2: 2 + 2 = 4 > 3. Las lecturas ven siempre la última escritura confirmada, pero si una partición deja a un cliente con acceso a un solo nodo, ni lee ni escribe: se elige C.
  • Con N = 3, W = 1 y R = 1: 1 + 1 = 2, que no es mayor que 3. Cualquier nodo accesible responde, pero una lectura puede no ver la última escritura: se elige A.
  • Con N = 5, W = 3 y R = 3: 3 + 3 = 6 > 5, y el sistema sigue leyendo y escribiendo de forma consistente aunque fallen o queden aislados 2 de los 5 nodos, siempre que el cliente alcance a los otros 3.

Esta regla de los quórums es una simple cuenta de conjuntos: dos subconjuntos de tamaños R y W de un conjunto de N elementos se solapan siempre que R + W > N.

PACELC: lo que pasa cuando no hay partición

En 2010 Daniel Abadi propuso ampliar CAP con PACELC: si hay una Partición (P), elegir entre disponibilidad (A) y consistencia (C); si no (Else, E), elegir entre latencia (L) y consistencia (C). La segunda mitad recoge algo que CAP no dice: incluso con la red sana, mantener todas las réplicas sincronizadas antes de responder hace que cada operación tarde más. Muchos sistemas renuncian a algo de consistencia en el funcionamiento normal para responder más rápido.

Errores frecuentes al hablar de CAP

  • Decir que una base de datos «es CA». Si está distribuida, tiene que decidir qué hace cuando hay una partición.
  • Confundir la consistencia de CAP con la de ACID.
  • Pensar que un sistema AP devuelve datos incorrectos siempre: solo puede devolver datos atrasados durante una partición o mientras las réplicas se ponen al día.
  • Creer que CAP habla de rendimiento. No dice nada de la latencia; eso lo añade PACELC.

Historia

Eric Brewer, profesor de la Universidad de California en Berkeley, presentó la idea como conjetura en el simposio PODC (Principles of Distributed Computing) del año 2000. Por eso también se le llama teorema de Brewer. En 2002, Seth Gilbert y Nancy Lynch, del MIT, publicaron la demostración formal, con las definiciones precisas de C, A y P, y la conjetura pasó a ser un teorema. En 2012 Brewer publicó en la revista Computer del IEEE el artículo «CAP twelve years later: how the “rules” have changed», donde matizó el resumen de «dos de tres».

CAP es un buen ejemplo de que un teorema no tiene por qué ser de geometría o de cálculo: es un enunciado preciso, con hipótesis y demostración, sobre un modelo matemático de los sistemas distribuidos. Si te interesa esa diferencia entre enunciado intuitivo y teorema demostrado, lo tienes en la guía de qué es un teorema; y otros resultados de imposibilidad, todavía más profundos, en la de los teoremas de incompletitud de Gödel. La lógica de «si hay partición, entonces no (C y A)» se niega y se transforma con las leyes de De Morgan: «no (C y A)» equivale a «no C o no A».

Preguntas frecuentes

¿Qué es el teorema CAP?

Un resultado de sistemas distribuidos que dice que, con datos replicados en una red que puede partirse, no se pueden garantizar a la vez consistencia (lecturas siempre actualizadas) y disponibilidad (todo nodo responde). Durante una partición hay que elegir una de las dos.

¿Qué significan C, A y P?

C es consistencia: toda lectura ve la última escritura. A es disponibilidad: todo nodo que funciona responde. P es tolerancia a particiones: el sistema sigue funcionando aunque se pierdan mensajes entre nodos.

¿Por qué se llama también teorema de Brewer?

Porque lo propuso Eric Brewer como conjetura en el año 2000. Lo demostraron formalmente Seth Gilbert y Nancy Lynch en 2002.

¿Existen bases de datos CA?

Solo si no están distribuidas o si se acepta que dejen de funcionar cuando falla la red. En un sistema repartido en varias máquinas las particiones pueden ocurrir, y la elección real es entre C y A cuando ocurren.

¿Qué es PACELC?

Una ampliación de CAP propuesta por Daniel Abadi en 2010: si hay partición, elegir entre disponibilidad y consistencia; si no, entre latencia y consistencia.

Fuentes

Teoremas

RELACIONADOS

Subir