Raft协议的一些总结

转载于 : https://zhuanlan.zhihu.com/p/51358042

参考资料

什么一致？

一致性协议都是为了保证所有的节点状态是一致的，而一致的日志输出到状态机就可以产生一致的状态，所以只需要保证日志是一致的。

怎么保证？

简化问题

首先明确一下适用的场景：异步网络通信环境，非拜占庭错误。设想一种理想情况，没有节点宕机和网络分区发生。这样保证起来就会很简单，所有的请求都发给leader，leader把日志都同步给follower后，将日志提交到状态机。由于所有的follower都是复制的同一个leader的日志，自然大家都是一致的。然而现实情况不会这么完美，在分布式系统中节点宕机，网络分区是常态，所以我们要解决可能出现的问题。

现实情况下会出现什么问题

leader出故障了
follower出故障了
网络分区了

下面分别阐述Raft是怎么解决这三个问题的

1. leader出故障了

这是最复杂的情况，会影响选主和日志的同步

选主
由于我们在上面说的理想情况下，follower都是复制的leader的日志，所以我们必须保证集群中任何时刻都存在leader，并且期望有且只有一个，因为leader大于1个时，日志就出现冲突了。当leader出故障时，必然就需要重新选一个leader，所以Raft就设计了选主的算法，具体算法直接看论文就可以了。这里提出几个问题：

为什么要设置任期号?
任期号在Raft中(以及其它的一些一致性协议中)非常重要，它其实代表了当前节点的状态是否足够新，因为我们总是认为新的更为准确。在分布式环境中，节点可能会收到彼此冲突的消息，那选哪个呢，就选任期号大的，所以在发动选举时，就会将任期号加一来保证新的leader会被识别为更新的。
什么时候leader会大于1个，怎么处理?
当网络分区时，就可能出现leader大于1个的情况，普通的网络分区比较简单，比如A,B和C，D，E出现了分区。这里讨论一种稍微复杂的情况，比如当前有A,B,C,D,E五台机，A为leader，此时A和B二者的网络出现分区，但是A,C,D,E以及B,C,D,E都可以正常通信，由于B超过一定时间没有收到leader的心跳，这时候B的term+1，发起新的选举，然后分两种情况:1.在B选举之前，A向C,D,E写了新的日志，那这时候B的日志不是最新的，选举永远不会成功，相当于此时集群中A,C,D,E会正常对外服务，leader不变 2.在B选举之前，A没有写新的日志，由于B的term更大，所以C，D，E会投票给B，这时候B成为新的leader，在此刻集群中出现了A,B两个leader，但A发出的请求不会被多数派通过(因为C,D,E的term更大)，所以对外是一致的。所以即使出现了两个leader，Raft也可以保证确定log的时候不会有冲突。但有一个问题是，A在向C,D,E发心跳包的时候，从响应中可以知道自己的term落后了，就降为follower。然后，A也有可能再按照B的方式发起选举，这样就周而复始不断选举，造成很大的网络开销，这个可以通过pre-vote解决。

pre-vote说明：

Raft协议的一些总结

Follower_2在electionTimeout没收到心跳之后,会发起选举，并转为Candidate。每次发起选举时，会把Term加一。由于网络隔离，它既不会被选成Leader，也不会收到Leader的消息，而是会一直不断地发起选举。Term会不断增大。

一段时间之后，这个节点的Term会非常大。在网络恢复之后，这个节点会把它的Term传播到集群的其他节点，导致其他节点更新自己的term，变为Follower。然后触发重新选主，但这个旧的Follower_2节点由于其日志不是最新，并不会成为Leader。整个集群被这个网络隔离过的旧节点扰乱，显然需要避免的。

在PreVote算法中，Candidate首先要确认自己能赢得集群中大多数节点的投票，这样才会把自己的term增加，然后发起真正的投票。其他投票节点同意发起选举的条件是（同时满足下面两个条件）：

