一个 Paxos 库的功能模块划分
source link: http://www.ideawu.net/blog/archives/1133.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Paxos 算法本身非常狭窄, 只解决共识问题, 如果只在这个领域封装一个 libpaxos 没有必要, 没有太大的使用场景. 如果要封装一个 Paxos 库, 几乎就是要重新发明(实现) Raft. 但 "Paxos" 这个词比较唬门外汉, 所以咱们就说"开发一个 Paxos 库"吧.
正如计算机领域解决问题的经典思路, 一个 Paxos 库应该拆分成三五个模块: 共识模块, 排序模块, 应用模块, 重传模块.
共识模块: 使用本节点所知的下一个未使用的日志序号, 执行 Paxos 算法的两阶段. 如果一条日志(对应一个序号)达成共识, 将日志传递给日志排序模块. 这个模块要记录所有已达成共识的序号, 当然, 不一定要离散地记录每一个序号, 可以优化成记录离散的 range, 最终只有一个 range. 维护这些 range, leetcode 上有一些题目有涉及, 有成熟可用的代码.
排序模块: 接受共识模块传递过来地已达成共识的日志, 按序号进行排序(因为是乱序达成共识). 然后连续地推进 commitIndex. 将 committed 的日志, 按连续的顺序发给日志应用模块.
应用模块: 接受日志排序模块的输出, 用独立的线程将日志发送给状态机(apply). 状态机 Apply 完成每一条日志之后, 更新 appliedIndex.
重传模块: 已经达成共识的日志, 不一定能全部被共识模块收到. 这时, 需要日志重传模块从其它节点拉取缺失的日志, 传递给日志排序模块.
以上各个模块, 组成这样的工作链条:
+--- 重传模块 --+
/ \
@--+----- 共识模块 ---- 排序模块 ---- 应用模块
如果从一条日志的生命周期的角度分析, 这个工作链条代表着日志的生命周期.
具体的实现编写代码的时候, 每一个模块肯定要对输入进行校验. 例如, 已经达成过共识的日志, 共识模块不再接受(leetcode 上面有判断一个整数是否落在 range 列表中的题). 小于等于 commmitIndex 的日志要被排序模块丢弃, 等等.
还有优化方面的考虑, 特别是重传模块, 最好借鉴 TCP 流量控制算法. 本质上来说, 整个 Paxos 库其实是在实现并裁剪 TCP 协议. 这里 Paxos 库要用拉取重传, 如果是 Raft 的话, 是推送方(leader)主动重传.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK