Capítulo 9 - Consistencia y Consenso

“Is it better to be alive and wrong or right and dead” Jay Kreps

Consistencia y consenso → Algoritmos y protocolos para construir sistema distribudios tolerantes a fallas

• Se asume que todos los problemas que pueden ocurrir en un sistema distirbuido van a ocurrir
  • Paquetes perdidos, reordenados o duplicados
  • Demoras arbitrarias en la red
  • Relojes desincronizados
  • Puasas de nodos
  • Nodos que se caen
• La mejor forma para construir sistemas distribuidos tolerantes a fallas es mediante abstracciones de proposito general con garantias utiles.
• Consenso
  • def. Garantía de que todos los nodos del sistema van a estar de acuerdo en algo

Garantías de Consistencia

• Aislamiento de transacciones
  • Serializabilidad → prevenir condiciones de carrera
• Consistencia distribuida
  • Linealizabilidad → Coordinar el estado de las replicas en entornos donde hay demoras de red y fallos de nodos

Linealizabilidad (Consistencia atómica)

• La garantía de consistencia más fuerte utlizada comunmente por los sistemas de datos
• def. Dar la ilusión de que en el sistema solo hay “Una copia de los datos”
  • En un sistema linealizable, todas las operaciones leen la versión más reciente de los datos. Se abstrae el hecho de que los datos están distribuidos, dandole la ilusión a los clientes de que los datos están todos almacenados en el mismo sitio.
  • Es una garantía de actualidad
    • El sistema se comporta como si solo existiera una copia de los datos, donde cada operación es atómica. Esto significa que por cada dos operaciones, siempre se puede señalar cual ocurrrió primero.
  • https://stackoverflow.com/questions/9762101/what-is-linearizability

• Contra-Ejemplo → Sistema No Linealizable

  

  • Bob leé datos de una nodo que no ha sido actualizado. El sistema no se comporta como si solo hubiera una copia de los datos.

• Ejemplo - Sistema Linealizable

  

  • Después de que alguna operación de escritura leé el valor actualizado x=1, todas las operaciones que le siguen deben leer el mismo valor.

• Linealizabilidad ≠ Serializabilidad

  • Serializabilidad es una propiedad de aislamiento de las transacciones → Garantiza que las transacciones se van a comportar como si se hubieran ejecutado serialmente, una detrás de otra
  • Linealizabilidad es una propiedad de actualidad en las operaciones de escritura y lectura de un registro de datos. No agrupa las operaciones en transacciones, por eso no previene problemas como las lecturas o escrituras sesgadas.

• Casos de uso para usar Linealizabilidad

  • Candados distribuidos → escoger un nodo para que sea el lider
    • Todos los nodos deben estar de acuerdo en quien es el lider
  • Restricciones y univocidad → Requerimiento para tener un valor único y actualizado donde todos los nodos deben estar de acuerdo
    • Nombres de usuarios unicos
    • No balances negativos
    • No personas reservando el mismo asiento

• Implementación de sistemas linealizables

  • Replicación un solo lider → Linealizable
  • Replicación multilider → No linealizable
    • Varios lideres se deben sincronizar de forma asíncrona
  • Sin lider (Leaderless) → No linealizale
    • La penalidad de linealizarlo es muy alta

El Costo de Linealizar → Teorema CAP

• Caso: Cuando hay una interrupción de red, se debe escoger entre linealizabilidad (consistencia) o disponibilidad. Si los nodos de un sistema no se pueden comunicar y usted quiere que el sistema siga sirviendo tráfico, entonces el sistema no va a ser consistente, pero sí va a estar disponible. Por otro lado, si usted quiere preservar la consistencia, el sistema no va a estar disponible por un tiempo.
  • Cuando se construyen sistemas distribuidos en los que los componentes se conectan mediante una red que no es fiable (IP, Ethernet, etc.), se van a tener problemas de red. Trade-off entre disponibilidad y consistencia → Teorema CAP

• Teorema CAP → Consistency (Linearizability), Availability, Partition tolerance

  • Si una aplicación requiere ser linealizable (consistente) y las réplicas (nodos) se desconectan, se debe esperar a que el error de red se resuelva para poder mantener la consistencia del sistema. Durante ese tiempo, los nodos que no tengan comunicación con el líder no estarán disponibles. Consistencia (Linealizablidad) pero no disponibilidad
  • Si una aplicación NO requiere linealizabilidad y las replicas se desconectan del lider, cada nodo puede seguir procesando datos de forma independiente. Durante ese tiempo, el sistema no va a ser consistente entre sus nodos. No consistencia pero si disponibilidad

  

