Algoritmos de Consenso Comparados: Raft, Multi-Paxos, Viewstamped Replication y EPaxos

Por Qué el Consenso Es Difícil (Repaso Rápido)

El problema fundamental: N servidores necesitan ponerse de acuerdo en una secuencia de operaciones, incluso si hasta F de ellos crashean (donde N >= 2F + 1). Este acuerdo debe ser:

• Safe: Todos los servidores no-fallados acuerdan la misma secuencia
• Live: El sistema eventualmente avanza (asumiendo menos de F+1 crasheos y que la red eventualmente entrega los mensajes)

El resultado de imposibilidad FLP nos dice que no podemos tener ambos en una red asincrónica con incluso una sola falla por crash. Cada algoritmo de consenso práctico lo soluciona usando timeouts como detectores de fallas — lo cual técnicamente viola el modelo asincrónico, pero funciona en la práctica porque las redes reales tienen delays acotados-pero-desconocidos.

Raft: El Algoritmo Que Se Explica Solo

Raft fue diseñado para ser entendible, y cumple esa promesa. El algoritmo se descompone en tres subproblemas: elección de líder, replicación de log, y safety. El enfoque a continuación son las partes que son más difíciles de implementar de lo que el paper sugiere.

Elección de Líder: Las Partes Sutiles

El mecanismo básico es simple: los candidatos incrementan su term, votan por sí mismos, y piden votos a los demás. Pero los detalles de implementación importan enormemente.

type RaftNode struct {
 mu sync.Mutex
 state NodeState
 currentTerm uint64
 votedFor *uint64
 log []LogEntry

 // Timing de elección - estos valores importan más de lo que considerars
 electionTimeout time.Duration
 heartbeatTimeout time.Duration
 lastHeartbeat time.Time

 // Protocolo pre-vote (Sección 9.6 de la disertación de Raft)
 preVoteEnabled bool
}

func (n *RaftNode) startElection() {
 n.mu.Lock()
 defer n.mu.Unlock()

 if n.preVoteEnabled {
 // Pre-vote: preguntar a los peers si votarían por nosotros SIN incrementar term
 // Esto previene disrupciones de nodos particionados
 n.runPreVote()
 return
 }

 n.currentTerm++
 n.state = Candidate
 n.votedFor = &n.id
 n.persistState() // DEBE ser durable antes de enviar RequestVote

 lastLogIndex, lastLogTerm := n.lastLogInfo()

 for _, peer := range n.peers {
 go func(p PeerID) {
 reply, err := n.sendRequestVote(p, &RequestVoteArgs{
 Term: n.currentTerm,
 CandidateID: n.id,
 LastLogIndex: lastLogIndex,
 LastLogTerm: lastLogTerm,
 })
 if err != nil {
 return
 }
 n.handleVoteResponse(reply)
 }(peer)
 }
}

El protocolo pre-vote es crítico y usualmente se omite en los tutoriales. Sin él, un nodo que se particiona del cluster sigue incrementando su term. Cuando se reconecta, su term artificialmente alto fuerza una nueva elección, rompiendo el cluster sano. Pre-vote pregunta "¿votarías por mí?" sin incrementar el term. Si la respuesta es no (porque el cluster ya tiene un líder sano), el nodo se queda eficiente.

Log Compaction: Donde Vive el Dolor

La Sección 7 del paper de Raft sobre log compaction ocupa como una página. Mi implementación son 2,000 líneas. Acá va el por qué:

type SnapshotManager struct {
 stateMachine StateMachine
 raftLog *RaftLog
 snapshotDir string

 inProgress atomic.Bool
 lastIncluded struct {
 Index uint64
 Term uint64
 }
}

func (sm *SnapshotManager) TakeSnapshot() error {
 if !sm.inProgress.CompareAndSwap(false, true) {
 return ErrSnapshotInProgress
 }
 defer sm.inProgress.Store(false)

 // 1. Obtener snapshot point-in-time consistente de la state machine
 snapshot, appliedIndex, appliedTerm := sm.stateMachine.Snapshot()

 // 2. Escribir a archivo temporal primero (crash safety)
 tmpPath := filepath.Join(sm.snapshotDir, fmt.Sprintf("snap-%d.tmp", appliedIndex))
 finalPath := filepath.Join(sm.snapshotDir, fmt.Sprintf("snap-%d.dat", appliedIndex))

 f, err := os.Create(tmpPath)
 if err != nil {
 return err
 }

 header := SnapshotHeader{
 LastIncludedIndex: appliedIndex,
 LastIncludedTerm: appliedTerm,
 Size: uint64(len(snapshot)),
 Checksum: crc32.ChecksumIEEE(snapshot),
 }

 if err := binary.Write(f, binary.LittleEndian, header); err != nil {
 f.Close()
 os.Remove(tmpPath)
 return err
 }

 if _, err := f.Write(snapshot); err != nil {
 f.Close()
 os.Remove(tmpPath)
 return err
 }

 // Fsync antes del rename (crítico para crash safety)
 if err := f.Sync(); err != nil {
 f.Close()
 os.Remove(tmpPath)
 return err
 }
 f.Close()

 if err := os.Rename(tmpPath, finalPath); err != nil {
 return err
 }

 sm.raftLog.TruncateBefore(appliedIndex)
 sm.lastIncluded.Index = appliedIndex
 sm.lastIncluded.Term = appliedTerm

 return nil
}

