Raft原理

Raft原理 Raft 原理

Raft论文：https://pdos.csail.mit.edu/6.824/papers/raft-extended.pdf

本文只是初步了解Raft原理，后续将持续推出Fabric使用的Raft的详细实现，源代码分析。

动机

为了解决这样一个问题：
假设现在有两个服务器s1和s2，两个客户端c1和c2。

两台客户端需要连其中一台服务器呢，还是两台呢，如果只连一台服务器，那么没有一定的共识机制，两台服务器之间的数据会不一致，如果必须连两台呢？oh，It‘s worse。why？因为只要一台宕机，整个系统都不会work。

那么一定会说，那就搞个共识机制啊。确实。这个时候只要有一台服务器存在系统都能work。那么问题来了：假设因为网络原因导致网络分区了，就是说s1和c1在一个网络，s2和c2在一个网络，每个服务器都觉得自己是对的，这个时候数据不一致的问题又出现了。

原理

怎么解决以上问题呢？類

共识机制还是要搞的，系统还需要一个leader，这个就是说是这个网络中的老大，所有人都要听我的，我说执行这个就执行这个。有个leader能够简化很多问题，不会出现众说纷纭不知道听谁的现象发生。遇事也只能交给老大处理，其他人一概没有权利。

怎么选这个leader呢，既然是老大，肯定要得到众人的支持啊，但是都知道不可能所有人都会支持你嘛，那我也不寡，只要有超过一半的人支持我当老大我就可以当！少数服从多数。这还适用于leader执行 *** 作，当leader给其他服务器发送一个请求，只要得到超过半数节点的回复，就可以执行该请求了，不必再等待其他服务器的响应。

这里需要注意的是，总节点数必须是当前集群中的所有节点，而不是当前在线的节点数，即使宕机节点也算一个数。当然在已有集群中可以继续增加或者删除服务器。

为什么这样就能解决上述问题呢？

既然需要超过一半，那么系统中的节点数必须是奇数。这样无论怎么分区，至多只会有一个分区节点数超过一半。试想上述中的例子，如果是三台服务器，出现分区的话，那么好的情况是2+1的分区，只有1个节点的分区是无法选举leader的，因为获得的投票数肯定不会超过一半，它只能得到自己的投票，如果恰巧这个1就是leader，当它执行客户端请求的时候，是不会得到超过半数的回复的，这条请求不被执行就不会有数据不一致的情况。

leader选举

leader选举是一个很重要的步骤。

必须确保在每一个时刻都至多只有一个leader，否则会使系统崩溃。那怎么保证呢？

首先要知道term，即每一任leader都有一个专属的term。如果leader超时，即超过一定时间没有收到leader的消息，那么follower晋升成为candidate参与选举，并将自己的current term + 1。

每个server只能投出一票，注意candidate自己会给自己投票的，投完自己的票之后是不会再给别人投票的，这样就能够确保至多只有一个candidate能够获得超过半数的赞成票。既然对于leader的要求很高，所以也不是会对所有candiate都投赞成票，是有限制的，如果发现candidate的term比自己的current term小，投反对票，如果比自己高，比较log中最后一个位置的term谁的比较大，如果candidate的更大，投赞成票，如果一样，比较谁的log更长，如果candidate log更长，投赞成票。否则都是反对票。

Log 执行

raft是一个log为基础的共识机制。就是对于每个 *** 作都会记录下 *** 作的log。并且这些log是需要持久化的（具体多久持久化一次具体看Fabric的实现）。

raft的应用层需要依靠数据库，一般是KV数据库，比如说对数据库执行读写 *** 作，需要所有服务器上备份的数据都保持一致。

整个log执行过程如下：

• leader接收到来自客户端的 *** 作请求，将该 *** 作记录进log中，然后将该 *** 作（AppendEntry RPC）广播给所有followers，当followers将该 *** 作写入log后会返回成功的回复给leader。
• leader收集到超过半数的成功回复后，就会将该 *** 作抛到应用层，让应用层执行，应用层返回结果后，将该log apply到状态机中，表示该 *** 作已经被commit，然后把结果返回客户端。
• 上述 *** 作完成后，leader再次发送AppendEntry RPC，告诉followers我已经commit这个 *** 作了，你们也可以执行并且apply到状态机了。这次消息的发送可以是随着客户端下次请求的消息携带，亦或者是额外的消息，一般情况下使用前者。
• 如果这些 *** 作失败怎么办？会一直retry直到超时。

（在这里可以思考两个问题：1. leader这边网络故障只能发却不能收，导致整个系统并不work。2. Leader commit完之后还没来得及发送消息给followers就直接宕机了，那是不是系统整个就少了这个 *** 作的执行？）

这里还需要强调的一点是：leader的log只能增加而不能删除和修改，但是followers可以。

同步

日志是怎么做到大部分节点同步的呢？特别是在leader更换的时候。

当旧leader下线后，需要进行新的选举，新的leader选出来之后，需要给其他followers发送一条Append RPC消息，这个消息里面携带prevTerm和prevIndex，分别是上一个log index及其对应的term。那么follower收到后，首先对比对应index位置的日志，如果缺失或者index对应位置的日志的term对不上，返回消息说执行失败。当leader发现失败后，会回退index一位，再次发送Append RPC，直到超过半数的follower都强制统一了日志。

考虑以下场景：

如下图所示，s1、s2、s3分别为三台服务器，而后面的方框代表它们本地的日志，最上面的序号为日志的Index，方框中的值为term值，例如，s1目前日志中只有一条日志，即index为1的地方有一条term为1的日志。

图1.term1

如图1所示，在term1时，s3为leader，s1可能因为丢包没有同步第二条日志，这时候s3离线，造成leader的重新选举，这时候应该是s2当选leader，因为它的log比s1长，能够获得自己和s1的投票，已经超过半数了。

图2.term2

如图2所示，s2刚刚发送了一条来自term2的日志后还没来得及commit或者发送append消息就下线了，假设又因为网络原因导致s1也没有收到这条append消息，也可能是s2还没来得及发送，这时候假设s3又再次上线，同理，s3能当选leader。

图3.term3

如图3所示，s3当选leader后，它又发送了一条来自term3的日志，但是又因为网络原因，s1并没有收到，所以s3会超时，且s2已经下线了也是收不到的，这时s3宕机重启，s2也启动了，又会触发一次新的选举，在term4，按照规则，s2（自己和s1的投票）和s3（自己和s1或者s2的投票，如果s2还没有投给自己）都有可能获得超过半数的投票，所以都可能会再次当选leader，假设是s3成功当选，然后它需要发送一条来自term4的append消息告知follower，这时候我们看怎么同步日志。

图4.term4

如图4所示的日志，s2接收到来自term4的append消息，这条消息中携带了两个信息：1. prevLogIndex，即当选该term的leader前的一条日志，这里是3；2. preLogTerm，即即当选该term的leader前的一条日志所对应的term，这里是3。s2会对比Index为3上的log上的term，发现自己的是term2，不匹配，返回处理失败给leader，s3收到后，会回退一条日志，即到Index为2处，再次发送append消息，这时s2会发现这里的日志匹配，返回成功的消息，接下来会强制用leader的日志强制覆盖index为3处的日志。再看s1，会发现Index为3处的日志缺失，也会返回失败，leader回退一条，s1还是发现缺失，返回失败，leader再次回退，这时s1发现日志匹配，从这里开始补上s3的日志，这样就同步成功了。

其实通过上述过程也发现，如果缺失或者不匹配的日志过多，会有多次交互，但这些交互是不必要的，论文中也提到为了优化该过程，follower发现日志缺失或者匹配不上时可以在回复消息中携带额外的信息，冲突term的信息，以及该term的第一个index的位置，如果是缺失，那么返回其最后一条日志的index以及term。这样leader就能一次回退很多条日志，极大的减小了交互的开销。

快照

因为log需要持久化，如果log一直无限增长对于磁盘的消耗是很大的。这就需要避免这个问题。怎么避免呢？

快照！我们知道对于KV数据库而言，对同一个条目的很多个 *** 作最终都可以总结为一个结果，且其实作为优化，读 *** 作的log是不需要存储的，但是注意要保证顺序（TiKV是这样做的，具体实现可以看看）。

所以leader根据回复其实是可以确定多数服务器最后一个commit的log，那么从这个log往前都可以直接生成一个快照，并且删除这之前的log。这其实加大了系统启动恢复数据的复杂度，另外就是因为宕机原因服务器缺失删除log项的恢复机制。