Replicación de la máquina de estado

En informática , la replicación de la máquina de estado o el enfoque de la máquina de estado es un método general para implementar un servicio tolerante a fallas mediante la replicación de servidores y la coordinación de las interacciones de los clientes con las réplicas de servidores. El enfoque también proporciona un marco para comprender y diseñar protocolos de administración de replicación. ^[1]

Definición del problema

Servicios distribuidos

El software distribuido a menudo se estructura en términos de clientes y servicios. Cada servicio comprende uno o más servidores y exporta operaciones que los clientes invocan al realizar solicitudes. Aunque el uso de un único servidor centralizado es la forma más sencilla de implementar un servicio, el servicio resultante solo puede ser tan tolerante a fallas como el procesador que ejecuta ese servidor. Si este nivel de tolerancia a fallas es inaceptable, entonces se pueden usar varios servidores que fallan de forma independiente. Por lo general, las réplicas de un solo servidor se ejecutan en procesadores separados de un sistema distribuido y se utilizan protocolos para coordinar las interacciones del cliente con estas réplicas. El aislamiento físico y eléctrico de los procesadores en un sistema distribuido garantiza que las fallas del servidor sean independientes, según sea necesario.

Máquina de estado

Artículo principal: máquina de estados finitos

Para la discusión posterior, una máquina de estados se definirá como la siguiente tupla de valores ^[2] (ver también Mealy machine y Moore Machine ):

• Un conjunto de estados
• Un conjunto de entradas
• Un conjunto de salidas
• Una función de transición (Entrada × Estado → Estado)
• Una función de salida (Entrada × Estado → Salida)
• Un estado distinguido llamado Start.

Una máquina de estado comienza en el estado etiquetado como Inicio. Cada entrada recibida pasa a través de la función de transición y salida para producir un nuevo estado y una salida. El estado se mantiene estable hasta que se recibe una nueva entrada, mientras que la salida se comunica al receptor apropiado.

Esta discusión requiere que una máquina de estados sea determinista : múltiples copias de la misma máquina de estados comienzan en el estado de inicio y, al recibir las mismas entradas en el mismo orden, llegarán al mismo estado habiendo generado las mismas salidas.

Normalmente, los sistemas basados ​​en State Machine Replication restringen voluntariamente sus implementaciones para utilizar máquinas de estado finito para simplificar la recuperación de errores.

Tolerancia a fallas

El determinismo es una característica ideal para proporcionar tolerancia a fallas. Intuitivamente, si existen múltiples copias de un sistema, una falla en una se notará como una diferencia en el Estado o Salida de las demás.

Una pequeña deducción muestra que el número mínimo de copias necesarias para la tolerancia a fallos es tres; uno que tiene una falla y otros dos con los que comparamos Estado y Salida. Dos copias no son suficientes, ya que no hay forma de saber qué copia es la defectuosa.

La deducción adicional muestra que un sistema de tres copias puede admitir como máximo una falla (después de lo cual debe reparar o reemplazar la copia defectuosa). Si fallara más de una de las copias, los tres estados y salidas podrían diferir y no habría forma de elegir cuál es la correcta.

En general, un sistema que admite fallas F debe tener copias 2F + 1 (también llamadas réplicas). ^[3] Las copias adicionales se utilizan como prueba para decidir cuáles de las copias son correctas y cuáles son defectuosas. Los casos especiales pueden mejorar estos límites. ^[4]

Toda esta deducción presupone que las réplicas están experimentando solo fallas independientes aleatorias, como errores de memoria o fallas del disco duro. Las fallas causadas por réplicas que intentan mentir, engañar o coludir también pueden ser manejadas por el Enfoque de máquina de estados, con cambios aislados.

No es necesario que las réplicas fallidas se detengan; pueden continuar funcionando, incluso generando salidas falsas o incorrectas.

Caso especial: Fail-Stop