Las partes complicadas:

1. Tomar el snapshot no debe bloquear la aplicación de log. Si tu state machine es un B-tree, se necesita semántica copy-on-write o un mecanismo de snapshot isolation. BoltDB te da esto gratis; un map in-memory naive no.

2. El RPC InstallSnapshot es chunked. Cuando un follower está tan atrasado que el líder ya compactó su log, el líder manda su snapshot. Para state machines de multi-GB, esto tiene que ser chunked y resumable. El paper lo menciona en una oración.

3. El crash recovery intercala snapshots y logs. Al reiniciar, cargás el último snapshot, después replayeás entries del log después del last included index del snapshot. Si crasheaste entre tomar un snapshot y truncar el log, es posible tener entries superpuestas. Tu lógica de recovery necesita manejar esto.

Multi-Paxos: Un Protocolo Sin Especificación Canónica

Acá va el secreto sucio de Multi-Paxos: no hay un paper canónico de Multi-Paxos. El "The Part-Time Parliament" original de Lamport describe Paxos de un solo decreto. La extensión a multi-decreto (una secuencia de instancias de consenso) se describe informalmente, y cada implementación toma decisiones diferentes.

La optimización core de Multi-Paxos sobre Paxos básico: una vez que se establece un líder, puede saltear la fase Prepare para entries de log subsiguientes, yendo directo a Accept. Esto significa que las operaciones en estado estable solo requieren un round-trip en vez de dos.

func (n *MultiPaxosNode) Propose(value []byte) (uint64, error) {
 if !n.proposerState.isLeader {
 return 0, ErrNotLeader
 }

 slot := atomic.AddUint64(&n.proposerState.maxSlot, 1)

 // Como líder establecido, saltear Phase 1 (Prepare)
 // Ir directo a Phase 2 (Accept)
 acceptMsg := &AcceptMessage{
 Ballot: n.proposerState.ballotNum,
 Slot: slot,
 Value: value,
 }

 ackCount := 1
 quorum := (len(n.peers) / 2) + 1

 for _, peer := range n.peers {
 go func(p PeerID) {
 reply, err := n.sendAccept(p, acceptMsg)
 if err != nil {
 return
 }

 if reply.Ballot > n.proposerState.ballotNum {
 n.stepDown(reply.Ballot)
 return
 }

 if atomic.AddInt32(&ackCount, 1) >= int32(quorum) {
 n.markChosen(slot, value)
 }
 }(peer)
 }

 return slot, nil
}

El Problema de los Gaps en los Slots

En Multi-Paxos, los slots se pueden elegir fuera de orden. El request del Cliente A puede caer en el slot 5, y el del Cliente B en el slot 7, mientras el slot 6 sigue pendiente. Cuando entregás comandos a la state machine, teners que entregarlos en orden. Esto significa que se necesita un mecanismo para rellenar gaps — ya sea con no-ops o re-proponiendo valores para slots vacíos.

Esta lógica de gap-filling es donde la mayoría de las implementaciones de Multi-Paxos tienen bugs. La interacción entre gap-filling, cambios de líder, y la fase accept es sutil. Si un nuevo líder empieza a llenar gaps concurrentemente con los accepts del viejo líder que todavía están en vuelo, es posible terminar con un slot elegido con dos valores diferentes a menos que el mecanismo de ballot number esté correctamente implementado.

Viewstamped Replication: El Hijo del Medio Olvidado

VR precede a Paxos en publicación y es notablemente similar a Raft en estructura — tiene un primary (líder), views (terms), y un log. Las diferencias clave están en el protocolo de view change y el mecanismo de reconfiguración.

Operación Normal (simplificada):
1. Cliente → Primary: REQUEST(op, client-id, request-num)
2. Primary: Asignar op-number, agregar al log
3. Primary → Backups: PREPARE(view, op-number, op, commit-number)
4. Backups: Agregar al log, responder PREPARE-OK
5. Primary: Después de f+1 PREPARE-OKs, commit
6. Primary → Cliente: REPLY(view, request-num, result)

Lo interesante de VR es su protocolo de view change, que es más estructurado que la elección de Raft. Cuando un backup sospecha que el primary falló:

1. Manda mensajes START-VIEW-CHANGE
2. Después de recibir f tales mensajes, un nodo manda DO-VIEW-CHANGE al nuevo primary (determinado por round-robin)
3. El nuevo primary recolecta f+1 mensajes DO-VIEW-CHANGE, selecciona el log con los datos más recientes, y arranca la nueva view

La selección determinista del primary (round-robin basado en el número de view) significa que no hay escenario de split-vote — no se necesita timeouts randomizados como Raft. El tradeoff es menos flexibilidad: no es posible preferir un nodo con mejor hardware o menor latencia a los clientes.

Donde VR Brilla