• CAP

  • Consistencia → No hay datos desactualizados (desincronizados) entre las replicas del sistema. NUNCA
  • Disponibilidad → Los clientes siguen recibiendo respuestas, inclusive si un nodo está fallando
  • Tolerancia a particiones (partition tolerance) → Sistema se mantiene funcional asi ocurran errores de red

• Nota. El término CAP es un poco engañoso. Las particiones (errores) de red no son algo que usted pueda escoger. Si o si van a ocurrir. La forma indicada de plantear el teorema CAP es asi:

  Consistente o disponible **cuando* ocurran particiones de red*

  Cuando hayan particiones de red, usted puede escoger entre mantener disponibilidad del sistema o ser consistente. NO AMBOS

• Nota. Si bien la linealizabilidad es una garantía util, pocos sistemas en la práctica son 100% linealizables. Esto se debe a que la linealizabilidad es costosa en terminos de desempeño. Soportar linealizabilidad hace que el sistema sea más lento.

Garantías de Orden

• Ordenamiento y causalidad → El orden ayuda a preservar la causalidad en un sistema
• La causalidad impone un ordenamiento de eventos
  • Causa viene antes del efecto
  • Ejemplos → Dependencias causales
    • Mensaje se envía antes de que el mensaje se reciba
    • La pregunta viene antes de la respuesta
    • Un nodo lee datos y escribe algo como resultado de la lectura de esos datos
• Si un sistema obedece el ordenamiento impuesto por la causalidad de eventos es causalmente consistente
  • Ej: Aislamiento con snapshot es causalmente consistente
• La linealizabilidad implica causalidad
  • Todo sistema linealizable preserva la causalidad de eventos correctamente
• Para que un sistema sea causalmente consistente, no necesita ser linealizable. Hay formas de lograrlo que no tienen efectos tan negativos en el desempeño como la linealizabilidad pura.
  • Para preservar causalidad, se debe saber que operacion ocurrió antes de cualquier otra operación → orden parcial
  • Las operaciones concurrentes se procesan en cualquier orden, pero si una operación ocurre antes de otra, entonces se debe mantener el orden de procesamiento en el resto de replicas. Para lograr esto, se necesita un mecanismo para describir el conocimiento de un nodo en el sistema.

Formas de capturar dependencias causales

• Ordenamiento secuencial → numeros secuenciales o timestamps para ordenar eventos

  • Estampilla Lamport (Lamport timestamp) → Cada nodo almacena una pareja de (contador, Id Nodo) donde

    • Contador: Número de operaciones que ha procesado
    • Id Nodo: Identificador del nodo que actualizó el objeto

    

    • Las estampillas de tiempo lamport proveen un ordenamiento consistente con causalidad
      • Si tiene dos timestamps, la que tiene el valor de contador más alto es el timestamp más reciente. Si ambas tienen el mismo valor en el contador, la que tiene el NodeId mayor es la más reciente.
    • IMPORTANTE. Las garantía de ordenamiento no son suficientes para satisfacer todos los requerimientos de consistencia en un sistema distribuido, como asegurarse que solo existan usernames ú*nicos en el sistema. Cuando dos usuarios tratan de crear el mismo *username, escoger la operación con menor timestamp solo funciona en retrospectiva. Un nodo no puede decidir inmediatamente si la petición de un username debe ser aceptada, sin antes saber si otro nodo está procesando la misma petición por otro usuario. Verificar que ningun nodo esté procesando la misma operación no es eficiente. Por eso, **el sistema también debe conocer cuando una operación finaliza para asegurarse que ningun otro nodo pueda realizar la misma operación. Esto se conoce como **broadcast de orden total
      • Broadcast de orden total (total order broadcast)

Broadcast de Orden Total (Total Order Broadcast)

• def. Protocolo de comunicación entre nodos de un sistema distribuido para intercambiar mensajes
• También se conoce como broadcast atómico
• El protocolo dicta que estas propiedades siempre se deben satisfacer para la comunicación entre partes del sistema
  • Entrega fiable (reliable delivery) → No hay mensajes perdidos
    • Si un mensaje se entrega a un nodo, se le entrega a todos los nodos
  • Entrega de orden total (totally ordered delivery) → Los mensajes se entregan a cada nodo en el mismo orden

