Tolerancia a Fallos en Sistemas Distribuidos

Esta sección introduce los conceptos básicos de tolerancia a fallas en sistemas distribuidos. Se destaca la diferencia entre una falla total en sistemas no distribuidos y las fallas parciales en sistemas distribuidos, donde el objetivo es una recuperación automática sin afectar el rendimiento global. Se definen términos clave como disponibilidad (la capacidad del sistema de estar listo para su uso en cualquier momento), confiabilidad (la capacidad del sistema de ejecutar servicios continuamente sin fallas), seguridad (evitar consecuencias catastróficas ante fallas temporales) y mantenibilidad (la facilidad de reparación ante una falla). Se establece la relación entre falla del sistema, error y falla externa, enfatizando que identificar la 'falla' es importante, aunque no siempre proporciona una solución directa. Se define una falla del sistema como el incumplimiento de los objetivos y la insatisfacción del usuario, mientras que un error es una parte del estado del sistema que produce dicha falla. Los sistemas tolerantes a fallas no evitan las fallas, sino que las controlan, manteniendo la provisión de servicios incluso en su presencia. Se clasifican las fallas externas en transitorias (ocurren una vez y desaparecen) e intermitentes (ocurren, desaparecen, y vuelven a ocurrir).

Se presentan distintos modelos de fallas del sistema. Las fallas por muerte (crash failures) implican la detención del servidor, funcionando correctamente hasta el momento de la falla. Las fallas por omisión (omission failures) se dividen en fallas de recepción y de envío de mensajes, donde el servidor deja de responder a las solicitudes. Las fallas de temporización (timeouts) ocurren cuando la respuesta del servidor excede el tiempo límite. Las fallas de transición de estados describen desviaciones del flujo correcto de control. Finalmente, las fallas arbitrarias o bizantinas se caracterizan por respuestas arbitrarias e impredecibles del servidor. Adicionalmente, se describen otros modelos como las fallas de fallo-detención (fail-stop), que son detectables; las fallas silenciosas, indetectables y confundibles con lentitud; las fallas seguras (fail-safe), con salidas reconocibles como fallas; y nuevamente, las bizantinas, con salidas erróneas que se confunden con salidas correctas. Se mencionan técnicas de detección de fallas como la adición de información (códigos de Hamming, bits de paridad) y la repetición de acciones (modelo de transacciones).

La redundancia se presenta como la técnica más utilizada para enmascarar las fallas. Se menciona la redundancia física (presente en biología, aviones, deportes y circuitos electrónicos) como la más común para proporcionar tolerancia a fallas. Se plantea la pregunta de cuánta replicación es necesaria al usar grupos de procesos, definiendo un sistema k-tolerante a fallas como aquel que continúa funcionando aún con k fallas. Se explican los grupos de procesos y la comunicación en grupo como mecanismos para implementar redundancia. Se detallan dos enfoques de replicación por grupos: el protocolo basado en primario (primary-based o primary-backup), también llamado replicación pasiva, implementado con grupos jerárquicos; y el protocolo de escritura replicada (replicated-write), o replicación activa. Se describen los pasos de la replicación activa: petición (multicast del cliente/proxy), coordinación (multicast atómico y ordenamiento), y la obtención de respuestas por parte del cliente/proxy. Se mencionan las ventajas y desventajas de cada enfoque, con énfasis en la sobrecarga del principal en la replicación pasiva, y la necesidad de algoritmos de elección de coordinador cuando este falla.

El documento clasifica los modelos de fallas en sistemas distribuidos. Se describen las fallas por muerte ('crash failures'), donde el servidor se detiene completamente tras un funcionamiento correcto previo. Las fallas por omisión ('omission failures') se subdividen en fallas de recepción y de envío de mensajes, indicando la incapacidad del servidor para recibir o enviar mensajes. Las fallas de temporización ('timeouts') se producen cuando la respuesta del servidor supera el intervalo de tiempo establecido. También se incluyen fallas en la transición de estados, donde el servidor se desvía del flujo de control correcto. Finalmente, se abordan las fallas arbitrarias o bizantinas, caracterizadas por respuestas erráticas e impredecibles del servidor. Este análisis de diferentes tipos de fallas proporciona una base fundamental para comprender las complejidades de la tolerancia a fallas en sistemas distribuidos, permitiendo la selección de estrategias adecuadas para su mitigación.

