通过 Paxos 的教会协议，顺利地帮助大家解决了"今天中午吃什么"的问题，但生活远不只吃午饭这么简单。这不，大家又遇到了一个新的挑战——抢车位。

在某个商场的地下停车场中，共有 1000 个车位和 3 个出入口，每个出入口设有一个保安亭，每个保安亭内都有一位保安在值班。因为该停车场一直都没有进行数字化转型，所以保安之间只能通过老旧的点对点式对讲机进行联系，车辆的进出也都是靠人手一个笔记本进行记录。

在过往的经营中，经常出现：

• 停车场的空闲车位数不准；

  
  

• 从东门进入的车，想从西门出去，结果西门的保安找不到相关车辆的入场记录，不知道该收多少费；

  
  

• 只剩最后一个车位时，有三辆车同时从三个门被放行进入停车场，导致有两辆车没找到车位。

随着客户投诉越来越多，这么下去也不是个办法。所以大家趁着某天下班之后聚在一起，决心找出办法来降低客诉，把下面这些问题都解决掉：

• 如何保证每个人记录的空闲的车位数是准确的？

  
  

• 如何保证每个人的车辆进出记录是一致的？

  
  

• 如何保证让放行进入的车辆都有位可停？即没有空位时，坚决不放行车辆入场。
  

• ……

众人之中有一个同学比较好学，闲暇之余恰好读了 Paxos 的论文。他觉得 Paxos 中的议会协议似乎可以用来解决大家遇到的问题，但是 Paxos 描述得有点抽象，如果要落到实际中，还有很多细节需要考虑。所以他将整个落地过程被拆分为了设计、研发、测试、发布这四个阶段，接下来就一起看一看大家每个阶段做了哪些事情吧。

选举过程在完整版教会协议里已经阐述过了，这里再简单的描述一下选值班长机制：

 但是这种选举方式，无法保证在任一时刻只有一个值班长（可能出现脑裂）。

比如 N 和 W 之间对讲机因干扰而无法对话，但是他们又各自可以与 E 正常地交流。

通过上面的选举过程，W 和 E 会认为 W 是值班长，N 则会认为自己是值班长。但多个值班长并不影响整个过程的安全性。

因为教会协议里提到：选举只是为了保证算法的活性，即使没有值班长或者有多个值班长，并不会破坏算法的安全性。如果出现了多值班长的情况，他们有可能给并发的事件相同的编号，并且并发的发起教会协议。但教会协议的安全性能保证，在同一个教会协议实例中的并发多个事件，最终只会通过其中的一个。

设计阶段明确了值班长需要给事件进行编号这个职责，但是具体应该怎么做呢？先要分析一下这个编号的作用：

• 作为事件的全局唯一标识，更正确的解释是作为已通过的事件的全局唯一标识。因为可能会存在并发地多个事件使用同一个编号，但是最终只会有一个事件通过这种场景，所以其它未通过事件是不会有标识的。

• 为已通过的事件确定全序关系。只有大家对初始状态按顺序完全相同的事件进行计算，才能得到一致的新状态。

在选出值班长之后，给事件编号也相应变得容易了。值班长自身维护一个事件号的计数器，每此当选值班长后将自己笔记本上记录的已通过最大事件号作为初始值；每当新来一个事件时，将计数器+1，取计数器的值作为新事件的编号。

这种方式有一个小问题：假设 E 上了个厕所回来重新当选为值班长，这期间可能发生了很多次进出场事件。如果 E 依然沿用之前的计数器，就可能导致后续的部分新事件无法通过。因为过时的计数器产生的新编号，已经被之前的事件使用掉了。

为了解决这个问题，需要当选为值班长后，不急于处理新事件，先从其他人哪里抄写自己缺失的已通过事件。

随着设计和研发阶段的完成，议会协议也基本成型。众人商量决定，先投入实际中试运行一段时间。梳理出来的议会协议过程整理出来如下：

经过几周的试运行，大家或多或少的发现了一些问题（第一个版本嘛，难免的嘛）。但大方向是没有问题的，于是大家撸起了袖子，准备把这些发展中的小问题给逐个击破。

试运行的议会协议中，对每个事件都要用上一次完整的教会协议。实在是有点冗余，需要说好多话浪费好多口水：

1）作为值班长的保安（对于每个事件的每一轮表决需要说 5 句话）：

• 2 * “我要开始 xxx 表决了”（NextBallot） + 1 * “开始 xxx 表决：……准备进/出停车场”（BeginBallot） + 2 * “……已经进/出停车场了”（Success）；

• 如果每个事件，平均发生了 轮表决，那他需要说 5* n 句话；

• 如果共发生了 m 个事件，那么总共需要说 5*n*m 句话。

2）作为非值班长的保安，相应的，总共需要说 2*n*m 句话（LastVote + Voted）。

两者相加，那就要说 7*n*m 句话。这不仅费口水，还有点费对讲机的电。

