TP2 - Raft

Introducción

Este es el primero de una serie de trabajos prácticos en los que construirán un sistema de almacenamiento clave/valor tolerante a fallos. En este TP implementarán Raft, un protocolo de máquina de estados replicada. En el siguiente TP construirán un servicio clave/valor sobre Raft.

Un servicio replicado logra tolerancia a fallos almacenando copias completas de su estado (es decir, sus datos) en múltiples servidores réplica. La replicación permite que el servicio siga operando incluso si algunos de sus servidores sufren fallas (caídas o problemas de red). El desafío es que las fallas pueden causar que las réplicas mantengan copias diferentes de los datos.

Raft organiza las solicitudes de los clientes en una secuencia llamada log, y asegura que todos los servidores réplica vean el mismo log. Cada réplica ejecuta las solicitudes de los clientes en el orden del log, aplicándolas a su copia local del estado del servicio. Como todas las réplicas activas ven el mismo contenido del log, ejecutan las mismas solicitudes en el mismo orden y, por lo tanto, mantienen un estado de servicio idéntico. Si un servidor falla pero luego se recupera, Raft se encarga de actualizar su log. Raft continuará operando mientras al menos una mayoría de los servidores estén activos y puedan comunicarse entre sí. Si no existe tal mayoría, Raft no avanzará, pero retomará donde quedó en cuanto una mayoría pueda comunicarse nuevamente.

En este TP implementarán Raft como un tipo de objeto en Go con sus métodos asociados, pensado para ser usado como módulo en un servicio más grande. Un conjunto de instancias de Raft se comunican entre sí mediante RPC para mantener logs replicados. La interfaz de Raft soportará una secuencia indefinida de comandos numerados, también llamados entradas de log. Las entradas están numeradas con índices. La entrada del log con un índice dado eventualmente será committed. En ese momento, la implementación de Raft debe enviar la entrada de log al servicio más grande para que la ejecute.

Deben seguir el diseño del paper extendido de Raft, con especial atención a la Figura 2. Implementarán la mayor parte de lo descrito en el paper, incluyendo guardar estado persistente y leerlo después de que un nodo falle y luego reinicie. No implementarán cambios de membresía del cluster (Sección 6).

Pueden encontrar útiles esta guía para estudiantes de Raft, estos consejos sobre locking y estructura para concurrencia, y este diagrama de interacciones de Raft.

Tengan presente que la parte más desafiante de este TP puede no ser implementar la solución, sino debuggearla. Para ayudar con esto, dediquen tiempo a pensar cómo hacer que la implementación sea más fácil de depurar. Pueden consultar este blog post sobre print statements efectivos.

Este trabajo práctico se divide en cuatro partes: 2A, 2B, 2C y 2D.

El código

Implementarán Raft agregando código en raft/raft.go. Allí encontrarán código esqueleto, además de ejemplos de cómo enviar y recibir RPCs.

La implementación debe soportar la siguiente interfaz, que los tests (y eventualmente el servidor clave/valor) usarán. Encontrarán más detalles en los comentarios de raft.go.

// crear una nueva instancia del servidor Raft:
rf := Make(peers, me, persister, applyCh)

// iniciar el acuerdo sobre una nueva entrada de log:
rf.Start(command interface{}) (index, term, isleader)

// consultar a un Raft por su term actual y si cree ser líder
rf.GetState() (term, isLeader)

// cada vez que una nueva entrada es committed en el log,
// cada peer Raft debe enviar un ApplyMsg al servicio (o al tester).
type ApplyMsg

Un servicio llama a Make(peers, me, ...) para crear un peer Raft. El argumento peers es un array de identificadores de red de los peers Raft (incluyendo el propio), para uso con RPC. El argumento me es el índice de este peer en el array. Start(command) le pide a Raft que inicie el procesamiento para agregar el comando al log replicado. Start() debe retornar inmediatamente, sin esperar a que las operaciones de append completen. El servicio espera que la implementación envíe un ApplyMsg por cada nueva entrada de log committed al canal applyCh pasado como argumento a Make().

raft.go contiene código de ejemplo que envía un RPC (sendRequestVote()) y que maneja un RPC entrante (RequestVote()). Los peers Raft deben intercambiar RPCs usando el paquete Go labrpc (código fuente en src/labrpc). Los tests pueden indicarle a labrpc que retrase RPCs, los reordene y los descarte para simular diversas fallas de red. Si bien pueden modificar labrpc temporalmente, asegúrense de que Raft funcione con el labrpc original, ya que es el que se usará para los tests. Las instancias de Raft deben interactuar únicamente a través de RPC; por ejemplo, no está permitido comunicarse usando variables compartidas de Go ni archivos.

Los trabajos prácticos subsiguientes se construyen sobre éste, así que es importante darse tiempo suficiente para escribir código sólido.

Parte 2A: Elección de líder

Implementen la elección de líder y los heartbeats de Raft (RPCs AppendEntries sin entradas de log). El objetivo de la Parte 2A es que se elija un único líder, que el líder permanezca como tal si no hay fallas, y que un nuevo líder asuma si el antiguo falla o si los paquetes desde/hacia el antiguo líder se pierden.

