对Raft的一些总结

​ 历时一个半月，总算完成6.824的四个Lab，虽然为了赶进度很多思路都是借鉴网上的博文，思路，但作为第一次接触分布式共识算法小白的我来说，也从其中学到了不少东西。在实现过程中，也遇到了许多Bug，一些Conner case要反复调试才能出来，对此，也认识到了实现一个可靠完备的共识算法是十分艰辛的。接下来，我会以问题的形式总结一些在实现6.824Lab过程中的思考，也是对Raft算法的一个个人总结吧。

Raft

为什么说Raft是强一致性的？

​ 这个问题是源于，看到部分博文说raft在接收到客户端请求并不能将entries同步到集群中的所有成员，所以并不能算强一致性。

​ 这里要先理解强一致性的概念，在剑桥大学一篇slide中，阐述了这一概念

Strong consistency – ensures that only consistent state can be seen.

• All replicas return the same value when queried for the attribute of an object All replicas return the same value when queried for the attribute of an object. This may be achieved at a cost – high latency.

Weak consistency – for when the “fast access” requirement dominates.

• update some replica, e.g. the closest or some designated replica
• the updated replica sends up date messages to all other replicas.
• different replicas can return different values for the queried attribute of the object the value should be returned, or “not known”, with a timestamp
• in the long term all updates must propagate to all replicas …….
  • consider failure and restart procedures,
  • consider order of arrival,
  • consider possible conflicting updates consider possible conflicting updates

​ 意思是，强一致集群中，对任何一个节点发起请求都会得到相同的回复，但将产生相对高的延迟；

​ 而对于弱一致性，则具有更低的响应延迟，但有可能回复过期的数据；

​ 最终一致性是弱一致性的特别情况，它是指数据会经过一段时间后达到一致性。

可以看出来，强一致性强调的强一致性读，即不会读到过期的结果。而并不要求将每个写请求都写到集群中的每个节点上。

领导选举的过程

​ Raft对于每个节点会有三种状态：Candidate，Follower，Leader。使用发送RPC的请求的方式进行选举。对于Follower，会维护一个随机时长的定时器，当没有收到Leader心跳检测并且定时器时间到，就会触发选举。这是，该Follower会转变为Candidate，并且Term++，然后向所有节点发送RequestVote RPC。等待其他节点投票给自己。

​ 如果该Candidate收到的选票超过半数，就会转变为Leader，并且立即发送AE给其他节点；如果其他节点赢得了选举，会导致接下来发送RequestVote RPC中Term小于该节点的Term或者说相等但该节点已经投了自己，这是就会使得自己转变为Follower；还有一种平票的情况，很极端，但有可能发生，那么这时候不会出现Leader，因为没有一个节点的票超过半数，这是等待选举计时器再次到（随机时间很重要），再次触发选举。

日志复制

​ 一旦Leader被选举出来，就会开始为每个节点提供服务。客户端发送给Leader节点请求，Raft层收到后会生成一个Entry，通过发送AppendEntries RPC（简称AE）复制给其他的节点，其中包含了Leader含有的所有日志条目（包括刚刚的Entry），还有一些其他信息（任期号，ID，前一日志任期号和索引【用于检查日志是否过期以及执行快照】，Leader提交的日志号）。

​ Follower再确认Leader身份后，就需要重置定时器，然后判断当前Follower是否复制过了该节点

return index <= rf.getLastLog().Index && rf.logs[index-rf.getFirstLog().Index].Term == term

​ 一旦不满足上述要求，说明 日志缺失 或者 日志过老，对于前者，需要使用conflictIndex返回缺失的第一个Index，等待下次AE进行复制；对于后者，则需要根据任期找出第一个不匹配的日志，设置conflictIndex，然后等待下次AE进行覆盖。

​ 下次AE就可以确定该节点冲突的Index和Term，从而进行日志拷贝。

安全性

​ 所谓安全，我认为是指作为Leader的节点必须要具有日志控制的绝对权。因为在不可靠的网络中，Leader是十分有可能宕机，而新Leader是否如何处理一些不正常的日志就变得尤为关键，另外还有Follower和Cadidate宕机的情况。

​ 对于Leader宕机的处理情况，我们需要加入选举约束和新Leader不能提交之前任期内的日志条目来保证：

​ 选举约束：这是在选举时增加对日志最后条目的判断，也就是通过索引和任期来判断哪个日志更新，如果任期号不同，任期号大的更新；任期号相同，日志较长的更新。

​ 新Leader不能提交之前任期内的日志条目：也就是说Leader只会计算自己产生的新日志的副本条目来判断是否提交。具体见Lab2文章分析

持久化，哪些需要持久化，为什么；为什么其他不需要？

​ 根据Figure2，所知道的状态有：

• currentTerm：从0开始递增，server所知道的最大的Term号
• voteFor：server投票给的Cadidate ID
• log[]：server维护的日志列表
• commitIndex：server提交的最高日志索引值
• lastApplied：状态机apply的最高日志索引值
• nextIndex：集群中每个节点待接收的日志索引号（模糊）
• matchIndex：集群中每个节点和该server对齐的日志Index（准确）

currentTerm

​ 这是需要持久化的。试想，如果三个节点都挂了，那么它们重启后currentTerm都会变成0，进而election timeout后currentTerm变成1，如果之前的日志Term比1大，那么就无法选举出Leader。

​ 那么，为什么不使用log最新的term来进行代替呢？

​ 考虑一种情况：