El protocolo de reconfiguración de VR (cambiar el set de réplicas) es significativamente más simple que el approach de joint consensus de Raft. En VR, la reconfiguración es simplemente una operación especial en el log. Cuando se commitea, la nueva configuración toma efecto en ese punto del log. Las réplicas viejas transfieren estado a las nuevas, y la transición es limpia.

Usé el approach de reconfiguración de VR incluso en mi implementación de Raft, porque el joint consensus de Raft (Sección 6 del paper) es una pesadilla de implementar correctamente. El approach de cambios de un solo servidor (de la disertación de Raft) es más simple pero puede llevar a problemas de disponibilidad durante cambios de membership de múltiples servidores.

EPaxos: La Promesa Leaderless

EPaxos (Egalitarian Paxos) es el más intelectualmente ambicioso de los cuatro. En vez de canalizar todas las operaciones a través de un líder, cualquier réplica puede proponer comandos. Los comandos que no conflictúan se pueden commitear en un solo round-trip (el fast path), y los conflictos se resuelven a través de un grafo de dependencias.

El Grafo de Dependencias

Acá es donde EPaxos se complica. Cada comando lleva un set de dependencias — otros comandos después de los cuales debe ejecutarse:

func (r *EPaxosReplica) StartCommand(cmd []byte) {
 inst := &EPaxosInstance{
 Command: cmd,
 SeqNum: 0,
 Deps: make(map[InstanceID]uint64),
 Status: PreAccepted,
 }

 for id, other := range r.instances {
 if r.conflictsWithAny(cmd, other.Command) {
 inst.Deps[id] = other.SeqNum
 if other.SeqNum >= inst.SeqNum {
 inst.SeqNum = other.SeqNum + 1
 }
 }
 }

 superQuorum := (3*len(r.peers)/4) + 1
 replies := r.broadcastPreAccept(inst)

 if r.fastPathSucceeded(replies, inst, superQuorum) {
 inst.Status = Committed
 r.broadcastCommit(inst)
 } else {
 r.mergedDeps(inst, replies)
 inst.Status = Accepted
 r.broadcastAccept(inst)
 }
}

El Problema de la Ejecución

Commitear es fácil. Ejecutar es difícil. Porque los comandos son commiteados por distintas réplicas con distintos sets de dependencias, se necesita un algoritmo determinístico para linearizar el grafo de dependencias. Esto usa el algoritmo de componentes fuertemente conectados de Tarjan:

1. Construir el grafo de dependencias de instancias commiteadas
2. Encontrar todas las componentes fuertemente conectadas (SCCs)
3. Ejecutar SCCs en orden topológico inverso
4. Dentro de cada SCC, ejecutar comandos en orden de número de secuencia

Esto significa que no es posible ejecutar un comando en el momento que se commitea — teners que esperar hasta que todas sus dependencias también estén commiteadas, y después computar el orden de ejecución. En la práctica, esto agrega varianza de latencia que los ahorros del fast-path no siempre compensan.

Comparación de Performance

Benchmarkeé los cuatro en un cluster de 5 nodos (AWS c6g.xlarge, misma región, 0.3ms RTT inter-nodo):

Algoritmo	Throughput (ops/s)	Latencia P50	Latencia P99	Notas
Raft	42,000	0.8ms	2.1ms	BatchSize=64
Multi-Paxos	58,000	0.6ms	1.8ms	Accepts pipelined
VR	41,000	0.9ms	2.3ms	Similar a Raft
EPaxos (sin conflictos)	73,000	0.4ms	1.2ms	Fast path
EPaxos (50% conflictos)	31,000	1.4ms	8.7ms	Slow path + deps

EPaxos gana convincentemente cuando los comandos no conflictúan. Pero con 50% de tasa de conflicto (común en workloads key-value donde las keys siguen distribución Zipf), es el peor performer. El overhead de resolución de dependencias domina.

Multi-Paxos supera a Raft porque pipelines los accepts — el líder no espera a que el slot N se commitee antes de mandar el slot N+1. Raft también puede hacer esto (se llama "pipelining" en la implementación de etcd), pero no es parte del protocolo core.

Qué Elegiría Hoy

Para la mayoría de los sistemas: Raft con las optimizaciones de etcd (pipelining, learner nodes, pre-vote, leader lease para reads). El ecosistema no tiene comparación — etcd, CockroachDB, TiKV, y Consul todos usan variantes de Raft, y sus implementaciones battle-tested están disponibles como librerías.

Para sistemas geo-distribuidos con operaciones mayormente no conflictivas: EPaxos, pero solo si teners los recurse es de ingeniería para manejar la complejidad de implementación y la pesadilla de debugging que es la resolución de grafos de dependencias.

Para aprender y construir intuición: implementá Raft primero, después VR. Las similitudes van a cristalizar tu entendimiento, y las diferencias en view change vs. election te van a enseñar por qué estas decisiones de diseño importan.

Multi-Paxos es la respuesta correcta si se necesita máximo throughput en un solo líder y se está dispuesto a invertir en una implementación custom. Pero honestamente, llegado ese punto, probablemente deberías usar etcd o CockroachDB y enfocar tu esfuerzo de ingeniería en tu producto real.