深入浅出 Raft - Leader 选举

本文为我司首架唐刘老师的小猪佩奇版“深入浅出 Raft”第二弹。上篇内容戳这里 → 深入浅出 Raft - 基本概念

Leader

很快，泥坑银行就在回音山谷和海盗岛建立了网点。这时候，兔小姐就对猪爸爸说到：『猪爸爸，现在我们已经有三个银行网点了，那么我们是不是可以允许客户在三个地方都可以进行交易呢？』

猪爸爸想了想，说到：『恐怕不行，兔小姐。』
兔小姐奇怪的回复到：『为什么？，客户在任何地方交易，我们不是都可以先记录下来，然后通知其他两个地方，如果多数银行都确认了这笔交易，这不就行了吗？』
『因为我们的交易记录都是有唯一 ID，而且这个 ID 都是单调加 1 递增的。假设现在我们的交易记录 ID 是 10 了，如果我们允许在多个地方同时交易，譬如在泥坑小镇和回音山谷，那么这次交易的记录 ID 都是 11，这时候，海盗岛就会收到两个 ID 都是 11 的交易记录，海盗岛这边没法区分到底哪一个是正确的记录了。』
『嗯，这么说起来倒是的，但我们现在可是在三个地方都建立了银行网点，如果不使用，真的很可惜。』
『兔小姐，我们最开始在三个地方建立银行网点的目的就是为了完全保证数据的安全性，也就是如果一个地方出现了问题，我们的系统仍然能够正常的工作。』
『我明白了，猪爸爸。也就是说，我们的系统虽然部署在了三个地方，但同时只有一个能对外提供服务是吧？』
『是的，兔小姐。』
『那么，猪爸爸，我有个问题。我们是如何知道哪一个能对外提供服务呢？因为现在我们有三个网点，很有可能每个网点都认为自己能对外提供服务了。』
『这是个好问题，我们需要有一套机制，能让这三个网点自己选出一个 Leader 网点，对外提供服务。同时，如果这个 Leader 网点出现了故障，其他两个网点能够知道并再次选出一个 Leader 网点对外提供服务。』

猪爸爸接着道：『为了容易说明，我这里以我们实际的选举为例吧。假设现在有三个成员，A，B 和 C，他们三人会相互投票选出一个领导。这里我们先定义三种状态，Leader，Candiate 和 Follower。最开始三个人都是 Follower 状态，然后他们如果决定要选举了，就变成 Candiate 状态，如果一个 Candiate 收到了大多数的选票，那么这个 Candiate 就变成了 Leader。而这时候其他的成员都重新变成 Follower，只有 Leader 能跟外部进行交互。我这么解释你大概能明白吧，兔小姐？』
兔小姐：『是的，猪爸爸，我大概能明白这三种状态，也就是只要一个网点成为了 Leader，这个网点才能对外提供服务吧。』

好吧，又轮到作者吐槽自己吐槽了，现实中银行这么多个网点如果每次只能有一个主的银行网点能对外提供服务，那么这个银行应该会被客户给投诉了。但这里我们就假设这样吧。在 Raft 里面，每次只会有一个节点对外提供服务，这个节点就是 Leader，而其他的节点就叫做 Follower。当节点开始竞选的时候，它们就会从 Follower 变成 Candidate。

Election

