Replicación de Máquinas de Estado

La replicación de máquinas de estado hace que un servicio sea tolerante a fallos al ejecutar réplicas deterministas que ejecutan los mismos comandos en el mismo orden, de modo que los supervivientes enmascaran el fallo de otros.

Definition

La replicación de máquinas de estado es una técnica en la que un servicio se modela como una máquina de estado determinista y se replica en varios servidores que aplican la misma secuencia ordenada de comandos del cliente, asegurando que las réplicas no defectuosas permanezcan en estados idénticos y puedan sustituir a las fallidas.

Scope

Este tema cubre el modelo de máquina de estado de un servicio, el requisito de que las réplicas sean deterministas, el uso de difusión de orden total (atómica) o consenso para acordar la secuencia de comandos, y el contraste con la replicación primaria-secundaria (pasiva). También cubre el manejo del no determinismo, la reconfiguración de réplicas y la extensión a réplicas bizantinas.

Core questions

• ¿Por qué las réplicas deben ser deterministas y procesar los comandos en un orden idéntico?
• ¿Cómo se produce el orden de comandos acordado a partir del consenso o la difusión atómica?
• ¿En qué se diferencia la replicación activa (máquina de estado) de la replicación pasiva primaria-secundaria?

Key theories

El enfoque de la máquina de estado

Cualquier servicio determinista puede hacerse tolerante a fallos replicándolo y alimentando a cada réplica con el mismo flujo de comandos ordenado; siempre que fallen menos del número tolerado de réplicas, el servicio sigue siendo correcto y disponible.

Ordenación mediante consenso

El orden total requerido para los comandos es exactamente una difusión atómica, que es equivalente al consenso, por lo que las máquinas de estado replicadas se construyen típicamente sobre un protocolo de consenso como Paxos o Raft.

Replicación bizantina de máquinas de estado

Extender el enfoque para tolerar fallos arbitrarios requiere un acuerdo entre más de dos tercios de las réplicas y la votación de resultados por parte de los clientes, como se realiza en la replicación práctica tolerante a fallos bizantinos.

Clinical relevance

La replicación de máquinas de estado es la forma estándar de construir un servicio de alta disponibilidad y fuertemente consistente; los registros replicados, los servicios de coordinación y muchas bases de datos distribuidas son máquinas de estado impulsadas por un flujo de comandos ordenado por consenso.

History

El artículo de Lamport sobre relojes lógicos esbozó la idea de la máquina de estado replicada en 1978; el tutorial de Schneider de 1990 lo convirtió en el marco canónico para servicios tolerantes a fallos; y el PBFT de Castro y Liskov de 1999 lo extendió al entorno bizantino, una línea que más tarde influyó en los diseños de blockchain.

Debates

Replicación activa versus pasiva

La replicación activa (máquina de estado) ejecuta comandos en todas las réplicas para una conmutación por error rápida, pero desperdicia trabajo y requiere determinismo; la replicación pasiva primaria-secundaria se ejecuta solo en un primario y envía el estado, ahorrando trabajo pero incurriendo en un retraso en la conmutación por error y un único punto de ejecución.

Key figures

• Fred Schneider
• Leslie Lamport
• Miguel Castro
• Barbara Liskov

Seminal works

• schneider1990
• lamport1998
• castro1999

Frequently asked questions

¿Por qué el servicio replicado debe ser determinista?

Si las réplicas pudieran tomar decisiones diferentes con la misma entrada —debido a la aleatoriedad, la temporización o la programación de hilos— sus estados divergirían a pesar de ver comandos idénticos. El determinismo garantiza que el mismo flujo de comandos ordenado produce el mismo estado en todas partes.