微信号:pingcap2015

介绍:PingCAP 专注于新型分布式数据库的研发,是知名开源数据库 TiDB (Github 4100 stars) 背后的团队,研发总部在北京,是国内第一家开源的新型分布式 NewSQL 数据库公司,也是国内领先的大数据技术和解决方案提供商.

深入浅出 Raft - Membership Change

2017-11-13 16:07 唐刘

我司高产作家唐刘老师的小猪佩奇版“深入浅出 Raft”第四弹来啦~~前几篇内容戳这里 ↓

在猪爸爸的努力下,泥坑银行终于能高效正常的运作了,但猪爸爸一直比较担心海盗岛那边的网点,因为他总是担心跨海的通讯会因为极端情况出现问题。果不其然,一个雷雨交加的晚上,海盗岛的发电站被击中,整个岛处于停电状态,海盗岛的网点没法正常工作了。虽然狗爷爷尽了很多努力,让海盗岛重新供电也花了一天时间。

第二天,猪爸爸去见了兔小姐:『兔小姐,我觉得我们不能再将网点放在海盗岛上面,因为这个岛上面的情况太复杂,很容易就因为极端天气导致网点不可用。』 

『看起来是的,猪爸爸,那么我们怎么办呢?』 

『我们需要再找几个安全的地方设立新的网点,顺带将海盗岛的网点移除。』 

『是的,猪爸爸,可是我们要怎么做呢?直接找一个地方就对外提供服务吗?或者为了更加安全,我们直接多设置几个网点?』 

『当然不是的,兔小姐,为了保证数据的安全,我们需要做很多事情,防止我们在添加网点的时候出现多个 Leader 的情况。』 

『哦,好复杂,猪爸爸,你能详细解释一下吗?』 

『好的,兔小姐。』

Problem

『首先我们来看现在面临的问题,为了更好的举例,我就仍然以之前选举的例子,成员 A,B,C 来举例吧,兔小姐。』 

『好的,猪爸爸。』

『假设现在 A 已经是 Leader 了,我们有三个成员,这时候要加入两个新的成员,D 和 E,因为 D 和 E 在加入的时候,其实是会知道之前的 A,B,C,所以我们需要处理的问题就是如何让 A,B,C 能知道新加入的 D 和 E。』

『恩,这是一个问题。』兔小姐沉思道。 

『最简单的做法,就是我们有另外一个全局协调者,先依次告诉 A,B,C 休息一下,别开会了,第二天 D 和 E 要加入,这样大家都知道了最新的成员信息,然后第二天,就是五个成员开始竞选 Leader 了。这个方式最好,但有一个问题就是一段时间会议没法进行,对我们银行来说,也就意味着不能正常对外提供服务。』

这里, 其实就是一个集群成员变更常见的问题,当我们添加或者删除节点的时候,如何让其他的节点知道成员变更了。最通常的做法,可能就是通过一个全局的协调器,譬如 zookeeper 或者 etcd 这种的,做一个 Two Phase(2 PC) 的变更,但这样其实是有问题的,先不说 2 PC 一些 corner case 需要处理,整个过程还可能会导致暂时的服务不可用,虽然这个时间在多数情况下面可能比较短,所以 Raft 这边采用了另外一种做法,我们继续说明。

Add/Remove one Node

『那怎么办呢?』兔小姐继续问道。 

『为了保证在进行成员变更的时候,仍然能正常工作,我们可以这样做。不知道你还记不记得,当一个 Leader 被选出来之后,所有的操作都是由 Leader 进行的。兔小姐?』

『当然记得,猪爸爸。』 

『好的,所以这里,如果我们要添加新的成员,我们就可以直接告诉 Leader,然后让 Leader 再去告诉其他的 Follower,当这条消息被大多数成员确认了,我们就知道新的成员已经加入了。』 

『这方法不错,我们也不需要额外在用一个外部的协调人员了。』 

『是的,兔小姐,但这个方法也有一个问题,就是一次只能进行一个成员的变更,不能进行多个。』 

『哦,这是怎么回事?』兔小姐困惑的问道。 

『继续上面的例子,A,B,C,A 现在是 Leader,然后我们告诉 A 要加入了 D 和 E, A 给 B 和 C 发了消息,当我们确认这条消息被 committed 之后,A,B,C 都可能会 apply 这条消息,并且知道了 D 和 E 已经加入了。』

猪爸爸稍微休息了一会,继续说道:『那么,这时候,就有可能出现一种情况,C 先 apply 了这条消息,然后 C 就知道了 D 和 E,但 A 和 B 因为还没 apply,不知道 D,E。然后 C,D,E 三个就可能选出新的 Leader,譬如 E,因为根据我们之前的讨论,五个成员只需要三个成员同意,但这个时候,A 还认为自己是 Leader,于是我们这里出现了两个 Leader。』 