猪爸爸喝了一口水，继续说到：『是的，兔小姐。我们继续以成员 A，B，C 为例。那我们现在要面临的第一个问题，就是这三个成员如何选出一个 Leader？』
猪爸爸：『我们先假设三个成员地上都有很多小石子，但他们手上都只有 0 颗。只有某个成员碰到了一些事件，他才会从地上捡起一颗或者多颗石子。到底是什么事件，我们稍后再详细解释。』
猪爸爸接着道：『最开始，我们知道三个成员都是 Follower。然后，我们约定一个时间，譬如 10 分钟之后吧，各个成员各自开始选举，变成了 Candidate，同时，各自从地上捡起来一颗石子。』
兔小姐：『看来，这就是你上面说的事件，也就是当一个 Follower 变成 Candidate 的时候，也就是自己开始新一轮选举的时候，就给自己加一颗石子吧。』
『非常正确，兔小姐。』然后猪爸爸接着说道：『 Candidate 会先给自己投一票，然后会给其他的几个成员发送投票信息，让它们选举自己成为 Leader。如果一个 Candidate 知道自己已经得到了大多数的选票，那么就能成为 Leader 了。』
『获得大部分投票就成为 Leader 这个就跟我们自己的选举一样的。但是，猪爸爸，自己给自己投一票我能理解，但其他人为什么要给我投票呢？』
『这是个好问题，兔小姐，你还记得我前面说的石子吧？』
『当然记得，猪爸爸，当开始选举的时候，就给自己加一颗石子。』
『是的，兔小姐。首先我们来考虑初始情况，这时候我们还没进行任何交易，交易记录还是 0。当一个 Candidate 给其他成员发送投票消息的时候，会带上自己的石子数量。当其他成员收到投票消息，如果发现自己的石子数量比收到的投票信息消息的石子数量要少，就给这个 Candidate 投票，同时自己变成跟随者，从地上捡起来足够多的石子直到自己的石子数量跟投票消息里面的一样。』
『如果自己的石子数量比投票消息的石子数量要多呢，我们如何处理？』
『兔小姐，如果是这样，那么就直接丢弃这条消息。我们通常不管石子数量比自己当前手上石子数量少的消息。』
『这主意不错，如果自己手上的石子数量跟投票消息里面的一样呢，我们又如何处理？』
『这个就要看自己是不是已经给其他人或者自己投票了，如果我已经给其他人或者自己投票了，我就给你回复一条拒绝消息。』
『我讨厌被拒绝。』兔小姐很伤心的说道，不过我想兔先生可不敢拒绝她。
『没办法，为了保证选举的安全，我们必须这样。所以对于一轮选举来说，它可能会碰到三种情况，自己变成了 Leader，其它节点变成了 Leader，以及没有选出 Leader。』
『为什么会没选出 Leader 呢？』
『考虑到这种情况，三个成员 A，B，C ，最开始石子数量都是 0，然后他们同时开始选举，先都给自己投了一票，这样所有人的石子数量现在都是 1，所以无论谁收到其他人的消息，都会回复拒绝，这样我们必须开始下一轮选举』
『但下一轮选举也可能没有选出来吧。』
『是的，兔小姐，你还记得我之前提到的 10 分钟吧。』
『记得，10 分钟之后，都开始选举。』
『如果每次大家重新开始选举的时间都是一样，很有可能都选不出来。所以我们可以约定一个时间范围，譬如 10 到 20 分钟，各个成员会随机在这个时间段里面选一个时间来等待，这样就能错开选举了。』
『这主意不错，这样选出来 Leader 的概率就大了很多。』

好了，说了这么多，该说说实际的 Raft 了。上面的石子数量就是 Raft 里面的 Term。每次开始一轮新的选举，Term 就加 1。如果选出了 Leader，那么就会 一直维持这个 Term，直到下一次选举。上面的 10 分钟就是  election timeout。

在实际 Raft 中，还有一些复杂的 corner case，譬如如果选出了 Leader，但另一个 Candidate 有更高的 Term，这样很可能会让 Leader 变成 Follower，或者让 Follower 给这个更高 Term 的 Candidate 重新投票。为了解决这样的问题，我们可以考虑 Pre-Vote，也就是一个 Follower 如果要开始投票，它并不会立刻变成 Candidate，给自己 Term + 1，而是会先变成 Pre-Candidate 的状态，用当前的 Term 去问其他的节点能否给自己投票，如果收到了大多数的同意消息，那么才会变成 Candidate 继续后面的选举流程。

另外，我们也可以考虑 Check Quorum，当一个 Follower 收到了更高的 Term 选举消息，如果它确信当前集群还在正在工作，也就是在 election timeout 的时间里面仍然收到了 Leader 的消息，那么这个 Follower 会直接丢掉这个消息。

这里我们只讨论了 Log 都没有的情况，对于已经有 Log 的情况，选举情况还要做一些其它判断，我们后续再说明。

Keepalive

猪爸爸休息了下，继续说道：『现在我们解决了第一个问题，就是如何选出一个 Leader。下面，我们就要面临两个问题。一个是如何让 Leader 一直能正常工作。另一个就是万一 Leader 出现了问题，其它的 Follower 如何知道，并开始重新选举？』
『这看起来有点复杂。』
『其实一点也不，兔小姐。当我们选出来 Leader 之后，Leader 就会就会开始处理外面的请求。你还记得我前面说的我们的安全交易模型吧？必须大多数节点都记录了这笔交易，我们才能实际交易。』
『当然记得，猪爸爸。』
『因为现在只有 Leader 能处理交易，所以每笔交易，Leader 都要发给 Follower，这样 Leader 和 Follower 之间就有了通信。所以只要我们一直有交易处理，这条通信链条就不会断掉，Leader 就一直能维持自己是 Leader 的状态了。』
『嗯，是这样的。但如果到了晚上，没有交易，怎么办呢？』
『这是个好问题，兔小姐。所以 Leader 会定期给 Follower 发送一条消息，说我现在还是 Leader，这个消息其实就是跟上面说的发送交易记录的作用一样的，只是让 Follower 知道 Leader 还在就可以了。』
『这主意不错，那如果很长一段时间 Follower 没收到 Leader 发过来的消息，那我们怎么办呢？』
『还记得我前面说的 10 分钟吧，我们可以继续约定，如果 10 分钟内，Follower 没有收到 Leader 的任何消息，那么 Follower 就认为 Leader 有问题了，这样 Follower 就开始重新选举。』

