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

2. Raft. Основы

В статье 1. Зачем нужен consensus мы выяснили суровую истину распределенных систем: без математически строгого алгоритма согласования любой распределенный кластер неизбежно развалится на изолированные конфликтующие части (Split-Brain) при первом же кабеле, перекушенном экскаватором, или кратковременном сетевом сбое.

Долгое время непререкаемым авторитетом в теории распределенных вычислений оставался алгоритм Paxos, предложенный Лесли Лэмпортом в 1989 году (опубликован в 1998 г. в легендарной работе "The Part-Time Parliament"). Paxos был математически безупречен, лаконичен и... практически непостижим для рядовых инженеров.

Создатели Google Chubby (сервиса блокировок на основе Paxos) в знаменитой статье 2007 года констатировали: между строгим математическим описанием алгоритма Paxos и требованиями реальной промышленной отказоустойчивой системы лежит непреодолимая пропасть. Реализация Paxos обрастала сотнями нетривиальных краевых условий. Каждый раз, когда инженеры брались писать код, на свет появлялся новый, закрытый и несовместимый с другими «диалект».

В 2013–2014 годах Диего Онгаро и Джон Оустерхаут из Стэнфордского университета опубликовали революционную работу: "In Search of an Understandable Consensus Algorithm". Их целью было не превзойти Paxos по теоретической пропускной способности, а создать алгоритм, который человеческий мозг способен понять и безошибочно запрограммировать.

Так родился Raft.

Сегодня Raft — безоговорочный де-факто стандарт в современной облачной инфраструктуре. На нем построены:

  • etcd — распределенное хранилище метаданных и «мозг» всей платформы Kubernetes;
  • Consul и Nomad от HashiCorp — фундамент service discovery и оркестрации тысяч enterprise-кластеров;
  • Распределенные NewSQL-базы данных (CockroachDB, TiDB), где Raft реплицирует диапазоны данных (Range Groups);
  • Стриминговые платформы нового поколения (Redpanda), заменившие связку Kafka + ZooKeeper на единый бинарник с собственным движком на Raft.

И самое отрадное для нас: эталонные, наиболее надежные и производительные реализации Raft в мире написаны именно на языке Go (go.etcd.io/raft и hashicorp/raft).

Декомпозиция сложности

Главная архитектурная инновация Raft заключается не в открытии новых законов физики, а в мудрой декомпозиции. Вместо того чтобы пытаться решить задачу консенсуса единым монолитным математическим уравнением, создатели Raft разделили ее на три независимые и доступные для рассуждения подзадачи:

  1. Leader Election (Выбор лидера): Кластер обязан в любой момент иметь ровно одного полномочного лидера. Если лидер падает или изолируется, оставшиеся узлы обязаны согласованно и быстро выбрать нового вожака.
  2. Log Replication (Репликация журнала): Лидер принимает команды записи от клиентов, прикрепляет их к своему журналу (Append-Only Log) и распространяет среди фолловеров так, чтобы каждый узел применил команды в строго одинаковом порядке.
  3. Safety (Безопасность и целостность): Железная гарантия того, что если какой-либо узел применил запись лога с определенным индексом к своему конечному автомату (State Machine, например базе данных key-value), ни один другой узел кластера никогда не применит другую команду на том же самом индексе лога.
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 RaftAlgorithm["Архитектурная триада Raft"]
        E["1. Leader Election<br/>Выбор единственного лидера"]:::warning --> R["2. Log Replication<br/>Однонаправленный поток команд"]
        R --> S["3. Safety Guarantees<br/>Инварианты целостности стейт-машины"]
    end

В этой статье мы заложим фундамент: разберем жизненный цикл узла, три ключевые роли, концепцию логического времени и сетевые RPC-протоколы.

1. Роли узлов (Server States)

