Paxos算法.pdf
立即下载
楊♡
2025-06-18
提议
议员
编号
Paxos
算法
描述
Senator
环境
生效
记事
221.3 KB
先说 Paxos，它是一个基于消息传递的一致性算法，Leslie Lamport 在 1990 年提出，近
几年被广泛应用于分布式计算中，Google 的 Chubby，Apache 的 Zookeeper 都是基于它的理
论来实现的，Paxos 还被认为是到目前为止唯一的分布式一致性算法，其它的算法都是 Paxos
的改进或简化。有个问题要提一下，Paxos 有一个前提：没有拜占庭将军问题。就是说 Paxos
只有在一个可信的计算环境中才能成立，这个环境是不会被入侵所破坏的。
关于 Paxos 的具体描述可以在 Wiki 中找到：http://zh.wikipedia.org/zh-cn/Paxos 算法。网
上关于 Paxos 分析的文章也很多。这里希望用最简单的方式加以描述并建立起 Paxos 和 ZK
Server 的对应关系。
Paxos 描述了这样一个场景，有一个叫做 Paxos 的小岛(Island)上面住了一批居民，岛上
面所有的事情由一些特殊的人决定，他们叫做议员(Senator)。议员的总数(Senator Count)是确
定的，不能更改。岛上每次环境事务的变更都需要通过一个提议(Proposal)，每个提议都有一
个编号(PID)，这个编号是一直增长的，不能倒退。每个提议都需要超过半数((Senator Count)/2
+1)的议员同意才能生效。每个议员只会同意大于当前编号的提议，包括已生效的和未生效
的。如果议员收到小于等于当前编号的提议，他会拒绝，并告知对方：你的提议已经有人提
过了。这里的当前编号是每个议员在自己记事本上面记录的编号，他不断更新这个编号。整
个议会不能保证所有议员记事本上的编号总是相同的。现在议会有一个目标：保证所有的议
员对于提议都能达成一致的看法。
好，现在议会开始运作，所有议员一开始记事本上面记录的编号都是 0。有一个议员发
了一个提议：将电费设定为 1 元/度。他首先看了一下记事本，嗯，当前提议编号是 0，那么
我的这个提议的编号就是 1，于是他给所有议员发消息：1 号提议，设定电费 1 元/度。其他
议员收到消息以后查了一下记事本，哦，当前提议编号是 0，这个提议可接受，于是他记录
下这个提议并回复：我接受你的 1 号提议，同时他在记事本上
提议/议员/编号/Paxos/算法/描述/Senator/环境/生效/记事/
提议/议员/编号/Paxos/算法/描述/Senator/环境/生效/记事/
-->