Consenso distribuido

📐 Fundamento

El problema del consenso:

Dado un conjunto de nodos que proponen valores, deben acordar un único valor tal que:

1. Terminación: Eventualmente, todos los nodos no fallados deciden.
2. Validez: El valor decidido fue propuesto por algún nodo.
3. Acuerdo: Todos los nodos no fallados deciden el mismo valor.

Teorema FLP (Fisher, Lynch, Paterson, 1985):

En un sistema distribuido completamente asíncrono (sin garantías de tiempo) con al menos un proceso que puede fallar (crash-stop), es imposible garantizar que el consenso termine.

Implicación práctica: Los algoritmos de consenso reales (Paxos, Raft) asumen modelos parcialmente síncronos — eventualmente los mensajes llegan en tiempo acotado. Esto los hace viables pero no garantizados en el peor caso.

Quórum:

Para tolerar f fallos en un sistema de n nodos, se necesita que el quórum q cumpla:

Con n=5: quórum = 3. Tolera 2 fallos. Si 3+ nodos están vivos y se comunican, el sistema avanza.

¿Por qué quórum mayoritario? Dos quórums cualesquiera siempre se solapan en al menos un nodo. Ese nodo en común garantiza que el segundo quórum "sabe" lo que acordó el primero.

📐 Fundamento

Roles en Raft:

• Leader: Recibe escrituras de los clientes, replica al resto.
• Follower: Acepta el log del leader y responde a heartbeats.
• Candidate: Cuando no hay heartbeat, intenta convertirse en leader.

Elección de líder:

Estado inicial: todos son followers
Follower: si no recibo heartbeat en timeout aleatorio (150-300ms)...
  → me convierto en Candidate
  → incremento mi term (era 1, ahora 2)
  → me voto a mí mismo
  → envío RequestVote a todos

Otros nodos: si term > mi term y no voté en este term...
  → voto por el candidato
  → actualizo mi term

Si recibo mayoría de votos:
  → me convierto en Leader
  → envío heartbeats inmediatamente para evitar otra elección

Replicación de log:

Cliente → Leader: "registrar pedido #456"
Leader:
  1. Agrega entry al log local: {term:2, index:7, comando: "pedido #456"}
  2. Envía AppendEntries(entry) a todos los followers
  
Follower: recibe AppendEntries
  → verifica consistencia del log
  → agrega entry al log local
  → responde OK

Leader: cuando mayoría de followers confirmó:
  → entry está "commiteado"
  → aplica el comando a la máquina de estados
  → responde al cliente: "OK, pedido #456 registrado"
  → notifica a followers que pueden commitear también

Propiedades de seguridad de Raft:

1. Log Matching: Si dos logs tienen un entry con el mismo índice y term, entonces todos los entries anteriores son idénticos.
2. Leader Completeness: Si un entry está commiteado en un term, estará presente en todos los líderes futuros.
3. State Machine Safety: Si un servidor aplica un entry en el índice i, ningún otro servidor aplica un entry diferente en ese índice.

Implementación simplificada:

from enum import Enum
import random, threading, time

class Rol(Enum):
    FOLLOWER = 'follower'
    CANDIDATE = 'candidate'
    LEADER = 'leader'

class NodoRaft:
    def __init__(self, nodo_id: int, peers: list):
        self.id = nodo_id
        self.peers = peers           # lista de otros nodos
        self.rol = Rol.FOLLOWER
        
        # Estado persistente
        self.current_term = 0
        self.voted_for = None
        self.log = []               # [{term, index, comando}]
        
        # Estado volátil
        self.commit_index = 0
        self.last_applied = 0
        self.leader_id = None
        
        # Solo en leaders
        self.next_index = {}
        self.match_index = {}
        
        # Timer
        self.election_timeout = random.uniform(0.15, 0.30)
        self.last_heartbeat = time.time()
    
    def solicitar_voto(self, term, candidate_id, last_log_index, last_log_term):
        """Manejar RequestVote RPC."""
        if term < self.current_term:
            return {'term': self.current_term, 'vote_granted': False}
        
        if term > self.current_term:
            self.current_term = term
            self.rol = Rol.FOLLOWER
            self.voted_for = None
        
        voto_disponible = (self.voted_for is None or self.voted_for == candidate_id)
        log_actualizado = (last_log_term > self._ultimo_term() or
                          (last_log_term == self._ultimo_term() and
                           last_log_index >= len(self.log)))
        
        if voto_disponible and log_actualizado:
            self.voted_for = candidate_id
            return {'term': self.current_term, 'vote_granted': True}
        
        return {'term': self.current_term, 'vote_granted': False}
    
    def _ultimo_term(self):
        return self.log[-1]['term'] if self.log else 0

etcd — Raft en producción:

etcd es la base de datos de configuración de Kubernetes. Usa Raft para garantizar que todos los nodos del clúster de Kubernetes tengan la misma vista de la configuración del sistema.

# Ver el estado del clúster etcd (en un nodo de Kubernetes)
etcdctl endpoint status --cluster
# endpoint    ID            version  db size  is leader  is learner  raft term  raft index
# etcd-0:2379  8e9e05c52164  3.5.0    25 MB    false      false       42         12567
# etcd-1:2379  f1b27fbe4749  3.5.0    25 MB    true       false       42         12567
# etcd-2:2379  9fffb4c23500  3.5.0    25 MB    false      false       42         12567

📐 Fundamento

Paxos (Leslie Lamport, 1989/1998) fue el primer algoritmo de consenso ampliamente estudiado. Hay dos fases:

Fase 1 (Prepare/Promise):

Proposer → todos: "Prepare(n=42)"
    "¿Pueden prometerte no aceptar números menores que 42?"

Acceptors: si n > mi mayor prepare previo:
    → "Promise(n=42)" + cualquier valor ya aceptado previo

Fase 2 (Accept/Accepted):

Proposer: tiene quórum de promises → 
    → "Accept(n=42, valor='pupusa')" o el valor aceptado más alto

Acceptors: si n >= mi mayor prepare previo:
    → "Accepted(n=42, valor='pupusa')"
    
Proposer: recibe quórum de Accepted → ¡CONSENSO! valor='pupusa'

¿Por qué Raft ganó popularidad sobre Paxos?

• Paxos original solo resuelve un valor — para un log replicado se necesita "Multi-Paxos", que Lamport describió vagamente.
• Las implementaciones reales de Paxos difieren significativamente del paper.
• Raft fue diseñado desde cero para el caso completo (leader election + log replication) y tiene una especificación completa.

Sistemas que usan Paxos: Google Chubby (coordinación en Spanner), Google Megastore. Sistemas que usan Raft: etcd, CockroachDB, TiKV, Consul.