Teorema CAP

Hasta este punto deberíamos tener un panorama general de lo que es un clúster, como es que funcionan los diferentes servicios distribuidos y para que podemos usar cada uno de estos, pero bueno, llego la hora de incrementar un poco el nivel, y procederemos al apartado de almacenamiento, las bases de datos NoSQL y para descontrolarnos un poco describiré y demostraré la esencia del teorema CAP, que es un teorema que es de utilidad para esta área y poder elegir una base de datos NoSQL y no solo por decir un nombre por que es la única que conocemos, y a partir de aquí comienza la sección relacionada a NoSQL.

Este teorema trata tres puntos esenciales en un sistema distribuido los cuales son consistency, availability y partition tolerance.

Antes de empezar a jugar con este teorema empezaré por definir las 3 características anteriores.

1. Consistency (Consistencia): Cualquier operación de lectura que se realice después de una operación de escritura se complete debe regresar el valor correspondiente a la operación de escritura que se acaba de realizar.
2. Availability (Disponibilidad): Cada petición que se reciba a un nodo activo del clúster necesita regresar una respuesta. 
3. Partition Tolerance (Tolerancia a Particiones): El clúster permitirá la perdida de bloques arbitrarios que son enviados de un lugar a otro entre la red del clúster.

Una vez definido esto, como tal vez con palabras no es algo muy explicito y a veces algo abstracto de entender, explicaré las dos primeras de forma gráfica, ya que la tercera fue explicada en un post anteriores llamado Replicas y Formas de Paralelización.

Consistencia

Supongamos  que tenemos el siguiente sistema distribuido con dos máquinas y un cliente externo, nuestro clúster contiene información v0 inicial obviamente en ambas máquinas.

De acuerdo a nuestra definición de consistencia, si el cliente manda una operación de escritura sobre la información de v0 de la máquina dos luciría así la imagen.

Una vez que la petición es aceptada por m2, en esta máquina se refleja el cambio  y regresa un mensaje de que se ha terminado la operación de forma exitosa.

Así terminando el ciclo, pero hasta este punto, no se cumple la consistencia, ya que si el cliente le hace una petición de lectura a la misma información a la máquina m1, la máquina m1 regresará el valor v0, mientras que la máquina m2 tiene el valor de v1, por lo cuál no sería consistente, pero que pasa si en lugar de una vez terminado el cambio en m2, ese cambio se reflejara en m1 en lugar de avisar que se termino el flujo cuando se replico la primera vez, veamos gráficamente lo anterior en una imagen. 

  

Entonces en lugar de regresar un mensaje de finalizado al cliente, la máquina m1 manda la misma petición de escritura a la máquina m1, una vez que también se realiza el cambio en m1, m2 manda un mensaje de que termino de escribir.

Y una vez que m2 recibe el mensaje de que m1 termino la operación de escritura, m2 manda un mensaje de finalización al cliente.



Terminando el flujo, el estado del clúster lucirá de la siguiente manera. 

Entonces ahora si el cliente desea ejecutar una operación de lectura al clúster, ya no hay problema, por que ambas máquinas pertenecientes al clúster, regresarán el mismo resultado en una operación de lectura.

Disponibilidad

La disponibilidad implica que si se manda una petición al servidor y el cliente sigue vivo, entonces siempre debe recibir una respuesta, en caso contrario significa que el servicio no esta disponible.

Una vez explicado lo anterior, procederemos a citar lo que el teorema CAP afirma.

Teorema CAP

El teorema CAP afirma que en un sistema distribuido no pueden existir simultáneamente las 3 características de Consistencia, Disponibilidad y Tolerancia a Particiones. 

Una vez que conocemos esto, probaremos la afirmación anterior, primero de forma gráfica y luego de una manera más formal, entonces empezamos probando la afirmación del teorema CAP por contradicción, osea, nosotros supondremos que un Sistema Distribuido puede tener las 3 características.

Y lo primero que vamos a hacerle a nuestro clúster de dos máquinas es partirlo.

Una vez que hemos partido nuestro clúster en 2 conjuntos disjuntos de máquinas procederemos a suponer que el cliente manda una petición de escritura a una máquina, en este caso G2, como nuestro sistema esta Disponible el cliente recibirá una respuesta después de realizar la operación, como el clúster se particiono G2 no podrá replicar el resultado en G1 a esta parte del proceso se le llamará α1.

Una vez que se termino la fase α1, podemos definir una fase α2  la cuál consistirá en pura lectura a nuestro clúster la cuál viene descrita con las siguientes palabras, como nuestro sistema distribuido esta disponible nuestro cliente hace una petición de lectura a nuestra máquina G1 y como esta disponible ella responderá, pero como el clúster se particiono, G2 no pudo replicar su valor en G1, por lo que se quedo con el valor v0 la máquina G1 entonces nos regresara el valor v0.

Por lo que el clúster se vuelve inconsistente ya que la información de ambos objetos es diferente en cada máquina, por lo cuál se llego a una contradicción.

Una vez explicado de manera gráfica el teorema CAP, procederemos a escribirlo de una manera más formal, la cuál puede leerse de la siguiente manera.

Por último daré las siguientes dos definiciones que creo hacen falta para poder entender la idea anterior.

Así que como podemos ver en toda la descripción anterior, este teorema demuestra que no se pueden tener estas tres propiedades en un sistema distribuido, por lo cuál las Bases de Datos en general solo pueden garantizar dos de ellas, como podemos ver en la siguiente imagen.

Como podemos ver hemos trabajado toda nuestra vida con este teorema ya que todas las RDBMS (Bases de Datos Relacionales) cumplen con la Consistencia y la Disponibilidad, pero en este apartado de Bases de Datos NoSQL trabajaremos con Bases Bases de Datos que son del tipo AP y CP, las cuales descubriremos poco a poco.

Cabe destacar que aunque los sistemas distribuidos no cumplen con las 3 características de manera estricta, hay ciertas herramientas que cumplen de manera débil la que no pueden cumplir, simulando que cumple las 3, para elegir una Base de Datos NoSQL debemos de analizar bien que es lo que queremos y para que es que lo necesitamos.