严格来说这并不是一个缺陷，但为了绿色低碳环保，大家思考了很久很久……突然 E 灵光一闪，发现值班长和非值班长说的第一句话，其实并没有包含任何与当前事件相关的信息。

如果把第一句话理解为用来占位的，那可不可以一次性占多个位呢？

值班长一旦当选后，给大家说“我要开始第 m 号事件之后所有事件的第 b 轮表决了”（m 是值班长已完成事件中最大的事件号）。因为教会协议只是要求表决号唯一且可比较，所以我们可以用一个表决号 b，作为多个事件的表决号进行占位并发起表决。

非值班长的保安们在收到这个消息之后，随即回复：“我参与 m 号实例之后的所有表决。并且在 m+1 号实例的第 a 轮投票了 xx 事件；在 m + 2号……”。省略号部分是这个保安在 m 号实例之后，投过票的进行中的事件和已通过的事件，已方便。

值班长收到这个回复之后：一方面可以继续推进进行中的事件；另一方面从其他人那里学习到m 号之后已通过的事件；最后还对大于 m 所有教会协议实例的第 b 轮表决进行了占位，获得了其他人的承诺。

口水是省了，但是又引入了一个新的问题，表决号还需要自增么？

正常情况下，因为只有一个值班长 E，他在当选后即用 b 这个表决号为后续所有事件进行了占位，所以他对于后续的教会协议实例，都不用修改占位用的表决号 b。

但是如果 E 和 W 同时认为自己是值班长，且 W 的占位的表决号 b' 比 b 更大，那么 E 发起的所有教会实例都无法通过（这会影响算法的活性，但不影响安全性）。

解决这个问题的关键在于教会协议的第4步，因为 W 用 b' 在 N 那儿站位了，所以 N 在第 4 步不会给 E 的任何教会实例投任何的票，但 N 可以告诉 E “我不给你投票的原因是因为你的表决号 b 太小了，我已经给 b' 承诺了”。

这时，E 可以根据 N 的回复，调整自己的表决号，并重新开始当选值班长之后的所有步骤。

（这个时候值班长的表决号 b 有点类似于 Raft 的 term 和 ZAB 的 epoch 了）

 在试运行期间，大家还是意外的收到一起投诉。

事情是这样的，在一个风和日丽的下午，一辆车想从东门进入停车场，大家按照试运行的议会协议对入场事件达成了共识，然后放行其入场。但是车主在停车场找了半天也没找到一个空闲车位，于是就愤愤离场，立马打电话给商场投诉。

大家在复盘这件事情的时候，发现了一个致命的问题，通过执行这辆车入场之前的所有事件，发现此时停车场的空闲车位已经是 0 了，也就是说没有空闲车位了。再加上这辆车的入场事件，空闲车位数变成了 -1……不被投诉就奇怪了。

这个时候大家才开始重新审视整个方法过程，找出了问题症结所在：出场事件和入场是事件并不是等同的。出场事件只需要在当前状态下简单的 +1 即可，但入场事件却不能简单的将空闲车位 -1，它还需要先判断当前的空闲车位数是否 > 0。要攻克这个问题，等效于解决下面的两个问题：

1）如何拿到精准的当前状态？

议会协议能保证事件在众人间是一致性，但是它不保证时效性。

也就是说在某一个时刻，每个人记录的事件集可能是不一样的。有的人记到了 110 号事件，有的人只记录到了 108 号事件，有的人 100 号事件是空缺的，有的人 99 号和 101 号事件是空缺的。

要攻克这个问题，一种可行的方式是出入口对应的保安把“读取停车场当前状态”作为一个读取事件，为它也发起一次教会协议。在这个读取事件完成后，就可以通过执行所有事件，算出直到这个读取事件的这一刻，停车场的空闲车位数是多少。这样就精准的完成了“判断当前状态”。如果此时已经没有空闲车位了，那就拒绝车辆入场。

2）如何保证判断当前状态的“读取事件”和放行车辆的“入场事件的”是原子的？

假设这两个事件间，被插入了其他的事件，那就有可能导致错误的结果。

比如停车场的当前状态还有 1 个空闲车位。在完成入场事件之前，又来了一个车辆要入场，并且更快地完成了它的读取事件和入场事件。那前一个车辆入场事件就不应该也不能够被执行了。我们在解决前一个问题的时候引入了读取事件，这个读取事件一定是有一个事件号的。

假设读取事件是 99 号，那么可以把接下来的入场事件赋予 100 的事件号，为它发起一次教会协议，如果 100 号实例通过了，并且事件确实就是本次的入场事件（而非并发的其他事件），这样就能保证 99 号事件和 100 号事件之间没有发生其他事件。换句话说，它们就是原子的。

正文中提到了一种简单的选值班长的方式，但是这样会带来一个问题：