En teoría, si se garantiza que una réplica fallida se detendrá sin generar salidas, solo se requieren réplicas F + 1 y los clientes pueden aceptar la primera salida generada por el sistema. Ningún sistema existente alcanza este límite, pero a menudo se usa cuando se analizan sistemas construidos sobre una capa tolerante a fallas (dado que la capa tolerante a fallas proporciona semántica de parada de fallas a todas las capas por encima de ella).

Caso especial: fracaso bizantino

Las fallas en las que una réplica envía diferentes valores en diferentes direcciones (por ejemplo, la salida correcta a algunas de sus réplicas compañeras y las salidas incorrectas a otras) se denominan fallas bizantinas . ^{[5] Las} fallas bizantinas pueden ser aleatorias, fallas espúreas o ataques inteligentes maliciosos. Las réplicas 2F + 1, con hashes no criptográficos, son suficientes para sobrevivir a todas las fallas bizantinas no maliciosas (con alta probabilidad). Los ataques maliciosos requieren primitivas criptográficas para lograr 2F + 1 (usando firmas de mensajes), o se pueden aplicar técnicas no criptográficas, pero el número de réplicas debe aumentarse a 3F + 1. ^[5]

El enfoque de la máquina de estado

La explicación intuitiva anterior implica una técnica simple para implementar un servicio tolerante a fallas en términos de una máquina de estado:

1. Coloque copias de la máquina de estado en varios servidores independientes.
2. Reciba solicitudes de clientes, interpretadas como Entradas a la Máquina de Estado.
3. Elija un orden para las entradas.
4. Ejecute las entradas en el orden elegido en cada servidor.
5. Responda a los clientes con la salida de la máquina de estado.
6. Supervise las réplicas para detectar diferencias en el estado o la salida.

El resto de este artículo desarrolla los detalles de esta técnica.

• Los pasos 1 y 2 están fuera del alcance de este artículo.
• El paso 3 es la operación crítica, consulte Pedido de entradas .
• El paso 4 está cubierto por la definición de máquina de estado .
• Paso 5, consulte Pedido de salidas .
• Paso 6, consulte Auditoría y detección de fallas .

El apéndice contiene una discusión sobre las extensiones típicas que se utilizan en los sistemas del mundo real, como el registro , los puntos de control , la reconfiguración y la transferencia de estado .

Pedidos de entradas

El paso crítico en la construcción de un sistema distribuido de Máquinas de Estado es elegir un orden para procesar las Entradas. Dado que todas las réplicas no defectuosas llegarán al mismo estado y salida si se les dan las mismas entradas, es imperativo que las entradas se envíen en un orden equivalente en cada réplica. Se han propuesto muchas soluciones en la literatura. ^{[2] [6] [7] [8] [9]}

Un canal visible es una ruta de comunicación entre dos entidades que participan activamente en el sistema (como clientes y servidores). Ejemplo: cliente a servidor, servidor a servidor

Un canal oculto es una ruta de comunicación que no se revela al sistema. Ejemplo: los canales de cliente a cliente suelen estar ocultos; como usuarios que se comunican por teléfono o un proceso que escribe archivos en el disco que son leídos por otro proceso.

Cuando todas las rutas de comunicación son canales visibles y no existen canales ocultos, se puede inferir un orden global parcial (orden causal ) del patrón de comunicaciones. ^{[8] [10]} Cada servidor puede derivar una orden causal de forma independiente. Las entradas a la máquina de estado se pueden ejecutar en orden causal, lo que garantiza un estado y una salida consistentes para todas las réplicas que no presenten fallas.

En los sistemas abiertos, los canales ocultos son comunes y se debe utilizar una forma de ordenación más débil. Se puede definir un orden de Entradas mediante un protocolo de votación cuyos resultados dependen únicamente de los canales visibles.