Raft исповедует парадигму Сильного Лидера (Strong Leader). В нормальном режиме работы все решения принимаются централизованно. Клиенты не могут писать произвольным узлам (как в безлидерных AP-системах вроде Apache Cassandra или Amazon Dynamo, где неизбежно возникают конфликты версий и необходимость согласования по часам или векторным таймстампам). В Raft поток изменений строго однонаправлен: от Лидера к Фолловерам.

В любой момент времени каждый процесс (Go-нода) находится ровно в одном из трех состояний:

  • Фолловер (Follower — Ведомый): Абсолютно пассивное состояние. Узел не инициирует сетевых запросов самостоятельно; он лишь молча слушает входящие RPC от Лидера или Кандидатов и отвечает на них. Если клиент по ошибке присылает запрос на запись (например, HTTP POST или gRPC-вызов) Фолловеру, тот либо возвращает ошибку с адресом действующего Лидера, либо прозрачно проксирует запрос Лидеру.
  • Кандидат (Candidate — Претендент): Промежуточное кратковременное состояние. Если Фолловер в течение установленного таймаута не получает никаких вестей от Лидера, он заключает, что лидер погиб или изолирован, провозглашает себя Кандидатом, инкрементирует счетчик эпохи и объявляет досрочные выборы.
  • Лидер (Leader — Вожак): Полномочный правитель кластера. Принимает клиентские операции записи, генерирует записи лога, координирует их репликацию на фолловеры и с периодичностью в десятки миллисекунд отправляет контрольные сигналы пульса (Heartbeats), сообщая: «Я жив, выборы начинать запрещено!».
stateDiagram-v2
    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
    [*] --> Follower: Старт процесса

    Follower --> Candidate: Таймаут ожидания пульса Лидера
    Candidate --> Leader: Получен Кворум голосов (N/2 + 1)

    Leader --> Follower: Обнаружен узел с бОльшим Term
    Candidate --> Follower: Обнаружен легитимный Лидер или больший Term
    Candidate --> Candidate: Ничья на выборах (таймаут истек, новый тур)

Обратите внимание на симметрию переходов: любой узел — будь то зазнавшийся Кандидат или правящий Лидер — мгновенно и беспрекословно капитулирует и возвращается в роль смиренного Фолловера, как только видит в сети сообщение с номером эпохи выше своего собственного.

2. Эпохи (Terms) — Логическое время Raft

В статье 5. Time и clock drift мы детально разбирали, почему физическим часам серверов (кварцевым генераторам и протоколу NTP) категорически нельзя доверять в задачах упорядочивания распределенных событий. Дрифт таймеров и прыжки времени способны мгновенно разрушить логику транзакций.

Raft элегантно решает эту дилемму, опираясь исключительно на Логические часы (вариацию часов Лэмпорта). В терминологии Raft это дискретное время называется Term (Эпоха или Срок правления).

DIAGRAM 
         ┌─────────────────────────────────────────────────────────────┐
Term 1   │ Лидер A правит, реплицирует лог ... (сбой Лидера A)        │
         └─────────────────────────────────────────────────────────────┘
                                        ▼ (Выборы нового лидера)
         ┌─────────────────────────────────────────────────────────────┐
Term 2   │ Кандидат B избран лидером, правит кластером ...              │
         └─────────────────────────────────────────────────────────────┘
                                        ▼ (Разделение голосов / Split Vote)
         ┌─────────────────────────────────────────────────────────────┐
Term 3   │ Ничья: никто не набрал кворума, выборы провалены            │
         └─────────────────────────────────────────────────────────────┘
                                        ▼ (Новый тур выборов)
         ┌─────────────────────────────────────────────────────────────┐
Term 4   │ Кандидат C избран лидером, нормальная работа                │
         └─────────────────────────────────────────────────────────────┘

Каждая эпоха обозначается строго монотонно возрастающим 64-битным беззнаковым целым числом (uint64). Каждые выборы начинаются с обязательного инкремента Терма.

