Modelos de consistencia, CAP y PACELC

Qué significa "consistente" cuando los datos se copian

En cuanto un sistema guarda más de una copia de un dato, en réplicas de zonas distintas, en cachés o en otros servicios, las copias pueden discrepar durante un tiempo. Un modelo de consistencia es el contrato que dice qué discrepancias pueden observar los clientes. Es una promesa sobre lo que pueden devolver las lecturas dadas las escrituras que han ocurrido y, por tanto, una promesa sobre qué sorpresas debe manejar el código de la aplicación.

Cuidado con esta palabra tan cargada de significados. La C de ACID (Sección 0.5) significa que una transacción lleva la base de datos de un estado válido a otro, respetando reglas como "un saldo nunca baja de cero". La C de CAP significa algo distinto y más limitado: cada lectura se comporta como si hubiera una única copia actualizada. Los niveles de aislamiento de las bases de datos, como serializable o read committed, son una tercera familia, referida a las transacciones concurrentes; se tratan en transacciones y aislamiento. Esta sección trata de las garantías de los datos replicados.

Modelos de consistencia, del más fuerte al más débil

La linealizabilidad, definida por Maurice Herlihy y Jeannette Wing en 1990, es el modelo de un solo objeto más fuerte. Cada operación parece surtir efecto instantáneamente en algún momento entre su inicio y su fin, y todos los clientes ven el mismo orden, que respeta el tiempo real: una vez completada una escritura, toda lectura que empiece después la ve, o ve algo más reciente. El sistema se comporta como si hubiera una sola copia. Ejemplo de reparto de comida: dos clientes intentan canjear el último código de descuento; con un almacén linealizable, exactamente uno lo consigue y el otro ve que ya no está, sea cual sea la réplica a la que llegue.

La consistencia secuencial, definida por Leslie Lamport en 1979 para multiprocesadores, mantiene el orden global único y mantiene las operaciones de cada cliente en el orden en que ese cliente las emitió, pero elimina el requisito de tiempo real. Un cliente puede leer un valor ligeramente desactualizado, siempre que todos estén de acuerdo en el orden de todas las escrituras. Las bases de datos distribuidas rara vez la ofrecen por su nombre, pero explica la diferencia entre "un orden acordado" y "un orden acordado que coincide con el reloj".

La consistencia causal solo exige que las operaciones relacionadas causalmente se vean en el mismo orden por parte de todos: si escribir B dependió de haber visto A, nadie puede ver B sin A. Las escrituras concurrentes y no relacionadas pueden verse en órdenes distintos por clientes distintos. Ejemplo: un restaurante responde "Sí, es sin gluten" a la pregunta de un cliente en el chat del pedido; nadie debería ver nunca la respuesta sin la pregunta. La consistencia causal resulta atractiva porque el mapa de modelos de consistencia de Jepsen, muy utilizado, la clasifica como alcanzable con disponibilidad adherente (sticky): puede seguir funcionando durante una partición siempre que cada cliente permanezca con la misma réplica.

Las garantías de sesión, descritas por Douglas Terry y sus colegas en 1994, son promesas más débiles, por cliente, que eliminan las anomalías más confusas. Leer tus propias escrituras (read-your-writes): después de que un cliente cambie la dirección de entrega, la siguiente lectura de ese cliente muestra la nueva dirección, aunque otros usuarios la vean más tarde. Lecturas monótonas: una vez que un cliente ha visto el estado del pedido "en reparto", nunca ve después "en preparación" porque una lectura posterior llegó a una réplica retrasada. (Otras dos garantías, las escrituras monótonas y las escrituras que siguen a las lecturas, restringen el orden en que se aplican las escrituras de un cliente.)

La consistencia eventual, popularizada por Werner Vogels en 2008, es la garantía útil más débil: si no llegan escrituras nuevas, todas las réplicas acaban convergiendo en el mismo valor. No dice nada sobre cuánto tarda eso ni sobre qué puede leerse mientras tanto, y una implementación básica que resuelve las escrituras en conflicto conservando la de marca de tiempo más reciente, conocida como last write wins (gana la última escritura), descarta la otra en silencio. Las formas más fuertes, como la consistencia eventual fuerte con tipos de datos replicados libres de conflictos (CRDT), garantizan que las réplicas que han recibido las mismas actualizaciones tengan el mismo estado, usando tipos de datos cuyas actualizaciones concurrentes siempre se fusionan, como contadores y conjuntos.

