Paxos 理论介绍 (3): Master 选举

前文：Paxos理论介绍(2): Multi-Paxos与Leader

建议没有阅读前面文章的读者可以先花少许时间阅读一下。

Master

开门见山，我们先明确一下 Master 的定义。Master 是一个角色，这个角色的特点是，在我们选定的一些节点集合内，任一时刻，仅有一个节点成为 Master 或者没有任何节点成为 Master。这是一个非常严格的单点定义。

Master 的应用非常广泛。比如在分布式存储里面，我们希望读取一个最新的值，那么常见的做法是我们先选举出一个 Master，读写都经由 Master 来完成，那么在 Master 上读取到的就肯定是最新的。另外还比如一些仲裁模块，往往也希望有 Master 来协助。

Master 选举与 Paxos 的关系

如何选举 Master？由于 Master 具有严格的单点定义，那么必须有一个强一致性的算法才能完成选举，当然我们这里采用了 Paxos。但 Master 选举算法自身也是一个通用性的算法，它可以与任何强一致性算法搭配来完成，而无需要求一定是 Paxos。所以这里我们希望设计一个与 Paxos 完全解耦的工程实现，也就是 Master 选举只用到 Paxos 工程实现的 API，而无需侵入 Paxos 算法内部。

Paxos 的工程应用

这个涉及到 Paxos 工程上 API 设计以及状态机，这里先不展开讲，来看一张图相信大家就懂了，图片来自论文"Paxos Made Live"。

Paxos 的应用简明来讲就是由算法确定一个操作系列，通过编写这些操作系列的 callback（也就是状态机的状态转移函数），使得节点进行相同顺序的 callback，从而保证各个节点的状态一致。

Master 选举租约算法

BeMaster 是一个操作，这个操作很简单，就是提议自己成为 Master，图片里面 A 节点希望自己成为 Master。任何节点都可以发起这个操作尝试将自己提升为 Master，除了已经得知别人已被选为 Master。当得知别人被选为 Master 后，必须等待 timeout 长度时间，才能发起 BeMaster 操作。而如果是获知自己成为 Master，那么从 BeMaster 开始的 timeout 时间内可认为自己是 Master，如图示，T2-T3 的时间窗内，视作 Master 的任期。

如何将上面所述的租约算法与 Paxos 结合起来？

• BeMaster 可以认为是一个 Submit 操作，其 Value 携带的就是自己的节点信息。

• callback 做两件事情，第一：发现 Value 的节点非自己，则等待 timeout 时间再发起 BeMaster。第二：发现 Value 的节点是自己，那么将自己提升为 Master，并在 T(BeMaster) + timeout 后过期。

算法正确性如何保证？

• 一致性由 Paxos 保证，也就是只要 Value 被 Paxos 选出来，那么其包含的肯定是同一个节点信息，不会出现选举冲突。

• Master 的单点性通过租约算法保证。由于恒定 T(BeMaster) < T(Know other as master)，那么 Master 的过期时间肯定要比非 Master 节点认为 Master 过期的时间早，从而保证 Master 任期内，肯定不会出现其他节点尝试来抢占 Master。

这里给大家提一个问题，图示里面，为何 Master 任期的起始时间是从 BeMaster 算起，而不能是从 BeMaster success 算起？相信如果理解了 Paxos 算法的读者，应该可以很轻松回答这个问题。

Master 续任

只需要在 Master 任期内成功成功完成一次 BeMaster 操作，即可延长 Master 任期，在正常情况下这样不断迭代下去，一般会使得 Master 非常的稳定。

上图可以看到在多次的 BeMaster 选举里面，我们需要给每一个任期赋予一个 version，这是为什么？下面通过一个例子来解释这个问题。

这个图示情况是 NodeA 不断的在续任，但 NodeC 可能与 NodeA 无法通信或者其他原因，在获知 NodeA 第二次续任成功后就再也收不到任何消息了，于是当 NodeC 认为 A 的 Master 任期过期后，即可尝试发起 BeMaster 操作。这就违背了算法的保证了，出现了 NodeA 在任期内，但 NodeC 发起 BeMaster 操作的情况。

这里问题的本质是，NodeC 还未获得最新的 Master 情况，所以发起了一次错误的 BeMaster。version 的加入是参考了乐观锁来解决这个问题。发起 BeMaster 的时候携带上一次的 version，如果这个 version 已经不是最新，那么这一次 BeMaster 自然会失效，从而解决问题。理解乐观锁的读者应该可以很快脑补出 version 的作用，这里就不详细展开了。

小贴纸

说的再多不如阅读源码，猛击进入我们的开源 Paxos 类库实现：https://github.com/tencent-wechat/phxpaxos 在 src/master 目录有完整的 Master 租约算法实现代码。

OpenIMgithub 开源地址：

https://github.com/OpenIMSDK/Open-IM-Server

OpenIM 官网 ： https://www.rentsoft.cn

OpenIM 官方论坛： https://forum.rentsoft.cn/

更多技术文章：

开源 OpenIM：高性能、可伸缩、易扩展的即时通讯架构https://forum.rentsoft.cn/thread/3

【OpenIM 原创】简单轻松入门 一文讲解 WebRTC 实现 1 对 1 音视频通信原理https://forum.rentsoft.cn/thread/4