El problema de votar por un valor único por un grupo de entidades independientes se llama Consenso . Por extensión, una serie de valores puede elegirse mediante una serie de instancias de consenso. Este problema se vuelve difícil cuando los participantes o su medio de comunicación pueden experimentar fallas. ^[3]

Las entradas pueden ordenarse por su posición en la serie de instancias de consenso ( Orden de consenso ). ^[7] Cada servidor puede derivar una Orden de consenso de forma independiente. Las entradas a la máquina de estados se pueden ejecutar en orden de consenso, lo que garantiza un estado y una salida coherentes para todas las réplicas que no presenten fallas.

Optimización del orden causal y por consenso

En algunos casos, hay información adicional disponible (como relojes en tiempo real). En estos casos, es posible lograr un orden causal o de consenso más eficiente para las Entradas, con un número reducido de mensajes, menos rondas de mensajes o tamaños de mensaje más pequeños. Ver referencias para más detalles ^{[1] [4] [6] [11]}

Hay más optimizaciones disponibles cuando se tiene en cuenta la semántica de las operaciones de la máquina de estados (como las operaciones de lectura frente a escritura). Ver referencias Paxos Generalizados . ^{[2] [12]}

Envío de resultados

Las solicitudes de los clientes se interpretan como entradas a la máquina de estado y se procesan en salidas en el orden apropiado. Cada réplica generará una salida de forma independiente. Las réplicas no defectuosas siempre producirán el mismo resultado. Antes de que se pueda enviar la respuesta del cliente, se deben filtrar las salidas defectuosas. Normalmente, la mayoría de las réplicas devolverán el mismo resultado, y este resultado se envía como respuesta al cliente.

Fallo del sistema

Si no hay una mayoría de réplicas con la misma salida, o si menos de la mayoría de las réplicas devuelve una salida, se ha producido una falla en el sistema. La respuesta del cliente debe ser la única salida: FALLO.

Auditoría y detección de fallas

El compromiso permanente y no planificado de una réplica se denomina Fallo . La prueba del fracaso es difícil de obtener, ya que la réplica puede simplemente tardar en responder, ^[13] o incluso mentir sobre su estado. ^[5]

Las réplicas no defectuosas siempre contendrán el mismo estado y producirán las mismas salidas. Este invariante permite la detección de fallas comparando estados y salidas de todas las réplicas. Normalmente, una réplica con Estado o Salida que difiere de la mayoría de las réplicas se declara defectuosa.

Una implementación común es pasar sumas de comprobación del estado de la réplica actual y las salidas recientes entre los servidores. Un proceso de auditoría en cada servidor reinicia la réplica local si se detecta una desviación. ^[14] No se requiere seguridad criptográfica para las sumas de comprobación.

Es posible que el servidor local esté comprometido o que el proceso de auditoría sea defectuoso y la réplica continúe funcionando incorrectamente. Este caso se maneja de forma segura mediante el filtro de salida descrito anteriormente (consulte Envío de salidas ).

Apéndice: Extensiones

Registro de entrada

En un sistema sin fallas, las entradas pueden descartarse después de ser procesadas por la máquina de estados. Las implementaciones realistas deben compensar los comportamientos transitorios sin fallas del sistema, como la pérdida de mensajes, las particiones de red y los procesadores lentos. ^[14]

Una técnica consiste en almacenar la serie de entradas en un registro. Durante momentos de comportamiento transitorio, las réplicas pueden solicitar copias de una entrada de registro de otra réplica para completar las entradas que faltan. ^[7]

En general, no es necesario que el registro sea persistente (puede guardarse en la memoria). Un registro persistente puede compensar períodos transitorios prolongados o admitir funciones adicionales del sistema, como puntos de control y reconfiguración .

Puntos de control

Si no se marca, un registro crecerá hasta agotar todos los recursos de almacenamiento disponibles. Para un funcionamiento continuo, es necesario olvidar las entradas del registro. En general, una entrada de registro puede olvidarse cuando su contenido ya no es relevante (por ejemplo, si todas las réplicas han procesado una entrada, el conocimiento de la entrada ya no es necesario).

