Algoritmos de Consenso Distribuido

El consenso distribuido es uno de los problemas más difíciles en ciencias de la computación. Pregunta: ¿cómo puede un grupo de máquinas acordar un valor, incluso cuando algunas máquinas fallan o los mensajes se retrasan? El consenso es la base de las máquinas de estados replicadas, bases de datos distribuidas y servicios de coordinación. Sin consenso, no puedes construir sistemas distribuidos confiables.

El Problema del Consenso

Un algoritmo de consenso debe satisfacer tres propiedades:

Acuerdo: Todos los nodos no defectuosos deciden el mismo valor
Validez: El valor decidido debe haber sido propuesto por algún nodo
Terminación: Todos los nodos no defectuosos eventualmente deciden un valor

Imposibilidad FLP

Fischer, Lynch y Paterson demostraron en 1985 que ningún algoritmo de consenso determinista puede garantizar las tres propiedades en un sistema asíncrono donde incluso un proceso puede fallar. En la práctica, los algoritmos evitan esta imposibilidad usando timeouts (sincronía parcial) o aleatorización para asegurar progreso.

Algoritmo Paxos (Simplificado)

Paxos, inventado por Leslie Lamport en 1989, fue el primer algoritmo de consenso demostrado. Es notoriamente difícil de entender e implementar. Aquí está la versión simplificada de decreto único (consenso sobre un solo valor).

Roles de Paxos

Rol	Responsabilidad
Proponente	Propone valores y conduce el protocolo
Aceptor	Vota sobre propuestas y almacena valores aceptados
Aprendiz	Aprende el valor decidido una vez que se alcanza el consenso

Fases del Protocolo Paxos

// Phase 1: Prepare
// Proposer selects a proposal number n and sends Prepare(n) to a majority of acceptors

interface PrepareRequest {
  proposalNumber: number;
}

interface PrepareResponse {
  promise: boolean;           // Will the acceptor promise not to accept lower proposals?
  acceptedProposal?: number;  // Highest proposal number previously accepted
  acceptedValue?: string;     // Value from that proposal
}

// Phase 2: Accept
// If proposer receives promises from a majority:
// - If any acceptor already accepted a value, proposer must use the value
//   from the highest-numbered accepted proposal
// - Otherwise, proposer can use its own value
// Proposer sends Accept(n, value) to a majority of acceptors

interface AcceptRequest {
  proposalNumber: number;
  value: string;
}

interface AcceptResponse {
  accepted: boolean;
}

// Simplified Paxos Proposer
class PaxosProposer {
  private proposalNumber: number = 0;

  async propose(value: string, acceptors: Acceptor[]): Promise<string> {
    const majority = Math.floor(acceptors.length / 2) + 1;

    // Phase 1: Prepare
    this.proposalNumber++;
    const prepareResponses = await Promise.all(
      acceptors.map((a) => a.prepare({ proposalNumber: this.proposalNumber }))
    );

    const promises = prepareResponses.filter((r) => r.promise);
    if (promises.length < majority) {
      throw new Error("Failed to get majority promises");
    }

    // Use the value from the highest accepted proposal, or our own
    const highestAccepted = promises
      .filter((r) => r.acceptedProposal !== undefined)
      .sort((a, b) => (b.acceptedProposal || 0) - (a.acceptedProposal || 0))[0];

    const finalValue = highestAccepted?.acceptedValue || value;

    // Phase 2: Accept
    const acceptResponses = await Promise.all(
      acceptors.map((a) =>
        a.accept({ proposalNumber: this.proposalNumber, value: finalValue })
      )
    );

    const accepted = acceptResponses.filter((r) => r.accepted);
    if (accepted.length < majority) {
      throw new Error("Failed to get majority acceptance");
    }

    return finalValue; // Consensus reached!
  }
}

Algoritmo Raft (Detallado)

Raft fue diseñado por Diego Ongaro y John Ousterhout en 2014 como una alternativa comprensible a Paxos. Descompone el consenso en tres sub-problemas: elección de líder, replicación de log y seguridad.

Estados de Nodo Raft

Cada nodo en un clúster Raft está en uno de tres estados: Seguidor, Candidato o Líder. Todos los nodos comienzan como seguidores.

enum RaftState {
  FOLLOWER = "FOLLOWER",
  CANDIDATE = "CANDIDATE",
  LEADER = "LEADER",
}

interface LogEntry {
  term: number;
  index: number;
  command: string;
}

interface RaftNode {
  id: string;
  state: RaftState;
  currentTerm: number;
  votedFor: string | null;
  log: LogEntry[];
  commitIndex: number;
  lastApplied: number;

  // Leader-only state
  nextIndex: Map<string, number>;
  matchIndex: Map<string, number>;
}

Elección de Líder

class RaftElection {
  private electionTimeout: number; // Random between 150-300ms
  private heartbeatInterval: number = 50;

  startElection(node: RaftNode, peers: string[]): void {
    node.currentTerm++;
    node.state = RaftState.CANDIDATE;
    node.votedFor = node.id;

    let votesReceived = 1;
    const majority = Math.floor(peers.length / 2) + 1;

    for (const peerId of peers) {
      const response = this.sendRequestVote(peerId, {
        term: node.currentTerm,
        candidateId: node.id,
        lastLogIndex: node.log.length - 1,
        lastLogTerm: node.log.length > 0
          ? node.log[node.log.length - 1].term
          : 0,
      });

      if (response.voteGranted) {
        votesReceived++;
      }
      if (response.term > node.currentTerm) {
        node.currentTerm = response.term;
        node.state = RaftState.FOLLOWER;
        return;
      }
    }

    if (votesReceived >= majority) {
      node.state = RaftState.LEADER;
      this.initializeLeaderState(node, peers);
      this.sendHeartbeats(node, peers);
    }
  }

  // A node grants a vote if:
  // 1. The candidate's term >= the voter's term
  // 2. The voter hasn't voted for someone else in this term
  // 3. The candidate's log is at least as up-to-date as the voter's
  handleRequestVote(node: RaftNode, request: RequestVoteRequest): RequestVoteResponse {
    if (request.term < node.currentTerm) {
      return { term: node.currentTerm, voteGranted: false };
    }

    if (request.term > node.currentTerm) {
      node.currentTerm = request.term;
      node.state = RaftState.FOLLOWER;
      node.votedFor = null;
    }

    const logOk = request.lastLogTerm > this.getLastLogTerm(node) ||
      (request.lastLogTerm === this.getLastLogTerm(node) &&
       request.lastLogIndex >= node.log.length - 1);

    if ((node.votedFor === null || node.votedFor === request.candidateId) && logOk) {
      node.votedFor = request.candidateId;
      return { term: node.currentTerm, voteGranted: true };
    }

    return { term: node.currentTerm, voteGranted: false };
  }
}

Replicación de Log

Una vez que se elige un líder, acepta solicitudes de clientes, las agrega a su log y replica las entradas del log a los seguidores. Una entrada se considera confirmada una vez que una mayoría de nodos la han replicado.

class RaftLogReplication {
  async replicateEntry(
    leader: RaftNode,
    command: string,
    peers: string[]
  ): Promise<boolean> {
    const entry: LogEntry = {
      term: leader.currentTerm,
      index: leader.log.length,
      command,
    };
    leader.log.push(entry);

    let replicatedCount = 1;
    const majority = Math.floor(peers.length / 2) + 1;

    const results = await Promise.all(
      peers.map((peerId) =>
        this.sendAppendEntries(peerId, {
          term: leader.currentTerm,
          leaderId: leader.id,
          prevLogIndex: entry.index - 1,
          prevLogTerm: entry.index > 0 ? leader.log[entry.index - 1].term : 0,
          entries: [entry],
          leaderCommit: leader.commitIndex,
        })
      )
    );

    for (const result of results) {
      if (result.success) replicatedCount++;
    }

    if (replicatedCount >= majority) {
      leader.commitIndex = entry.index;
      return true;
    }

    return false;
  }
}

ZooKeeper y etcd

ZooKeeper y etcd son los dos servicios de coordinación basados en consenso más utilizados.

Característica	ZooKeeper	etcd
Algoritmo de Consenso	ZAB (ZooKeeper Atomic Broadcast)	Raft
Lenguaje	Java	Go
Modelo de Datos	Jerárquico (árbol de znodes)	Almacén clave-valor plano
Mecanismo de Watch	Triggers de una sola vez (deben re-registrarse)	Watches persistentes con streaming
Usuarios Principales	Kafka, Hadoop, HBase	Kubernetes, CoreDNS

Aplicaciones Prácticas

Elección de líder: Asegurar que solo una instancia de un servicio actúe como líder (ej. un scheduler, una base de datos primaria)
Gestión de configuración: Almacenar y distribuir configuración con garantías de consistencia fuerte
Bloqueo distribuido: Coordinar acceso a recursos compartidos entre múltiples servicios
Descubrimiento de servicios: Registrar y descubrir instancias de servicio con verificación de salud
Máquinas de estados replicadas: Construir servicios tolerantes a fallos que sobrevivan fallos de nodos replicando el log de operaciones
Gestión de metadatos: Almacenar mapas de particiones, membresía del clúster e información de esquema

Cuándo NO Usar Consenso

Los algoritmos de consenso agregan latencia (cada escritura requiere un quórum mayoritario) y complejidad. No los uses para almacenamiento de datos de alto rendimiento o cuando la consistencia eventual es aceptable. Usa consenso para metadatos de coordinación (¿quién es el líder? ¿cuál es el mapa de particiones?) y usa replicación más simple para datos en masa.