Каждый узел обязан непрерывно хранить значение текущей эпохи (currentTerm) в энергонезависимой памяти на диске и прикреплять его к абсолютно каждому сетевому сообщению (RPC-запросу или ответу).

Золотые правила Термов в Raft:

  1. Обновление при встрече с будущим: Если узел получает сетевое сообщение с term, который строго больше его локального currentTerm, он немедленно перезаписывает свой currentTerm = msg.Term и сбрасывает свое состояние до Фолловера.
  2. Игнорирование вестей из прошлого: Если узел получает запрос от узла со старым term < currentTerm, этот запрос немедленно отклоняется.
  3. Один лидер на эпоху: В рамках одного конкретного Терма может быть избран максимум один Лидер (или ни одного, если голоса разделились поровну). Два лидера с одинаковым номером эпохи существовать не могут математически, так как для победы требуется строгое большинство голосов.

Это элегантнейшее правило автоматически нейтрализует коварную проблему «зомби-лидеров» при исцелении сетевых разделений.

3. Коммуникация (RPC)

Гениальная простота спецификации Raft видна в ее интерфейсе взаимодействия: для реализации консенсуса, репликации и управления кластером узлам требуется всего два базовых типа RPC-вызовов (обычно упакованных в Protobuf и передаваемых поверх gRPC или кастомных TCP-сокетов):

  1. RequestVote RPC:
    Инициируется исключительно Кандидатами во время предвыборной кампании. Кандидат обращается ко всем остальным узлам кластера с аргументами (candidateId, term, lastLogIndex, lastLogTerm) и просит отдать за него свой голос.
  2. AppendEntries RPC:
    Инициируется исключительно действующим Лидером. Этот метод выполняет сразу две фундаментальные функции:
    • Репликация данных: Передача пачки новых записей лога фолловерам для синхронизации состояния.
    • Пульс кластера (Heartbeat): Если новых команд от клиентов нет, Лидер с регулярным интервалом рассылает пустой AppendEntries (где срез записей пуст). Получив такой сигнал, Фолловеры убеждаются, что Лидер жив и работоспособен, и перезапускают свои таймеры выборов.
sequenceDiagram
    autonumber
    actor Client as Клиент
    participant L as Лидер (Term 2)
    participant F1 as Фолловер 1
    participant F2 as Фолловер 2

    Note over L,F2: Периодический Heartbeat (AppendEntries без записей)
    L->>F1: AppendEntries (term=2, entries=[])
    L->>F2: AppendEntries (term=2, entries=[])
    F1-->>L: Success: true
    F2-->>L: Success: true

    Note over Client,L: Поступление команды на запись
    Client->>L: HTTP POST /set (k="name", v="gopher")
    L->>L: Запись в локальный WAL

    Note over L,F2: Репликация данных (AppendEntries с записями)
    L->>F1: AppendEntries (term=2, entries=[SET name=gopher])
    L->>F2: AppendEntries (term=2, entries=[SET name=gopher])
    F1-->>L: Success: true
    F2-->>L: Success: true

    Note over L: Кворум достигнут (3/3 подтвердили)
    L->>L: Apply to State Machine
    L-->>Client: HTTP 200 OK (committed)

Mechanical Sympathy: Raft Node в рантайме Go

Как концепция математического конечного автомата проецируется на идиоматичные конструкции Go — горутины, каналы и планировщик?

В промышленном коде управления состоянием узла часто используется паттерн Actor / Single-Threaded Event Loop. Вся внутренняя мутация структур ноды выполняется строго внутри одной управляющей горутины через цикл с конструкцией select. Это избавляет кодовую базу от ада распределенных мьютексов (sync.Mutex), защищая код от взаимных блокировок (Deadlocks) и дорогостоящей конкуренции за кэш-линии процессора (Cache Line Bouncing).

Взглянем на скелет управляющего цикла ноды:

Go 
package raft

import (
    "context"
    "time"
)

type State int

