Raft共识算法详解

约 2014 字大约 7 分钟

distributedraftconsensus

2025-05-23

概述

Raft是由Diego Ongaro和John Ousterhout在2014年提出的一种分布式共识算法。它的设计目标是比Paxos更容易理解和实现，同时提供与Paxos等价的安全性保证。Raft已被广泛应用于etcd、Consul、TiKV、CockroachDB等生产系统中。

核心概念

Raft将共识问题分解为三个相对独立的子问题：

Leader选举（Leader Election）
日志复制（Log Replication）
安全性（Safety）

节点角色

Leader：处理所有客户端请求，负责日志复制
Follower：被动响应Leader和Candidate的请求
Candidate：在选举期间请求其他节点投票

任期（Term）

Raft将时间划分为连续的任期，每个任期以一次选举开始。任期号是Raft中的逻辑时钟。

Leader选举

选举流程

选举超时

为避免多个节点同时发起选举导致分票，每个节点的选举超时时间是随机的（通常150-300ms）。

// Raft选举超时的实现
func (rf *Raft) electionTimeout() time.Duration {
    // 基础超时 + 随机偏移
    base := 150 * time.Millisecond
    jitter := time.Duration(rand.Int63n(150)) * time.Millisecond
    return base + jitter
}

func (rf *Raft) runElectionTimer() {
    timeout := rf.electionTimeout()
    rf.mu.Lock()
    termStarted := rf.currentTerm
    rf.mu.Unlock()

    ticker := time.NewTicker(10 * time.Millisecond)
    defer ticker.Stop()

    for {
        <-ticker.C
        rf.mu.Lock()
        // 如果角色变了或任期变了，退出
        if rf.state != Follower && rf.state != Candidate {
            rf.mu.Unlock()
            return
        }
        if rf.currentTerm != termStarted {
            rf.mu.Unlock()
            return
        }
        // 检查是否超时
        if time.Since(rf.lastHeartbeat) >= timeout {
            rf.startElection()
            rf.mu.Unlock()
            return
        }
        rf.mu.Unlock()
    }
}

投票规则

节点在收到RequestVote请求时，按以下规则决定是否投票：

func (rf *Raft) handleRequestVote(args *RequestVoteArgs, reply *RequestVoteReply) {
    rf.mu.Lock()
    defer rf.mu.Unlock()

    reply.Term = rf.currentTerm

    // 规则1: 拒绝任期比自己低的请求
    if args.Term < rf.currentTerm {
        reply.VoteGranted = false
        return
    }

    // 如果发现更高的任期，更新自己的任期并转为Follower
    if args.Term > rf.currentTerm {
        rf.currentTerm = args.Term
        rf.state = Follower
        rf.votedFor = -1
    }

    // 规则2: 每个任期只能投一票
    if rf.votedFor != -1 && rf.votedFor != args.CandidateId {
        reply.VoteGranted = false
        return
    }

    // 规则3: Candidate的日志必须至少和自己一样新（选举限制）
    lastLogIndex := len(rf.log) - 1
    lastLogTerm := rf.log[lastLogIndex].Term
    if args.LastLogTerm < lastLogTerm ||
        (args.LastLogTerm == lastLogTerm && args.LastLogIndex < lastLogIndex) {
        reply.VoteGranted = false
        return
    }

    // 同意投票
    reply.VoteGranted = true
    rf.votedFor = args.CandidateId
    rf.lastHeartbeat = time.Now()
}

日志复制

Leader接收客户端请求，将其作为新日志条目追加到本地日志，然后通过AppendEntries RPC并行发送给所有Follower。

日志结构

Leader的日志:
+-------+-------+-------+-------+-------+-------+
| idx=1 | idx=2 | idx=3 | idx=4 | idx=5 | idx=6 |
| term=1| term=1| term=2| term=2| term=3| term=3|
| set a | set b | set c | del a | set d | set x |
+-------+-------+-------+-------+-------+-------+
                          ↑ commitIndex=4

日志一致性检查

