前言

PolarFS 是一个具有超低延迟和高可用性的分布式文件系统，专为 PolarDB 数据库服务而设计，现已在阿里云上提供该服务。PolarFS 采用轻量级网络协议栈和用户空间 I/O 协议栈，充分利用了 RDMA、NVMe 和 SPDK 等新兴技术，这让PolarFS 的端到端延迟大大降低，实验表明，PolarFS 的写延迟与固态硬盘上的本地文件系统相当接近。为了在保持副本一致性的同时最大化 PolarFS 的 I/O 吞吐量，阿里的开发者们开发了 ParallelRaft，这是一种源自 Raft 的共识协议，它利用数据库的乱序 I/O 完成容错能力，打破了 Raft 严格的序列化。ParallelRaft 继承了 Raft 的易理解性和易用性，同时为 PolarFS 提供了更好的 I/O 扩展性。

本文将重点分析PolarFS中采用的Parallel Raft技术，分析阿里的开发者们对标准的Raft算法的瓶颈的认知，以及为了克服Raft算法瓶颈而做的一系列改进，由于论文本身写的比较简略，网上资料又甚少，许多细节要依赖笔者自己去推敲，部分细节可能不完全正确，如有错误欢迎读者们在评论区指出！

PolarFS论文原文链接

关于传统Raft共识算法的瓶颈

PolarFS的开发者们起初出于Raft的易理解性和实现上的简洁性而选择了Raft作为PolarFS的共识协议，然而在开发过程中他们发现，当他们在NVMe SSD和RDMA NIC这类超低延迟的硬件上应用Raft算法的时候，Raft算法本身设计上的缺陷导致其在高并发写入的场景下存在一定的延迟，这也让Raft算法不太适合超高并发写入的生产环境。

具体的说，因为Raft算法在设计之初，为了易理解性和实现的简洁性，不允许有日志空洞，所有的日志均需要按序确认，提交，应用，那么假如说有多个log请求同时到达raft leader，这几个请求必须在follower节点上必须强制按序确认，再提交，这就导致了并发的请求被强制串行化了，一定程度上降低了并行度。

而在现代的分布式通信网络架构中，leader和follower之间常常有多条通路来进行通信，那么就意味着leader发送给follower的请求可能是乱序到达follower的，甚至可能存在部分请求丢失的情况，这种情况下follower常常会收到乱序到达的请求，而在此通信方式下，若follower仍然采用按序确认提交的办法，那几乎不可能实现正确的确认和提交，导致写入被无限延迟，所以传统的raft算法难以兼容并行的通信线路。

因此，由于传统Raft实现上的简洁性与维护的简单性，PolarFS的开发者们并不打算出于以上几个缺点就直接放弃Raft算法，他们因此改进出了Parallel Raft来应对PolarFS的高并发写入场景。

并发理论基础

事务处理系统，诸如数据库，都具备并发控制算法来容许乱序（并发）I/O的执行，论文原文并未详细解释这一说法，笔者认为，论文想表达的意思是，对于并发写入的场景，由于数据库系统有并发控制协议来应对并发事务的执行，因此在并发乱序I/O请求同时到达数据库时，在事务层上不会导致结果出现未定义的情况（详情可参考GFS的undefined的定义），而在底层的存储结构上，同一事务之间若修改多个不同且互不影响的page时（比如同时修改page A，page B，page C，他们之间是互不影响的），这就意味着这些修改又可以安全地并行地执行。而只有在修改相同的page的时候，底层结构的锁才会强制将I/O串行化保证并发安全。

那么根据论文原文的意思，也可以认为，Parallel Raft的底层存储结构具备处理并发无序I/O的能力，这也是Parallel Raft算法设计的重要基础之一。

Parallel Raft简介

Parallel Raft的总体框架设计的仍然沿袭了Raft相似的结构，Parallel Raft分成以下三个子模块：

  1. 日志复制
  2. 领导人选举
  3. 日志追赶（个人认为称为日志同步也许更合适）

Parallel Raft在总体设计上，将 确认(acknowledge) ， 提交(commit) 全部修改成了乱序执行的步骤，他们的执行不再依赖于顺序，也就是一次日志的确认不再需要等到前面的日志完全确认后才去确认，从而实现乱序确认，而一次提交也不需要再等到前面的日志全部提交才去提交，从而实现了乱序提交，这两个方面的改进让Raft得以实现高度的并行化。

而Parallel Raft的并发理论基础的原文比较拗口，笔者直接用自己的话去解释：

Parallel Raft的所有日志都有一个待写入的硬盘位置，称为LBA(Logical Block Address)，直接理解为硬盘page 号即可；

若日志1要向硬盘 page1写入，而日志2也要向硬盘 page1写入 ，我们认为他们的写入目的就产生了冲突，那么日志1和日志2就必须按照完全一致的顺序在所有的Parallel Raft的节点上应用，以保证Parallel Raft的复制状态机属性。