CAP: lo que dice realmente

Eric Brewer presentó la idea de CAP como una conjetura en su conferencia principal en el ACM Symposium on Principles of Distributed Computing (PODC) de 2000. En 2002, Seth Gilbert y Nancy Lynch publicaron una demostración formal, que la convirtió en un teorema para sus definiciones precisas. Consistencia significaba linealizabilidad. Disponibilidad significaba que toda solicitud recibida por un nodo que no ha fallado debe producir una respuesta. Tolerancia a particiones significaba que el sistema cumple sus promesas incluso cuando la red pierde un número arbitrario de mensajes entre nodos.

Leído con atención, el teorema CAP es limitado. Dice que, cuando se produce una partición de red, de modo que algunos nodos no pueden comunicarse con otros, un sistema replicado debe elegir para cada solicitud entre consistencia y disponibilidad. Un nodo aislado de las últimas escrituras puede negarse a responder (o esperar a que la partición se resuelva), preservando la consistencia, o responder con lo que tiene, preservando la disponibilidad a riesgo de devolver datos obsoletos o de aceptar escrituras en conflicto. El diagrama muestra el dilema en un sistema de venta de entradas que vende el asiento 14C.

Varias interpretaciones populares son erróneas. "Elige dos de los tres" sugiere que la tolerancia a particiones es opcional, pero en cualquier sistema que se comunica a través de una red las particiones ocurren lo elijas o no; la única elección real es cómo comportarse cuando ocurren. Un sistema llamado "CA" es uno que no ha decidido qué hacer cuando se produce una partición; eso solo es defendible donde las particiones son prácticamente imposibles, como en un único nodo. "Nuestra base de datos es CP (o AP)" suele ser impreciso: la disponibilidad de CAP es una propiedad muy fuerte que muchos sistemas comercializados como de alta disponibilidad no tienen, y muchos sistemas llamados CP tampoco son linealizables. Martin Kleppmann sostuvo en 2015 que las bases de datos no deberían etiquetarse en absoluto como CP o AP, porque la mayoría no encaja en ninguna de las dos definiciones y su comportamiento depende de la configuración. "CAP explica nuestra latencia" también es erróneo: CAP no dice nada sobre lo que ocurre cuando no hay partición, que es la mayor parte del tiempo.

CAP doce años después

En 2012, en un artículo de IEEE Computer titulado "CAP Twelve Years Later: How the Rules Have Changed", el propio Brewer explicó que el planteamiento de dos de tres había confundido a la gente. Las particiones son poco frecuentes, así que un sistema puede ofrecer consistencia y disponibilidad casi todo el tiempo; la elección solo se aplica durante una partición, y solo a las operaciones afectadas. Tampoco hace falta que la elección sea global: operaciones distintas y datos distintos pueden elegir de forma distinta.

Brewer recomendó diseñar explícitamente para las particiones en tres pasos: detectar la partición, entrar en un modo de partición explícito en el que algunas operaciones se limitan (por ejemplo, aceptar pedidos pero aplazar los reembolsos) y ejecutar después un proceso de recuperación que fusione el estado y compense los errores cometidos durante la partición. También señaló que la C de CAP es la consistencia de copia única, un subconjunto más estricto de lo que protege la C de ACID, y que invariantes como "no vender nunca de más" pueden tener que repararse a posteriori. Este planteamiento conduce directamente a las compensaciones a nivel de negocio de las sagas: una aerolínea que vende más plazas de las que tiene un vuelo compensa al pasajero en lugar de rechazar todas las reservas durante un fallo de red.

PACELC: el compromiso que pagas cada día

Daniel Abadi señaló en una entrada de blog de 2010, y en un artículo de IEEE Computer de 2012, "Consistency Tradeoffs in Modern Distributed Database System Design: CAP is Only Part of the Story", que CAP ignora el compromiso al que se enfrentan realmente los diseñadores la mayor parte del tiempo. PACELC se lee así: si hay una Partición, elige entre disponibilidad (Availability) y Consistencia; en caso contrario (Else), en funcionamiento normal, elige entre Latencia y Consistencia.