在 Raft 里面，如果选出来一个 Leader，Leader 会定期给 Follower 发送心跳，这个定期的时间我们通常叫做 heartbeat timeout，如果 Follower 在 election timeout 的时间里都没收到 Leader 的消息，就开始新一轮的选举。Heartbeat timeout 的时间要比 election timeout 小很多，譬如 election timeout 如果是 10s，那么 heartbeat timeout 可能就是 2s 或者 3s。

More about Election

兔小姐听完了猪爸爸的回答，仔细想了想，说道『猪爸爸，你前面说的重新选举，貌似假设的是初始情况，没有任何交易记录的情况。但我们选出了 Leader，这时候可能进行了很多交易了，那么这时候 Follower 再选举 Leader 还有啥需要注意的呢？』
『这个问题非常的好，兔小姐！』猪爸爸由衷的赞叹道。『之前，我们仅仅是通过石子数量来决定是否成为 Leader，但这样是远远不够的，我们还必须通过各自交易记录的数量来最终确定是否能成为 Leader。』
『要通过交易记录数量来确定？』兔小姐不解的问道。
『是的，兔小姐。你还记得最开始我说的交易记录的特性吧。每次交易，我们都会使用一个递增的唯一 ID 来标识记录。』
『我当然记得，猪爸爸』
『现在我们回到银行网点这边，假设它们之间选出泥坑小镇作为了 Leader，那么客户就能在泥坑小镇进行交易了。一段时间之后，泥坑小镇 这边进行了 10 次交易，也就是最后一次交易记录 ID 是 10。因为一次交易必须大部分银行网点都确定收到了这次交易记录，所以一定有一个网点交易数量是跟泥坑小镇 一样的，假设这里是回音山谷。而海盗岛可能稍微落后了，只有 9 条，最后一次交易记录是 9。如果只按照我们先前的石子数量来判断，如果海盗岛的石子数量最多，那海盗岛在泥坑小镇出现了问题之后，就会被选出 Leader，但实际是不允许的。因为只有回音山谷有最新的交易数据，但海盗岛没有。』
『虽然很绕，但我大概有点明白了，猪爸爸。也就是说，我们选举的时候，还需要判断，被选举者是否有最新的交易记录吧。』
『是的，兔小姐，所以 Candidate 在发送投票消息的时候，不光要带上石子数量，还需要带上自己最后一条交易记录的 ID。如果我收到了一条投票消息，发现这条消息里面的交易记录 ID 比我当前的还要大或者相等，那我就能认为发送这条投票消息的人有比我更多的交易记录，我就可以给他投票。』

在实际 Raft 里面，Candidate 给其他节点发送投票消息的时候，会带上自己当前最后一条 Log 的 Term 和 Index。如果投票消息的 Term 比自己最后一条 Log 的 Term 大，或者两个 Term 相等，但投票消息的 Index 大于或者等于自己最后一条 Log 的 Index，那么就可以给这个 Candidate 投票。至于为什么要同时判断 Term 和 Index，我们可以考虑一个 corner case，假设有 A，B，C 三个节点。

A 在 Term 10 被选成了 Leader，开始对外服务，假设这时候都把 Log 写到了 Index 99。

出现了脑裂，A 被隔离，但这时候，A 仍然收到了一个外部请求，先写入自己的 Log，A 的 last Log Index 是 100，但这个 Log 没法发送给 B 和 C。

B 和 C 重新开始选举，Term 增加，在 Term 11 的时候 B 成为了 Leader，对外服务。

B 在 Log 10 的位置写入了另一个新的 Log。

A 的网络恢复，开始给 B 和 C 投票，这时候 A 的 Term 可能已经是 12 了。

在 5 的时候，A 也有一个 Log 100，但这个 Log 其实是不正确的，所以 B 和 C 必须拒绝给 A 投票，所以这里我们要借助 Term。因为 A 写 Log 100 的时候，Term 还是 10，但 B 和 C 这时候写的 Log 100 里面的 Term 已经是 11 了，所以它们就会知道 A 并没有最新的 Log。

小结

好了，扯了这么多，都无非是说的 Raft 里面的 Leader Election，虽然 Raft 的 Leader Election 原理很好理解，主要还是一些 corner case 的问题，以及出现了一个坏的节点，如果让它别乱发投票消息，影响到整个集群。

延展阅读

深入浅出 Raft - 基本概念

长按关注

新型分布式 NewSQL 数据库

微信号：pingcap2015