• Nota. El broadcast de orden total es la forma más adecuada de implementar replicación en una base de datos

  Total order broadcast

  

• Broadcast de orden total ≠ Linealizabilidad

  	Broadcast atómico	Linealizabilidad
  ¿Qué es?	Protocolo de comunicación	Modelo de consistencia
  Enfoque	La entrega y ordenamiento de mensajes	Apariencia y orden de operaciones
  Objetivo	Asegurarse que los mensajes se entreguen de cierta forma	Asegurarse que el sistema entero se comporte como si solo existiera una copia de los datos
  Aplicaciones	Mecanismo de bajo nivel para implementar modelos de consistencia como linealizabilidad	Propiedad del sistema como tal

Transacciones Distribuidas y Consenso

• Consenso (definición informal) → Hacer que varios nodos estén de acuerdo en algo
  • No es algo fácil de implementar
• Situaciones donde los nodos de un sistema deben estar de acuerdo
  • Escoger un lider → Todos los nodos deben estar de acuerdo en quien es el lider
  • commit atómico → Todos los nodos deben estar de acuerdo en el resultado de una transacción
    • Problema: Una transacción puede abortarse en un nodo pero ser exitosa en otro nodo
    • Solución: Commit de dos fases (two-phase commit)

Commit de dos fases (two-phase commit - 2PC*)*

• def. algoritmo para lograr transacciones atómicas que involucran multiples nodos
  • Es la forma para implementar commits atómicos en un sistema distribuido
  • Sistema de un solo nodo → Un solo dispositivo controla el exito de un commit. El unico requisito es que la operación se efectue en el log en disco
  • Sistema de multiples nodos → La operación puede abortarse en un nodo pero ser exitosa en otro nodo
    • Un nodo solo puede hacer commit si está seguro que el resto de nodos también puedne hacer commit
• Commit de dos fases → Implementación

• Coordinador → Componente adicional que se encarga de administrar las transacciones
• Pasos
  1. App cliente realiza operación de escritura en varios nodos → Le avisa al coordinador
  2. Coordinador empieza la fase 1 → Enviar petición de prepare a los nodos
     1. Petición de prepare: “Eres capaz de hacer commit?”
     2. Coordinador recibe respuesta de los nodos
  3. Coordinador empieza la fase 2 → commit o rollback
     1. Si todos los nodos respindieron SI en la fase 1 → commit
     2. Si algun nodo respondió NO en la fase 1 → rollback
• Nota. Si un nodo retorna SI en la petición de preparación, debe hacer commit si el coordinador lo solicita en la segunda fase. Si por alguna razón el nodo se cae, el coordinador va a reintentar la operación hasta que se haga commit.
• 2 promesas aseguran la atomicidad del 2PC
  • Si un nodo promete hacer commit en la fase 1, debe si o si hacerlo si el coordinador lo solicita en la fase 2
  • Una vez el coordinador toma una decision, es irrevocable

Transacciones Distirbuidas en la Práctica

• Dos notas importantes sobre las transacciones distribuidas
  1. Ofrecen la garantía de seguridad con el commit de dos fases
  2. Causan problemas operacionales e impactan el desempeño
     1. Ej. Las transacciones distribuidas en MySQL son 10 veces más lentas que las transacciones en un solo nodo
     2. Muchos servicios en la nube deciden no implementar transacciones distribuidas debido a sus implicaciones en desempeño
• 2 tipos de transacciones dsitribudas
  • Internas → Mismo sistema de almacenamiento
    • DBs que usan replicación y particionamiento en su configuración estandar soportan transacciones internas entre los nodos de la BD
  • Heterogeneas → Multiples sistemas de almacenamiento
    • Dos BDs de vendors distintos (MySQL replication)
    • Brokers de mensajería (Kafka)
• Procesameinto de mensajers - Garantía de “Exactly once”
  • Las transacciones distribuidas heterogenas permiten que sistemas diversos se integren de formas muy poderosas
    • Ejemplo: Un mensaje de un broker (Kafka, pubsub) pueder ser reconocido como procesado si y solo si la transacción en la BD transaccional fue commited
  • Protocolo atómico que soporta las transacciones distribuidas en sistemas heterogeneos → Transacciones XA

Transacciones XA