1. S1作为日志Term从5开始，S2，S3也是从5开始
2. 此时，S1发起选举并获得大多数选票成为Leader，并收到Client的一个请求，此时增加日志Term=6，但是没发出AE就crash（也就是还没有进行日志复制）
3. 这时，S1飞速重启，又像上一步一样成为Leader，收到请求，增加日志Term=7，然后crash
4. S2，S3此时currentTerm应该是7，这是由于在收到投票请求时更新了。那么这两个节点在进行下次选举将会用Term=8
5. 但是，如果此时S2，S3 crash了，如果没有持久化currentTerm，他们就会用Term=6进行选举（因为最新日志是5）
6. 那么问题出现了，在同一个Term中会出现两个Leader（S1之前Term=6也是Leader）

votedFor

​ 这是需要持久化的。同样考虑一种情况：

1. S1获得S1和S2的选票，并且成为Term=1的Leader
2. S2突然crash又重启，vateFor变为-1
3. S3也发起Term=1的选举，获得S2和S3的投票，成为Term=1的Leader（S1：握草，你这家伙怎么出尔反尔，说好只投我呢（）
4. 此时，问题就是同一个Term出现两个Leader

log[]

​ 这个我想必须持久化吧。这是唯一能用来重建应用程序状态的信息，如果上层突然挂了，还可以通过log来恢复

commitIndex & lastApplied

​ commitIndex不需要持久化，这可以通过follower和leader的几次RPC通信就可以确定

​ lastApplied感觉也不需要持久化

nextIndex[] & matchIndex[]

​ 这两个是用于Leader和Follower同步日志的，当Leader crash之后，恢复由于不再是Leader，因此持久化了也没有任何意义。

Raft有哪些优化方式？

Read Index

​ 如果没有优化，对于读请求Raft会走一遍log（也就是同步log），由于WSL是顺序写入，故可以实现线性Read。但这样其实效率比较低，其实我们只需要保证当前读的一定是commit之后的即可，也就apply要达到之前commit的值即可返回最新写入的值。那么，我们可以维护一个ReadIndex：

1. 将当前自己commit Index记录到一个local变量ReadIndex里
2. 向其他节点发送一个heartbeat，如果大多数节点返回了heartbeat response，那么leader就能确定现在自己仍然是leader
3. Leader等待自己的状态机执行，直到apply index 超过 ReadIndex，这样就能提供线性读了
4. Leader也可以执行Read请求，将结果返回给client

Lease Read

​ Read Index的优化方式会多出一次heartbeat的开销，在论文中还提到一种通过 clock + heartbeat 的 lease read 优化方法。就是 leader 发送 heartbeat 的时候，会：首先记录一个时间点 start，当系统大部分节点都回复了 heartbeat response，那么我们就可以认为 leader 的 lease 有效期可以到 start + election timeout / clock drift bound这个时间点。

​ 也就是在上述Read Index的2步骤通过该方法判断是否为leader，会减少这次开销

Asynchronous Apply

​ 由于一旦log被commited了，被commited的log在任何时候被apply都不会影响数据的一致性，当一个log被commited之后，我们可以用另一个线程去异步apply这个log。

1. Leader接受一个client的request
2. Leader将对应的log发送给其他的follower并本地append
3. Leader继续接受其他client的request，然后持续执行2
4. Leader发现log已经被commited，在另一个线程apply
5. Leader异步apply log之后，返回结果给对应的client

PreVote——用于避免多余选举

​ 如果一个Follower因为物理隔离，那么由于无法和其他节点互通，便会不断发起选举，并term++。如果网络恢复，此时会产生：

• 原集群更新了许多日志和经历了很多此Term，这时Cadidate就会变为Follower
• 原集群没变化，这时就会发起新的选举，有可能导致Leader的改变，影响性能

​ 使用Prevote流程

1. 节点A决定选举，先不自增Term，向其他节点发送一个Prevote消息，携带的内容和RequestVote一致（Term都是A的Term+1）
2. 其他节点收到消息后，判断是否支持该选举请求，并返回结果。判断方式和RequestVote一致，但不更新自身的投票状态
3. A统计所有票数，如果确认可以当选，则A正常发起选举流程

CheckQuorum——退化机制

​ 如果一个Leader被单独隔离，这样Leader和其他节点无法通信，那么在其他节点中会再选举出一个新Leader，这时如果老Leader恢复网络，那么在一段时间内，上层Client发送请求到老Leader，就会导致Group无法正常工作

​ 所以，使用CheckQuorum这一类似心跳消息，Leader每隔一段时间发送，如果发现自己的连接节点没有超过半数，则退化为Follower。

Raft如何缓解leader同步数据量随着节点数增长而增长的问题？

​

Muti-Raft

muti-Raft是什么

​ 分布式系统的实现最大原因是为了解决单机的不可扩展性，提高存储系统的伸缩性；此外，单机由于都是Leader处理写请求，性能不好。为了支持大容量数据与高性能，就需要设计多个Raft集群，也就是multi-Raft。对于每个集群，也称为Group，集群中维护了不同分片数据，客户端在GET时，会向一个中心节点，称为ShardCtrler（TiDB中称为PD）发送请求，得到该分片所在Group对应的Server的元数据，从而发送请求到服务端。

multi-Raft需要解决哪些问题？

1. 数据如何分片
2. 如何让分片在系统中分布的更加均匀（分片迁移）
3. 如果删除已经不需要分片
4. 如果在分片迁移时依旧提供给客户端服务
5. 如何处理Snapshot

​

参考

TiKV 功能介绍 - Raft 的优化 | PingCAP