有一些分布式经验的同学应该都多少听过一些分布式的概念,没有听过也应该是直接或者间接接触过,例如搭建了一个 MongoDB 的集群,会有不同的配置方式,其中有一种叫做 Replica Set 的方式:

也就是说假设你有三台机器,三台机器共同存储了你的数据,当你的客户端想操作数据的时候,不用每台机器都单独得去写一遍,反之则是写到其中一台叫做 Primary 的机器上,然后再将 Primary 的操作记录(log)分发到其他两台机器(Secondary),然后在 Secondary 上重做操作记录,从而让你的操作在所有的机器上生效。

那么这里就有个很严肃的问题来了,既然有 3 台机器,那么谁来当 Primary?要想实现这一步可能还比较容易,大家猜拳决定呗,每个人随机出一个数字,谁大谁当,好办!那么问题又来了,如果一个人出了一个数之后,发现它是最大的,但是它又马上挂掉了怎么办?还有,如果大家的交流不畅,A 可以和 B 通信,但是 A 和 C 不能通信怎么办,类似的问题还有很多,其他归纳起来就是所谓的 CAP 无法全被满足。

为了提高整体体验,于是就有了各种共识算法,比特币的 POW 其实也是一种,但是,今天要聊的是 Raft 共识算法,Raft 共识算法被越来越多应用接受,用于替代 paxos。

Raft 共识算法

在开始 Raft 算法介绍之前,先来介绍一个简单的场景,类似于 Redis,就是一个 Client 往 Server 中写入一个值:site=https://liqiang.io,那么在单机部署的情况下应该是这样的:

这个很简单,Client 只要根据调用 Server 是否成功即可判定是否数据写入成功,当然,你得保证你 Server 的实现逻辑是正确的,如果 Server 自身都是错误的,那么就没啥共识可谈了。然后,当负载变大之后,你决定增加 Server 了,问题也就接着来了:

Server 的代码要怎么写?于是乎,Raft 算法就纳入了考虑,在 Raft 算法中,Server 统称为 Node,Node 有三个状态,分别是:

Raft 共识算法开始的时候,所有的节点都是 Follower,而 Raft 算法的协议就是如果一个 Follower 在一个时间区间内(150ms - 300ms 之间的随机数)没有收到 Leader 的心跳,那么就可以成为 Candidate。那么在这条规则之下,总会有一个 Follower 因为时间随机得短先行行动,成为 Candidate,从而告知其他 Follower:

如果 B 和 C 在接到 A 的通知之前自己的随机时间还没超时,那么都会回应 A:"行吧,就你了",这样 A 就顺理成章得成为了 Leader。

当然,有时可能有的人反应比较慢,或者说有的人根本就没听到 A 的呼喊,所以 A 是怎么也收不到他们的回应的,然而,没关系,在 Raft 算法中要求,只要超过 1/2 的节点认可,那么就可以了。也就是说 3 节点里面只需要 2 个节点(包括自己)认可,5 个节点里面只要有 3 个节点认可就够了,因为这样可以保证全局只有一个 Leader!

这个过程就是 Leader 选举啦!

那么这里面还有些问题需要解释,第一个就是当 A 准备成为 Candidate 的时候,那么不巧 B 也准备成为 Candidate,那么怎么办,这种场景在 3 节点上没啥好说的,因为谁争取到了 C 的票谁就是 Leader 了,咱们来看个有趣的,就是 4 个节点的时候:

然后更有趣的就是 C 和 D 一个回一个:

因为在 Raft 中还有一个递增的选举编号,表示这是第几轮选举,因为这时大家都是从一致的状态开始选举的,所以轮数(Term)都是一致的,而每个节点每轮只能发表一次,所以 C 和 D 互相回了一个没问题,这种情况下的话,会出现的一个情况就是大家都不是 Leader 状态,其中:

在这个时候,A、B、C 和 D 四个节点中只要有谁的倒计时先到 0,那么就会成为 Candidate 向其他节点发出下一轮的选举,直到被大多数节点认可成为 Leader。

所以注意到这里节点的状态都是通过倒计时来完成的,因此倒计时在 Raft 中的作用很重要。同时 Leader 和 Follower 之间会有心跳进行通信,一旦没有收到心跳,就会马上造反,出来选举搞事情。因此,节点之间的网络很重要!

复制集

有了 Leader 之后又有什么用呢?还是之前那个例子,当一个 Client 要想往 A、B 和 C 中写入数据的时候,这时可以先找到 Leader,然后先在 Leader 中写入数据(实际还未提交,只是 pending),并且由 Leader 生成一条操作日志:

然后 A 再将这个操作日志伴随心跳传递给 B 和 C,B 和 C 接收到之后,再根据这个操作日志在自己的数据中执行一遍,从而达到和 A 一样的状态,然后告诉 A 他们可以了:

当大多数的节点(超过 1/2)都接受这个操作日志之后,节点 A 就提交,那么写入的数据就持久化保存在 A 中了,然后 A 再告诉 B 和 C 提交了,B 和 C 再提交,这样就将数据持久化到大多数节点中了。

这里需要注意到的一点就是,Leader 节点 A 是在往 Follower 的 HeartBeat 中发送操作日志的,并且要等到大多数的节点都认可之后才告诉 Client OK 的。这也就是说 Client 最多要等待两个 Heartbeat 的周期才能收到 Server 的响应,这点很重要!

如果在使用的过程中,有部分节点失联了怎么办?这个在 Raft 中也挺好处理的,还是坚持大多数的原则,假设有 5 个节点,因为是 A、B、C、D 和 E。A 和 B 和其他小伙伴失联了,但是他们之间是好的,那么有两种情况:

如果 A 和 B 之间有一个原来是 Leader

假设 A 是 Leader,那么 A 就可以接受 Client 的请求,但是因为得不到大多数节点的响应,所以所有的操作都是 未提交 的,因为至多也就 2 票,无法满足大多数。

而 C、D 和 E 在 Leader A 失联之后,因为可以满足大多数的情况,所以假设 C 成为了 Leader,所以也可以接收 Client 的请求,并且因为可以得到大多数人的认可,所以也可以提交数据。

当这样持续一段时间之后,如果 A 和 B 永远不回来了,那么也没他们什么事了,一切都很正常。如果有一天 A 和 B 回来了,那么因为 C、D 和 E 的选举 ID 会比 A 和 B 高,所以 C 就会将 A 和 B 失联期间的所有操作日志都丢给他们,让 A 和 B 重做这些日志,从而恢复到 C、D 和 E 一样的状态。

如果 A 和 B 之间没有任何一个是 Leader

那么 A 和 B 之间就会发生选举,但是怎么也产生不了 Leader,因为永远也不可能得到大多数人的认可,这样下去的话,当有一天 A 和 B 和其他节点又恢复联系之后,这时就有点意思了,这里按理说 A、B 的选举轮数应该会比 C、D 和 E 高很多,毕竟他们没事就在那选举嘛,那么这个时候要不要让他们成为 Leader 呢?

这里有涉及到 Raft 的另外一条 Follower 的应答机制了,Follower 只有在选举轮数比自己存的高,并且目标节点的日志信息不比 Follower 旧的时候才会同意,那么很显然,除非在这期间 C、D 和 E 都没有作过更新,那么才会成立,否则那么还是必能成为 Leader 的。如果 C、D 和 E 都没更新过,那么让 A 和 B 其中一个做 Leader 也没什么问题。

Reference