Модуль 14 ⏱ ~34 мин чтения 📐 3 Mermaid диаграмм

3. Raft. Leader election

В прошлой статье 2. Raft. Основы мы разобрались с фундаментальным каркасом распределенного консенсуса: познакомились с тремя ролями узлов и увидели, как логическое время (Эпохи или Term) защищает распределенную систему от анархии. В нормальном режиме работы кластером безраздельно управляет Сильный Лидер (Strong Leader), а остальные узлы смиренно пребывают в роли Фолловеров, исполняя его команды и регулярно получая контрольные сигналы пульса (Heartbeat).

Но распределенные системы живут в суровом физическом мире, где серверы выключаются уборщицами, ядра Linux зависают в kernel panic, а сетевые коммутаторы внезапно делят стойку пополам. Что происходит, когда Лидер внезапно замолкает?

Как группа равноправных серверов, не имеющих общего диска, разделяемой оперативной памяти или внешнего арбитра, способна за доли секунды договориться и избрать нового единого лидера? Причем сделать это так, чтобы ни при каких условиях не расколоться на два враждующих лагеря?

Выборы в Raft — это шедевр инженерного прагматизма, основанный на таймаутах, теории вероятностей и строгом правиле большинства.

1. Анатомия выборов: От молчания к власти

Всё начинается с тревожной тишины.

У каждого Фолловера в кластере непрерывно тикает таймер ожидания — Election Timeout (Таймаут выборов). Пока действующий Лидер жив и находится в здравии, он с высокой частотой (обычно каждые 50–100 миллисекунд) рассылает пустые RPC-пакеты AppendEntries. Получая очередной Heartbeat, Фолловер убеждается, что центр управления на месте, и обнуляет свой таймер выборов.

Но вот питание стойки Лидера отключилось. Очередной пульс не пришел. Миллисекунды бегут, и таймер одного из Фолловеров доходит до нуля.

sequenceDiagram
    autonumber
    participant OldLeader as Старый Лидер (Упал)
    participant C as Фолловер -> Кандидат
    participant F1 as Фолловер 1
    participant F2 as Фолловер 2

    Note over OldLeader: Питание отключено
    Note over C: Истек Election Timeout!
    C->>C: Переход в Candidate<br/>Term = Term + 1 (Term 2)<br/>Голосует за себя (1/3)

    par Агитация (Fan-Out)
        C->>F1: RequestVote (Term=2, candidateId=C, lastLog...)
        C->>F2: RequestVote (Term=2, candidateId=C, lastLog...)
    end

    F1-->>C: VoteGranted: true (2/3 голоса)
    Note over C: Собрано большинство (Кворум 2 из 3)!

    C->>C: Провозглашает себя Лидером (Term 2)
    par Мгновенный пульс (Heartbeat)
        C->>F1: AppendEntries (Term=2, entries=[])
        C->>F2: AppendEntries (Term=2, entries=[])
    end
    F2-->>C: VoteGranted: true (или запоздалый ответ)

В этот момент запускается строгий конечный автомат:

  1. Смена роли: Фолловер разрывает пассивное ожидание и переходит в статус Кандидата (Candidate).
  2. Новая эпоха: Кандидат делает term++. Это торжественный манифест: «Предыдущая эпоха завершилась, я открываю выборы Терма $N+1$».
  3. Голос за себя: Кандидат незамедлительно отдает собственный голос самому себе (счетчик голосов votes = 1).
  4. Агитация (Broadcast): Кандидат параллельно рассылает RPC-сообщение RequestVote всем остальным узлам кластера, требуя признать его верховную власть.

У предвыборной кампании Кандидата есть ровно три возможных финала:

  • Триумф: Кандидат собирает голоса большинства узлов кластера, немедленно надевает корону Лидера и рассылает по сети подавляющий залп Heartbeat-сообщений, заставляя замолчать всех остальных претендентов.
  • Капитуляция: Во время ожидания ответов Кандидат получает AppendEntries от другого узла, чей Term больше или равен его текущему. Это означает, что кто-то другой уже победил на выборах. Кандидат признает поражение и покорно возвращается в статус Фолловера.
  • Ничья (Split Vote): Голоса избирателей разделились поровну (например, в кластере из 4 узлов два кандидата набрали по 2 голоса). Ни один не набрал кворум (3 голоса). По истечении таймера выборов раунд аннулируется, и начинается новый тур.