Una técnica común para controlar el tamaño del registro es almacenar un estado duplicado (llamado punto de control ) y luego descartar cualquier entrada del registro que contribuyó al punto de control. Esto ahorra espacio cuando el estado duplicado es más pequeño que el tamaño del registro.

Los puntos de control se pueden agregar a cualquier máquina de estado al admitir una entrada adicional llamada PUNTO DE CONTROL . Cada réplica mantiene un punto de control además del valor de estado actual. Cuando el registro crece, una réplica envía el comando CHECKPOINT como una solicitud de cliente. El sistema se asegurará de que las réplicas no defectuosas procesen este comando en el mismo orden, después de lo cual se descartarán todas las entradas del registro antes del punto de control.

En un sistema con puntos de control, se ignoran las solicitudes de entradas de registro que ocurren antes del punto de control. Las réplicas que no pueden localizar copias de una entrada de registro necesaria son defectuosas y deben volver a unirse al sistema (consulte Reconfiguración ).

Reconfiguración

La reconfiguración permite agregar y eliminar réplicas de un sistema mientras se siguen procesando las solicitudes de los clientes. El mantenimiento planificado y la falla de réplica son ejemplos comunes de reconfiguración. La reconfiguración implica salir y unirse .

Saliendo

Cuando un servidor detecta que su estado o salida es defectuoso (consulte Auditoría y detección de fallas ), puede salir del sistema de manera selectiva. Asimismo, un administrador puede ejecutar manualmente un comando para eliminar una réplica para su mantenimiento.

Se agrega una nueva entrada a la máquina de estado llamada QUIT . ^{[2] [6]} Una réplica envía este comando al sistema como una solicitud de cliente. Todas las réplicas no defectuosas eliminan la réplica que sale del sistema al procesar esta entrada. Durante este tiempo, la réplica puede ignorar todos los mensajes de protocolo. Si la mayoría de las réplicas no defectuosas permanecen, el cierre se realiza correctamente. Si no es así, hay una falla del sistema .

Uniéndose

Después de salir, un servidor fallido puede reiniciarse selectivamente o volver a unirse al sistema. Asimismo, un administrador puede agregar una nueva réplica al grupo para obtener capacidad adicional.

Se agrega una nueva entrada a la máquina de estado llamada JOIN . Una réplica envía este comando al sistema como una solicitud de cliente. Todas las réplicas no defectuosas agregan el nodo de unión al sistema al procesar esta entrada. Una nueva réplica debe estar actualizada en el estado del sistema antes de unirse (consulte Transferencia de estado ).

Transferencia de estado

Cuando se pone a disposición una nueva réplica o se reinicia una réplica antigua, se debe llevar al estado actual antes de procesar las entradas (consulte Unirse ). Lógicamente, esto requiere aplicar todas las entradas desde los inicios del sistema en el orden adecuado.

Las implementaciones típicas provocan un cortocircuito en el flujo lógico al realizar una Transferencia de estado del punto de control más reciente (consulte Puntos de control ). Esto implica copiar directamente el estado de una réplica a otra utilizando un protocolo fuera de banda.

Un puesto de control puede ser grande y requerir un período de transferencia prolongado. Durante este tiempo, se pueden agregar nuevas entradas al registro. Si esto ocurre, la nueva réplica también debe recibir las nuevas entradas y aplicarlas después de recibir el punto de control. Las implementaciones típicas agregan la nueva réplica como un observador al protocolo de pedido antes de comenzar la transferencia de estado, lo que permite que la nueva réplica recopile Entradas durante este período.

Optimización de la transferencia de estado

Las implementaciones comunes reducen los tiempos de transferencia de estado al enviar solo componentes de estado que difieren. Esto requiere conocimiento de los componentes internos de State Machine. Dado que la transferencia de estado suele ser un protocolo fuera de banda, esta suposición no es difícil de lograr.

