idea's blog

如果用面向对象的方法来分析 Paxos 和 Raft 的对象层次结构关系, 我们会发现, 两者其实没那么多差异, 或者说, 这种差异我们平时在做面向对象建模和编写代码时经常使用.

Basic Paxos

type Entry struct {
	promised_num int64
	proposal_num int64
	proposal_value []byte
}

Multi Paxos

type Node struct {
	entries []struct {
		promised_num int64
		proposal_num int64
		proposal_value []byte
	}
}

Raft

type Node struct {
	currentTerm int64 // promised_num
	entries []struct {
		term  int64   // proposal_num
		value []byte  // proposal_value
	}
}

首先, Basic Paxos 关注的是一条日志(Log Entry), 和 Raft 不是一个层次的东西. Multi Paxos 和 Raft 的结构类似, 本质上都是"日志复制状态机".

但是, Raft 把 promised_num从每一条日志里面抽出来, 不再作为日志的一个属性, 而是作为外层对象(Node)的一个属性, 而且换了个名字叫做 currentTerm. 纯理论上说, Multi Paxos 和 Raft 两种建模方案各有优劣, 无非就是控制粒度大小的区别. Multi Paxos 每一条日志都能控制 promised_num, 粒度更小更灵活, 但 Raft 的 currentTerm 粒度大, 反而更简单.

Leslie Lamport 自称:

The Paxos algorithm, when presented in plain English, is very simple.

我并不认为在这里用"simple(简单)"这个单词是合适的, 我认为使用"neat(简洁)"会更合适. 我们常人认为的简单等价于易懂, 但 Lamport 应该是指简洁的意思.

无数人的经历已经证明了, 用简洁的自然语言来描述的 Paxos 算法并不简单. 用类似编程语言的过程描述才能让 Paxos 算法变得简单. 所以, 要想弄懂 Paxos 的操作流程(Phase 1, 2), 应该紧紧围绕着上面的几个变量, 这也是 Raft 论文被认为易懂的原因.

如果把 Paxos 和 Raft 看作是统一的话, 算法的描述将非常简单:

1. 选主(Phase 1a)阶段, Proposer(Leader) 将 Leader.currentTerm 加 1, 然后请求投票
2. 选主(Phase 1b)阶段, Acceptor(Follower) 拒绝 Msg.currentTerm <= Follower.currentTerm 的请求, 否则同意并更新 Follower.currentTerm=Msg.currentTerm, 同时返回旧日志(如有) Entry{term, value}.
3. 创建日志阶段, Proposer(Leader) 从响应中找到 term 最大的日志对应的 value, 创建 Entry{Leader.currentTerm, max_value}, 如果没有, 则创建 Entry{Leader.currentTerm, my_value}
4. 复制(Phase 2a)阶段, Proposer(Leader) 将刚创建的日志发送给其它节点
5. 复制(Phase 2b)阶段, Acceptor(Follower) 拒绝 Entry.term < Follower.currentTerm 的日志, 否则接受, 并更新 Follower.currentTerm=Entry.term

从工程实践的角度看, 客户端希望写入的是 my_value, 但上述流程有可能没有成功写入, 而是写入了 max_value(修复共识). 所以, Leader 要换下一个位置重试. 最终一定能找到某个位置, 所有的 Follower 都没有旧日志, 才能成功写入. 这里是 Paxos 最让人难以理解的重点! 常理认为, 客户端要求写入什么, 集群就应该写入什么, 但是, Paxos 整个流程走下来, 竟然完全没按客户端的要求来, 这就让人疑惑了.

通常人们认为 Paxos 和 Raft 的区别, 还在于 Raft 可以循环执行 3-5 三个步骤, 而 Paxos 每一次都要执行 1-5 全部步骤. 也就是:

Paxos: 选主, 复制, 选主, 复制, 选主, 复制...
Raft:  选主, 复制, 复制, 复制, 复制, 复制...

Paxos 选主和复制一一对应频繁选主, 而 Raft 只需要选主一次就可以不断地复制. 有些人说, Paxos 也可以优化成"像 Raft 那样"只选主一次, 哈哈, 没错, 最终大家都把 Paxos 实现成了 Raft 的样子. 再说了, 如果 Raft 每一次复制前都进行一次选主, 不就成了 Paxos 的样子了吗?

Related posts:

1. Raft 选主优化之 PreVote
2. 再谈 Paxos 和 Raft
3. Paxos 与分布式强一致性
4. Paxos vs Raft 的争论
5. 为什么 Leader Based 的分布式协议 Raft 是更好的