Consensus e Raft: como nós discordam e chegam a acordo

Consenso: um conjunto de processos precisa concordar em um único valor, dado que cada processo propõe um valor e alguns podem falhar. Sons simples? Em teoria, é. Na prática — com rede não confiável, timeouts, máquinas que congelam por GC, e relógios que divergem — é o pesadelo que levou 30 anos de pesquisa pra domar.

Fischer, Lynch e Paterson provaram em 1985 o resultado mais importante de sistemas distribuídos:

A intuição: sem limite superior no tempo de mensagens, você não consegue distinguir um processo morto de um processo lento. Se você espera, pode esperar pra sempre. Se não espera, pode decidir sem contar com ele e quebrar agreement.

Como a prática contornou FLP? Três escapes principais:

Raft e Paxos pagam o preço assumindo timeouts. Isso significa: em uma partição de rede muito longa, o cluster pode ficar indisponível (escolhe consistência — CP no CAP). É uma escolha deliberada.

Paxos foi proposto por Leslie Lamport em 1989 e publicado formalmente em 1998 ("The Part-Time Parliament"). Ganhou Turing Award, inspirou uma geração de sistemas — e todo mundo acha horrível de entender. Lamport escreveu o paper como uma alegoria sobre um parlamento na Grécia antiga. Foi rejeitado. Reescreveu simples ("Paxos Made Simple", 2001) e ainda assim é difícil.

Intuição em 3 fases:

Cliente ──► PROPONER ──► ACCEPTORS (2F+1 nós, tolera F falhas)
                │             │
                │  1. PREPARE(n)                     ──► todos os acceptors
                │                                    ◄── PROMISE(n, maior valor já aceito)
                │
                │  2. ACCEPT(n, v)  (v = valor escolhido)  ──► todos
                │                                    ◄── ACCEPTED(n, v) de quórum
                │
                │  3. LEARN(v)                       ──► LEARNERS aplicam v
                ▼
            Valor decidido

A complexidade real do Paxos vem de Multi-Paxos (sequência de decisões), reconfigurações dinâmicas e otimizações. Ninguém implementa Paxos do paper — todas as implementações usam variantes (Zab, Raft, Viewstamped Replication). Isso levou Ongaro e Ousterhout a criarem o Raft em 2014 com um objetivo explícito: ser entendível.

Raft foi projetado em Stanford (2014) com o objetivo explícito de ser didático. Ele decompõe o problema em 3 subproblemas independentes que você pode estudar separadamente:

Estados de um nó Raft:

               timeout, start election
     ┌──────────────────────────────────────────┐
     ▼                                           │
┌─────────┐   discovers leader/        ┌──────────────┐
│FOLLOWER │──── higher term ──────────►│  CANDIDATE   │
│         │◄───────────────────────────│              │
└─────────┘                            └──────────────┘
     ▲                                         │
     │                                         │ wins election
     │     discovers higher term               │ (maioria de votos)
     │                                         ▼
     │                                 ┌──────────────┐
     └─────────────────────────────────│    LEADER    │
                                        └──────────────┘

A vida inteira do cluster é dividida em terms (períodos numerados monotonicamente). Cada term tem no máximo 1 leader. Se um term não eleger leader (split vote), um novo term começa. O número do term é carimbado em cada RPC e entry — e é a chave da safety do Raft.

Quando um follower não recebe heartbeat do leader em electionTimeout(tipicamente 150-300ms, randomizado pra evitar split votes), ele:

1. Vira candidate
2. Incrementa seu currentTerm
3. Vota em si mesmo
4. Envia RequestVote(term, candidateId, lastLogIndex, lastLogTerm) pra todos
5. Se recebe maioria → vira leader, começa a mandar heartbeats
6. Se recebe heartbeat de leader legítimo (term >= seu) → volta a follower
7. Se timeout sem decisão → novo term, nova eleição

Implementação didática de RequestVote (Python):

# request_vote.py — mostra as regras de voto do Raft
from dataclasses import dataclass