La compresión es otra característica comúnmente agregada a los protocolos de transferencia de estado, lo que reduce el tamaño de la transferencia total.

Elección de líder (para Paxos)

Paxos ^[7] es un protocolo para resolver el consenso y puede utilizarse como protocolo para implementar la Orden de Consenso.

Paxos requiere un solo líder para garantizar la vitalidad. ^[7] Es decir, una de las réplicas debe permanecer líder el tiempo suficiente para lograr un consenso sobre la próxima operación de la máquina estatal. El comportamiento del sistema no se ve afectado si el líder cambia después de cada instancia, o si el líder cambia varias veces por instancia. El único requisito es que una réplica siga siendo líder el tiempo suficiente para hacer avanzar el sistema.

Resolución de conflictos

En general, un líder es necesario solo cuando hay desacuerdo sobre qué operación realizar, ^[11] y si esas operaciones entran en conflicto de alguna manera (por ejemplo, si no se desplazan al trabajo). ^[12]

Cuando se proponen operaciones en conflicto, el líder actúa como la autoridad única para aclarar las cosas, definiendo un orden para las operaciones, permitiendo que el sistema avance.

Con Paxos, varias réplicas pueden creer que son líderes al mismo tiempo. Esta propiedad hace que la elección de líder para Paxos sea muy simple, y cualquier algoritmo que garantice un 'líder eventual' funcionará.

Antecedentes históricos

Varios investigadores publicaron artículos sobre el enfoque de la máquina de estados replicada a principios de la década de 1980. Anita Borg describió una implementación de un sistema operativo tolerante a fallas basado en máquinas de estado replicadas en un artículo de 1983 "Un sistema de mensajes que soporta tolerancia a fallas" . Leslie Lamport también propuso el enfoque de la máquina de estado, en su artículo de 1984 sobre "Uso del tiempo en lugar del tiempo de espera en sistemas distribuidos" . Fred Schneider elaboró ​​posteriormente el enfoque en su artículo "Implementación de servicios tolerantes a fallas utilizando el enfoque de máquina de estados: un tutorial" .

Ken Birman desarrolló el modelo de sincronía virtual en una serie de artículos publicados entre 1985 y 1987. La referencia principal a este trabajo es "Explotación de la sincronización virtual en sistemas distribuidos" , que describe el Isis Toolkit, un sistema que se utilizó para construir el New York y las Bolsas de Valores de Suiza, el Sistema de Control de Tráfico Aéreo Francés, el Buque de Guerra AEGIS de la Armada de los Estados Unidos y otras aplicaciones.

Un trabajo reciente de Miguel Castro y Barbara Liskov utilizó el enfoque de máquina de estado en lo que ellos llaman una arquitectura de "tolerancia práctica a fallas bizantinas" que replica servicios especialmente sensibles usando una versión del enfoque de máquina de estado original de Lamport, pero con optimizaciones que mejoran sustancialmente el rendimiento.

Más recientemente, también se creó la biblioteca BFT-SMaRt, ^[15] una biblioteca de replicación de máquina de estado bizantina tolerante a fallas de alto rendimiento desarrollada en Java. Esta biblioteca implementa un protocolo muy similar al de PBFT, además de protocolos complementarios que ofrecen transferencia de estado y reconfiguración de hosts sobre la marcha (es decir, operaciones JOIN y LEAVE). BFT-SMaRt es el esfuerzo más reciente para implementar la replicación de la máquina de estado, que aún se mantiene de forma activa.

Raft , un algoritmo basado en consenso, se desarrolló en 2013.

Motivado por PBFT, Tendermint BFT ^[16] se introdujo para redes asíncronas parciales y se utiliza principalmente para cadenas de bloques de prueba de participación.

Referencias