Además de las categorías principales, el documento explora otros modelos de fallas. Las fallas de fallo-detención ('fail-stop failures') son detectables, generando una notificación. En contraste, las fallas silenciosas son indetectables y pueden confundirse con un servidor lento. Las fallas seguras ('fail-safe failures') producen salidas que se reconocen como fallas. Nuevamente se describe el modelo de fallas bizantinas, donde la salida errónea del servidor se confunde con una salida correcta. Se proponen estrategias para detectar estas fallas, incluyendo la adición de información redundante, como códigos de Hamming o bits de paridad, y el uso de mecanismos de tiempo, permitiendo la repetición de acciones en caso de necesidad, similar al modelo de transacciones. La comprensión de estas distinciones es crucial para implementar mecanismos de tolerancia a fallas eficaces.

La redundancia se identifica como la técnica más empleada para enmascarar las fallas en sistemas distribuidos. Se menciona la redundancia física como un ejemplo ampliamente utilizado en diferentes campos, como biología, aviación, deportes y electrónica. Se introduce el concepto de 'k-tolerancia a fallas', donde un sistema puede seguir funcionando incluso con la falla de k componentes. La replicación, empleando grupos de procesos y comunicación en grupo, se presenta como un método para lograr la redundancia. Se describe la existencia de dos enfoques principales de replicación: el protocolo basado en primario (o replicación pasiva, primary-backup), implementado con grupos jerárquicos, y el protocolo de escritura replicada (o replicación activa, replicated-write). Cada uno tiene sus particularidades, como la sobrecarga del servidor principal en la replicación pasiva y la necesidad de algoritmos para la elección de un nuevo coordinador en caso de fallo. Se destaca la importancia de la redundancia como estrategia para asegurar la disponibilidad y confiabilidad del sistema.

Se profundiza en las características de la replicación pasiva, resaltando la necesidad de algoritmos de elección de coordinador ante fallos del servidor principal. La replicación activa (escrituras replicadas) se detalla paso a paso: el cliente/proxy envía una petición multicast al grupo; el sistema de comunicación en grupo distribuye la petición mediante un multicast atómico y ordenado; y el cliente/proxy puede procesar la primera respuesta recibida, ignorando las demás. Se enfatizan las características de la replicación activa, permitiendo que el cliente/proxy reciba y procese respuestas de varios servidores. Estos detalles sobre los protocolos de replicación proporcionan una visión más profunda de cómo la redundancia se implementa en la práctica, ofreciendo diferentes alternativas según las necesidades y limitaciones del sistema.

La sección se centra en la recuperación de transacciones, esencial para garantizar la atomicidad incluso ante fallas del servidor. Esto implica asegurar que las transacciones se completen completamente o no se ejecuten en absoluto, manteniendo la consistencia de los datos. Se menciona la necesidad de restaurar los ítems de datos del servidor tras una caída y de reorganizar el archivo de recuperación para mejorar el rendimiento. La atomicidad se explica en términos de durabilidad (los ítems de datos se guardan permanentemente y están disponibles indefinidamente) y atomicidad en las fallas (las transacciones mantienen su atomicidad incluso en presencia de fallas). La recuperación de transacciones es fundamental para la integridad de los datos en un sistema distribuido, evitando inconsistencias que podrían surgir por fallos inesperados.

Se describe el rol del administrador de recuperación, responsable de guardar los ítems de datos en almacenamiento permanente, en un archivo de recuperación, pertenecientes a transacciones comprometidas. Durante el progreso de una transacción, las actualizaciones se aplican a un conjunto privado de versiones tentativas. Cada servidor mantiene un registro de las intenciones de todas sus transacciones activas. El administrador de recuperación es fundamental para asegurar la integridad de los datos tras una falla, gestionando el proceso de restauración de manera eficiente y minimizando las interrupciones del servicio. La organización eficiente del archivo de recuperación es responsabilidad del administrador, buscando la rapidez en el proceso de recuperación y la reducción del uso del espacio.