没有收到有效领导的心跳，至少有一次选举超时。
Candidate的日志足够新（Term更大，或者Term相同raft index更大）。

日志同步
论文列举了几种leader和follower的日志不一致的情况，但除了(a)，本质原因都是由于这个follower以前是leader，当有未提交的日志时挂了，等恢复成follower的时候，就跟当前的leader日志不一致了。当出现不一致时，Raft采取的做法是用Leader的日志覆盖Follower的日志。这里提出几个问题：

为什么leader将某个log entry设为commited之后，这个log entry之前的所有log，包括其他leader的log，都是可提交的?
因为日志匹配特性，某个日志是commit，说明leader和大多数节点在这条日志以及这条日志之前的日志都是相同的，因此都是可以提交的。
leader完整特性怎么证明？有什么作用?
证明：虽然论文上的证明比较长，但可以由日志匹配特性直接得出leader完整特性，假设leader1不包含之前的某个leader2已经commit的日志，而如果这条commit的日志是最后一条日志，那这个leader1因为日志不够新不会赢得选举;如果这条日志不是最后一条日志，那leader1的最后一条日志在被append的时候（那时候leader1还是follower），就会被当时的leader发现leader1中间缺失了一条commit日志，append就会失败。
作用：由于每个leader都包含之前的term被commit的所有日志，就意味着不管leader怎么改变，已经commit的日志不会丢，所以输入到状态机的日志就是一致的，保证了状态机安全特性。 3. 为什么需要日志匹配特性？
日志匹配特性的目的有两个：一是为了得到leader完整特性，二是保证如果一个log entry可以commit了，那它之前的entry都是可以提交的。第二个目的让leader可以顺序的commit日志，进而状态机也可以顺序的apply日志，简化了处理逻辑。假设我们可以放弃这两个目的(比如ParallelRaft)，比如通过其他措施来保证leader完整特性和状态机的安全特性，那我们就可以放弃日志匹配特性，那follower每次AppendEntry的时候就不用等待前面的entry都Append，就可以提高系统的整体吞吐。

2.follower出故障了

只要出问题的follower小于总节点数量的一半，整个Raft Group就能正常工作。由于不一致时，follower会用leader的日志覆盖自己的，所以不管follower出什么问题，leader会对follower不断重试，只要在恢复时通过RPC将follower的日志恢复成leader的即可。

3.网络分区

网络分区可能会导致脑裂问题，在选主的第3个问题讨论了网络分区对选主的影响。同时，网络分区还可能会导致stale read, 可以通过ReadIndex Read和Lease Read的方法来解决，具体参考https://pingcap.com/blog-cn/lease-read/这篇文章。当 raft group 发生脑裂的情况下，老的 raft leader 可能在一段时间内并不知道新的 leader 已经被选举出来，这时候客户端在老的 leader 上可能会读取出陈旧的数据（stale read）。

具体如下：

Raft log read

TiKV 是一个要保证线性一致性的分布式 KV 系统，所谓线性一致性，一个简单的例子就是在 t1 的时间我们写入了一个值，那么在 t1 之后，我们的读一定能读到这个值，不可能读到 t1 之前的值。

因为 Raft 本来就是一个为了实现分布式环境下面线性一致性的算法，所以我们可以通过 Raft 非常方便的实现线性 read，也就是将任何的读请求走一次 Raft log，等这个 log 提交之后，在 apply 的时候从状态机里面读取值，我们就一定能够保证这个读取到的值是满足线性要求的。

当然，大家知道，因为每次 read 都需要走 Raft 流程，所以性能是非常的低效的，所以大家通常都不会使用。

