分布式共识算法：Raft与Paxos详解

前言

在分布式系统中，多个节点需要就某个值达成一致，这就是共识问题。共识算法是分布式系统的基石，无论是数据库的主从复制、配置中心的数据同步，还是分布式锁的实现，都依赖共识算法来保证一致性。本文将深入分析两个最重要的共识算法——Paxos 和 Raft，帮助你理解它们的核心原理和实际应用。

共识问题的本质

什么是共识

共识问题的形式化定义：在一个由 N 个节点组成的分布式系统中，即使部分节点发生故障，所有正常节点最终也要就某个提议值达成一致。

共识算法需要满足三个属性：

1. 一致性（Agreement）：所有正常节点决定的值相同
2. 有效性（Validity）：决定的值必须是某个节点提议的值
3. 终止性（Termination）：所有正常节点最终都能做出决定

FLP 不可能定理

Fischer、Lynch 和 Paterson 在 1985 年证明了：在异步网络模型中，即使只有一个节点可能崩溃，也不存在能保证终止性的确定性共识算法。

这意味着实际的共识算法都需要某种形式的妥协——通常是引入超时机制或随机化来绕过 FLP 限制。

Paxos 算法

基本概念

Paxos 由 Leslie Lamport 在 1990 年提出，是第一个被严格证明正确性的共识算法。它定义了三种角色：

• Proposer（提议者）：发起提议
• Acceptor（接受者）：参与投票，决定是否接受提议
• Learner（学习者）：学习最终被选定的值

graph LR
    P1[Proposer 1] --> A1[Acceptor 1]
    P1 --> A2[Acceptor 2]
    P1 --> A3[Acceptor 3]
    P2[Proposer 2] --> A1
    P2 --> A2
    P2 --> A3
    A1 --> L1[Learner 1]
    A2 --> L1
    A3 --> L1
    A1 --> L2[Learner 2]
    A2 --> L2
    A3 --> L2

Basic Paxos：两阶段协议

Phase 1: Prepare

Proposer 选择一个提案编号 n，向多数派 Acceptor 发送 Prepare(n) 请求。

Phase 2: Accept

如果 Proposer 收到多数派的 Promise 响应，它就发送 Accept(n, v) 请求。

sequenceDiagram
    participant P as Proposer
    participant A1 as Acceptor 1
    participant A2 as Acceptor 2
    participant A3 as Acceptor 3

    Note over P: Phase 1: Prepare
    P->>A1: Prepare(n=1)
    P->>A2: Prepare(n=1)
    P->>A3: Prepare(n=1)

    A1-->>P: Promise(n=1, 无已接受值)
    A2-->>P: Promise(n=1, 无已接受值)
    A3-->>P: Promise(n=1, 无已接受值)

    Note over P: 收到多数派Promise<br/>Phase 2: Accept
    P->>A1: Accept(n=1, v="X")
    P->>A2: Accept(n=1, v="X")
    P->>A3: Accept(n=1, v="X")

    A1-->>P: Accepted(n=1, v="X")
    A2-->>P: Accepted(n=1, v="X")
    A3-->>P: Accepted(n=1, v="X")

    Note over P: 值 "X" 被选定

竞争场景

当两个 Proposer 同时发起提议时，可能出现活锁（Livelock）。

sequenceDiagram
    participant P1 as Proposer 1
    participant A1 as Acceptor 1
    participant A2 as Acceptor 2
    participant A3 as Acceptor 3
    participant P2 as Proposer 2

    P1->>A1: Prepare(n=1)
    P1->>A2: Prepare(n=1)
    A1-->>P1: Promise(n=1)
    A2-->>P1: Promise(n=1)

    Note over P2: P2 使用更高编号
    P2->>A2: Prepare(n=2)
    P2->>A3: Prepare(n=2)
    A2-->>P2: Promise(n=2)
    A3-->>P2: Promise(n=2)

    P1->>A1: Accept(n=1, v="X")
    P1->>A2: Accept(n=1, v="X")
    A2-->>P1: Reject(已承诺n=2)

    Note over P1: 失败,使用更高编号n=3重试
    Note over P1,P2: 可能无限循环...活锁!