Las listas de intención y los archivos de recuperación se utilizan para mantener un registro de los ítems de datos accedidos por las transacciones. Las entradas en el archivo de recuperación incluyen el tipo de entrada, una descripción, el ítem de dato y su valor, además del estado de la transacción (ready, wait, commit, abort) y otros valores. La historia de las transacciones se registra en este archivo, donde el orden de las entradas refleja el orden de preparación de las transacciones. El mecanismo de logging utiliza el archivo de recuperación como un log que contiene la historia de todas las transacciones realizadas por un servidor. Conceptualmente, solo se requiere una copia de las versiones comprometidas de todos los ítems de datos para la recuperación. El checkpointing se describe como el proceso de escritura de los valores comprometidos actuales a un nuevo archivo de recuperación, junto con la información de estado de las transacciones y sus listas de intención. Esto ayuda a reducir el número de transacciones a tratar durante la recuperación y a recobrar espacio.

El checkpointing se explica como una estrategia para reducir el tiempo y espacio necesarios en la recuperación, permitiendo la optimización del proceso. Se plantea cuándo realizar un checkpoint: después de una recuperación, antes de una nueva transacción o periódicamente durante la actividad normal del servidor. Como alternativa al logging, se presenta el uso de versiones sombras, organizando el archivo de recuperación mediante un mapa que localiza versiones de los ítems de datos en un almacenamiento de versiones ('version store'). Las entradas del estado de la transacción y las listas de intenciones se guardan en un archivo de estado de transacción. Se plantean preguntas sobre el proceso de recuperación con versiones sombras y los posibles problemas si el servidor falla entre añadir un estado 'committed' y actualizar el mapa. Ambas estrategias, checkpointing y versiones sombras, ofrecen diferentes enfoques para la recuperación eficiente de transacciones, permitiendo la selección de la opción más adecuada para el sistema.

Esta sección introduce la problemática de lograr acuerdos en sistemas distribuidos sujetos a fallas. Se enfatiza que las fallas en estos sistemas pueden afectar las decisiones distribuidas. El objetivo principal de los algoritmos de acuerdo distribuidos es alcanzar un consenso entre los procesos sobrevivientes, considerando tanto fallas silenciosas como fallas bizantinas. Se menciona que estos algoritmos son comunes en diversas situaciones, como el Two Phase Commit, la elección de coordinador, la sincronización y la exclusión mutua. La dificultad radica en la necesidad de asegurar la consistencia y la fiabilidad de las decisiones tomadas por un conjunto de nodos que pueden experimentar fallos individuales o incluso comportamientos maliciosos (fallas bizantinas), lo que implica el diseño de algoritmos robustos y resistentes a estas eventualidades.

Se utiliza la analogía del 'problema de los dos ejércitos' para ilustrar los desafíos de los acuerdos distribuidos. Se analiza la posibilidad de llegar a un acuerdo bajo dos escenarios: con líneas de comunicación confiables y procesos que pueden fallar de manera bizantina (en este caso, un acuerdo es posible); y con procesos confiables pero líneas de comunicación poco fiables (en este escenario, alcanzar un acuerdo resulta imposible). Esta analogía resalta la importancia de la fiabilidad tanto de los procesos individuales como de las comunicaciones entre ellos para garantizar la consecución de un acuerdo distribuido. La situación ilustra la necesidad de mecanismos robustos de comunicación y de algoritmos de consenso que puedan superar las limitaciones impuestas por fallos tanto en los nodos como en la infraestructura.

El documento introduce el 'problema de los generales bizantinos' como un ejemplo clásico de la necesidad de algoritmos de consenso resistentes a fallas bizantinas. Se establece que para soportar este tipo de fallas, se requiere un número específico de generales (3m + 1) y un número limitado de traidores (m) para alcanzar un acuerdo. Este problema destaca la complejidad de lograr un consenso en sistemas donde algunos participantes pueden actuar de manera maliciosa o errática, presentando una salida incorrecta que se asemeja a una salida correcta. Se enfatiza la necesidad de diseñar algoritmos que puedan identificar y tolerar este tipo de comportamiento para asegurar la integridad y la consistencia de las decisiones tomadas en el sistema distribuido.