Designing Data-Intensive Applications: 9. Consistency and Consensus

[guilleiguaran]

Esta semana a cargo: @orendon
Siguiente semana: @samuskitchen

[calbertora]

Consistency and Consensus

Consistency Guarantees

Como hemos visto antes, si consultamos 2 nodos al mismo tiempo, es muy probable ver diferencias en los datos debido a que los nodos se actualizan a diferentes velocidades. Este tipo de inconsistencias pueden ocurrir independientemente del método de réplica que usemos.

La mayoría de bases de datos replicadas proveen al menos la consistencia eventual (eventual consistency). Esto quiere decir que, si escribimos un dato y esperamos una cantidad X de tiempo, este estará en todas las réplicas eventualmente.

Cuando se trabaja con este tipo de garantía (week guarantees) se debe estar consciente de sus limitaciones, puesto que los errores que pueden ocasionar son muy difíciles de detectar y de replicar.

Linearizability

La idea detrás de la Linearizability es dar la ilusión de tener una sola réplica y evitar preocuparse por el lag (replication lag)

Un sistema tiene lilnearizability si cualquier nodo que consulte los datos siempre muestre la misma data de los demás
incluso si la escritura se está dando concurrentemente.

Relying on Linearizability

La linearizability es útil en los siguientes escenarios:

• Locking and leader election: Una manera de elegir un nodo líder es haciendo un bloqueo (locking). Este bloqueo debe ser linearizable o de lo contrario seria inútil (ZooKeeper, etcd, Oracle Real Application Clusters {RAC})
• Constraints and uniqueness guarantees: Restricciones de llaves únicas como por ejemplos usernames, evitar que 2 usuarios accedan a una misma ruta o restricciones de una cuenta bancaria que nunca pueda ser 0.
• Cross-channel timing dependencies: Ideal para evitar race conditions entre 2 servicios que van por diferentes canales de comunicación

Implementing Linearizable Systems

Los métodos de réplica más comunes son:

• Single-leader replication: Potencialmente linearizable
• Consensus algorithms: Este es linearizable
• Multi-leader replication: No linearizable
• Liderless replication: Probablemente no linearizable

The Cost of Linearizability

Aplicar linearizability en un sistema trae consigo varios trade offs, por ejemplo, todos los sistemas que soportan linearizability son lentos. Otro problema es que, según el Teorema de CAP, si hay fallas en la red, el sistema no tendrá disponibilidad (para que haya linearizability el sistema debe estar conectado entre sus nodos).

Ordering Guarantees

Como se vio previamente en la linearizability, el sistema funciona como si sólo hubiese una sola copia de los datos, lo que requiere que cada operación sea ejecutada en cierto orden. Aquí veremos la conección entre ordering, linearizability y consensus.

Ordering and Causality.

La razón por la cual se habla tanto de ordenamiento (ordering) es porque este preserva la causalidad (causality). Como por ejemplo los casos que se han visto previamente en el libro (un registro que intenta actualizar antes de su creación, un correo que llega antes de ser enviado etc etc)

The causal order is not a total order

La diferencia entre ordenamiento total y parcial se ve reflejada así:

• Linearizability: En un sistema linearizable tenemos un orden total de las operaciones, por lo tanto tiene ordenamiento total
• Causality: Dos operaciones ocurren concurrentemente y están ordenados si uno es causal del otro, pero no tenemos manera de compararlos. Por lo tanto son parcialmente ordenados.

Linearizability is stronger than causal consistency

Como se ha visto, la linearizability es la manera en que se conserva la causalidad. Desafortunadamente esto implica un daño en el performance y la disponibilidad. Sin embargo, no es la única forma de lograr la causalidad.

El causal consistency es el modelo de consistencia más fuerte que permite que no se afecte el performance sino que mantiene la disponibilidad incluso cuando hay problemas de red.

Capturing causal dependencies

Con el fin de mantener la causalidad, se necesita saber que operación ocurre antes o después de otra. De esta manera podremos saber el orden en el que fueron generadas las operaciones.

Sequence Number Ordering

A pesar que la causalidad es un concepto importante, se vuelve inconveniente mantener la traza de todas las dependencias. Sin embargo, hay una manera de hacer track de las transacciones usando timestamps (un algoritmo usado para generar secuencias de números para identificar operaciones)

Noncausal sequence number generators

Para sistemas multi-leader y leaderless se pueden usar estrategias para generar secuencias (reloj físico del nodo, numeraciones por nodo etc etc). Y a pesar que estas se desemepeñan mejor y son más escalables que en un single-leader es bastante complejo sincronizar las operaciones entre nodos.

Lamport timestamps