也就是说，若日志的写入范围产生了冲突（即写入范围之间存在重叠），Parallel Raft算法就必须保证他们在所有节点上按照完全一致的顺序应用，若两日志的写入范围不存在冲突，则Parallel Raft允许他们在所有的节点上并发乱序写入（参考上文并发理论基础），这样的改进无疑大幅度增加了Parallel Raft的写入的并发度，降低了写入延迟。

仅做日志追加(Append Only)

和Raft一样，Parallel Raft中，在通常情况下，leader也只会向follower发起日志追加的rpc，以达成集群共识。

日志辨识(Log Recognization)

和Raft一样，Parallel Raft中，可以通过一个日志的index和term唯一地确定一个日志

乱序确认(Out-of-order Acknowledge)

Parallel Raft中，只要一个Log Entry成功被复制到一个follower节点，就可以不顾日志顺序直接返回成功确认的信息，这样就避免了额外的等待时间。

乱序提交(Out-of-order Commit)

Parallel Raft中，只要leader收到一个Log Entry的过半节点的复制成功的消息，便可以提交该日志。

在有日志空洞的前提下应用日志(Apply with Holes in the Log)

Parallel Raft引入了一个数据结构 反向检查缓冲区(Look Behind Buffer) 以保证我们上述提到过的一个最重要的原则：Parallel Raft需要保证所有存在冲突的日志在所有的节点上，按相同的顺序被应用，从而实现复制状态机。

具体说就是，在Parallel Raft中，leader发送的每个Log Entry都会带有一个反向检查缓冲区，反向检查缓冲区记录了从leader要发送的Log Entry开始，往前连续N个日志的总的修改的LBA记录（也就是其修改的硬盘位置的记录）（N是一个由用户自己配置的参数）

如上图，我们假设当前leader要发送的日志的index为5，而我们选择的N为4，那么反向检查缓冲区会记录往前四个日志所修改的LBA

我们通过下一个例子分析反向检查缓冲区的作用

假如说我们选择了N=2

leader将index=10的Log Entry发往follower，而此时follower收到index=10的Log Entry以后，该follower的index=8和index=9的位置都是空洞，但是由于反向检查缓冲区携带了前2个日志的LBA的修改信息，因此follower能够容忍存在两个日志空洞的情况，而又由于反向检查缓冲区中记录的LBA的写入情况和index=10的日志写入情况不构成冲突，因此只要该日志可以在该节点上复制成功，并全局提交后便可以直接执行应用。

看完这个例子你也许就理解了论文的那句话：

The look behind buffer contains the LBA modified by the previous N log entries, so that a look behind buffer acts as a bridge built over a possible hole in the log. N is the span of this bridge, which is also the maximum size of a log hole permitted.

（老实说，这段话刚开始读的时候我只觉得相当抽象，然而论文也没有给出很好的例子，因此笔者只能自己画了一晚上推导图来思考各种coner case）

延迟列表(Pending List)

Parallel Raft的设计中，提交与应用是两个解耦的步骤，提交了以后的日志并不能马上被应用，我们前面提到过，Parallel Raft保证了每一个节点的冲突日志都必须在所有节点上按相同的顺序写入，这是怎么实现的呢。

如上图，leader将index = 10的日志发往follower后，该日志通过LBA检测到了前两个空洞的冲突，那么它将在复制到该节点后，将该日志添加到延迟列表(Pending List)中，而论文中仅仅提到：只有在前两个空洞的日志被应用后（冲突解决后），才能够将该日志从延迟列表中移出，并应用到复制状态机上。

这里论文讲的非常的不详细，既没有提到检测到冲突以后是否返回成功确认的消息，也没有提到重发的细节，给读者留下了很大的想象空间。

而笔者个人推测如下，由于论文提到了，一旦成功复制就可以返回确认，那么笔者认为这里理应是可以返回成功确认的消息的，但是在复制完成以后，follower还需要告知leader，自己需要前两个空洞的日志，在leader下次的rpc中，leader会发送相应的缺漏日志给follower，follower在应用了缺漏的日志以后便可以正常处理Pending List的日志了。

极其特殊的情况：连续空洞的数量大于N

论文完全没有提到这种情况应该如何去处理，笔者认为若存在大于N的连续空洞的话，则此情况理应对应后文中提到的Catch up的条件，那么留到后文分析即可。

领导人选举(Leader Election)

和Raft一样，在Parallel Raft的选举中，只有具有最长的Log Entries且最后一个Log的Term值比其他follower大的candidate才有资格得到其他follower的投票（实际上还有一个限制是：只有checkpoint进度最新的candidate才能成为leader，当然在这里这不重要）

论文中反复提到了 follower candidate(跟随者候选人) 这个概念，但是又并没有对它下一个清晰的定义，笔者推测该follower candidate的含义是有机会成为candidate的所有节点（这也可以推测其实Parallel Raft同样采用了Prevote算法来优化选举，同时也能够用这个机制来推测自己是否为follower candidate）