La mitad del "else" es la aportación importante. Para que una lectura sea consistente, un sistema replicado debe coordinarse: enviar la escritura a otras réplicas y esperar las confirmaciones, o dirigir todas las lecturas a un líder, o contactar con varias réplicas y comparar. Cada una de esas opciones cuesta viajes de ida y vuelta por la red, y entre regiones un viaje de ida y vuelta puede costar decenas o incluso cientos de milisegundos. Un sistema que responde desde la réplica más cercana sin coordinarse es más rápido, pero puede devolver datos obsoletos. Ese compromiso se paga en cada solicitud, haya partición o no.

A menudo se citan clasificaciones PACELC, como PA/EL para los sistemas ajustados para la velocidad y la disponibilidad, y PC/EC para los sistemas que siempre prefieren la consistencia. Trátalas como descripciones de una configuración, no de un producto: la misma base de datos puede ser PA/EL en un despliegue y PC/EC en otro, según los ajustes elegidos por tabla, por consulta o por solicitud.

Quórums: ajustar la consistencia con aritmética

Los almacenes replicados sin líder, al estilo del artículo de Dynamo de Amazon (2007), permiten que cada operación elija cuántas réplicas intervienen. Con N réplicas de un elemento, una escritura se confirma cuando W réplicas la han almacenado, y una lectura recoge respuestas de R réplicas y devuelve la versión más reciente entre ellas. Si R + W > N, todo conjunto de lectura se solapa con todo conjunto de escritura en al menos una réplica, así que una lectura incluirá al menos una copia de la última escritura confirmada.

La elección de R y W intercambia consistencia, latencia y disponibilidad. Valores más bajos significan esperar a menos réplicas, y más rápidas, y tolerar más fallos, a cambio de posibles lecturas obsoletas. Valores más altos significan lo contrario. De todos modos, las escrituras suelen enviarse a las N réplicas; W solo decide cuántas confirmaciones espera el cliente.

El solapamiento del quórum es necesario para obtener lecturas actualizadas, pero no es, por sí solo, linealizabilidad. Las escrituras concurrentes pueden ordenarse con marcas de tiempo de relojes que no coinciden, de modo que una escritura posterior puede perder con last-write-wins. Una escritura que falló después de llegar a algunas réplicas puede seguir siendo visible en ellas. Los quórums "laxos" (sloppy), que aceptan escrituras en nodos sustitutos durante los fallos, rompen el solapamiento. Y dos lecturas que se solapan con una escritura todavía en curso pueden ver el valor nuevo y luego el antiguo, a menos que el lector repare las réplicas retrasadas antes de devolver el resultado. Los almacenes que necesitan una verdadera semántica de comparar e intercambiar (compare-and-set) añaden un protocolo de consenso, como las transacciones ligeras basadas en Paxos de Apache Cassandra, solo para esas operaciones.

Cómo se pueden configurar bases de datos conocidas

Los productos reales rara vez se sitúan en un solo punto de la escalera. Exponen ajustes, y la descripción correcta es "cómo está configurado este despliegue". Siguen cuatro ejemplos habituales; consulta la documentación actual de la versión que ejecutas, porque los valores por defecto cambian de una versión a otra.

Elegir la consistencia según el caso de uso

El hábito más útil es dejar de preguntar "¿es consistente nuestro sistema?" y preguntar, para cada dato y cada operación, qué sale mal si un cliente ve un valor obsoleto o reordenado, y cuánto cuesta. El movimiento de dinero, los recursos únicos y los invariantes suelen justificar la consistencia fuerte y su latencia. Los contadores, los feeds, las recomendaciones y la analítica normalmente no. Muchas anomalías que ve el usuario desaparecen solo con las garantías de sesión, que son baratas: dirige las lecturas de un usuario al primario durante unos segundos después de que ese usuario escriba, o lleva un token de versión en la sesión y espera hasta que la réplica se haya puesto al día con él.