@dataclass
class RaftNode:
    id: str
    current_term: int = 0
    voted_for: str | None = None
    log: list = None                  # lista de (term, command)

    def last_log_index(self) -> int:
        return len(self.log or []) - 1

    def last_log_term(self) -> int:
        return self.log[-1][0] if self.log else 0

    def handle_request_vote(
        self,
        candidate_id: str,
        candidate_term: int,
        candidate_last_idx: int,
        candidate_last_term: int,
    ) -> tuple[int, bool]:
        # Rule 1: term antigo — recusa
        if candidate_term < self.current_term:
            return (self.current_term, False)

        # Rule 2: term maior — atualiza e volta a follower
        if candidate_term > self.current_term:
            self.current_term = candidate_term
            self.voted_for = None

        # Rule 3: já votou em outro candidato neste term — recusa
        if self.voted_for not in (None, candidate_id):
            return (self.current_term, False)

        # Rule 4: log do candidato é atualizado o suficiente?
        # "up-to-date": maior term vence; mesmo term → maior índice vence
        my_last_term = self.last_log_term()
        my_last_idx = self.last_log_index()
        log_ok = (
            candidate_last_term > my_last_term
            or (candidate_last_term == my_last_term and candidate_last_idx >= my_last_idx)
        )
        if not log_ok:
            return (self.current_term, False)

        # Concede voto
        self.voted_for = candidate_id
        return (self.current_term, True)

Uma vez eleito, o leader começa a atender clientes. Cada comando vira uma log entry (term + índice + comando). O protocolo é:

CLIENTE              LEADER                  FOLLOWERS (2+ em cluster de 5)
   │                    │                          │
   ├─ command ─────────►│                          │
   │                    │  1. Append ao seu log   │
   │                    │     (term=T, idx=I)      │
   │                    │                          │
   │                    ├─ AppendEntries(T,I,cmd) ►│  (em paralelo pra todos)
   │                    │                          ├─ Valida log consistency
   │                    │                          ├─ Append ao próprio log
   │                    │◄─── ACK ─────────────────┤
   │                    │                          │
   │                    │  2. Recebe ACK de maioria (quórum)
   │                    │                          │
   │                    │  3. commitIndex = I      │
   │                    │     aplica na state machine
   │                    │                          │
   │◄─ result ──────────┤                          │
   │                    │                          │
   │                    ├─ heartbeat (com commitIdx)►│
   │                    │                          ├─ followers aplicam entries
   │                    │                          │   committed na state machine

A RPC AppendEntries carrega (entre outros):

• term: term do leader
• prevLogIndex, prevLogTerm: o índice/term da entry imediatamente antes das novas — usado pra log matching
• entries[]: lista de entries novas
• leaderCommit: o commitIndex atual do leader

Mini-implementação do AppendEntries:

# append_entries.py — log replication do lado do follower
def handle_append_entries(
    node: RaftNode,
    leader_term: int,
    prev_log_idx: int,
    prev_log_term: int,
    entries: list,          # [(term, cmd), ...]
    leader_commit: int,
) -> tuple[int, bool]:
    # 1. Term antigo — rejeita
    if leader_term < node.current_term:
        return (node.current_term, False)

    # 2. Atualiza term se o leader tem term maior
    if leader_term > node.current_term:
        node.current_term = leader_term
        node.voted_for = None

    # 3. Reset election timer (recebeu heartbeat válido)
    node.reset_election_timer()

    # 4. Log matching check: prevLog precisa existir e bater
    log = node.log or []
    if prev_log_idx >= 0:
        if prev_log_idx >= len(log):
            return (node.current_term, False)  # log do follower é curto demais
        if log[prev_log_idx][0] != prev_log_term:
            return (node.current_term, False)  # term não bate — conflito

    # 5. Append entries (truncando conflitos, se houver)
    for i, (term, cmd) in enumerate(entries):
        idx = prev_log_idx + 1 + i
        if idx < len(log) and log[idx][0] != term:
            # conflito: trunca tudo a partir daqui
            log = log[:idx]
        if idx >= len(log):
            log.append((term, cmd))
    node.log = log

    # 6. Avança commitIndex até o min(leaderCommit, último índice local)
    if leader_commit > node.commit_index:
        node.commit_index = min(leader_commit, len(log) - 1)
        node.apply_committed_entries()

    return (node.current_term, True)

Essas 5 propriedades são provadas formalmente no paper original e verificadas em TLA+. Elas valem mesmo em cenários patológicos: crashes em rajada, partições assimétricas, reordenação de mensagens, máquinas congelando por minutos.

Se você usa Kubernetes, você já depende de Raft. Quando o etcd fica lento, seu API server responde 500. Quando o quórum do etcd quebra (2 de 3 nós mortos), o K8s vira read-only e depois morre. Entender Raft = entender o chão onde seu cluster anda.