¿Cuál es el razonamiento detrás del teorema CAP?

21

http://en.wikipedia.org/wiki/CAP_theorem

http://www.cs.berkeley.edu/~brewer/cs262b-2004/PODC-keynote.pdf

Creo que no es muy sencillo por qué solo dos de

  1. Consistencia
  2. Disponibilidad
  3. Tolerancia de partición

puede mantenerse para cualquier sistema de base de datos distribuido. Esta conjetura fue probada, pero ¿hay una manera más fácil de ver por qué probablemente esto podría ser válido?

No estoy buscando una prueba, solo una buena manera de entender por qué este teorema podría tener sentido. ¿Cuál es el razonamiento?

Lazer
fuente

Respuestas:

23

OK, imaginemos que tiene una base de datos distribuida. Digamos que tiene un nodo en Oregon y uno en California. La teoría CAP dice que tendrá problemas al configurar este tipo de base de datos.

Por ejemplo, si consulta datos de una base de datos, debe ser igual a los datos de la otra base de datos. Esto asegura que cualquier valor que tenga en una base de datos está garantizado en la otra ( Consistencia de la teoría CAP). Hacer esto le permite actualizar los datos en una base de datos y consultarlos desde otra, obteniendo los mismos resultados.

Una computadora que actualiza los datos en Oregon, transfiere los datos a California

Cuando actualizamos los datos en el nodo Oregon, los datos se envían al nodo California para que las bases de datos sean consistentes. Para mantener realmente la coherencia, debemos asegurarnos de que ambas bases de datos obtengan la actualización antes de que se les permita realmente guardar los datos (confirmación en dos fases mediante transacciones distribuidas). En otras palabras, si la base de datos de California no puede guardar los datos por alguna razón (por ejemplo, falla del disco duro), entonces la base de datos en Oregon no guardará los datos y fallará la transacción.

El problema con las transacciones distribuidas como la anterior viene cuando queremos tener alta disponibilidad. En este escenario anterior, el proceso de tratar de sincronizar ambas bases de datos es un proceso muy, muy lento. (Imagínese, tenemos que enviar los datos de Oregón a California, asegurarnos de que llegue allí, asegurarnos de que ambas bases de datos tengan bloqueos en los datos, etc.) Esto causa problemas importantes cuando queremos un sistema que sea rápido y sensible incluso durante tiempos de alta demanda. (Esta es la disponibilidad del teorema CAP.)

Por lo general, lo que hacemos para asegurar una alta disponibilidad es usar replicación en lugar de transacciones distribuidas. Entonces, en lugar de garantizar que California pueda aceptar los datos, simplemente seguimos almacenándolos en el nodo de Oregón y luego enviamos los datos a California cuando nos acercamos a ellos. Esto garantiza que siempre podamos almacenar los datos, independientemente de si California está lista para almacenar los datos o no.

El nodo de Oregon actualiza los datos mientras California los lee.  Más tarde, los datos se trasladan a California.

Esto mejora la disponibilidad, pero a costa de la coherencia. Vea, si alguien actualiza los datos en Oregon y luego alguien (al mismo tiempo) lee los datos en California, no está obteniendo los nuevos datos, las bases de datos ya no son consistentes. De hecho, ¡no serán consistentes hasta que Oregon envíe los datos a California!

Entonces, esa es la disponibilidad -vs- Consistencia de compensación.

La tolerancia de partición es el tercer aspecto de la teoría CAP. Particionar es, en este contexto, la idea de que una base de datos (u otro sistema distribuido) puede dividirse en secciones separadas y seguir funcionando correctamente.

La pregunta es, ¿qué sucede cuando ambas bases de datos se ejecutan correctamente, pero el enlace de Oregon a California se corta?

Oregon se actualiza mientras se lee el nodo de California.  La red entre los nodos se corta.

Si actualizamos la base de datos en Oregón, necesitamos llevar los datos a California de una forma u otra (transacción distribuida o replicación). Sin embargo, si el enlace entre los dos se corta, entonces el sistema se ha dividido y las bases de datos ya no están unidas.

Cuando esto sucede, sus opciones son dejar de permitir actualizaciones (para mantener la coherencia) a costa de la disponibilidad o permitir las actualizaciones (para mantener la disponibilidad) a costa de la coherencia.

Como puede ver, la tolerancia de partición crea compensaciones directas entre Consistencia y Disponibilidad.


Obviamente, hay más que eso, pero esos son un par de ejemplos sobre cómo estos tres aspectos principales de los sistemas distribuidos funcionan uno contra el otro. La explicación de Julian Browne de la teoría CAP es un excelente lugar para aprender más.

Ricardo
fuente
Respuesta relacionada de Remus Rusanu.
Nick Chammas el
¡Con una imagen mucho más bonita!
Richard