Multi-Paxos

Basic Paxos 每决定一个值需要两轮通信，效率太低。Multi-Paxos 通过选举一个稳定的 Leader 来优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

// Multi-Paxos Leader 的简化逻辑
type MultiPaxosNode struct {
    id          int
    isLeader    bool
    currentTerm int
    log         []LogEntry
    acceptors   []Acceptor
}

func (n *MultiPaxosNode) propose(value interface{}) error {
    if !n.isLeader {
        return ErrNotLeader
    }

    // Leader 已经完成了 Phase 1，可以直接进入 Phase 2
    entry := LogEntry{
        Index: len(n.log),
        Term:  n.currentTerm,
        Value: value,
    }

    // 向多数派发送 Accept 请求
    ackCount := 1 // 自己先接受
    for _, acceptor := range n.acceptors {
        if acceptor.Accept(n.currentTerm, entry) {
            ackCount++
        }
    }

    if ackCount > len(n.acceptors)/2 {
        n.log = append(n.log, entry)
        // 通知所有 Learner
        n.notifyLearners(entry)
        return nil
    }
    return ErrNotEnoughAcks
}

Raft 算法

设计理念

Raft 由 Diego Ongaro 和 John Ousterhout 在 2014 年提出，其核心目标是可理解性。Raft 将共识问题分解为三个相对独立的子问题：

1. Leader Election（领导者选举）
2. Log Replication（日志复制）
3. Safety（安全性保证）

节点状态

Raft 中每个节点有三种状态：

stateDiagram-v2
    [*] --> Follower
    Follower --> Candidate: 选举超时<br/>未收到心跳
    Candidate --> Leader: 获得多数票
    Candidate --> Follower: 发现更高任期的Leader
    Candidate --> Candidate: 选举超时<br/>重新选举
    Leader --> Follower: 发现更高任期

Leader Election

sequenceDiagram
    participant F1 as Node A<br/>(Follower)
    participant C as Node B<br/>(Candidate)
    participant F2 as Node C<br/>(Follower)
    participant F3 as Node D<br/>(Follower)
    participant F4 as Node E<br/>(Follower)

    Note over C: 选举超时,转为Candidate<br/>term: 1 → 2
    C->>C: 投票给自己
    C->>F1: RequestVote(term=2)
    C->>F2: RequestVote(term=2)
    C->>F3: RequestVote(term=2)
    C->>F4: RequestVote(term=2)

    F1-->>C: VoteGranted(term=2)
    F2-->>C: VoteGranted(term=2)
    F3-->>C: VoteGranted(term=2)

    Note over C: 获得4票(含自己)<br/>成为Leader

    loop 心跳
        C->>F1: AppendEntries(heartbeat)
        C->>F2: AppendEntries(heartbeat)
        C->>F3: AppendEntries(heartbeat)
        C->>F4: AppendEntries(heartbeat)
    end

选举超时的随机化是 Raft 避免分票（split vote）的关键机制。每个 Follower 的选举超时时间在 150ms-300ms 之间随机选择。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

// Raft 节点核心结构
type RaftNode struct {
    mu          sync.Mutex
    id          int
    state       NodeState
    currentTerm int
    votedFor    int
    log         []LogEntry
    commitIndex int
    lastApplied int

    // Leader 专属
    nextIndex   []int
    matchIndex  []int

    // 选举相关
    electionTimeout  time.Duration
    heartbeatTimeout time.Duration
    electionTimer    *time.Timer
}

