replicación de máquina de estados

En cuanto a clientes y servicios, cada servicio consta de uno o más servidores y exporta operaciones que los clientes invocan mediante solicitudes. Si bien usar un único servidor centralizado es la forma más sencilla de implementar un servicio, su tolerancia a fallos depende del procesador que lo ejecuta. Si este nivel de tolerancia a fallos resulta inaceptable, se pueden utilizar varios servidores que fallen de forma independiente. Generalmente, las réplicas de un único servidor se ejecutan en procesadores separados de un sistema distribuido, y se utilizan protocolos para coordinar las interacciones de los clientes con estas réplicas.

Para la discusión subsiguiente, una máquina de estados se definirá como la siguiente tupla de valores ^{[ 2 ]} (Véase también máquina de Mealy y máquina de Moore ):

• Un conjunto de Estados
• Un conjunto de entradas
• Un conjunto de resultados
• 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 estados comienza en el estado denominado "Inicio". Cada entrada recibida pasa por la función de transición y salida para generar 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 correspondiente.

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 inicial y, al recibir las mismas entradas en el mismo orden, llegarán al mismo estado habiendo generado las mismas salidas.

Por lo general, los sistemas basados ​​en la replicación de máquinas de estados restringen voluntariamente sus implementaciones al uso de máquinas de estados finitos para simplificar la recuperación de errores.

El determinismo es una característica ideal para garantizar la tolerancia a fallos. Intuitivamente, si existen varias copias de un sistema, un fallo en una de ellas se manifestaría como una diferencia en el estado o la salida con respecto a las demás.

El número mínimo de copias necesarias para la tolerancia a fallos es tres: una con el fallo y otras dos con las que se comparan el estado y la salida. Dos copias no son suficientes, ya que no hay forma de determinar cuál es la defectuosa.

Un sistema de tres copias puede soportar como máximo un fallo (tras el cual debe reparar o reemplazar la copia defectuosa). Si fallara más de una copia, los tres estados y resultados podrían ser diferentes, y sería imposible determinar cuál es el correcto.

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

Todo este razonamiento presupone que las réplicas experimentan únicamente fallos aleatorios e independientes, como errores de memoria o fallos del disco duro. Los fallos causados ​​por réplicas que intentan mentir, engañar o confabularse también pueden ser gestionados mediante el enfoque de máquina de estados, con cambios aislados.

Las réplicas que fallen no tienen por qué detenerse; pueden seguir funcionando, incluso generando resultados erróneos o incorrectos.

El paso crítico en la construcción de un sistema distribuido de máquinas de estados es elegir el orden en que se procesarán las entradas. Dado que todas las réplicas sin fallos llegarán al mismo estado y salida si reciben las mismas entradas, es imperativo que estas se envíen en un orden equivalente en cada réplica. Se han propuesto numerosas soluciones en la literatura. ^{[ 2 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ]}

Un canal visible es una vía 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. Por ejemplo, los canales entre clientes suelen estar ocultos, como la comunicación telefónica entre usuarios o la escritura de archivos en un disco por parte de 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 ) a partir del patrón de comunicaciones. ^{[ 8 ] [ 10 ]} Cada servidor puede derivar el Orden Causal de forma independiente. Las entradas a la máquina de estados se pueden ejecutar en Orden Causal, lo que garantiza un estado y una salida consistentes para todas las réplicas que no presenten fallos.

En los sistemas abiertos, los canales ocultos son comunes y se debe utilizar una forma de ordenación menos estricta. El orden de las entradas se puede definir mediante un protocolo de votación cuyos resultados dependen únicamente de los canales visibles.

El problema de la votación por un único valor por parte de un grupo de entidades independientes se denomina Consenso . Por extensión, una serie de valores pueden ser elegidos por una serie de instancias de consenso. Este problema se complica cuando los participantes o su medio de comunicación pueden sufrir fallos. ^{[ 3 ]}

Las entradas pueden ordenarse según su posición en la serie de instancias de consenso ( Orden de Consenso ). ^{[ 7 ]} Cada servidor puede derivar el Orden de Consenso de forma independiente. Las entradas a la Máquina de Estados pueden ejecutarse en Orden de Consenso, lo que garantiza un Estado y una Salida consistentes para todas las réplicas que no presenten fallos.

Optimización del ordenamiento causal y por consenso

En algunos casos, se dispone de información adicional (como relojes en tiempo real). En estos casos, es posible lograr un ordenamiento causal o de consenso más eficiente para las entradas, con un número reducido de mensajes, menos rondas de mensajes o mensajes de menor tamaño. Consulte las referencias para obtener más detalles ^{[ 1 ] [ 4 ] [ 6 ] [ 11 ].}

Se pueden realizar optimizaciones adicionales al considerar la semántica de las operaciones de la máquina de estados (como las operaciones de lectura frente a las de escritura). Véanse las referencias Paxos generalizado . ^{[ 2 ] [ 12 ]}

Si bien el SMR clásico suele imponer un orden total de las solicitudes, investigaciones recientes sobre libros de contabilidad distribuidos fragmentados demuestran que un orden parcial es suficiente para la consistencia cuando las transacciones no entran en conflicto. Los modelos de dependencia basados ​​en grafos, como los utilizados en el protocolo Cerberus, permiten que las transiciones de estado sin conflicto se produzcan en paralelo en diferentes réplicas, superando las limitaciones de rendimiento de un único registro lineal. ^{[ 13 ]}

