teorema CAP

4.1 Consistencia sobre Brewera

Para empezar, Eric Brewer no es, y nunca afirmó ser, un experto en bases de datos. Pertenece a la comunidad de los sistemas distribuidos, y su famosa charla, en la que aparecía el "teorema" de la CAP, fue impartida en la conferencia "Principles of Distributed Computing". (Por cierto, diez años después, en 2010, volvió a dar una charla invitada en la misma conferencia, y en esta charla dio, en particular, una serie de ejemplos de sistemas distribuidos, cuyo desarrollo tuvo en cuenta la " teorema" de CAP.) En esta área tiene su propia interpretación de los términos utilizados en el campo de las bases de datos.

En particular, el término "coherencia inmediata" significa que después de que el usuario recibe una notificación del sistema sobre la finalización exitosa de alguna operación de actualización de datos, el resultado de esta operación se vuelve instantáneamente visible para todos los observadores.

La consistencia eventual significa que si no ingresan nuevas operaciones de actualización de datos al sistema durante un período de tiempo lo suficientemente largo, entonces se puede esperar que los resultados de todas las operaciones de actualización de datos anteriores eventualmente se extiendan a todos los nodos del sistema, y ​​todos los datos de réplicas son consistente (aparentemente, esto debe entenderse como "todas las réplicas tendrán el mismo estado".

Con este sentido de consistencia en mente, el "teorema" de Brewer puede considerarse bastante comprensible y obvio: en cualquier sistema distribuido con datos compartidos, solo se pueden garantizar simultáneamente dos propiedades cualesquiera de consistencia, disponibilidad y tolerancia de partición de la red. En este sentido, Brewer incluso contrasta el conjunto de propiedades ACID con su conjunto propuesto de propiedades BASE (básicamente disponible, estado suave, consistencia eventual : disponibilidad en la mayoría de los casos; estado inestable; consistencia final). Pero esta oposición, en mi opinión, no está justificada, ya que en el primer caso estamos hablando de las características lógicas de las transacciones, y en el segundo, de las propiedades físicas de los sistemas distribuidos.

4.2 Prueba del "teorema"

Muchos creen que el "teorema" de Brewer ha sido probado formalmente. De hecho, el artículo de Seth Gilbert y Nancy Lynch introduce algunas definiciones (casi) formales, en cuyo contexto el "teorema" realmente se convierte en un teorema y se prueba. Sin embargo, veamos cómo se determinan esas tres propiedades de un sistema distribuido, de las cuales, según el “teorema” de Brewer, solo se pueden soportar dos propiedades simultáneamente.

La consistencia se denomina consistencia atómica o linealizable (consistencia atómica o linealizable), que es una propiedad del sistema, cuyos objetos de datos individuales son atómicos (linealizables). A su vez, un objeto atómico es un objeto con varias operaciones, de modo que la llamada de la operación y la recepción de los datos de respuesta ocurren como si fueran instantáneas, es decir, el objeto no acepta la llamada de la siguiente operación hasta que la operación anterior se haya completado por completo. El orden en que se reciben las operaciones debe ser tal que si llega una operación de tipo lectura después de que se haya realizado alguna operación de tipo escritura, entonces la operación de lectura debe devolver el valor escrito por esta o alguna operación de escritura posterior.

Un sistema distribuido siempre está disponible si cada solicitud recibida por un nodo que no falló debe ser respondida. La resistencia del sistema a la partición de la red se modela como la preservación de la viabilidad del sistema en caso de pérdida de un número arbitrario de mensajes enviados de un nodo a otro.

Con base en estas definiciones, Hilbert y Lynch formulan el siguiente teorema (no hay reloj en el modelo de red asíncrona y los nodos deben tomar decisiones solo sobre la base de los mensajes recibidos y los cálculos locales):

En un modelo de red asíncrona, no es posible implementar un objeto de datos de lectura/escritura que garantice las propiedades de disponibilidad y consistencia atómica para todas las ejecuciones válidas (incluidas aquellas que pierden mensajes).

En realidad, este teorema se demuestra formalmente de manera bastante simple mediante el método "por contradicción". El artículo continúa concluyendo que:

En un modelo de red asíncrona, no es posible implementar un objeto de datos de lectura/escritura que garantice propiedades de accesibilidad para todas las ejecuciones válidas y consistencia atómica para ejecuciones válidas en las que no se pierdan mensajes.

Además, se prueba la verdad del teorema principal para un modelo de red parcialmente síncrona, en el que cada nodo tiene un reloj, cuyo tiempo mostrado aumenta a la misma velocidad, pero que no están sincronizados, es decir puede mostrar diferentes tiempos en el mismo momento real. Se muestra que para este caso no se deriva una consecuencia similar y, por tanto, para redes parcialmente síncronas hay más posibilidades de organizar sistemas distribuidos con "buenas" propiedades.

Sí, en cierto sentido (no necesariamente el mismo que el pretendido por Brewer), se puede considerar que Gilbert y Lynch demostraron que es imposible garantizar simultáneamente las propiedades de consistencia atómica, disponibilidad y tolerancia de partición de una red en un solo sistema distribuido. Pero, ¿qué tiene esto que ver con las transacciones de bases de datos en general y las transacciones ACID en particular?

4.3 Transacciones ACID

Esto es lo que Julian Browne escribe sobre esto en su nota sobre la discusión del "teorema" de CAP:

En su demostración, Hilbert y Lynch usan el término atomicidad en lugar del término consistencia, que tiene más sentido desde un punto de vista técnico porque, estrictamente hablando, la consistencia en el sentido de ACID se refiere a las propiedades ideales de las transacciones de bases de datos y significa que no los datos se volverán persistentes si violan algunas restricciones preestablecidas. Pero si asumimos que una limitación preestablecida de los sistemas distribuidos es la prohibición de la presencia de varios valores diferentes para el mismo elemento de datos, entonces, en mi opinión, se puede considerar esta falla en la abstracción de la consistencia. insignificante (además, si Brewer usara el término atomicidad, entonces aparecería el teorema AAP, cuyo nombre sería extremadamente incómodo de pronunciar).

Esto está escrito no muy en serio, pero honestamente. Y, de hecho, el requisito de consistencia atómica no debe mezclarse con los requisitos de consistencia transaccional en el sentido de ACID. Las restricciones de integridad de la base de datos son requisitos comerciales lógicos, por así decirlo. Vienen de la lógica del dominio de la aplicación. El requisito de consistencia atómica es de un tipo muy diferente. Este es un requisito de implementación que cae en la categoría a la que tradicionalmente se hace referencia en la industria de las bases de datos como consistencia física (por ejemplo, al realizar cualquier operación de cambio de índice, todos los bloques del árbol B+ correspondiente deben contener valores válidos y estar vinculados por referencias válidas). ).

