Paxos y Raft

Paxos y Raft son los dos protocolos de consenso prácticos más influyentes, que proporcionan un acuerdo tolerante a fallos por caídas en un registro replicado que sustenta los sistemas de coordinación del mundo real.

Definition

Paxos y Raft son protocolos basados en quórum que permiten a un conjunto de réplicas acordar una secuencia ordenada de comandos (un registro replicado) a pesar de los fallos por caídas, asegurando que las entradas confirmadas nunca se pierdan o reordenen siempre que la mayoría de las réplicas permanezcan disponibles.

Scope

Este tema cubre la familia Paxos —Paxos de decreto único, Multi-Paxos y sus mejoras de ingeniería— y el protocolo Raft, que reorganiza las mismas garantías en torno a un líder explícito, replicación de registros y cambio de membresía para facilitar la comprensión. Cubre los roles de proponentes/aceptadores y líderes/seguidores, intersección de quórum, elección de líder y términos, coincidencia de registros y las preocupaciones prácticas de las instantáneas y la reconfiguración.

Core questions

• ¿Cómo la intersección de quórum y la numeración de propuestas mantienen a Paxos seguro a través de rondas y cambios de líder?
• ¿Cómo descompone Raft el consenso en elección de líder, replicación de registros y seguridad?
• ¿Qué desafíos de ingeniería surgen al convertir estos protocolos en sistemas de producción?

Key theories

Paxos de decreto único y Multi-Paxos

Paxos llega a un acuerdo sobre un valor a través de fases de preparación y aceptación gobernadas por números de propuesta monotónicos y quórums mayoritarios; Multi-Paxos amortiza la fase de preparación a través de un flujo de decisiones liderado por un líder estable para construir un registro replicado.

Descomposición de Raft

Raft logra la misma seguridad que Paxos al elegir un único líder por término, haciendo que el líder añada entradas que los seguidores replican, y aplicando una propiedad de coincidencia de registros, intercambiando deliberadamente la minimalidad por la comprensibilidad y la facilidad de implementación.

De la especificación al sistema en funcionamiento

La implementación de Paxos en la práctica requiere manejar fallos de disco, arrendamientos de líder, compactación de registros y reconfiguración, detalles a menudo pasados por alto en el algoritmo original pero esenciales para la corrección y el rendimiento.

Clinical relevance

Paxos y Raft se ejecutan dentro de servicios de coordinación, bases de datos distribuidas y almacenes de configuración ampliamente utilizados; comprenderlos es esencial para construir u operar cualquier sistema que deba mantener las réplicas fuertemente consistentes a través de fallos.

History

Lamport describió Paxos en su artículo de 1998 'part-time parliament' y lo clarificó en 'Paxos made simple' (2001); Chandra y sus colegas informaron sobre las realidades de hacerlo funcionar a escala en 2007; y Ongaro y Ousterhout introdujeron Raft en 2014 para hacer que las garantías equivalentes fueran mucho más fáciles de enseñar e implementar.

Debates

Comprensibilidad versus minimalidad en los protocolos de consenso

Raft fue diseñado explícitamente para ser más fácil de entender que Paxos, lo que provocó un debate sobre si su estructura adicional (un líder fuerte) sacrifica la flexibilidad; los defensores argumentan que la comprensibilidad reduce los errores de implementación, mientras que otros señalan que las variantes de Paxos pueden ser más generales.

Key figures

• Leslie Lamport
• Diego Ongaro
• John Ousterhout
• Tushar Chandra

Seminal works

• lamport1998
• ongaro2014
• chandra2007

Frequently asked questions

¿Son Paxos y Raft algoritmos fundamentalmente diferentes?

No, resuelven el mismo problema con el mismo núcleo de quórum mayoritario y garantías de seguridad equivalentes. Raft principalmente reorganiza Paxos en torno a un líder fuerte y un registro explícito para hacer que el protocolo sea más fácil de entender e implementar.