我们知道，在 Raft 里面，节点有三个状态，leader，candidate 和 follower，任何 Raft 的写入操作都必须经过 leader，只有 leader 将对应的 raft log 复制到 majority 的节点上面，我们才会认为这一次写入是成功的。所以我们可以认为，如果当前 leader 能确定一定是 leader，那么我们就可以直接在这个 leader 上面读取数据，因为对于 leader 来说，如果确认一个 log 已经提交到了大多数节点，在 t1 的时候 apply 写入到状态机，那么在 t1 之后后面的 read 就一定能读取到这个新写入的数据。

那么如何确认 leader 在处理这次 read 的时候一定是 leader 呢？在 Raft 论文里面，提到了两种方法。

ReadIndex Read

第一种就是 ReadIndex，当 leader 要处理一个读请求的时候：

将当前自己的 commit index 记录到一个 local 变量 ReadIndex 里面。
向其他节点发起一次 heartbeat，如果大多数节点返回了对应的 heartbeat response，那么 leader 就能够确定现在自己仍然是 leader。
Leader 等待自己的状态机执行，直到 apply index 超过了 ReadIndex，这样就能够安全的提供 linearizable read 了。
Leader 执行 read 请求，将结果返回给 client。

可以看到，不同于最开始的通过 Raft log 的 read，ReadIndex read 使用了 heartbeat 的方式来让 leader 确认自己是 leader，省去了 Raft log 那一套流程。虽然仍然会有网络开销，但 heartbeat 本来就很小，所以性能还是非常好的。

但这里，需要注意，实现 ReadIndex 的时候有一个 corner case，在 etcd 和 TiKV 最初实现的时候，我们都没有注意到。也就是leader 刚通过选举成为 leader 的时候，这时候的 commit index 并不能够保证是当前整个系统最新的 commit index，所以 Raft 要求当 leader 选举成功之后，首先提交一个 no-op 的 entry，保证 leader 的 commit index 成为最新的。

所以，如果在 no-op 的 entry 还没提交成功之前，leader 是不能够处理 ReadIndex 的。但之前 etcd 和 TiKV 的实现都没有注意到这个情况，也就是有 bug。解决的方法也很简单，因为 leader 在选举成功之后，term 一定会增加，在处理 ReadIndex 的时候，如果当前最新的 commit log 的 term 还没到新的 term，就会一直等待跟新的 term 一致，也就是 no-op entry 提交之后，才可以对外处理 ReadIndex。这是为了确保当前没有提交的日志也能尽快得到提交。

使用 ReadIndex，我们也可以非常方便的提供 follower read 的功能，follower 收到 read 请求之后，直接给 leader 发送一个获取 ReadIndex 的命令，leader 仍然走一遍之前的流程，然后将 ReadIndex 返回给 follower，follower 等到当前的状态机的 apply index 超过 ReadIndex 之后，就可以 read 然后将结果返回给 client 了。

Lease Read

虽然 ReadIndex 比原来的 Raft log read 快了很多，但毕竟还是有 Heartbeat 的开销，所以我们可以考虑做更进一步的优化。

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

为什么能够这么认为呢？主要是在于 Raft 的选举机制，因为 follower 会在至少 election timeout 的时间之后，才会重新发生选举，所以下一个 leader 选出来的时间一定可以保证大于 start + election timeout / clock drift bound。

虽然采用 lease 的做法很高效，但仍然会面临风险问题，也就是我们有了一个预设的前提，各个服务器的 CPU clock 的时间是准的，即使有误差，也会在一个非常小的 bound 范围里面，如果各个服务器之间 clock 走的频率不一样，有些太快，有些太慢，这套 lease 机制就可能出问题。

TiKV 使用了 lease read 机制，主要是我们觉得在大多数情况下面 CPU 时钟都是正确的，当然这里会有隐患，所以我们也仍然提供了 ReadIndex 的方案。

TiKV 的 lease read 实现在原理上面跟 Raft 论文上面的一样，但实现细节上面有些差别，我们并没有通过 heartbeat 来更新 lease，而是通过写操作。对于任何的写入操作，都会走一次 Raft log，所以我们在 propose 这次 write 请求的时候，记录下当前的时间戳 start，然后等到对应的请求 apply 之后，我们就可以续约 leader 的 lease。当然实际实现还有很多细节需要考虑的，譬如：

