实现 Raft:第 5 部分 - 一次性交付

这是一系列介绍 Raft 分布式共识算法及其在 Go 中完整实现的帖子的第 5 部分。系列帖子如下:

在本部分,基于 Raft 共识完成了复制键值数据库的实现。在第 4 部分结尾讨论了由于客户端重试逻辑可能出现的一致性问题,现在要解决它。

本部分代码位于此目录

添加 APPEND 操作到数据库

  • 第 4 部分的 KV DB 支持基本操作:PUT(k,v)、GET(k)、CAS(k, cmp, v)。
  • 新增操作 APPEND(k,v),将 v 追加到键 k 的值后,若之前数据库中不存在 k,则行为类似 PUT(k,v)。
  • 例如序列 PUT("x","foo") APPEND("x", "bar") APPEND("y","hello"),应用于空数据库后,结果为 x=foobar,y=hello。

客户端重试的问题 - 以 APPEND 为例

  • KV 客户端工作方式在Part 4中有详细描述,客户端逐个尝试 KV 服务,直到从领导者获得成功响应,且记住上次尝试时的领导者服务以避免下次浪费时间。
  • 假设已成功向数据库提交 PUT("x","foo"),现要发送 APPEND("x","bar")命令,客户端记得服务 B 是领导者,将请求发送给 B,若未收到响应则重试发送给 C。但可能 B 已接收并提交命令但未响应客户端就崩溃了,之后 B 失去集群领导,客户端会一直重试,导致 APPEND 可能被应用多次,数据库中 x 的值最终为"foobarbar",这是不好的。
  • 问题不在于重试本身,而在于核心算法中重试时缺乏足够的安全保证。

解决重试问题的命令去重

  • 原始 Raft 论文第 8 节明确指出此问题,解决方案是为每个命令分配唯一序列号,KV 服务可避免重复应用相同命令。
  • 为命令唯一标识的方法:每个客户端有全局唯一 ID,每个客户端发送的命令有唯一 ID 且单调递增。
  • 在 APPEND 示例中,客户端 ID 为 42,APPEND("x","bar")命令 ID 为 1,B 接收并提交命令后崩溃,客户端重试给 C,C 因命令 ID 已应用过不会再次应用。

实现去重

  • 客户端:在 KVClient 结构体中添加 clientID 和 requestID 字段,clientID 在创建客户端时由全局原子自增分配,requestID 跟踪客户端发送的最后请求的 ID,每次发送新请求时递增。
  • 服务端:在 KVService 结构体中添加 lastRequestIDPerClient 字段,在 Command 结构体中添加 ClientID、RequestID 和 IsDuplicate 字段。在 runUpdater goroutine 中进行去重逻辑,根据客户端 ID 和请求 ID 判断是否为重复命令,若重复则标记为 IsDuplicate = true 并处理。
  • HTTP 处理程序处理重复命令时返回特殊 API 状态 api.StatusDuplicateRequest,客户端将其视为错误并通知用户。

重新审视一致性保证

  • Part 4中讨论了 KV 服务的一致性保证为严格可序列化,添加客户端模块后由于客户端重试问题,系统不再是线性化的,添加去重后系统再次变为严格可序列化,实现了精确一次交付。
  • 无客户端重试时命令最多交付一次,添加客户端重试后为至少一次交付,存在重复交付问题,去重后可实现精确一次交付。Ron Garret 的帖子Kafka 开发者的帖子都讨论了精确一次交付的相关内容。

结论

本系列帖子完成了在 Go 中实现完整的 Raft 共识模块,并在其之上构建了严格可序列化的 KV 数据库。如有问题或意见可发送邮件或在 GitHub 上打开issue

附录 1:PUT 的重试与线性化

本部分通过添加 APPEND 操作演示了重试和重复导致的问题,即使没有 APPEND 操作,若允许无去重的重试,系统也不是线性化的,并通过图表展示了 PUT 的重试导致的线性化问题,即“lost update”。

附录 2:etcd 中的丢失更新与客户端重试

etcd 是基于 Raft 的工业级键值数据库,其一些客户端库存在本帖中描述的重试问题,Jepsen 分析得出此机制导致线性化丢失,建议禁用。etcd 本身是严格可序列化的,但不支持 APPEND 操作,可通过事务实现类似功能,并避免非线性化行为。

注:

  • [1]:命令的 ID 需存储在 Raft 日志中以实现跨节点去重。
  • [2]:若担心客户端在其生命周期内发送请求过多,可使用 math/big.Int 改为任意大的数。
  • [3]:Command 结构体中的 IsDuplicate 用于从更新协程向请求处理程序通信结果,可进行简单重构使用单独的数据结构。
  • [4]:此假设服务处理的不同客户端总数不过大,在实际系统中是合理的,若客户端数量无界,应维护某种“垃圾回收”方案。
阅读 10
0 条评论