1. Schneider, Fred (1990). "Implementación de servicios tolerantes a fallas utilizando el enfoque de máquina de estados: un tutorial" (PS) . Encuestas de computación ACM . 22 (4): 299–319. CiteSeerX  10.1.1.69.1536 . doi : 10.1145 / 98163.98167 .
2. Lamport, Leslie (1978). "La implementación de sistemas multiproceso distribuidos confiables" . Redes informáticas . 2 (2): 95-114. doi : 10.1016 / 0376-5075 (78) 90045-4 . Consultado el 13 de marzo de 2008 .
3. Lamport, Leslie (2004). "Límites inferiores para el consenso asincrónico" .
4. Lamport, Leslie; Mike Massa (2004). Paxos baratos . Actas de la Conferencia internacional sobre redes y sistemas fiables (DSN 2004) . págs. 307–314. doi : 10.1109 / DSN.2004.1311900 . ISBN 978-0-7695-2052-0.
5. Lamport, Leslie; Robert Shostak; Marshall Pease (julio de 1982). "El problema de los generales bizantinos" . Transacciones ACM sobre lenguajes y sistemas de programación . 4 (3): 382–401. CiteSeerX 10.1.1.64.2312 . doi : 10.1145 / 357172.357176 . Consultado el 2 de febrero de 2007 . 
6. Lamport, Leslie (1984). "Uso de tiempo en lugar de tiempo de espera para sistemas distribuidos tolerantes a fallas" . Transacciones ACM sobre lenguajes y sistemas de programación . 6 (2): 254–280. CiteSeerX 10.1.1.71.1078 . doi : 10.1145 / 2993.2994 . Consultado el 13 de marzo de 2008 . 
7. Lamport, Leslie (mayo de 1998). "El Parlamento a tiempo parcial" . Transacciones ACM en sistemas informáticos . 16 (2): 133-169. doi : 10.1145 / 279227.279229 . Consultado el 2 de febrero de 2007 .
8. Birmano, Kenneth; Thomas Joseph (1987). "Explotación de la sincronía virtual en sistemas distribuidos". Actas del XI Simposio de ACM sobre principios de sistemas operativos (SOSP) . 21 (5): 123. doi : 10.1145 / 37499.37515 . hdl : 1813/6651 .
9. Lampson, Butler (1996). "Cómo construir un sistema de alta disponibilidad utilizando consenso" . Consultado el 13 de marzo de 2008 .
10. Lamport, Leslie (julio de 1978). "Tiempo, relojes y ordenación de eventos en un sistema distribuido" . Comunicaciones de la ACM . 21 (7): 558–565. doi : 10.1145 / 359545.359563 . Consultado el 2 de febrero de 2007 .
11. Lamport, Leslie (2005). "Paxos rápidos" .
12. Lamport, Leslie (2005). "Consenso generalizado y Paxos" .
13. Fischer, Michael J .; Nancy A. Lynch; Michael S. Paterson (1985). "Imposibilidad de consenso distribuido con un proceso defectuoso" . Revista de la Asociación de Maquinaria Informática . 32 (2): 347–382. doi : 10.1145 / 3149.214121 . Consultado el 13 de marzo de 2008 .
14. Chandra, Tushar; Robert Griesemer; Joshua Redstone (2007). Paxos Made Live: una perspectiva de ingeniería (PDF) . PODC '07: 26º Simposio ACM sobre Principios de Computación Distribuida . págs. 398–407. doi : 10.1145 / 1281100.1281103 . ISBN  9781595936165.
15. BFT-SMaRt . Repositorio de Google Code para la biblioteca de replicación BFT-SMaRt.
16. Buchman, E .; Kwon, J .; Milosevic, Z. (2018). "El último chisme sobre el consenso de BFT". arXiv : 1807.04938 [ cs.DC ].

Enlaces externos

• Video de máquinas de estado replicadas en MIT TechTV
• Apache Bookkeeper, un servicio de registro replicado que se puede utilizar para construir máquinas de estado replicadas.