我们使用的 monotonic raw clock，而不是 monotonic clock，因为 monotonic clock 虽然不会出现 time jump back 的情况，但它的速率仍然会受到 NTP 等的影响。
我们默认的 election timeout 是 10s，而我们会用 9s 的一个固定 max time 值来续约 lease，这样一个是为了处理 clock drift bound 的问题，而另一个则是为了保证在滚动升级 TiKV 的时候，如果用户调整了 election timeout，lease read 仍然是正确的。因为有了 max lease time，用户的 election timeout 只能设置的比这个值大，也就是 election timeout 只能调大，这样的好处在于滚动升级的时候即使出现了 leader 脑裂，我们也一定能够保证下一个 leader 选举出来的时候，老的 leader lease 已经过期了。

当然，使用 Raft log 来更新 lease 还有一个问题，就是如果用户长时间没有写入操作，这时候来的读取操作因为早就已经没有 lease 了，所以只能强制走一次上面的 ReadIndex 机制来 read，但上面已经说了，这套机制性能也是有保证的。至于为什么我们不在 heartbeat 那边更新 lease，原因就是我们 TiKV 的 Raft 代码想跟 etcd 保持一致，但 etcd 没这个需求，所以我们就做到了外面。

Multi-Raft

数据量大的时候，单个Raft实例负载太高，为了提高整体吞吐，往往将数据分为多个片，每个片由独立的Raft Group来管理。会有一个类似于元数据服务器的东西来管理所有的Raft Group，负责数据的分片，Group间的负载均衡等，难点Elasticell-Multi-Raft实现这篇文章提到的：

数据何如分片
分片中的数据越来越大，需要分裂产生更多的分片，组成更多Raft-Group
分片的调度，让负载在系统中更平均（分片副本的迁移，补全，Leader切换等等）
一个节点上，所有的Raft-Group复用链接（否则Raft副本之间两两建链，链接爆炸了）
如何处理stale的请求（例如Proposal和Apply的时候，当前的副本不是Leader、分裂了、被销毁了等等）
Snapshot如何管理（限制Snapshot，避免带宽、CPU、IO资源被过度占用）
具体可以参考上面这篇文章看看他们是怎么解决这些问题的

ParallelRaft

这是在阿里的PolarFS中提出的对Raft在高I/O场景下的一种改进。具体来说就是Follower可以乱序确认，leader可以乱序提交，状态机可以乱序应用。
乱序确认是指Follower可以不管日志匹配特性，直接确认，所以我认为面向云数据库，超低延迟文件系统PolarFS 诞生了这篇文章中提到的ParallelRaft继承了Raft的LogMatching特性应该是有问题的，因为如果是乱序确认是没法满足LogMatching的。但是日志匹配特性的不满足就会导致leader完整特性的不满足，所以ParallelRaft用了另外的手段来满足leader完整特性，就是在leader选举的时候将leader中的log空洞给补上，这里感觉和multi-paxos很像。日志匹配特性的不满足还会带来的另一个问题就是一个entry变为commited之后，并不代表它之前的entry都可以commit了，因此leader的提交注定也是乱序的。状态机这里接收到一个log entry，如果发现它之前的entry不在的话当然可以一直等，直到把空洞补齐。但ParallelRaft采用了一种叫look behind buffer的数据结构来提高apply entry的并行度，每个log entry都记录自己前面的N个entry的修改情况（follower接收到的entry是乱序的，但leader生成entry的时候肯定是有序的，所以leader在生成一个entry的时候肯定知道了它前面的N个enty的修改情况）。look behind buffer记录每个entry修改的LBA（逻辑块地址），如果修改的块有重叠就代表有冲突，就需要等待，否则就可以乱序执行。

{{userData.name}}已认证