『那我们如何去防止这样的事情发生呢?』 

『很简单,兔小姐,我们一次只能进行一个成员的变更。譬如上面的例子,我们只能先加入 D,然后等 D 加入成功之后,才能加入 E。』 

『那这样为什么就没有问题呢?』 

『我们继续上面的例子,C 仍然先 apply 知道了 D,但 C 和 D 这边知道现在是四个成员,也就是至少需要三个成员投票才能选出 Leader,而 A 和 B 这时候因为根本还不知道 D,而且 A 仍然还是 Leader, 所以 A 和 B 都不可能给 D 投票。也就是说,只要我们能保证每次成员添加的时候,新的成员集合仍然跟老的成员集合大部分的成员是重合的,那么就不会有任何问题。』 

『恩,我想我大概明白了,那么对我们来说,现在要做的就是先移除掉海盗岛的网点,当海盗岛的网点移除成功了,我们在加入一个新的网点,是吧,猪爸爸?』 

『非常正确,兔小姐!』

在 Raft 的博士论文里面,当 Leader 收到 Configuration Change 的消息之后,它就将新的配置(后面叫 C-new,旧的叫 C-old) 作为一个特殊的 Raft Entry 发送到其他的 Follower 上面,任何节点只要收到了这个 Entry,就开始直接使用 C-new。当 C-new 这个 Log 被 committed,那么这次 Configuration Change 就结束了。当在 TiKV 以及 etcd 里面,我们并没有使用这种方式,只有当 C-new 这个 Log 被 committed 以及被 applied 之后,节点才知道最新的 Configuration 的情况。这样做的方式是比较简单,但需要注意几点:

  1. 当 Log 里面有一个 Configuration Change 还没有被 committed,不允许接受新的 Configuration Change 请求,主要是为了防止出现多 Leader 情况。

  2. 如果只有两个节点,需要移除一个节点,如果 Leader 在发起命令之后,另一个节点挂了,这时候系统没法恢复了。

Snapshot

好了,我们继续回到小镇银行这边,兔小姐跟猪爸爸选好了新的场地 - 森林小径,然后就准备开始海盗岛的网点替换工作了。但这时候,兔小姐突然想到一个严重的问题:

『猪爸爸,我们是可以建立新的网点,但这边新的网点现在可是完全没有数据的呀。』 

『这个问题非常的好,兔小姐,我完全考虑到了。一个最简单的做法,因为我们每笔交易都有记录,我们将记录从最开始以此重新发给新的网点不就可以了。』 

『这办法很不错,但我们银行现在已经开业这么久了,记录都有很多了,而且我们还在不停的交易,如果重头这么传输,不知道要多久呀!』兔小姐担心的问道。 

『是的,兔小姐,很佩服你能想到这个问题。所以这里我们需要的是一套 snapshot 机制。』猪爸爸回答道。 

『Snapshot,这个是什么?』

『就是镜像,兔小姐。你可以这样理解,虽然一个客户进行了很多笔交易,但在某一个时间点上面,客户的金钱总数就是一个固定的值。』 

『这个我能理解,猪爸爸。』 

『所以,我们只需要在一个时间点上面,记录下客户当前的金钱总数,然后将这条数据发送到新的网点,然后新的网点收到之后,直接在金库里面给对应的客户设置好相应的金钱。然后对于这个时间点后面新的交易,我们还是按照之前交易记录发送的方式来同步了。』 

『哦,猪爸爸,听起来有点糊涂,你能在详细解释一下吗。』 

『好的,兔小姐,我这里简单举一个例子,假设我们就一个客户,这个客户进行了 100 次交易,也就是我们现在有 100 条交易记录,100 次交易之后,客户的金钱是 100 块钱,我们只需要告诉新的网点这个客户是 100 块钱就行了。然后当这个客户继续进行第 101 次交易的时候,我们仅仅需要将 101 这次的交易记录发给新的网点就可以了。』 

『哦,我明白了,猪爸爸。』

Snapshot 虽然简单,但需要注意,假设 3 个节点,然后新加入了一个节点,如果 Leader 在给新的 Follower 发送 Snapshot 的时候,另一个 Follower 当掉了,这时候整个系统是没法工作了,只有等 Follower 完全收完 Snapshot 之后才能恢复。为了解决这个问题,我们可以引入 Learner 的状态,也就是新加入的 Learner 节点是不能算 Quorum 的,它不能投票。只有 Leader 确认这个 Learner 接受完了 Snapshot,能正常同步 Raft Log 了,才会考虑将其变成正常的可以 Vote 的节点。

Joint Consensus