在Parallel Raft中，一次选举结束以后，在选举胜出的candidate并不能马上成为leader，它首先会切换到一个中间过渡态 leader candidate(领导人候选者) 。这是为什么呢？

由于Parallel Raft允许一定程度上的日志空洞与乱序执行，在选举中胜出的candidate实际上是不一定具有所有的集群已提交的日志的，这时候，为了得到集群中所有的已提交的日志，leader candidate需要预先经过一个merge的阶段

合并(Merge)

（这里需要注意的是，与普通的Raft算法不同，由于Parallel Raft算法的日志空洞，异步确认以及提交的机制，Parallel Raft中没有commit Index这样的概念，不要用commit Index来分析日志的提交问题，只要日志复制到了超半数节点就可以执行提交）

在leader candidate状态的节点，会向其他的follower candidate发出合并日志的请求来获取所有已提交的日志，对于leader candidate自己的日志，需要分如下三种异常情况做处理

1.在其他follower candidate节点上已提交但是在本节点上没有执行提交的index：

由于已提交的日志是一定复制到了超过半数的集群节点的，因此在其他的follower candidate节点必然可以找到对应的index下的在集群中已提交的日志。那么只需要将其他的节点上已提交的日志直接复制到对应的leader candidate节点的index即可。

2.在本节点上没有提交，且其他follower candidate节点均不存在的index（空洞）：

这说明这个日志在其他任何节点都没有提交，也就不可能已经复制到过半数的节点，所以可以直接跳过对这个日志的处理（把它当成无效日志即可）

3.在其他follower candidate节点上均未提交且均不一致(term不相同)的index：

Parallel Raft对它的处理是，选择其他follower candidate上term最大的一份日志，并复制到本地，这样一个选择出于两方面的原因:

（1）Parallel Raft的合并策略决定了Parrallel Raft中，若一个index出现了多个日志，且均未提交，这就说明了，那么也就说明此index下，具有较小的term的日志不可能在某些节点上被提交，只有最大的term才有可能在某些节点上已被提交。（这一点详细解释较为复杂，读者可自行画图理解）

（2）Parallel Raft中，若一个老leader成功将日志复制到过半节点并正确提交，而在没有及时通知follower的情况下就发生了崩溃，这时候选出的新leader candidate有可能就不具有这个已提交的日志，则同样的，我们需要把这个日志同步到leader candidate上。

Parallel Raft的选举收尾阶段

在选出Leader Candidate后，Leader Candidate会将自己的日志同步到所有的Follower Candidate上，同步结束后会将所有同步成功的日志全部提交

笔者对于Parallel Raft的容错性的一些思考

讲到这里，我们可以来分析一下Paralllel Raft的环环相扣的设计与容错性了

笔者认为，结合上面的机制，Parallel Raft不需要传统Raft的一致性检查算法，原因如下：

（1）经过Leader Candidate的合并阶段，所有Follower Candidate都能与Leader Candidate保持一致

（2）在发送日志追加rpc时，Leader会根据Follower的反向检查缓冲区来检查空洞情况，并对空洞进行补全。

那么可以想象几种日志不一致的情况

假如是Follower Candidate与Leader Candidate日志不一致，则在选举结束以后，经历合并，同步与提交三个阶段后，所有的往期日志都会被强制同步，所以Follower Candidate和Leader Candidate不会出现不一致的日志情况。

假如是Follower Newbie与新Leader有巨大的日志差异，则通过Catch up可以恢复同步（我们留到下一期再解析CheckPoint与Catch Up的联系）

在新leader上任以后，经过以上两个步骤，所有的已commit日志（注意在选举结束阶段，Leader Candidate的所有日志都会被强制同步）都能在各个节点之间同步，而leader如果没有更替的话，那么，在其他节点上，唯一的异常日志情况就只有空洞，为什么呢？设想一下，如果leader没有更替，新的日志写入请求是不是只有可能汇集到leader上呢，其他所有的follower都只会乱序接收leader发过来的日志，那也就不可能在其他follower上产生不一致的日志了。

所以经过以上分析，笔者认为，通过Leader Candidate的合并算法和Catch up算法，Parallel Raft并不需要通过一致性检查来检测往期日志的不一致的情况。


后记

有关 Parallel Raft的Checkpoint和Catch up机制，笔者留到下一篇再更

笔者认为Parallel Raft固然是对现有Raft算法的优秀的改进，在保证了强大的高可用的基础上，Parallel Raft提供了高度的并行性与写入的低延迟，一举突破了一个性能瓶颈。

但是笔者仍然觉得这篇论文是一篇晦涩难读的论文，论文中大量的表述都有点模糊不清，再加上互联网上对本论文的分析少之又少，因此笔者在解读Parallel Raft的时候，大量的细节都需要自己去推敲。