Algoritmo de consenso Raft (2015)
(raft.github.io)- Raft fue diseñado para hacer más fácil de entender el problema del consenso, donde varios servidores en un sistema distribuido deben tomar la misma decisión, y apunta a una tolerancia a fallas y un rendimiento equivalentes a los de Paxos
- Raft divide su estructura en subproblemas como elección de líder, replicación de logs y seguridad, para dejar claros los puntos de decisión necesarios para implementar una máquina de estados replicada
- Puede seguir avanzando mientras siga viva la mayoría de los servidores, y mantiene la seguridad al detenerse si desaparece la mayoría, sin producir resultados incorrectos
- El sitio reúne RaftScope basado en navegador, la visualización de The Secret Lives of Data, el paper de Raft, la especificación en TLA+, además de papers y charlas sobre verificación y análisis
- Hay implementaciones organizadas en varios lenguajes como Rust, Go, Java, C++, C#, Python y más; cada una difiere en el alcance de soporte para elección de líder y replicación de logs, persistencia, cambios de membresía y compactación de logs
El problema de consenso al que apunta Raft
- Raft fue diseñado para que un público más amplio pueda entender los algoritmos de consenso
- Su objetivo es alcanzar un nivel de tolerancia a fallas y rendimiento equivalente al de Paxos
- La diferencia clave está en la estructura
- Divide el problema en subproblemas relativamente independientes
- Separa y trata por partes los componentes necesarios para implementar sistemas reales
- El objetivo es hacer que los sistemas basados en consenso sean más fáciles de entender y de implementar con mayor calidad
Consenso y máquinas de estados replicadas
- El consenso (consensus) es un problema fundamental en los sistemas distribuidos tolerantes a fallas
- Varios servidores acuerdan un solo valor, y una vez decidido, ese valor se vuelve el estado final
- Un algoritmo de consenso típico avanza cuando está disponible la mayoría de los servidores
- Un clúster de 5 servidores puede seguir funcionando aunque fallen 2
- Si fallan más servidores, el progreso se detiene
- Aun así, es importante que no se devuelvan resultados incorrectos
- El consenso suele usarse para construir una máquina de estados replicada
- Cada servidor tiene una máquina de estados y un log
- La máquina de estados puede ser el componente al que se le quiere dar tolerancia a fallas, como una tabla hash
- Los clientes pueden verlo como si interactuaran con una sola máquina de estados confiable, aunque algunos servidores fallen
- Cada máquina de estados recibe comandos como entrada desde su propio log
- En el ejemplo de la tabla hash, comandos como
set x to 3entran en el log - El algoritmo de consenso decide qué comandos poner en los logs de los servidores y en qué orden
- Si una máquina de estados aplicó
set x to 3como el comando número n, debe garantizarse que otra máquina de estados no aplique un comando distinto en esa misma posición
- En el ejemplo de la tabla hash, comandos como
- Como resultado, todas las máquinas de estados procesan la misma secuencia de comandos y llegan a la misma secuencia de resultados y estados
Visualizaciones para entender Raft
- Se puede manipular directamente una visualización de un clúster Raft que corre en el navegador
- A la izquierda se muestran 5 servidores
- A la derecha se muestran los logs de cada servidor
- El usuario puede interactuar y observar el funcionamiento de Raft
- RaftScope todavía tiene bastante por pulir y recibe con gusto Pull Requests
- The Secret Lives of Data es una visualización distinta de Raft
- Está más guiada y tiene menos interacción
- Puede ser un punto de entrada más amable para quien lo ve por primera vez
Papers, especificaciones y material de verificación
- In Search of an Understandable Consensus Algorithm (Extended Version) es el “paper de Raft” que lo trata en detalle
- Fue escrito por Diego Ongaro y John Ousterhout
- Una versión un poco más corta recibió el Best Paper Award en 2014 USENIX Annual Technical Conference
- La Ph.D. dissertation de Diego Ongaro amplía el contenido del paper con mayor profundidad
- Incluye un algoritmo más simple para cambios de membresía del clúster
- También contiene la especificación formal en TLA+ de Raft
- Una especificación ligeramente actualizada puede verse en raft.tla
- Los papers relacionados tratan la verificación formal de Raft, frameworks para implementar y verificar sistemas distribuidos, generación de código a partir de modelos formales y análisis de protocolos
- Planning for Change in a Formal Verification of the Raft Consensus Protocol, CPP 2016
- Verdi: A Framework for Implementing and Verifying Distributed Systems, PLDI 2015
- Automatic Distributed Code Generation from Formal Models of Asynchronous Concurrent Processes, PDP 2015
- Raft Refloated: Do We Have Consensus?, SIGOPS Operating Systems Review 2015
- ARC: Analysis of Raft Consensus, University of Cambridge Technical Report 2014
Charlas y material educativo
- También se incluye una lista de charlas introductorias sobre Raft
- Charla de John Ousterhout en la CS@Illinois Distinguished Lecture Series, agosto de 2016
- Charla de Jin Li sobre Raft y la especificación en TLA+ dentro de la Dr. TLA+ Series, julio de 2016
- Charlas de Diego Ongaro en Build Stuff 2015, CoreOS Fest 2015, Sourcegraph meetup, LinkedIn, USENIX ATC 2014, CraftConf 2014 y RICON West 2013
- Charla de Ben Johnson en Strange Loop 2013
- Clase de John Ousterhout sobre el Raft User Study, marzo de 2013
- En universidades y cursos también se usa Raft en clases o tareas de programación
- Se incluyen varios cursos de University of Copenhagen, Czech Technical University in Prague, The University of Hong Kong, University of Virginia, UC San Diego, Technical University of Munich, UIUC y más
- Algunos cursos ofrecen tareas de programación de Raft en Go, Java, Erlang y otros lenguajes
- MIT 6.824 incluye notas de clase sobre Raft y también enlaza textos sobre Raft de Jon Gjengset para docentes y estudiantes
- Se pueden actualizar cursos adicionales en el repositorio del sitio mediante Pull Requests o issues
Canal de preguntas y lista de implementaciones
- Para preguntas sobre Raft y sus implementaciones, se indica raft-dev Google group como el lugar adecuado
- Algunas implementaciones tienen su propia mailing list, así que conviene revisar cada README
- También se ofrece una lista de implementaciones de Raft con código fuente público
- Las implementaciones populares o actualizadas recientemente aparecen en la parte superior de la tabla
- La información puede volverse obsoleta con el tiempo y puede actualizarse mediante Pull Requests o issues
- La tabla compara Stars, nombre, autores principales, lenguaje, licencia y soporte de funciones por implementación
- Las funciones comparadas son elección de líder y replicación de logs, persistencia, cambios de membresía y compactación de logs
- Los ejemplos de implementaciones en la parte superior son los siguientes
- TiKV: Rust, Apache-2.0, 16,751★, soporte completo para elección de líder y replicación de logs / persistencia / cambios de membresía / compactación de logs
- RethinkDB: C++, Apache-2.0, 27,000★, soporte completo para las funciones principales
- Seastar Raft: C++20, AGPL, 15,624★, soporte completo para las funciones principales
- hashicorp/raft: Go, MPL-2.0, 9,048★, soporte completo para las funciones principales
- hazelcast-raft: Java, Apache-2.0, 6,579★, soporte completo para las funciones principales
- La lista incluye implementaciones en muchos lenguajes, como Rust, Go, Java, C++, C, Erlang, Python, Scala, C#, JavaScript, Haskell, OCaml, Kotlin, Zig, TypeScript, Elixir, F#, Shell y más
1 comentarios
Opiniones de Hacker News
Maelstrom, el banco de trabajo del creador de Jepsen para aprender sistemas distribuidos, incluye una implementación sencilla de verificación de modelo de Raft y un buen tutorial de implementación: https://github.com/jepsen-io/maelstrom/
Raft es un algoritmo simple, pero el artículo original tiene muchos detalles de corrección que a menudo se omiten en implementaciones de juguete
Si además se consideran la corrupción de memoria/disco y las fallas grises en hardware real, SLA de latencia estrictos, quórums flexibles y membresía dinámica del clúster, una implementación de producción se vuelve un trabajo largo y pesado
Basta ver el historial de commits de etcd y hashicorp/raft para notar que incluso las implementaciones open source de Raft más verificadas revelan regularmente bugs de corrección
El equipo de TigerBeetle trata en detalle la realidad de los sistemas distribuidos con hardware imperfecto y modelos de sistema no abstraídos, y también explica por qué eligieron Viewstamped Replication, que es más antiguo que Paxos pero parece más parecido a Raft: https://github.com/tigerbeetle/tigerbeetle/blob/main/docs/DE...
No sé bien qué implicaciones tenga para las preocupaciones de implementación, pero el paper en sí es excelente y lo recomiendo
También hay una charla, pero creo que el texto es mejor para ir consultando referencias hacia adelante y hacia atrás: https://www.youtube.com/watch?v=0K6kt39wyH0
Aunque nunca había visto algoritmos de consenso, después de leerlo varias veces pude seguirlo hasta cierto punto: https://dspace.mit.edu/bitstream/handle/1721.1/71763/MIT-CSA...
Hace poco implementé la elección de líder y la replicación de logs de Raft; no llegué hasta snapshots/checkpoints, pero fue de los proyectos más difíciles que he hecho hasta ahora
El paper de Raft es fácil de leer y da muy buena intuición
Aunque no lo implementes directamente, es muy probable que ya estés usando software basado en Raft, como etcd, Consul, CockroachDB o TiDB
Reuní aquí los recursos que me fueron útiles al implementarlo: https://github.com/eatonphil/goraft#references
También incluye la tesis doctoral de Diego Ongaro y la especificación en TLA+
Hay quien dice que “con la Figure 2 del paper de Raft basta”, pero comparada con la especificación en TLA+ es mucho más ambigua, así que no creo que sea cierto
Recomiendo conectarlo con los tests de Raft del curso de sistemas distribuidos del MIT: https://pdos.csail.mit.edu/6.824/labs/lab-raft.html
Al menos para elección de líder y replicación de logs parece posible con solo un poco de refactorización
Es especialmente recomendable para alguien que se acerca por primera vez a los algoritmos distribuidos
La calidad de la implementación no será gran cosa, pero la dejo por si a alguien le interesa: https://github.com/skowalak/fastapi-raft/
Dentro del paper hay varios detalles concretos más que se necesitan al implementar
Si te interesan los algoritmos de consenso, también vale la pena ver el libro Reasoning about Knowledge, que usamos en una clase de teoría de sistemas distribuidos: https://mitpress.mit.edu/9780262562003/reasoning-about-knowl...
Requiere invertir un poco para aprender lógica modal, pero una vez superada esa parte, las pruebas de por qué funcionan Raft o Paxos se vuelven muy intuitivas y simples
Es una forma de empujar la complejidad de la demostración hacia la estructura lógica usada en la prueba, y me cambió la manera de ver el consenso
“Raft Consensus Algorithm Failure”, Théodore Géricault, 1819: https://classicprogrammerpaintings.com/post/6141087496359280...
Si no sabes qué está mostrando la visualización, basta con notar que puedes hacer clic en un nodo para provocar una falla
Conviene probarlo especialmente con el nodo que actualmente es el líder, el que envía y recibe todos los paquetes
Si presionas el pequeño ícono de pausa junto al primer deslizador para volver a cambiarlo a reloj, la simulación se reanuda
Todavía no sé qué es la hoja de cálculo de la derecha; siempre está vacía, así que parece rota
Hasta ahora, los elementos clicables que encontré son los dos deslizadores, el ícono de reloj/pausa y cada servidor
Puedes simular el envío de un comando haciendo clic en el líder y eligiendo
requestSi desconectas una réplica, verás cómo se atrasa y luego se pone al día cuando vuelve
Hace unos años estuve en un entorno donde siempre era crítico contar con un sistema tipo Chubby robusto bajo carga intensa, y en ese momento, si no se toleraban fallas, se usaba ZooKeeper
Pero entiendo que hoy la gente lleva años poniendo cargas muy pesadas sobre opciones basadas en Raft como etcd y Consul
Me pregunto si alguna de ellas ya se volvió la opción predeterminada
La claridad conceptual y la elegancia de Raft parecen algo que debería traducirse en rendimiento y confiabilidad, pero mi intuición sobre este campo está desactualizada
Me pregunto qué usan en 2023 como práctica recomendada por defecto para sistemas de alta criticidad quienes no están atados a Google o GCP
Creo que había una implementación de Raft en Rust lista para producción hecha por el equipo de TiKV, y un servidor de locks robusto y de alto rendimiento parece un área que encaja bastante bien con Rust; también me pregunto si realmente se está usando
Si esta es la respuesta a “¿Qué es Raft?”, después de leerla sigo sin saberlo
“Raft es un algoritmo de consenso diseñado para ser fácil de entender. Es equivalente a Paxos en tolerancia a fallas y rendimiento. La diferencia es que está descompuesto en subproblemas relativamente independientes y aborda de forma limpia las partes principales necesarias para sistemas prácticos. Esperamos que Raft ponga el consenso al alcance de un público más amplio, y que ese público pueda construir una mayor variedad de sistemas de alta calidad basados en consenso que los que existen hoy”
Este tipo de cosas no es un problema exclusivo de ellos, pero me parece una lástima que no dediquen más tiempo a explicar bien su propio trabajo
Porque filtra automáticamente a los lectores que no saben qué significa
Para alguien que construye sistemas distribuidos y compara varios algoritmos de consenso, es una explicación simple y clara; si no, probablemente de todos modos no sea un algoritmo relevante para esa persona
En general, los algoritmos de consenso intentan resolver el problema de tener réplicas de un almacén de datos distribuidas entre varios dispositivos físicos y decidir qué hacer cuando algunos dispositivos o conexiones fallan de alguna manera
Se llama “consenso” porque, en una situación de falla, las máquinas tienen que ponerse de acuerdo sobre qué decisión tomar respecto de un fragmento de datos
Por ejemplo, si tres servidores replican la misma base de datos SQL y están en la forma
(A) - (B) - (C), cuando se corta la conexión de red entre C y los otros dos, A y B pueden enterarse de eso y promover a B como nodo principalPero C no sabe qué pasó y puede seguir recibiendo algunas escrituras
Cuando la conexión se restablece, A, B y C tienen que decidir qué hacer ahora
Como B y C recibieron de forma independiente conjuntos de escrituras distintos, los servidores tienen que ponerse de acuerdo sobre cómo tratar los datos
Ese es precisamente el problema que Raft, Paxos y otros intentan resolver de manera consistente y eficiente
Algunos conceptos son demasiado grandes para presentarlos en un solo párrafo a alguien sin ningún conocimiento previo
Aun así, creo que el artículo enlazado es un excelente material introductorio si sigues leyendo
Como investigador de protocolos de consenso, creo que gracias a la investigación sobre blockchain de la última década, el consenso se volvió mucho más fácil de entender
Raft, sobre todo si se incluyen sus partes sutiles, en comparación se lee y se implementa como si estuviera en griego
Si alguien empezara hoy a aprender protocolos de consenso, probablemente le haría empezar por Bitcoin y luego pasar a Paxos, Tendermint y Simplex, y le haría saltarse Raft por completo
Simplex es un artículo que escribí yo, una versión simplificada de PBFT
Raft parece relativamente simple
Me pregunto qué ofrece blockchain que sea más fácil de mantener y más difícil de equivocarse que “elegir un líder y replicar el log”
Me gusta este sitio
Esta página me fue realmente útil cuando aprendí e implementé Raft en una clase de sistemas distribuidos
El artículo en sí también es bastante fácil de leer
Gracias por hacer que Raft sea tan claro
Me pregunto si existen algoritmos de consenso en los que un cambio no tenga que pasar necesariamente por un líder
En muchos sistemas distribuidos también se quiere distribuir el procesamiento de entradas
Uno de ellos es Chord: https://en.m.wikipedia.org/wiki/Chord_(peer-to-peer)
Chord es un anillo P2P en el que los nodos se reparten los valores mediante hashing consistente
La red usa algo llamado “finger table”, que en esencia almacena información de replicación en forma de tabla
La información de esa tabla puede estar equivocada o desactualizada, y el peer al que se accede puede indicarte que vayas a otro peer, normalmente el siguiente nodo o un nodo sucesor, y así continuar hasta encontrar el valor o determinar que no se encuentra
La razón por la que este algoritmo puede usarse sin “líder” es que también funciona simplemente yendo a un nodo y recorriendo todos los nodos de forma lineal
La finger table para acelerar las consultas no es imprescindible
Estos sistemas suelen tener un “líder” por transacción, pero en la operación normal ese rol no se disputa
El coordinador de la transacción se declara a sí mismo como tal, por lo que solo hay elección si el coordinador falla por algún motivo
También pueden existir varios líderes simultáneamente para un dato o una clave específicos
Cassandra está desarrollando actualmente Accord, un protocolo sin líder de esta familia
De hecho, Cassandra ya usa un protocolo sin líder para LWT
Es una variante optimizada del Paxos clásico de consenso único, pero si se declaran simultáneamente transacciones en competencia sobre la misma clave, la sobrecarga es considerable
Si las transacciones abarcan temas independientes, se puede distribuir la carga shardeando el liderazgo
Consiste en asignar rangos del espacio de claves a distintos líderes y ajustar las elecciones para que cada nodo tenga una porción adecuada de liderazgo
Si se quiere operar sin líder, cada escritura puede organizarse, en la práctica, como una elección
Si se trata de transacciones tentativas o transacciones grandes, se puede transmitir la solicitud de transacción a todos los nodos y, si se obtiene un quórum de aceptación, gana y se confirma
Pero si varios nodos intentan transacciones casi al mismo tiempo, llegar a consenso puede tomar mucho tiempo
Si hay muchos nodos y todos tienen transacciones pendientes sobre el mismo tema, elegir un líder y enviar todas las transacciones a través de él es mucho más rápido que establecer un consenso individual para cada transacción
Sin embargo, si el objetivo es distribuir por throughput, un enfoque que solo requiera un líder podría ser más eficiente que el quórum que exige Paxos
Es una suposición
Paxos también es más eficiente si las llamadas van siempre al mismo lugar
Porque así se pueden evitar la contención y las revotaciones
En esencia, cada shard tiene su propio consenso Paxos