Los Lamport timestamps creado por Leslie Lamport, es un método para crear causalidad entre nodos, donde el timestamp (secuencia) se generada a partir de un consecutivo y un consecutivo de nodo. Así, cada cliente lee la última secuencia, la incrementa y la envía al servidor nuevamente, generando un ordenamiento entre operaciones.

Timestamp ordering is not sufficient

Con el fin de implementar algo como restricciones de llave únicas, un ordenamiento total no es suficiente, porque otro nodo puede estar procesando la misma llave al mismo tiempo. También es necesario saber qué es lo que están haciendo los otros nodos.

Total Order Broadcast

Se describe como un protocolo de intercambio de mensajes, y requiere que se cumpla:

• Ningún mensaje se debe perder
• Todos los mensajes se entreguen a todos los nodos en el mismo orden

Using order broadcast

Es la forma de llevar un mensaje a todos los nodos. En donde cada mensaje representa una escritura en la DB, por lo tanto todos los mensajes irán ordenados y se replicarán en cada nodo en el mismo orden.

Implementing linearizable storage using total order broadcast

A pesar que linearizability no es lo mismo que el order broadcast el primero se puede implementar por encima del segundo:

• Se agrega un mensaje a la cola
• Se espera que el mensaje se entregue y se regrese nuevamente la respuesta
• Se valida en el resto de mensajes qué otros intentan escribir el mismo dato, en caso de ser así, se abortan el resto de mensajes.

Implementing total order broadcast using linearizable storage

Para cada mensaje se usa un consecutivo entero que se adjunta al mensaje, y luego se envía a todos los nodos. Así, si un nodo envía un mensaje 4, y recibe una secuencia 6, sabe que debe esperar por el 5 para proceder.

Distributed Transactions and Consensus

A pesar que, a simple vista, el consenso suena bastante fácil (lograr que todos los nodos lleguen a un acuerdo), muchos sistemas fallan porque esto no es algo tan fácil de lograr.

Algunas de las situaciones en las que es importante un acuerdo entre nodos son:

• Elección de un líder
• Commit atómico.

Atomic Commit and Two Phase Commit (2PC)

Atomicidad (atomicity) es la que previene que, si una transacción falla, algunas escrituras en esta queden en la DB, y otras no.

From single-node to distributed atomic commit

Cuando en un sistema Single-Node se hace commit, quiere decir que la data que se quiere guardar ya queda en disco. Incluso si hay un crash en la DB estos datos se hacen durables y podrán ser leídos después de recuperar la DB.
En un sistema de múltiples nodos, no es tan sencillo hacer un commit, ya que una transacción puede tener escrituras en diferentes nodos, entonces se requiere que todos los nodos confirmen la transacción. Si unos nodos hacen commit pero otros no, no es posible reversar la transacción, ya que el commit es una operación sin marcha atrás, por lo que nuestros datos no serán confiables.

Introduction to two-phase commit

El 2PC, es un algoritmo para lograr el transacciones atómicas entre varios nodos, y así asegurar que todos los nodos hacen commit o todos abortan la transacción.

El algoritmo se apoya en un coordinador (coordinator) o controlador de transacciones (transaction manager). La transacción se envía a todos los nodos, una vez todos están listos para escribir empieza la fase 1, el coordinador envía un prepare request a todos los nodos, y cuando todos contestan yes, entonces envía un commit request. Si alguno contesta no, entonces se envía un abort.

A system promises

Lo más importante del algoritmo es que, cuando un nodo responde sí al prepare request, este debe asegurar que realmente está listo (incluso si hay timeouts, o crashes etc etc). Y que, incluso cuando el coordinador envíe el commit request, y un nodo no responda, este siga intentando las veces que sea necesario hasta que se complete la transacción.

Coordinator failure

La única forma de operar cuando hay una falla en el coordinador es, justamente esperar a que este se encuentre arriba nuevamente.

El coordinador escribe en disco sus operaciones, por lo que, cuando se recupere puede continuar donde estaba.

Three-phase commit

El 2PC se conoce como blocking atomic commit protocol.
El 3PC es un non blocking, pero se debe asumir que los tiempos de respuesta a nodos está dentro de unos límites, al igual que las pausas en los tiempos. Es por esto que a hoy el más usado es el 2PC

Distributed Transactions in Practice

Las transacciones distribuidas tienen reputación mezclada, por un lado, en teoría hay una seguridad en cuanto a la transaccionalidad, pero por otro lado impactan el rendimiento del sistema. Por lo tanto, mucha gente sugiere no usarlo.

Exactly-once message processing

Las transacciones distribuidas heterogéneas son las que permiten integrar diferentes DB de diferentes vendors. Es posible integrarlas por medio de una cola de mensajes, en donde el mensaje (transacción) se considera finalizado si la DB encargada hace commit de manera satisfactoria. Si el envío del mensaje, o la transacción falla, el mensaje se aborta.