2. Mechanical Sympathy: Таймеры в рантайме Go

Таймаут выборов — сердце отказоустойчивости Raft. Однако неопытный инженер, проектирующий ноду на Go, легко может создать мину замедленного действия прямо в диспетчере событий узла.

Взгляните на типичный антипаттерн, который часто можно встретить в сырых реализациях:

Go 
// АНТИПАТТЕРН: Скрытая утечка памяти и деградация GC!
func (n *RaftNode) followerLoop() {
    for {
        select {
        case msg := <-n.rpcCh:
            n.handleRPC(msg)
            // Иллюзия: разработчик думает, что переход на следующую итерацию
            // "отменяет" предыдущий таймаут...
        case <-time.After(300 * time.Millisecond):
            n.becomeCandidate()
            return
        }
    }
}

Идиоматичный подход (Zero Allocation Timer Pattern)

Чтобы добиться максимальной предсказуемости и нуля мусорных аллокаций, необходимо использовать единственный постоянный time.Timer, корректно сбрасывая его состояние:

Go 
// ИДИОМАТИЧНЫЙ ПОДХОД: Эффективное переиспользование таймера
func (n *RaftNode) followerLoop() {
    timeout := n.randomElectionTimeout()
    timer := time.NewTimer(timeout)
    // Обязательно останавливаем таймер при завершении функции,
    // чтобы освободить слот в runtime.timers
    defer timer.Stop()

    for {
        select {
        case msg := <-n.rpcCh:
            n.handleRPC(msg)

            // Канонический алгоритм сброса таймера в Go
            if !timer.Stop() {
                // Если таймер уже сработал и тик отправлен в канал C,
                // вычитываем его, чтобы избежать ложного срабатывания
                select {
                case <-timer.C:
                default:
                }
            }
            timer.Reset(n.randomElectionTimeout())

        case <-timer.C:
            // Пульс не пришел вовремя — объявляем выборы!
            n.becomeCandidate()
            return
        }
    }
}

3. Проблема ничьей и магия Рандомизации

Представьте детерминированный мир. Кластер из 4 узлов. Лидер выходит из строя. У всех трех оставшихся серверов таймаут выборов сконфигурирован одинаково: ровно 200ms.

Что произойдет? Произойдет идеальная инженерная катастрофа:

  1. Ровно через 200.000 мс у всех трех серверов одновременно срабатывают таймеры.
  2. Все три сервера одновременно переходят в состояние Кандидатов, инкрементируют Терм до 2 и голосуют сами за себя.
  3. Каждый рассылает запрос RequestVote двум своим соседям.
  4. Но соседи уже проголосовали за себя в Терме 2! Они отклоняют чужие запросы (VoteGranted: false).
  5. Ни один узел не может набрать кворум (для 4 узлов кворум равен 3).
  6. Проходит еще 200 мс... и цикл повторяется снова! Терм 3, ничья. Терм 4, ничья.
flowchart TD
    classDef process  fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success  fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error    fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
    classDef warning  fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef entry    fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    classDef aux      fill:#334155,stroke:#64748b,stroke-width:1px,color:#f8fafc
    classDef system   fill:#312e81,stroke:#a78bfa,stroke-width:1px,color:#f8fafc
    classDef data     fill:#132d29,stroke:#2dd4bf,stroke-width:1px,color:#f8fafc
    classDef network  fill:#881337,stroke:#fb7185,stroke-width:1px,color:#f8fafc
    classDef accent   fill:#1e1b4b,stroke:#818cf8,stroke-width:1px,color:#f8fafc
    subgraph Livelock["Динамический паралич (Livelock) при фиксированных таймаутах"]
        T1["Все узлы ждут ровно 200 мс"]:::entry --> C1["Синхронный старт выборов (Term N)"]
        C1 --> V1["Каждый голосует за себя (1 голос у каждого)"]
        V1 --> S1["Split Vote: Кворум (3 из 4) не набран"]
        S1 --> T1
    end