const (
    Follower State = iota
    Candidate
    Leader
)

type Entry struct {
    Index uint64
    Term  uint64
    Data  []byte
}

type AppendEntriesMsg struct {
    Term     uint64
    LeaderID string
    Entries  []Entry
    RespCh   chan bool
}

type RequestVoteMsg struct {
    Term        uint64
    CandidateID string
    RespCh      chan bool
}

type RaftNode struct {
    state State
    term  uint64
    log   []Entry

    // Каналы для приема входящих RPC-сообщений
    appendEntriesCh chan AppendEntriesMsg
    requestVoteCh   chan RequestVoteMsg

    heartbeatInterval time.Duration
    electionTimeout   time.Duration
}

func (n *RaftNode) Run(ctx context.Context) {
    // Внимание: для предотвращения утечек памяти в долгоживущих циклах
    // создаем таймер явно, а не дергаем time.After() на каждой итерации
    electionTimer := time.NewTimer(n.randomElectionTimeout())
    defer electionTimer.Stop()

    for {
        select {
        case <-ctx.Done():
            return

        // Обработка AppendEntries от Лидера (данные или Heartbeat)
        case msg := <-n.appendEntriesCh:
            n.handleAppendEntries(msg)
            // Сброс таймера выборов при получении валидного пульса
            n.resetTimer(electionTimer, n.randomElectionTimeout())

        // Обработка предвыборных запросов голоса
        case msg := <-n.requestVoteCh:
            n.handleRequestVote(msg)

        // Срабатывание таймера выборов (лидер замолчал)
        case <-electionTimer.C:
            if n.state == Follower || n.state == Candidate {
                // Увеличиваем Терм, голосуем за себя, рассылаем RequestVote
                n.becomeCandidate()
            }
            n.resetTimer(electionTimer, n.randomElectionTimeout())
        }
    }
}

func (n *RaftNode) resetTimer(t *time.Timer, d time.Duration) {
    if !t.Stop() {
        select {
        case <-t.C:
        default:
        }
    }
    t.Reset(d)
}

func (n *RaftNode) randomElectionTimeout() time.Duration {
    // В реальном коде рандомизация предотвращает разделение голосов (Livelock)
    return n.electionTimeout
}

func (n *RaftNode) handleAppendEntries(msg AppendEntriesMsg) {
    // Если входящий Терм больше нашего — признаем нового лидера
    if msg.Term > n.term {
        n.term = msg.Term
        n.state = Follower
    }
    msg.RespCh <- true
}

func (n *RaftNode) handleRequestVote(msg RequestVoteMsg) {
    // Логика проверки актуальности лога и Терма кандидата
    msg.RespCh <- true
}

func (n *RaftNode) becomeCandidate() {
    n.state = Candidate
    n.term++
}

4. Подводные камни и сетевые ловушки

Итог

  1. Raft принес в индустрию долгожданную ясность: он декомпозировал мистику распределенного консенсуса на понятные кирпичики — выбор лидера, репликацию лога и сохранение безопасности.
  2. Архитектура держится на трех китах:
    • Сильный Лидер (Strong Leader): Централизованная точка упорядочивания операций без междоусобных конфликтов.
    • Логические эпохи (Terms): Монотонные счетчики времени, защищающие кластер от старых лидеров и рассинхронизации.
    • Кворум большинства ($N/2 + 1$): Базовое математическое свойство непересекающихся множеств, исключающее возникновение двух лидеров.
  3. Простая система коммуникации всего из двух типов RPC — RequestVote и AppendEntries — обеспечивает как синхронизацию данных, так и контроль жизнеспособности узлов.

Мы заложили фундаментальный каркас. Но как именно Кандидат собирает голоса? Почему таймауты выборов (randomElectionTimeout) обязаны быть псевдослучайными, и что произойдет, если разработчик забудет инициализировать генератор случайных чисел math/rand? Об этом — в следующей статье: 3. Raft. Leader election.