func (rn *RaftNode) startElection() {
    rn.mu.Lock()
    rn.state = Candidate
    rn.currentTerm++
    rn.votedFor = rn.id
    currentTerm := rn.currentTerm
    lastLogIndex := len(rn.log) - 1
    lastLogTerm := 0
    if lastLogIndex >= 0 {
        lastLogTerm = rn.log[lastLogIndex].Term
    }
    rn.mu.Unlock()

    votes := 1 // 自己的一票
    var voteMu sync.Mutex

    for _, peer := range rn.peers {
        go func(p *Peer) {
            reply := p.RequestVote(&RequestVoteArgs{
                Term:         currentTerm,
                CandidateId:  rn.id,
                LastLogIndex: lastLogIndex,
                LastLogTerm:  lastLogTerm,
            })

            if reply.VoteGranted {
                voteMu.Lock()
                votes++
                if votes > len(rn.peers)/2 && rn.state == Candidate {
                    rn.becomeLeader()
                }
                voteMu.Unlock()
            } else if reply.Term > currentTerm {
                rn.becomeFollower(reply.Term)
            }
        }(peer)
    }
}

Log Replication

Leader 收到客户端请求后，将命令追加到本地日志，然后并行复制给所有 Follower。当多数派确认后，该日志条目被提交（committed）。

sequenceDiagram
    participant Client
    participant Leader
    participant F1 as Follower 1
    participant F2 as Follower 2
    participant F3 as Follower 3
    participant F4 as Follower 4

    Client->>Leader: SET x=5
    Note over Leader: 追加到本地日志<br/>index=3, term=2

    par 并行复制
        Leader->>F1: AppendEntries(index=3, SET x=5)
        Leader->>F2: AppendEntries(index=3, SET x=5)
        Leader->>F3: AppendEntries(index=3, SET x=5)
        Leader->>F4: AppendEntries(index=3, SET x=5)
    end

    F1-->>Leader: Success
    F2-->>Leader: Success
    F3-->>Leader: Success

    Note over Leader: 3个Follower确认<br/>加上自己共4个<br/>多数派确认,提交!

    Leader->>Leader: Apply to State Machine
    Leader-->>Client: OK

    Note over Leader: 下次心跳通知Follower提交
    Leader->>F1: AppendEntries(commitIndex=3)
    Leader->>F2: AppendEntries(commitIndex=3)
    Leader->>F3: AppendEntries(commitIndex=3)
    Leader->>F4: AppendEntries(commitIndex=3)

Safety 保证

Raft 的安全性核心保证是 Leader Completeness Property：如果某个日志条目在给定任期内被提交，那么更高任期的 Leader 一定包含该条目。

这通过 投票限制 来实现：Candidate 在 RequestVote 中携带自己最后一条日志的信息，Follower 只给日志至少和自己一样新的 Candidate 投票。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

func (rn *RaftNode) handleRequestVote(args *RequestVoteArgs) *RequestVoteReply {
    rn.mu.Lock()
    defer rn.mu.Unlock()

    reply := &RequestVoteReply{Term: rn.currentTerm}

    // 拒绝旧任期的请求
    if args.Term < rn.currentTerm {
        reply.VoteGranted = false
        return reply
    }

    // 检查是否已投票
    if rn.votedFor != -1 && rn.votedFor != args.CandidateId {
        reply.VoteGranted = false
        return reply
    }

    // 安全性检查：Candidate 的日志必须至少和自己一样新
    lastIndex := len(rn.log) - 1
    lastTerm := 0
    if lastIndex >= 0 {
        lastTerm = rn.log[lastIndex].Term
    }

    logOk := args.LastLogTerm > lastTerm ||
        (args.LastLogTerm == lastTerm && args.LastLogIndex >= lastIndex)

    if logOk {
        rn.votedFor = args.CandidateId
        reply.VoteGranted = true
        rn.resetElectionTimer()
    }

    return reply
}

Paxos vs Raft 对比

实际应用

etcd（使用 Raft）

etcd 是 Kubernetes 的底层存储，使用 Raft 实现数据一致性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# etcd 集群配置
etcd:
  name: node1
  initial-cluster: >
    node1=https://10.0.0.1:2380,
    node2=https://10.0.0.2:2380,
    node3=https://10.0.0.3:2380
  initial-cluster-state: new
  listen-peer-urls: https://10.0.0.1:2380
  listen-client-urls: https://10.0.0.1:2379
  # Raft 相关参数
  heartbeat-interval: 100    # 心跳间隔 100ms
  election-timeout: 1000     # 选举超时 1000ms
  snapshot-count: 10000      # 每 10000 条日志做一次快照