虽然上面一次进行一个成员变更的方式已经能在生产环境中满足大部分情况,但还有一种 corner case 我们是没有办法解决的。假设现在我们有 3 个 IDC,用 A,B,C 来表示,每个 IDC 里面有两台机器,就是 A1,A2,B1,B2,C1,C2。现在有一个 Raft 副本在 A1,B1,C1 上面,这时候,如果我们发现 A1 压力比较大,要将副本转移到 A2 上面,那么有两种办法:

  1. 移除 A1,增加 A2

  2. 增加 A2,移除 A1

但无论是上面哪一种方法,都会有风险,譬如第一种,当 A1 移除之后,如果 B1 或者 C1 当掉,那么整个集群是不可用的。而对于第二种,A2 增加之后,如果这时候整个 IDC A 当掉,那么整个 Raft 集群也是不可用的了。也就是说,我们虽然将数据放在了 3 个 IDC 上面,但在一些情况下面,如果一个 IDC 整个当掉,都可能引起 Raft 集群不可用。

我们可以通过 Learner 的方式缓解这个问题,也就是先增加 A2,但 A2 是 Learner,只有 A2 完全追上了,我们才将 A2 给变成 Voter,然后在移掉 A1。但这个方式只是能减少不可用的概率,并不能完全防止,所以最好的做法就是支持 Joint Consensus 算法。

这个算法其实比较简单,相对于上面的一次成员变更的算法,它只引入了一个过渡状态,叫做 joint consensus。当一个 Leader 收到成员变更的请求的时候,他首先会将 C-old 和 C-new 都放在 joint consensus 里面(我们叫做 C-old-new),作为一个 Raft Log 发送给其他的 Followers。当节点收到 Log,不需要等待 Log 被 committed,就可以使用最新的 C-new 配置了,但这时候,仍然只有 C-old 里面的集群能进行 Vote。如果这时候 Leader 当掉了,新选出来的节点 要不在 C-old 里面,要不在 C-old-new 里面,因为我们前面没约定 C-old-new 这个 Log 必须 committed。但无论是哪一种 Leader,C-new 这边的集群都不可能单边决策的。

当 C-old-new 被 committed 之后,就进行了 joint consensus 状态,在这个状态里面:

  1. Log 会被复制到所有在两个 configurations 里面的节点上面;

  2. 在两个 configuration 里面的节点都可能被选为 Leader;

  3. 但只有 C-old 里面 majority 和 C-new 里面 majority 都同意,才能选出 Leader 和进行 Log 提交。

当进入 joint consensus 之后,Leader 就可以再次提交一个新的 C-new Raft Log,仍然是只要其他节点收到了这个 Log,就可以使用新的 Configuration 了,当 C-new 这个 Log 被 committed 了,那么 C-old 就没用了,不在 C-new 的节点就可以直接关闭。这套流程就能保证在任意时候,C-old 和 C-new 不会出现单边投票的情况。

虽然 joint consensus 很强大,但现在用的最多的仍然是一次成员变更的方法,毕竟很简单,而 joint consensus 我只在 LogCabin 中看到过,所以这里并没有很详细的介绍。一些 corner case 的处理大家可以直接去看论文了。

那没有 joint consensus,一些极端的 corner case 怎么办呢?可能就先忍忍呗,或者使用 5 副本,甚至用 7 副本。

小结

成员变更我认为算是 Raft 里面最难的概念,尤其是在 Raft 的 Paper 里面,重点就提到的是 joint consensus 算法,其实比较让人难以理解。这里其实就体现了一个工程上面的取舍,虽然我知道理论上面 100% 的事情怎么做,但为了更加简单,我可以稍微放低一点要求。

TiKV 和 etcd 现在都是没有用 joint consensus 的,但我们现在在开始添加 Learner,后面如果真的遇到了其他的 corner case,会不会考虑一下,没准也不是不可能的事情。

延展阅读

深入浅出 Raft - 基本概念

深入浅出 Raft  - Leader 选举

深入浅出 Raft - Optimization



长按关注

新型分布式 NewSQL 数据库

微信号:pingcap2015



 
PingCAP 更多文章 实录 | 黄东旭:开源与基础软件创业在中国 【Infra Meetup 预告】TiDB 遇到 Spark - T Cloud + TiDB 技术解读 深入浅出 Raft - Leader 选举 易观 OLAP 大赛揭晓 PingCAP 斩获商业组桂冠
猜您喜欢 今年的 WWDC 2017 为我们带来了什么? 【分析】百度29页PPT展示大数据的未来 本周互联网小事儿:Twitter开了设计博客 iOS完全自学手册——[三]Objective-C语言速成,利用Objective-C创建自己的对象 告别2016!你好,移动通信!