Una demostración ilustrada del Teorema de la TAPA
El Teorema de la TAPA es un teorema fundamental en sistemas distribuidos que establece que cualquier sistema distribuido puede tener como máximo dos de las siguientes tres propiedades.
- Consistencia
- Disponibilidad
- Tolerancia de partición
¡Esta guía resumirá la especificación de Gilbert y Lynch y la prueba del Teorema de la TAPA con imágenes!
¿Qué es el teorema de la TAPA?
El teorema CAP establece que un sistema distribuido no puede ser consistente, disponible y tolerante a particiones simultáneamente. Suena bastante simple, pero ¿qué significa ser consistente? disponible? ¿tolerante a particiones? Diablos, ¿qué quieres decir exactamente con un sistema distribuido?
En esta sección, presentaremos un sistema distribuido simple y explicaremos lo que significa que ese sistema esté disponible, sea consistente y tolere particiones. Para una descripción formal del sistema y las tres propiedades, consulte el artículo de Gilbert y Lynch.
Un sistema distribuido
Consideremos un sistema distribuido muy simple. Nuestro sistema se compone de dos servidores, $G_1$ y $G_2$. Ambos servidores realizan un seguimiento de la misma variable, $v whose, cuyo valor es inicialmente $v_0.. $G_1 can y G G_2 can pueden comunicarse entre sí y también pueden comunicarse con clientes externos. Así es como luce nuestro sistema.
Un cliente puede solicitar escribir y leer desde cualquier servidor. Cuando un servidor recibe una solicitud, realiza los cálculos que desea y luego responde al cliente. Por ejemplo, así es como se ve una escritura.
Y así es como se ve una lectura.
Ahora que hemos establecido nuestro sistema, repasemos lo que significa para el sistema ser consistente, disponible y tolerante a particiones.
Consistencia
Así es como Gilbert y Lynch describen la consistencia.
cualquier operación de lectura que comience después de que se complete una operación de escritura debe devolver ese valor, o el resultado de una operación de escritura posterior
En un sistema consistente, una vez que un cliente escribe un valor en cualquier servidor y recibe una respuesta, espera recuperar ese valor (o un valor más fresco) de cualquier servidor desde el que lee.
Aquí hay un ejemplo de un sistema inconsistente.
Nuestro cliente escribe $v_1$ a $G_1$ y $G_1$ reconoce, pero cuando se lee desde $G_2$, se obtiene de los datos antiguos: $v_0$.
Por otro lado, aquí hay un ejemplo de un sistema consistente.
En este sistema, $G_1 repl replica su valor a G G_2 before antes de enviar un acuse de recibo al cliente. Por lo tanto, cuando el cliente se lee de $G_2$, se obtiene la mayoría hasta la fecha valor de $v$: $v_1$.
Disponibilidad
Así es como Gilbert y Lynch describen la disponibilidad.
cada solicitud recibida por un nodo que no falla en el sistema debe dar lugar a una respuesta
En un sistema disponible, si nuestro cliente envía una solicitud a un servidor y el servidor no se ha bloqueado, entonces el servidor debe responder finalmente al cliente. El servidor no puede ignorar las solicitudes del cliente.
Tolerancia de partición
Así es como Gilbert y Lynch describen las particiones.
a la red se le permitirá perder arbitrariamente muchos mensajes enviados de un nodo a otro
Esto significa que cualquier mensaje send G_1 and y G G_2 send enviado entre sí puede ser eliminado. Si se eliminaran todos los mensajes, entonces nuestro sistema se vería así.
Nuestro sistema tiene que ser capaz de funcionar correctamente a pesar de particiones de red arbitrarias para ser tolerante a particiones.
La prueba
Ahora que nos hemos familiarizado con la noción de consistencia, disponibilidad y tolerancia de particiones, podemos probar que un sistema no puede tener simultáneamente las tres.
Asuma para contradicción que existe un sistema que es consistente, disponible y tolerante a particiones. Lo primero que hacemos es particionar nuestro sistema. Se parece a esto.
a continuación, tenemos a nuestra solicitud de cliente que $v_1$ ser escrito $G_1$. Dado que nuestro sistema está disponible, $G_1 must debe responder. Sin embargo, dado que la red está particionada, $G_1 cannot no puede replicar sus datos a$ G_2.. Gilbert y Lynch llaman a esta fase de ejecución \ \ alpha_1..
A continuación, nuestro cliente emite una solicitud de lectura a $G_2.. De nuevo, dado que nuestro sistema está disponible, $G_2 must debe responder. Y como la red está particionada, $G_2 cannot no puede actualizar su valor desde $G_1.. Devuelve $v_0$. Gilbert y Lynch llaman a esta fase de ejecución \ \ alpha_2..
$G_2$ returns $v_0$ para nuestro cliente después de que el cliente ya había escrito $v_1$ a $G_1$. Esto es inconsistente.
Asumimos que existía un sistema consistente, disponible y tolerante a particiones, pero solo demostramos que existe una ejecución para cualquier sistema en el que el sistema actúe de manera inconsistente. Por lo tanto, no existe tal sistema.