• def. Open XA Transacciones → eXtended Architecture Transactions
  • ¿Qué es? Estandar para implementar 2PC en tecnologías heterogeneas, soportado por muchas BDs relacionales y brokers de mensajería
  • Basicamente es un API para interactuar con un coordinador de transacciones, permitiendo que multiples recursos transaccionales interactuen entre si para participar en una transacción global intersistemas

MySQL :: MySQL 8.4 Reference Manual :: 15.3.8 XA Transactions

• Coordinador → Libreria que se incluye en algun proceso como una aplicación
  • Hace seguimiento de los participantes en las transacciones
  • Recolecta las respuestas de los participantes despues del prepare
  • Utiliza un log en su disco local para llevar registro de los commits y rollbacks
• Las transacciones XA resuelven el problema de mantener varios sistemas de datos consistentes entre si, pero también tienen limitantes
  • Los coordinadores no replicados son puntos únicos de fallo que pueden causar bloqueos a nivel de sistema
  • Muchos coordinadores no soportan alta disponibilidad
  • aplicaciones sin estado pueden escalar facilmente, pero añadir un coordinador las hace stateful
  • Las transacciones XA no puden detectar deadlocks entre varios sistemas

Consenso Tolerante a Fallas

• Consenso → Hacer que multiples nodos estén de acuerdo en algo
  • Si muchas personas tratan de reservar el último puesto en un avión, el algoritmo de consenso debe determinar cuál de estas operaciones mutualmente incompatibles es la ganadora.
• “The Consensus Problem” → Uno o más nodos puede proponer valores, y el algoritmo de consenso decide alguno de esos valores.
• Un algoritmo de consenso debe satisfacer las siguiente propiedades
  • Acuerdo uniforme (Uniform agreement ) → Ningún nodo decide de manera diferente al resto de los nodos
  • Integridad → Ningún nodo decide dos veces
  • Validez → Si un nodo decide el valor V, entonces V fue propuesto por algún otro nodo
  • Terminación → Cada nodo que no se bloquea, eventualmente decide algún valor.
• Broadcast de orden total y consenso: El broadcast de orden total es lo mismo que rondas repetidas de consenso
  • Debido a la propiedad de acuerdo del consenso, todos los nodos deciden entregar los mismos mensajes en el mismo orden
  • Debido a la propiedad de integridad, los mensajes no se duplican
  • Debido a la propiedad de validez, los mensajes no se corrompen ni se crean de la nada
  • Debido a la propiedad de terminación, los mensajes no se pierden
• Algunos algoritmos de consenso
  • Viewstamped Replication → https://medium.com/@polyglot_factotum/understand-viewstamped-replication-with-rust-automerge-and-tla-7a94e9e4d553
  • Raft → https://www.geeksforgeeks.org/raft-consensus-algorithm/
  • Zab → https://medium.com/@adityashete009/the-zab-algorithm-502781c54498

Apache Zookeeper

• https://zookeeper.apache.org/
• def. Herramienta de codigo abierto que provee
  • algoritmo de Consenso
  • Detección de fallos
  • Servicio de membresía

• Herramientas como ZooKeeper: Proporcionan consenso y detección de fallos, evitando la necesidad de desarrollar algoritmos propios.

  Para implementar sistemas dsitribuidos

  • Muchos sistemas comunes utilizan Zookeeper por debajo
    • Apache Kafka
    • HBase
    • Hadoop Yarn
    • Redis

Resumen

• Linealizabilidad → modelo de consistencia con el objetivo de dar la ilusión de que los datos replicados se comporten como si solo existiera una copia de los datos
• Causalidad: Ordena eventos según causa y efecto, permite concurrencia y reduce la sobrecarga de coordinación.
• Consenso → Hacer que todos los nodos de un sistema estén de acuerdo en algo
  • Muchos en la práctica de los sistemas distribuidos se pueden reducir al problema de lograr consenso
  • Commit atómico
    • Una BD debe decidir si le hace commit o abort a una transacción distribuida
  • Broadcast de orden total
    • Un sistema debe deciri en que orden entregar los mensajes a los nodos
  • Restricción de univocidad
    • Cuando varias transacciones concurrentes intentan crear records conflictivos con la misma llave, se debe decidir cuales operaciones permitir y cuales rechazar
  • Registros linealizables
• Base de datos con un solo líder: Proporciona linealizabilidad pero falla si el líder es inaccesible.
  • Opciones para manejar fallos:
    • Esperar la recuperación del líder
    • Conmutación manual por fallos
    • Algoritmo de consenso automático