Кластер попадает в классический Livelock (динамический тупик). Сеть гудит от сообщений, CPU загружен на 100%, алгоритм безупречно исполняется, но полезная работа равна нулю.

Диего Онгаро предложил гениальное по своей простоте лекарство: псевдослучайная рандомизация таймаутов выборов.

Вместо фиксированного значения таймаут выбирается случайно из диапазона $[T, 2T]$ (обычно от 150 до 300 мс):

$$\text{ElectionTimeout} \in [T, 2T]$$

TEXT 
Узел 1: [====== 165 ms ======] -> ПРОСНУЛСЯ! Стал Кандидатом, собрал голоса
Узел 2: [============== 240 ms ==============] -> Еще спит, голосует за Узел 1
Узел 3: [================== 295 ms ==================] -> Еще спит, голосует за Узел 1

Благодаря случайному разбросу один из узлов практически гарантированно проснется раньше конкурентов (например, через 165 мс, пока остальные планируют спать до 240 мс и 295 мс). Этот узел успеет объявить себя Кандидатом, отправить RPC и получить голоса пока еще спящих Фолловеров до того, как они вообще осознают факт исчезновения Лидера.

4. Защита от глупца: Election Restriction

Рандомизация спасает от ничьей, но порождает еще более опасную угрозу: риск потери данных.

Представьте сценарий: сервер Node-3 из-за локального сетевого сбоя отключился от кластера на 10 минут. Пока он был изолирован, Лидер и остальные узлы успешно обработали 100 000 финансовых транзакций. Затем сеть восстанавливается. У Node-3 истекает таймаут выборов. По воле генератора случайных чисел Node-3 выбирает таймаут 150 мс и просыпается раньше всех!

Неужели этот отставший узел с пустым логом станет новым Лидером и заставит весь кластер стереть 100 000 транзакций?

Raft категорически запрещает подобный сценарий с помощью правила Election Restriction (Ограничение на избрание).

В запросе RequestVote Кандидат обязан передать координаты окончания своего журнала:

  • LastLogIndex — порядковый номер последней записи в своем логе;
  • LastLogTerm — эпоха, в которой была создана эта последняя запись.

Фолловер, получив запрос на голосование, сопоставляет лог претендента со своим собственным:

  1. Сравнение эпох: Если LastLogTerm Кандидата меньше, чем LastLogTerm Фолловера, Кандидат безнадежно отстал от жизни. Отказ в голосе.
  2. Сравнение длины: Если LastLogTerm одинаковы, но LastLogIndex Кандидата меньше, чем у Фолловера, лог Кандидата короче. Отказ в голосе.
  3. Согласие: Только если лог Кандидата не менее актуален, чем собственный лог Фолловера, голос отдается.
flowchart TD
    classDef process  fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success  fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error    fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
    classDef warning  fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef entry    fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    classDef aux      fill:#334155,stroke:#64748b,stroke-width:1px,color:#f8fafc
    classDef system   fill:#312e81,stroke:#a78bfa,stroke-width:1px,color:#f8fafc
    classDef data     fill:#132d29,stroke:#2dd4bf,stroke-width:1px,color:#f8fafc
    classDef network  fill:#881337,stroke:#fb7185,stroke-width:1px,color:#f8fafc
    classDef accent   fill:#1e1b4b,stroke:#818cf8,stroke-width:1px,color:#f8fafc
    Start["Входящий RequestVote(candTerm, candIndex)"]:::warning --> TermCheck{"candLastLogTerm == myLastLogTerm?"}

    TermCheck -- "candTerm > myTerm" --> Grant["Дать голос (VoteGranted: true)"]
    TermCheck -- "candTerm < myTerm" --> Reject["Отказать (Кандидат отстал по эпохе)"]

    TermCheck -- "Равны" --> IndexCheck{"candLastLogIndex >= myLastLogIndex?"}
    IndexCheck -- "Да (лог не короче)" --> Grant
    IndexCheck -- "Нет (лог короче)" --> Reject