Para ejecutar los tests de la parte 2A:

$ cd src/raft
$ go test -run 2A

Consejos

Salida esperada

Asegúrense de pasar los tests de 2A antes de avanzar:

$ go test -run 2A
Test (2A): initial election ...
  ... Passed --   3.5  3   58   16840    0
Test (2A): election after network failure ...
  ... Passed --   5.4  3  118   25269    0
Test (2A): multiple elections ...
  ... Passed --   7.3  7  624  138014    0
PASS
ok  	6.824/raft	16.265s

Cada línea “Passed” contiene cinco números: el tiempo que tomó el test en segundos, la cantidad de peers Raft, la cantidad de RPCs enviados durante el test, el total de bytes en los mensajes RPC, y la cantidad de entradas de log reportadas como committed. Sus números diferirán de los mostrados aquí. Pueden ignorar los números si quieren, pero les pueden servir para verificar la cantidad de RPCs que envía la implementación. Los tests fallarán la solución si toman más de 600 segundos en total (go test), o si cualquier test individual toma más de 120 segundos.

Parte 2B: Log

Implementen el código de líder y follower para agregar nuevas entradas de log, de manera que pasen todos los tests de 2B:

$ go test -run 2B

Consejos

Consideraciones de rendimiento

Los tests de futuros TPs pueden fallar si el código es demasiado lento. Pueden verificar cuánto tiempo real y de CPU usa la solución con el comando time. Salida típica:

$ time go test -run 2B
Test (2B): basic agreement ...
  ... Passed --   0.9  3   16    4572    3
Test (2B): RPC byte count ...
  ... Passed --   1.7  3   48  114536   11
Test (2B): agreement despite follower disconnection ...
  ... Passed --   3.6  3   78   22131    7
Test (2B): no agreement if too many followers disconnect ...
  ... Passed --   3.8  5  172   40935    3
Test (2B): concurrent Start()s ...
  ... Passed --   1.1  3   24    7379    6
Test (2B): rejoin of partitioned leader ...
  ... Passed --   5.1  3  152   37021    4
Test (2B): leader backs up quickly over incorrect follower logs ...
  ... Passed --  17.2  5 2080 1587388  102
Test (2B): RPC counts aren't too high ...
  ... Passed --   2.2  3   60   20119   12
PASS
ok  	6.824/raft	35.557s

real	0m35.899s
user	0m2.556s
sys	0m1.458s

Si la solución usa mucho más de un minuto de tiempo real para los tests de 2B, o mucho más de 5 segundos de tiempo de CPU, pueden tener problemas más adelante. Busquen tiempo gastado en sleeps o esperando timeouts de RPC, loops que corran sin dormir ni esperar condiciones o mensajes de canales, o grandes cantidades de RPCs enviados.

Parte 2C: Persistencia

Si un servidor basado en Raft se reinicia, debe retomar el servicio donde lo dejó. Esto requiere que Raft mantenga estado persistente que sobreviva un reinicio. La Figura 2 del paper menciona qué estado debe ser persistente.

Una implementación real escribiría el estado persistente de Raft a disco cada vez que cambie, y lo leería del disco al reiniciar. La implementación de este TP no usará el disco; en su lugar, guardará y restaurará el estado persistente desde un objeto Persister (ver persister.go). Quien llame a Raft.Make() proporcionará un Persister que inicialmente contiene el estado persistido más reciente de Raft (si existe). Raft debe inicializar su estado desde ese Persister, y debe usarlo para guardar su estado persistente cada vez que el estado cambie. Usen los métodos ReadRaftState() y SaveRaftState() del Persister.

Completen las funciones persist() y readPersist() en raft.go agregando código para guardar y restaurar el estado persistente. Necesitarán codificar (“serializar”) el estado como un array de bytes para pasarlo al Persister. Usen el encoder labgob; vean los comentarios en persist() y readPersist(). labgob es como el encoder gob de Go pero imprime mensajes de error si intentan encodear structs con nombres de campos en minúscula.

Inserten llamadas a persist() en los puntos donde la implementación cambie estado persistente. Una vez hecho esto, y si el resto de la implementación es correcto, deberían pasar todos los tests de 2C.

Consejos

XTerm:  term en la entrada conflictiva (si existe)
XIndex: índice de la primera entrada con ese term (si existe)
XLen:   longitud del log

Entonces la lógica del líder puede ser algo como:

  Caso 1: el líder no tiene XTerm:
    nextIndex = XIndex
  Caso 2: el líder tiene XTerm:
    nextIndex = última entrada del líder para XTerm
  Caso 3: el log del follower es demasiado corto:
    nextIndex = XLen

Salida esperada

El código debe pasar todos los tests de 2C, así como los de 2A y 2B.

$ go test -run 2C
Test (2C): basic persistence ...
  ... Passed --   5.0  3   86   22849    6
Test (2C): more persistence ...
  ... Passed --  17.6  5  952  218854   16
