Paxos KV

引言

个人使用，复习 Distributed System Final Project (Paxos Implementation) 项目结构。

整体结构

一、项目整体结构

该项目分为三个核心层次：

Paxos 层（paxos_impl.go）

实现基础的分布式一致性协议 Paxos，用于在多节点间就某个值达成一致。

RSM 层（paxosrsm/server_impl.go）

构建在 Paxos 之上的 Replicated State Machine（复制状态机），保证多个节点按相同顺序执行操作。

应用层：分片键值服务（ShardKV 与 ShardMaster）

使用 RSM 保证线性一致的键值存储，并通过 ShardMaster 动态调整分片与组的映射。

---

二、Paxos 层实现详解（paxos_impl.go）

数据结构设计

• slotInfo：每个序列号（seq）的状态，包含：

  • 提案号 np
  • 接受号 na
  • 值 va
  • 状态 ft

• paxosStatus：存储所有实例及每个节点的 done 状态。

• PaxosImpl：封装全部通信用的 channel，用于隔离多线程操作。

---

状态管理机制

通过多个 goroutine 与 channel 实现线程安全：

• 状态 goroutine 管理所有 slot 信息；
• RPC goroutine 处理 Prepare、Accept、Inform 请求；
• 通过 channel 通信实现无锁状态访问。

---

Paxos 协议逻辑

实现了标准的 三阶段 Paxos 算法：

Prepare 阶段

• Proposer 发送 Prepare(n)；
• 若 n > n_p，Acceptor 接受请求并返回当前最高的 (n_a, v_a)；
• 否则拒绝。

Accept 阶段

• Proposer 选择 v'（优先取最大 n_a 对应的 v_a，否则使用自己的 v）；
• 发送 Accept(n, v')；
• 若被多数 Acceptor 接受，则进入下一阶段。

Inform（Decided）阶段

• Proposer 通知所有节点 Decided(v')；
• 各节点更新状态为 Decided。

---

内存管理与最小序列

• 通过 Done() 更新本节点完成的最大序列；
• Min() 返回所有节点最小 done + 1；
• 低于 Min() 的实例会被清除（freeMem）。

---

核心特性

特性	说明
多线程安全	通过 channel 和 goroutine 实现
全异步、非阻塞 Start	不会阻塞主线程
状态自动回收	避免内存泄漏
可容忍部分节点失败	Paxos 天然支持容错

---

三、Replicated State Machine 层（paxosrsm/server_impl.go）

功能概述

在 Paxos 上实现一个 复制状态机（RSM），保证多节点按相同顺序执行操作（共识日志）。

---

主要机制

• 每个操作封装为 opRequest；
• privateAddOp() 循环调用 Paxos 协议，直到该操作被决定；
• 成功后调用 applyOp() 执行状态更新；
• 使用 指数退避（10ms–200ms） 避免活锁。

---

状态维护

• 当前 slot 号通过 slotChan 管理；
• 每次决定一个操作后，slot + 1；
• 多线程安全由 goroutine + channel 保证。

---

四、分布式键值存储层（shardkv/server_impl.go）

基本思想

• 每个 ShardKV 节点内部运行一个 PaxosRSM，用于同步所有操作。
• 操作类型包括：Get、Put、Append、Assign、Pull。

---

内部状态

• KVStore：键值映射；
• OpCache：防止重复请求；
• Config / Shards：记录当前配置及分片分配；
• 通过 channel 维护一致快照（snapshot）。

---

操作处理流程

1. 客户端请求 → 转换为 Op → nonBlockingAddOp() → PaxosRSM.AddOp()；
2. 决议达成后 → ApplyOp() 应用到本地快照；
3. 对于 Get/Put/Append：
   • 校验分片归属；
   • 检查幂等性；
4. Assign/Pull 用于分片迁移与复制。

---

快照与一致性

• 每次操作都生成新的 snapshot，通过 updateSnapshotChan 更新；
• Get 请求直接读取 snapshot，保证 线性一致性（Linearizability）。

---

五、分片管理器层（shardmaster/server_impl.go）

功能

负责全局 分片与组（group）的分配与管理，支持以下操作：

• Join：新组加入；
• Leave：组退出；
• Move：移动某个 shard；
• Query：查询当前配置。

---

实现机制

• 每次配置变更通过 PaxosRSM 达成共识；
• 每个操作编码为 Op；
• 操作完成后更新配置列表 configs；
• 自动调用各 ShardKV 的 RPC 进行分片重新分配。

---

Rebalance 算法

动态平衡分片分配：

1. 计算目标 shard 数；
2. 找出需要增减的组；
3. 按组 ID 排序，循环分配；
4. 确保分片尽量均匀。

---

六、项目特性与优点

特性	说明
一致性	Paxos 保证强一致性
容错性	节点宕机后自动恢复共识
可扩展性	通过 ShardMaster 支持动态扩展
并发性	全面使用 channel 实现无锁并发
持久性	通过 snapshot 机制维持状态副本

---