Las solicitudes del cliente se interpretan como entradas para la máquina de estados y se procesan para generar salidas en el orden adecuado. Cada réplica genera una salida de forma independiente. Las réplicas que no presentan fallos siempre producen la misma salida. Antes de enviar la respuesta al cliente, se deben filtrar las salidas defectuosas. Normalmente, la mayoría de las réplicas devuelven la misma salida, que se envía como respuesta al cliente.

Si no existe una mayoría de réplicas con la misma salida, o si menos de la mayoría de las réplicas devuelven una salida, se ha producido un fallo del sistema. La respuesta del cliente debe ser la única salida: FALLO.

El fallo permanente e imprevisto de una réplica se denomina fallo . Es difícil obtener pruebas de fallo, ya que la réplica puede simplemente tardar en responder ^{[ 14 ]} o incluso mentir sobre su estado ^{[ 5 ] .}

Las réplicas sin fallos siempre tendrán el mismo estado y producirán las mismas salidas. Esta invariante permite detectar fallos comparando los estados y las salidas de todas las réplicas. Normalmente, una réplica cuyo estado o salida difiere de la mayoría de las réplicas se considera defectuosa.

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

It is possible that the local server is compromised, or that the Audit process is faulty, and the replica continues to operate incorrectly. This case is handled safely by the Output filter described previously (see Sending Outputs).

In a system with no failures, the Inputs may be discarded after being processed by the State Machine. Realistic deployments must compensate for transient non-failure behaviors of the system such as message loss, network partitions, and slow processors.^[15]

One technique is to store the series of Inputs in a log. During times of transient behavior, replicas may request copies of a log entry from another replica in order to fill in missing Inputs.^[7]

In general the log is not required to be persistent (it may be held in memory). A persistent log may compensate for extended transient periods, or support additional system features such as Checkpoints, and Reconfiguration.

If left unchecked a log will grow until it exhausts all available storage resources. For continued operation, it is necessary to forget log entries. In general a log entry may be forgotten when its contents are no longer relevant (for instance if all replicas have processed an Input, the knowledge of the Input is no longer needed).

A common technique to control log size is store a duplicate State (called a Checkpoint), then discard any log entries which contributed to the checkpoint. This saves space when the duplicated State is smaller than the size of the log.

Checkpoints may be added to any State Machine by supporting an additional Input called CHECKPOINT. Each replica maintains a checkpoint in addition to the current State value. When the log grows large, a replica submits the CHECKPOINT command just like a client request. The system will ensure non-faulty replicas process this command in the same order, after which all log entries before the checkpoint may be discarded.

In a system with checkpoints, requests for log entries occurring before the checkpoint are ignored. Replicas which cannot locate copies of a needed log entry are faulty and must re-join the system (see Reconfiguration).

Reconfiguration allows replicas to be added and removed from a system while client requests continue to be processed. Planned maintenance and replica failure are common examples of reconfiguration. Reconfiguration involves Quitting and Joining.

Cuando un servidor detecta que su estado o salida es defectuoso (véase Auditoría y detección de fallos ), puede salir selectivamente del sistema. Del mismo modo, 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 estados llamada QUIT . ^{[ 2 ] [ 6 ]} Una réplica envía este comando al sistema como una solicitud de cliente. Todas las réplicas que no presentan fallas eliminan la réplica que se retira del sistema al procesar esta entrada. Durante este tiempo, la réplica puede ignorar todos los mensajes del protocolo. Si queda una mayoría de réplicas que no presentan fallas, la salida es exitosa. De lo contrario, se produce una falla del sistema .

Tras su desconexión, un servidor que ha fallado puede reiniciarse selectivamente o volver a unirse al sistema. Asimismo, un administrador puede añadir una nueva réplica al grupo para aumentar la capacidad.

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

Cuando se dispone de una nueva réplica o se reinicia una antigua, debe actualizarse al estado actual antes de procesar las entradas (véase la sección «Unión »). Lógicamente, esto requiere aplicar todas las entradas desde el inicio del sistema en el orden adecuado.

Las implementaciones típicas interrumpen el flujo lógico mediante una transferencia de estado del punto de control más reciente (véase Puntos de control ). Esto implica copiar directamente el estado de una réplica a otra mediante un protocolo fuera de banda.

Un punto de control puede ser extenso, lo que requiere 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 una vez recibido el punto de control. En las implementaciones típicas, se agrega la nueva réplica como observadora al protocolo de ordenación antes de iniciar la transferencia de estado, lo que permite que la nueva réplica recopile entradas durante este período.

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

Paxos requiere un único líder para garantizar la vivacidad. ^{[ 7 ]} Es decir, una de las réplicas debe permanecer como líder el tiempo suficiente para lograr el consenso sobre la siguiente operación de la máquina de estados. El comportamiento del sistema no se ve afectado si el líder cambia después de cada instancia, o si cambia varias veces por instancia. El único requisito es que una réplica permanezca como líder el tiempo suficiente para que el sistema avance.