5. Go-реализация: Параллельный сбор голосов

Сетевые вызовы — медленные I/O-операции. Если опрашивать членов кластера последовательно в цикле for, общее время выборов превысит любые допустимые таймауты.

Кандидат обязан опрашивать всех пиров строго параллельно с использованием паттерна Fan-Out / Fan-In.

Ниже приведена чистая и безопасная реализация сбора голосов на Go:

Go 
package raft

import (
    "sync"
)

type RequestVoteArgs struct {
    Term         uint64
    CandidateID  string
    LastLogIndex uint64
    LastLogTerm  uint64
}

type RequestVoteReply struct {
    Term        uint64
    VoteGranted bool
}

func (n *RaftNode) startElection() {
    n.mu.Lock()
    n.term++
    n.state = Candidate
    n.votedFor = n.id // Голосуем за себя
    savedTerm := n.term
    n.mu.Unlock()

    votes := 1 // Собственный голос уже в кармане
    quorum := (len(n.peers) / 2) + 1

    // ВАЖНО: Буферизованный канал на полный размер кластера!
    // Это защищает горутины от зависания (Goroutine Leak) при досрочном выходе.
    voteCh := make(chan bool, len(n.peers))

    // Fan-Out: запускаем асинхронный опрос всех узлов
    for _, peerID := range n.peers {
        go func(id string) {
            req := RequestVoteArgs{
                Term:         savedTerm,
                CandidateID:  n.id,
                LastLogIndex: n.log.lastIndex(),
                LastLogTerm:  n.log.lastTerm(),
            }

            reply, err := n.rpcClient.SendRequestVote(id, req)
            if err != nil {
                voteCh <- false
                return
            }

            n.mu.Lock()
            defer n.mu.Unlock()

            // Если узел ответил Термом из будущего — немедленно капитулируем
            if reply.Term > n.term {
                n.becomeFollower(reply.Term)
                voteCh <- false
                return
            }

            voteCh <- reply.VoteGranted
        }(peerID)
    }

    // Fan-In: подсчет голосов по мере их поступления
    for i := 0; i < len(n.peers); i++ {
        if <-voteCh {
            votes++
        }

        n.mu.Lock()
        // Проверяем инвариант: пока мы ждали сеть, мы могли перестать быть кандидатом
        // (например, пришел Heartbeat от более авторитетного лидера)
        if n.state != Candidate || n.term != savedTerm {
            n.mu.Unlock()
            return
        }

        // Досрочная победа: кворум собран, не ждем медленных отстающих узлов!
        if votes >= quorum {
            n.becomeLeader()
            n.mu.Unlock()
            return
        }
        n.mu.Unlock()
    }
}

Итог

  1. Тишина порождает власть: Выборы в Raft инициируются отсутствием сетевых сигналов пульса от старого Лидера по истечении Election Timeout.
  2. Рандомизация уничтожает Livelock: Выбор случайного времени ожидания в интервале $[T, 2T]$ разбивает симметрию и позволяет одному кандидату успеть собрать большинство голосов без конкуренции.
  3. Election Restriction хранит историю: Отстающие узлы математически не могут стать лидерами благодаря валидации LastLogTerm и LastLogIndex кворумом.
  4. Zero-Allocation таймеры в Go: Использование одиночного time.Timer вместо разовых time.After внутри циклов предотвращает деградацию рантайма и всплески Stop-the-World пауз сборщика мусора.

Лидер триумфально избран и наделен абсолютной властью. Теперь перед ним встает главная задача: безопасно принимать команды от клиентов и распространять их по кластеру. О том, как устроен журнал репликации и как Лидер восстанавливает согласованность логов у заблудших Фолловеров, мы узнаем в следующей статье: 4. Raft. Log replication.