XA transactions

Es un estándar para implementar 2PC en tecnologías heterogéneas. Generalmente es una librería que usa el XA API, la cual, tiene la funcionalidad del coordinador como se vio en el 2PC

Holding locks while in doubt

El bloqueo de una transacción en un nodo debe permanecer hasta alguna instrucción por parte del coordinador. Si el coordinador se queda bloqueado 20 min, el o los nodos se quedarán con el bloqueo esos 20 min, incluso indefinidamente hasta alguna intervención manual.

Recovering from coordinator failure

Algunas instrucciones por parte del coordinador pueden quedar en el limbo, incluso luego que el coordinador restablezca su funcionamiento luego de un fallo. Dichas instrucciones deben ser corregidas manualmente por el administrador del sistema.

Limitations of distributed transactions

XA tiene muchas limitaciones
Al guardar los logs de las transacciones (para recuperarse luego de una caída) funciona como una DB per se
Al funcionar como una DB, lo ideal sería que tuviera varios nodos también, de lo contrario, solo se tendría un único punto de quiebre para todo el sistema

Fault Tolerant Consensus

En términos informales, el consenso es cuando se logra que los nodos lleguen a un acuerdo sobre algo.

Un algoritmo de consenso debe cumplir las siguientes propiedades
Uniform agreement: ningún nodo decide diferente de otro
Integrity: Ningún nodo decide 2 veces
Validity: Un consenso sobre un valor v, quiere decir que algún nodo propuso ese valor
Termination: El algoritmo no se puede quedar esperando a que un nodo caído se recupere.

Consensus algorithms and total order broadcast

Los mejores algoritmos de consenso son Viewstamped Replication, Paxos, Raft y Zab. Todos tienen varias similitudes.

La mayoría no usa las anteriores propiedades. En cambio de eso, usan una secuencia de valores que los convierte en algoritmos de total order broadcast

Single-leader replication and consensus

Si se analiza más profundamente, elegir un líder en un sistema single leader se necesita de un consenso.

Todos los nodos deben elegir quién será el líder.

Epoch numbering and quorums

Que un nodo piense que es el líder, no lo hace el líder. La mayoría de algoritmos de consenso usan algo llamado un epoch number. Es algo como un baloto donde el que tenga el número epoch más grande gana. Por eso cuando un nodo gana ser el líder, debe cerciorarse que no hayan nodos con un epoch mayor.

Así pues, dicha revisión se hace en 2 ocasiones. La primera para elegir al líder y la segunda, para validar que efectivamente el mensaje que envía el líder no tiene un epoch menor a otro nodo.

Limitations of consensus

La manera en que los nodos votan los mensajes hace que el algoritmo funcione de manera síncrona

Al ser algoritmos de mayoría estricta, el mínimo de nodos para funcionar es 3.
Algunos algoritmos dictan que el número de nodos es fijo, por lo que no se puede ni agregar ni quitar nodos

Generalmente los sistemas con consenso detectan fallas por medio de timeouts, lo que podría ocasionar falsos positivos en nodos separados geográficamente

Membership and Coordination Services

Servicios como ZooKeeper o etcd son conocidos como "servicios de coordinación y configuración".

Básicamente funcionan como una DB para guardar pequeñas cantidades de datos, que puede ser replicada entre muchos nodos. Funcionan además implementado algoritmos de total order broadcast

Además tienen características muy interesantes como:
Linearizable atomic operations: Si varios nodos tratan de modificar un dato concurrentemente, solo uno de ellos podrá hacerlo.
Total Ordering of operations: Ordena todas las operaciones y les asigna un transaction ID y un version number
Failure detection: ZooKeeper tiene la capacidad de detectar cuando un nodo genera un timeout y decretar el nodo como caído.
Change notifications: Es posible que los clientes conectados a ZooKeeper vean que otros clientes se conectan y se desconectan por medio de notificaciones

Allocating work to nodes

ZooKeeper es de mucha ayuda redistribuyendo trabajo cuando un nodo se cae, o cuando por el contrario ingresa otro nodo al servicio, haciendo eso de manera automática.

Los datos que guarda ZooKeeper no deben cambiar mucho, por lo que, no está pensado para guardar todo el estado de la aplicación.

Service discovery

Generalmente estos servicios son usados también como service discovery. Esto es, como una especie de DNS donde encuentra a qué IP se debe conectar para alcanzar cierto servicio.

Membership services

ZooKeeper y etcd generalmente son usados también como membership services, los cuales determinan qué nodos están activos y qué nodos están muertos.

[calbertora]

Traté de hacerlo lo más resumido posible, pero el capítulo es bastante extenso 😫