写点什么

Paxos 理论介绍 (4): 动态成员变更

用户头像
OpenIM
关注
发布于: 4 小时前

多数派的本质

在讲解成员变更之前,我们先回顾一下前文介绍的 Paxos 理论第一篇文章 Paxos理论介绍(1): 朴素Paxos算法理论推导与证明, (仔细回顾数学定义和投票约束章节)文中提到 Bqrm 为一轮成功投票所需要的投票者集合,而 Paxos 算法理论第二条约束要求任意两个 Bqrm 的交集不为空,于是乎我们可以理解为 Bqrm 就是一个多数派的意思,因为在一个固定的投票者集合里面,取多数派作为 Bqrm,肯定是满足条件的。


而所有的理论介绍,都是基于投票者集合是固定的。一旦投票者集合出现变化,Bqrm 的定义将不再是多数派,Bqrm 的取值将变得异常困难,而无法定义 Bqrm,Paxos 算法的约束就无法达成一致性。也就是说,固定的成员是 Paxos 算法的根基。

人肉配置进行成员变更?

我们再进行第二篇文章 Paxos理论介绍(2): Multi-Paxos与Leader 的回顾,通过文章我们知道 Paxos 是以独立的实例的方式推进,从而产生一个一致的有序的系列,而每个实例都是单独运作的 Paxos 算法。再根据上文,我们得出一个要求,在相同的实例上,我们要求各个成员所认为的成员集合必须是一致的,也就是在一次完整的 Paxos 算法里面,成员其实还是固定的。


每个成员如何得知这个成员集合是什么?通常我们是通过配置文件。在通过配置的变更能否满足以上的要求呢?我们知道 Multi-Paxos 在推进的过程中是允许少数派落后的,而在同一个实例里面,获知 Value 被 chosen 也是有先后的,那么配置的变更可能出现在以上任何的先后夹缝内,下图演示一个更换节点 C 为 D 的样例。



注:绿色代表已经获知 chosen value 的实例


可以观察到 4 这个实例,已经出现了成员混乱,(A,C),(B,D)都可以被认为是 Bqrm,但明显这两个 Bqrm 没有交集,已经违反 Paxos 协议。


事实上我们追求的是找到一个切入时机,使得 Paxos 的运作程序都在这相同的时刻完成配置的原子切换,但明显在分布式环境里面能做原子切换的只有一致性算法,所以配置更新不靠谱。


题外话,如果真的要使用人肉配置更新,在工程上是有一些办法,通过一些工具加人肉的细微观察来无限逼近这个正确性,但终究只能逼近。在理论层面我们会放大任何现实中可能不会出现的细微错误,比如时间的不同步,网络包在交换机无限停留,操作系统调度导致的代码段卡壳等等,这些都会导致这些人肉方法不能上升到理论层面。况且,我们接下来要介绍的动态成员变更算法也是非常的简单。所以这些细致的问题就不展开来聊了。

Paxos 动态成员变更算法

这个算法在 Paxos Made Simple 的最后一段被一句话带过,可能作者认为这个是水到渠成的事情,根本不值一提。


Multi-Paxos 决议出的有序系列,一般被用来作为状态机的状态转移输入,一致的状态转移得出一致的状态,这是 Paxos 的基本应用。那么非常水到渠成的事情就是,成员(投票者集合)本身也是一个状态,我们通过 Paxos 来决议出成员变更的操作系列,那么各台机器就能获得一致的成员状态。如下图。



在 4 这个实例,我们通过 Paxos 算法来决议一个成员变更操作,所有的节点在实例 4 之后都能获取到成员从 A,B,C 变成了 A,B,D,在理论上达到了原子变更的要求。


延缓变更生效


通常 Paxos 的工程化为了性能和进展性都会由一个 Leader 节点进行数据写入,而成员变更往往可能会导致 Leader 节点发生变化。那么变化的瞬间可能会出现大量当前 Leader 节点堆积请求的失败。


另外如果采用多个实例基于窗口滑动并行提交(这里暂时不展开讲,而且我觉得这个在实际工程实现中必要性也不是很大)的话,在成员变更操作被 chosen 后,之后的实例可能还在 Paxos 算法运行当中,那么这些实例的 Bqrm 可能已经被确定下来,所以我们不能再去改动这些实例的 Bqrm。如上图例子,4 的时候进行了成员变更,但是由于并行提交的关系,5 和 6 可能都已经在提交当中了,那么他的 Bqrm 还是被确定下来为 A,B,C,这时候我们不能去改这些实例的 Bqrm 为 A,B,D。


为了解决这个问题,我们可以将成员生效时间延缓一下,在这个期间将请求引导到新的写入节点。



我们可以定义一个延缓窗口为 a,成员变更点为 I,则生效点为 I + a。这个 a 根据实际情况进行调节。如上图,成员变更点在实例 4,但是生效点可以在实例 6 之后。我们规定旧的 Leader 在 I + a 之前仍然能正常写入数据,而新的写入节点必须从 I + a 开始写入数据,这样可以完成一个平滑过渡。


这里有个异常情况,如果成员变更后,旧的 Leader 不写入数据了,实例停留在(I, I + a), 而新的写入节点因为要在 I + a 后才能写入数据,真个算法就卡住无法进行请求写入了。这种情况需要在工程上进行观察,如果出现则由新的写入节点对(I, I + a)进行 nullvalue 的写入,从而填补空洞。


说的再多不如阅读源码,猛击进入我们的开源 Paxos 类库实现:https://github.com/tencent-wechat/phxpaxos, 我们完整的实现成员变更算法。


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

用户头像

OpenIM

关注

还未添加个人签名 2021.08.30 加入

还未添加个人简介

评论

发布
暂无评论
Paxos理论介绍(4): 动态成员变更