AppendEntries RPC包含前一条日志的索引和任期号（prevLogIndex, prevLogTerm），Follower通过比对来确保日志的一致性：

func (rf *Raft) handleAppendEntries(args *AppendEntriesArgs, reply *AppendEntriesReply) {
    rf.mu.Lock()
    defer rf.mu.Unlock()

    reply.Term = rf.currentTerm
    reply.Success = false

    if args.Term < rf.currentTerm {
        return
    }

    rf.lastHeartbeat = time.Now()

    // 一致性检查
    if args.PrevLogIndex >= len(rf.log) {
        // 日志太短，无法匹配
        reply.ConflictIndex = len(rf.log)
        return
    }

    if rf.log[args.PrevLogIndex].Term != args.PrevLogTerm {
        // 任期不匹配，需要回退
        conflictTerm := rf.log[args.PrevLogIndex].Term
        // 优化：快速回退到冲突任期的第一条日志
        for i := args.PrevLogIndex; i >= 0; i-- {
            if rf.log[i].Term != conflictTerm {
                reply.ConflictIndex = i + 1
                break
            }
        }
        return
    }

    // 匹配成功，追加新日志
    rf.log = append(rf.log[:args.PrevLogIndex+1], args.Entries...)
    reply.Success = true

    // 更新commitIndex
    if args.LeaderCommit > rf.commitIndex {
        rf.commitIndex = min(args.LeaderCommit, len(rf.log)-1)
    }
}

安全性保证

选举限制

Raft通过选举限制（Election Restriction）确保新Leader一定包含所有已提交的日志：Candidate的日志必须至少和投票者的日志一样新。"更新"的定义是：最后一条日志的任期更大，或任期相同但索引更大。

提交规则

Leader只能提交当前任期的日志条目。对于之前任期的日志，只能通过提交当前任期的新日志条目来间接提交。

成员变更

集群成员变更（增加或减少节点）需要特殊处理，避免出现两个Leader的脑裂情况。

单节点变更（推荐）

etcd和Consul采用的方式，每次只增加或减少一个节点：

Joint Consensus（联合共识）

Raft论文中描述的方式，支持同时变更多个节点：

Leader创建 C_old,new 配置日志，需要新旧两个配置的多数派确认
C_old,new 提交后，创建 C_new 配置日志
C_new 提交后，变更完成

日志压缩（Snapshot）

随着运行时间增长，日志会无限增长。Raft使用快照（Snapshot）来压缩已提交的日志：

type Snapshot struct {
    LastIncludedIndex int    // 快照覆盖到的最后日志索引
    LastIncludedTerm  int    // 该日志条目的任期
    Data              []byte // 状态机快照数据
}

func (rf *Raft) takeSnapshot(lastIndex int, data []byte) {
    rf.mu.Lock()
    defer rf.mu.Unlock()

    snapshot := Snapshot{
        LastIncludedIndex: lastIndex,
        LastIncludedTerm:  rf.log[lastIndex].Term,
        Data:              data,
    }
    // 丢弃已包含在快照中的日志
    rf.log = rf.log[lastIndex:]
    rf.persister.SaveSnapshot(snapshot)
}

线性一致性读

默认情况下，所有读写请求都经过Leader处理。但在Leader刚选举成功时，可能存在过时的已提交日志，需要特殊处理：

ReadIndex方案

Lease Read方案

基于Leader租约的优化，在租约期内无需发送额外的心跳：

如果Leader在 heartbeatInterval 内收到了多数派的心跳响应，
那么在接下来的 electionTimeout - heartbeatInterval 时间内，
可以安全地处理读请求而无需再次确认Leader身份。

实际应用

系统	用途	Raft实现特点
etcd	KV存储/服务发现	标准Raft, ReadIndex/LeaseRead
Consul	服务网格	HashiCorp Raft库
TiKV	分布式KV存储	Multi-Raft（每个Region一个Raft组）
CockroachDB	NewSQL数据库	Multi-Raft
RethinkDB	实时数据库	标准Raft

9f6c2-feat: organize wiki content and refresh site setup于 2026/3/14