“假设工号最大的人 E 临时有事请了半天假，其他两个人正常的工作了半天之后，E 又回来上班了。这时，E 重新当选为值班长，但是他已经落后其他两个人很多事件了，需要从他们那里抄写这半天所有的事件到自己的笔记本上，在他抄写期间，没办法处理新的出入场事件。”

为了解决这个问题，大家改进了选值班长的过程：从“始终选工号最大的人做值班长”，到“选事件最多的人（即笔记本上记录事件最多的人）做值班长”。采用这种方式，可以发生换届时，不会花费大量时间在事件抄写上，从而影响到停车场的服务。作为补充，如果多个人记录的事件数一样，那么就选其中工号最大的人。

解决方案正式发布后，随着实际的执行，大家发现笔记本上记录的事件越来越多了。每次车辆入场前，都需要从头计算一次出入场事件，才能知道还有没有空位。最近越演越烈，需要前后翻几十页，计算十几分钟才能放车辆入场，大大的影响了效率。

大家在实际的过程中，渐渐的发现了问题所在：为什么每次计算空闲车位，都需要从最开始的状态开始依次计算每个出入场事件呢？如果计算今天的空闲车位，可以从昨天下班后的空闲车位（假设下班后不会再有车辆进出）再加上今天记录的事件，就能省掉大量的计算和时间。对于大家来说，计算一天的事件，还是可以接受的。

说干就干，大家现在在每天下班后，多了一件事情，就是通过笔记本上已完成的事件，计算出今天下班后停车场的空闲车位数，并记录下来。除了第一次计算需要从头到尾的计算所有出入场事件以外，后面每天只需要基于昨天下班后的空闲车位数 + 今天所有的出入场事件，就可以计算出今天下班后的空闲车位数。每天计算并记录下班后的空闲车位数之后，以前记录的事件就算是归档了，即使不慎遗失了，也不影响后续的工作。

这个过程还有一个场景需要处理。

假设 W 请了一周假之后回来上班了，他虽然没能当选值班长，但是也需要从 E 和 N 处抄写最近一周的所有事件。但是因为咱们改进了流程之后，E 和 N 对于记录的历史事件没那么上心了，不小心弄丢了。这个时候 W 就不能像原来那样抄写这一周的所有事件，而是从 E 或者 N 出抄写昨天下班后的空闲车位数，以及今天上班后新发生的所有事件。

上面这个过程只适用于需要抄写今天以前的事件，如果 W 只是去上了个厕所，那它还是需要从 E 或 N 处抄写（今天的）这段时间新发生的所有事件。

随着服务的提升，停车场的生意越来越好了，三个门偶尔都排起了队。管理层决定新招两名保安，把一直未开放的南一门和南二门也修葺一下，正式开放。

这时又引入了新的问题：

• 新加入的两名保安在什么时候才能加入到整个过程中来了，即什么时候开始可以作为选举的候选人？

  
  

• 什么时候开始可以参与表决？

• 什么时候开始可以参与投票？

最直接的方式就是在某天下班后，大家聚在一起开个会、吃个饭，然后约定明天就是 5 个人一起上班了。

这样在现实生活中当然没问题，但是假设停车场是 24 小时轮班制的，没有一个时间点能把 5 个门的保安都聚在一起。或者是这两个门并不是某天一上班就立马开始投入使用，而是中午后的某个不确定的时间点投入使用呢？

为了解决这个问题，我们得先来看一下事件的并发度问题“最大允许多少个在表决中的事件”。

如果这个数是无限大的话，一方面会增大事件间出现 gap 的概率和分布，另一方面也不利于解决新人加入的问题。具体到停车场的场景，这个并发度为 3 是比较合理的，因为最多只会有 3 辆车同时从 3 个门出入停车场。

明确了 3 这个并发度之后，新人到岗的问题也有相应解法了，就是增加一类新的事件“员工变更” — 这个事件中包含了变更后新的全量员工的集合。

那么这个事件多久生效呢？

假设是这个事件通过后立即生效，那么会存在这种情况，假设 100 号事件是员工变更事件，新在岗员工变更为 E、W、N、S1 和 S2，它已经通过。并且 102 号事件也已经通过，但是 101 号事件因为某些原因还未通过。值班长 N 需要对 101 号事件进行重试或者填补空缺。但是此时如果使用 100 号事件并更后的人员列表的话，就可能存在原始表决和重试的标记的多数派不一致，如果刚好是 S1、S2 和一个未参与原始表决的人形成了多数派，那么就会导致另一个的事件被通过，从而出现安全性问题（不一致）。

所以 100 号事件对于可能在进行中的事件不能造成影响，这里就引出了并发度的作用了，因为有它的存在，所以 100 号事件提出之后，至多只有 101 号和 102 号事件在并发，那么 101 和 102 必须沿用之前的员工名单，而 103 以及之后的事件，则可以使用变更之后的员工名单 —— 即 100 号事件通过后，在 100 + 3 号及后续事件中生效。