Test (2C): partitioned leader and one follower crash, leader restarts ...
  ... Passed --   2.0  3   34    8937    4
Test (2C): Figure 8 ...
  ... Passed --  31.2  5  580  130675   32
Test (2C): unreliable agreement ...
  ... Passed --   1.7  5 1044  366392  246
Test (2C): Figure 8 (unreliable) ...
  ... Passed --  33.6  5 10700 33695245  308
Test (2C): churn ...
  ... Passed --  16.1  5 8864 44771259 1544
Test (2C): unreliable churn ...
  ... Passed --  16.5  5 4220 6414632  906
PASS
ok  	6.824/raft	123.564s

Es buena idea correr los tests múltiples veces antes de dar por terminada cada parte.

$ for i in {0..10}; do go test; done

Parte 2D: Compactación del log

Tal como está, un servidor que reinicia reproduce el log completo de Raft para restaurar su estado. Sin embargo, no es práctico para un servicio de larga duración recordar el log completo de Raft para siempre. En su lugar, modificarán Raft para cooperar con servicios que almacenan persistentemente un snapshot de su estado de vez en cuando, momento en el cual Raft descarta las entradas de log previas al snapshot. El resultado es una menor cantidad de datos persistentes y un reinicio más rápido. Sin embargo, ahora es posible que un follower quede tan atrasado que el líder haya descartado las entradas de log que necesita para ponerse al día; el líder entonces debe enviar un snapshot más el log a partir del momento del snapshot. La Sección 7 del paper extendido de Raft describe el esquema; deberán diseñar los detalles.

Pueden consultar el diagrama de interacciones de Raft para entender cómo el servicio replicado y Raft se comunican.

Raft debe proveer la siguiente función que el servicio puede llamar con un snapshot serializado de su estado:

Snapshot(index int, snapshot []byte)

En esta parte, los tests llaman a Snapshot() periódicamente. En el TP3, escribirán un servidor clave/valor que llame a Snapshot(); el snapshot contendrá la tabla completa de pares clave/valor. La capa de servicio llama a Snapshot() en cada peer (no solo en el líder).

El argumento index indica la entrada de log más alta que está reflejada en el snapshot. Raft debe descartar sus entradas de log anteriores a ese punto. Necesitarán revisar el código de Raft para que opere almacenando solamente la cola del log.

Necesitarán implementar el RPC InstallSnapshot discutido en el paper, que permite que un líder Raft le indique a un peer atrasado que reemplace su estado con un snapshot. Probablemente necesitarán pensar cómo InstallSnapshot debe interactuar con el estado y las reglas de la Figura 2. Noten que los RPCs InstallSnapshot se envían entre peers Raft, mientras que Snapshot es usado por el servicio para comunicarse con Raft.

Cuando el código Raft de un follower recibe un RPC InstallSnapshot, puede usar applyCh para enviar el snapshot al servicio en un ApplyMsg. La definición del struct ApplyMsg ya contiene los campos que necesitarán (y que los tests esperan). Tengan cuidado de que estos snapshots solo avancen el estado del servicio, y no lo hagan retroceder.

Si un servidor se cae, debe reiniciar desde datos persistidos. Raft debe persistir tanto el estado de Raft como el snapshot correspondiente. Usen persister.SaveStateAndSnapshot(), que toma argumentos separados para el estado de Raft y el snapshot correspondiente. Si no hay snapshot, pasen nil como argumento de snapshot.

Cuando un servidor reinicia, la capa de aplicación lee el snapshot persistido y restaura su estado guardado.

Anteriormente, se recomendaba implementar una función llamada CondInstallSnapshot para evitar el requerimiento de que los snapshots y las entradas de log enviadas por applyCh estén coordinados. Esta interfaz vestigial permanece en el código, pero no es necesario implementarla: simplemente hagan que retorne true.

Implementen Snapshot() y el RPC InstallSnapshot, así como los cambios a Raft para soportar estos (por ejemplo, operar con un log recortado). La solución está completa cuando pasa los tests de 2D (y todos los tests previos del TP).

Consejos

Salida esperada

El código debe pasar todos los tests de 2D, así como los de 2A, 2B y 2C.

$ go test -run 2D
Test (2D): snapshots basic ...
  ... Passed --  11.6  3  176   61716  192
Test (2D): install snapshots (disconnect) ...
  ... Passed --  64.2  3  878  320610  336
Test (2D): install snapshots (disconnect+unreliable) ...
  ... Passed --  81.1  3 1059  375850  341
Test (2D): install snapshots (crash) ...
  ... Passed --  53.5  3  601  256638  339
Test (2D): install snapshots (unreliable+crash) ...
  ... Passed --  63.5  3  687  288294  336
PASS
ok      6.824/raft      293.456s

Referencias

Este trabajo práctico es una adaptación del Lab 2: Raft del curso 6.824 Distributed Systems del MIT (Robert Morris, Frans Kaashoek y Nickolai Zeldovich), traducido al castellano y con modificaciones menores para adaptarlo a la materia. El material original está licenciado bajo Creative Commons BY 3.0 US.