分布式一致性与状态机复制

1. 问题：单点故障#

假设你有一个 KV 存储服务器，客户端可以 Put(key, value) 和 Get(key)。

如果只有一台服务器，它崩溃了，服务就不可用了。

解决方案：用多台服务器，让它们保持相同的状态。

2. 状态机复制#

核心思想：如果多台服务器从相同的初始状态出发，按相同的顺序执行相同的操作，它们的状态就会保持一致。

服务器 1: 初始状态 → 执行 Put(a,1) → 执行 Put(b,2) → 状态: {a:1, b:2}
服务器 2: 初始状态 → 执行 Put(a,1) → 执行 Put(b,2) → 状态: {a:1, b:2}
服务器 3: 初始状态 → 执行 Put(a,1) → 执行 Put(b,2) → 状态: {a:1, b:2}

关键问题：如何保证所有服务器按相同的顺序执行操作？

这就是 Raft 要解决的问题。Raft 是一个共识算法，它让多台服务器就”操作的顺序”达成一致。

3. Raft 的角色#

Raft 集群里的每个节点有三种角色：

• Leader（领导者）：负责接收客户端请求，把操作追加到日志，然后复制给其他节点
• Follower（跟随者）：被动接收 Leader 的日志复制
• Candidate（候选人）：在选举期间的临时状态

任何时刻，集群里最多只有一个 Leader。

4. Raft 日志#

Raft 用日志来记录操作的顺序：

日志索引:  1        2        3        4
日志内容: Put(a,1) Put(b,2) Get(a)   Put(a,3)
任期号:    1        1        2        2

提交（commit）：当一条日志被多数节点（超过半数）复制后，就认为它被”提交”了。提交后的日志不会被删除或修改。

应用（apply）：提交的日志条目会被应用到状态机（执行操作）。

5. 安全性 vs 活性#

分布式系统有两个核心属性：

安全性（Safety）：不好的事情永远不会发生。

• 对于 Raft：不会有两个 Leader 同时存在；已提交的日志不会被覆盖

活性（Liveness）：好的事情最终会发生。

• 对于 Raft：如果多数节点存活，最终会选出 Leader；客户端的请求最终会被处理

重要：在网络分区的情况下，安全性和活性不能同时保证（CAP 定理）。Raft 选择保证安全性，牺牲部分活性。

6. 线性一致性（Linearizability）#

线性一致性是 Lab 3 要满足的正确性标准。

直觉理解：从客户端的角度看，所有操作好像是在一台单机上按某个顺序执行的，而且每个操作都是瞬间完成的（没有中间状态）。

具体例子：

时间轴:
客户端 1: Put(x, 1) ----完成----
客户端 2:              Get(x) ----返回 1----

客户端 2 的 Get(x) 在客户端 1 的 Put(x, 1) 完成之后才开始，所以必须返回 1。这是线性一致性的要求。

违反线性一致性的例子：

客户端 1: Put(x, 1) ----完成----
客户端 2:              Get(x) ----返回 0----  ← 违反！

7. 重复请求问题（去重）#

客户端发送请求后，如果没收到回复（网络超时），会重试。但服务器可能已经执行了这个请求。

如果不处理重复请求，Put(x, 1) 可能被执行两次，对于非幂等操作（比如 Append）会出错。

解决方案：每个客户端请求带一个唯一 ID（序列号）。服务器记录已执行的请求 ID，如果收到重复请求，直接返回之前的结果，不再执行。

type Clerk struct {
    clientID  int64  // 客户端唯一 ID
    seqNum    int    // 递增的序列号
}

// 每次发请求时
args := PutAppendArgs{
    Key:      key,
    Value:    value,
    ClientID: ck.clientID,
    SeqNum:   ck.seqNum,
}
ck.seqNum++

快速检验#

1. 状态机复制的核心思想是什么？为什么需要保证操作顺序一致？
2. Raft 里”提交”和”应用”有什么区别？
3. 为什么客户端需要给每个请求带一个唯一 ID？