Open guilleiguaran opened 5 years ago
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.
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.
La linearizability es útil en los siguientes escenarios:
Cross-channel timing dependencies: Ideal para evitar race conditions entre 2 servicios que van por diferentes canales de comunicación
Los métodos de réplica más comunes son:
Liderless replication: Probablemente no linearizable
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).
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.
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)
La diferencia entre ordenamiento total y parcial se ve reflejada así:
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.
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.
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.
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)
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.
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.
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.
Se describe como un protocolo de intercambio de mensajes, y requiere que se cumpla:
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.
A pesar que linearizability no es lo mismo que el order broadcast el primero se puede implementar por encima del segundo:
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.
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:
Atomicidad (atomicity) es la que previene que, si una transacción falla, algunas escrituras en esta queden en la DB, y otras no.
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.
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.
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.
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.
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
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.
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.
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
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.
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.
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
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.
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
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.
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.
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
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
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.
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.
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.
Traté de hacerlo lo más resumido posible, pero el capítulo es bastante extenso 😫
Esta semana a cargo: @orendon Siguiente semana: @samuskitchen