Y esto es lo que los representantes de la comunidad de bases de datos, Daniel Abadi y Alexander Thomson, escriben muy seriamente en su nota:

... el requisito de disponibilidad de sistemas transaccionales escalables es cada vez más crítico, y esto generalmente se cumple mediante la replicación y la redirección automática de solicitudes en caso de falla de uno de los nodos. Por lo tanto, los desarrolladores de aplicaciones esperan que las garantías de consistencia de los sistemas ACID (que originalmente consistían en soporte local para invariantes definidos por el usuario) se amplíen para garantizar una fuerte consistencia (que todas las réplicas de los mismos datos en un momento dado serán copias idénticas, es decir, en la consistencia de este caso está implícita en el sentido de CAP/PACELC.

En otras palabras, la consistencia de Brewer no tiene nada que ver con la consistencia ACID, pero es en los sistemas enfocados en brindar alta disponibilidad a través de la replicación de datos donde es deseable mantener una sólida consistencia de réplica. Esta no es una propiedad de ACID, sino una característica técnica (física) de DBMS masivamente paralelo que facilita el desarrollo de aplicaciones.

Según Michael Stonebreaker, la clave para construir un DBMS moderno de alta calidad es la elección correcta de compromisos técnicos. Al elegir una solución de ingeniería específica, se deben tener en cuenta muchos factores: los requisitos de los usuarios futuros, la probabilidad de varias situaciones de falla, etc., y no guiarse dogmáticamente por ninguna guía teórica general (incluido el "teorema" de CAP).

Stonebreaker cree que en el ámbito de los sistemas de bases de datos paralelas transaccionales, abandonar la consistencia de Brewer a favor de admitir alta disponibilidad y tolerancia a la partición de la red es una mala compensación porque (a) la consistencia de la réplica es una característica muy útil del sistema; (b) los DBMS transaccionales masivamente paralelos no necesitan clústeres con una gran cantidad de nodos, por lo que las situaciones de división de la red son poco probables; (c) el sistema puede dejar de estar disponible fácilmente, no debido a una partición de la red, sino, por ejemplo, a causa de la presencia de errores de software que ocurren regularmente.

Por lo tanto, la alta actividad de los representantes del campo NoSQL (léase NoACID), que a menudo se refieren al "teorema" de Brewer, no está relacionada con la imposibilidad teórica de construir SGBD transaccionales masivamente paralelos que admitan transacciones ACID, sino con el hecho de que los sistemas simplificados que no solo admiten transacciones ACID, sino también coherencia de réplica, se crean de manera más fácil y rápida. Debido a su organización simple, son capaces de procesar datos muy rápidamente y, para algunas aplicaciones, esto es más importante que todas las ventajas inherentes a la tecnología de bases de datos.

Veamos cómo responde la comunidad de bases de datos a este desafío.