乐趣区

关于im: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/…

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

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

更多技术文章:

开源 OpenIM:高性能、可伸缩、易扩大的即时通讯架构
https://forum.rentsoft.cn/thr…

【OpenIM 原创】简略轻松入门 一文解说 WebRTC 实现 1 对 1 音视频通信原理
https://forum.rentsoft.cn/thr…

退出移动版