1
2
3
4
5
6
7
8
9

# 查看 etcd 集群中的 Raft 状态
etcdctl endpoint status --write-out=table
# +------------------+------------------+---------+---------+-----------+
# |     ENDPOINT     |        ID        | VERSION | DB SIZE | IS LEADER |
# +------------------+------------------+---------+---------+-----------+
# | 10.0.0.1:2379    | 8e9e05c52164694d |  3.5.0  |   20 kB |      true |
# | 10.0.0.2:2379    | 4e2e05c52164694e |  3.5.0  |   20 kB |     false |
# | 10.0.0.3:2379    | 6f3e05c52164694f |  3.5.0  |   20 kB |     false |
# +------------------+------------------+---------+---------+-----------+

ZooKeeper（使用 ZAB）

ZooKeeper 使用 ZAB（ZooKeeper Atomic Broadcast）协议，它是 Paxos 的变种，针对主备模式进行了优化。

sequenceDiagram
    participant Client
    participant Leader as ZK Leader
    participant F1 as ZK Follower 1
    participant F2 as ZK Follower 2

    Client->>Leader: create /config/db_url
    Note over Leader: 生成 zxid<br/>epoch.counter

    Leader->>F1: Proposal(zxid, data)
    Leader->>F2: Proposal(zxid, data)

    F1-->>Leader: ACK
    F2-->>Leader: ACK

    Note over Leader: 多数派ACK,提交

    Leader->>F1: Commit(zxid)
    Leader->>F2: Commit(zxid)
    Leader-->>Client: OK

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

// ZooKeeper 客户端使用 Curator 框架
CuratorFramework client = CuratorFrameworkFactory.builder()
    .connectString("zk1:2181,zk2:2181,zk3:2181")
    .sessionTimeoutMs(5000)
    .retryPolicy(new ExponentialBackoffRetry(1000, 3))
    .build();
client.start();

// 分布式锁 - 基于 ZooKeeper 的临时顺序节点
InterProcessMutex lock = new InterProcessMutex(client, "/locks/order");
try {
    if (lock.acquire(10, TimeUnit.SECONDS)) {
        // 临界区操作
        processOrder(orderId);
    }
} finally {
    lock.release();
}

// Leader 选举
LeaderSelector selector = new LeaderSelector(client, "/leader/election",
    new LeaderSelectorListenerAdapter() {
        @Override
        public void takeLeadership(CuratorFramework client) throws Exception {
            System.out.println("I am the leader now!");
            // 执行 Leader 职责，方法返回则放弃 Leadership
            Thread.sleep(Long.MAX_VALUE);
        }
    });
selector.autoRequeue();
selector.start();

工程实践建议

集群规模

共识算法要求多数派确认，因此集群节点数推荐为奇数（3、5、7）：

• 3 节点：容忍 1 个故障，适合大多数场景
• 5 节点：容忍 2 个故障，适合高可用要求的生产环境
• 7 节点：容忍 3 个故障，极少使用，写入延迟增大

性能优化

graph TB
    subgraph 优化手段
        A[Batch 批量提交] --> D[减少网络往返]
        B[Pipeline 流水线] --> D
        C[Learner 只读副本] --> E[分担读压力]
        F[PreVote 预投票] --> G[减少不必要选举]
        H[快照压缩] --> I[减少日志大小]
    end

1. Batch：将多个客户端请求合并为一次 Raft 日志提交
2. Pipeline：Leader 不等待上一个 AppendEntries 的响应就发送下一个
3. Read Index / Lease Read：优化只读请求，避免走完整的 Raft 流程
4. PreVote：在正式发起选举前先预投票，避免网络分区恢复后的无谓选举

总结

共识算法是分布式系统的核心基石。Paxos 奠定了理论基础但工程实现困难，Raft 通过分解问题和强 Leader 模型让共识算法变得可理解和可实现。在实际选型中，Raft 已经成为事实标准，被 etcd、Consul、TiKV、CockroachDB 等系统广泛采用。理解这些算法的原理，对于设计和运维分布式系统至关重要。