Chaos 测试下的若干 NebulaGraph Raft 问题分析
Raft 是一种广泛使用的分布式共识算法。NebulaGraph 底层采用 Raft 算法实现 metad 和 storaged 的分布式功能。Raft 算法使 NebulaGraph 中的 metad 和 storaged 能够集群化部署、实现了多副本和高可用，同时 storaged 通过 multi-raft 模块实现了数据分片，分散了系统的负载，提升系统的吞吐。
作为分布式系统的基石 Raft 有非常明显的优势，但这也伴随着不小的挑战 —— Raft 算法的实现及其容易出错，同时算法的测试和调试也是一项巨大的挑战。NebulaGraph 目前使用的是自研的 Raft，鉴于 Raft 本身的复杂性我们构造了诸多 Chaos 测试来保障 NebulaGraph Raft 算法的稳定性。本文介绍几个我们使用 Chaos 测试发现的 NebulaGraph Raft 中比较有意思的问题。
Raft 背景知识
Raft 是一种广泛使用的分布式共识算法。一个 Raft 集群中的节点通过运行 Raft 算法保证各个节点之间复制日志序列。算法保证各个节点之间的日志序列是一致的，只要各个节点上的日志序列一致即可保证各个节点上数据的一致性。
Raft 是一种强主算法，系统通过选举产生一个主节点，用户向主节点提交日志，主节点再把日志复制到其他节点上。当一条日志复制到过半数的节点上后，Raft 即可认为这条日志已经提交成功，这条日志将无法被改写，Raft 算法保证这条日志后续能被复制到所有节点上。当一个主节点出现故障时，如 Crash、网络中断等，其他节点会在等待一段时间后发起新的一轮选举选出主节点，后续由这个新的主节点协调集群的工作。
Raft 中有一个 Term 概念，Term 是一个单调递增的非负整数，每个节点都有一个 Term 值，节点在发起选举前会先递增本地的 Term。同一个 Term 内最多只能有一个主节点，否则就意味着 Raft 出现脑裂。「脑裂」在 Raft 中是极其严重的故障，它意味着 Raft 的数据安全无法得到保障——两个主节点可以同时向从节点复制不同的日志数据，而从节点无条件信任主节点的请求。Term 在 Raft 中是一个逻辑时钟的概念，更高值的 Term 意味着 Raft 集群已经进入新时代；当一个 Raft 节点看到更高的 Term 值时需要更新它本地的 Term 值（跟着别人进入新时代），同时转变为从节点；忽略 Term 的更新可能会导致 Raft 集群选举异常，我们后面一个故障的例子即跟这点有关。
NebulaGraph Raft 踩坑记录
在介绍了 Raft 的背景知识后，本节我们介绍几个通过 Chaos 测试发现并处理的 NebulaGraph Raft 故障。
线程池死锁问题
这是在 NebulaGraph v2.6 之前发现的一个很有意思的问题。具体情况是，在一个五节点的集群中运行压测程序，运行我们的设计好的 Chaos 测试，基本上十几分钟后就能看到一个存储节点状态变成离线状态，但查看离线离线节点却发现存储服务还在运行：
通过 gdb attach 到离线的存储服务进程上，我们发现 Raft 向 peer 节点发消息的模块卡在一个条件变量上：
查看 src/kvstore/raftex/Host.h:44 的具体代码，通过分析我们可以知道这个函数正在等待当前所有的 append log 请求结束，也就是 44 行对应的 noMoreRequestCV_.wait() 调用，它一直在等待 requestOnGoing_ 变为 false：
如果我们继续看堆栈上的前一个调用，可以发现 Host.reset() 调用前，RaftPart::handleElectionResponses() 在 1141 这行代码获取了 raftLock_ 这个锁，我们看 src/kvstore/raftex/RaftPart.cpp:1145 中的具体代码：
进程不动，说明 requestOnGoing_ 一直都是 true 状态，通过 gdb attach 进去我们验证了这个猜测：
为什么 requestOnGoing_ 一直都是 true 状态呢？通过翻阅 src/kvstore/raftex/Host.cpp 中的代码，我们可以发现当存在 append log 请求时 requestOnGoing_ 在 Host::appendLogs() 函数中会被设置为 true，当 append log 请求都结束时，这个变量在 Host::appendLogsInternal() 函数中会被设置为 fasle。requestOnGoing_ 值一直不变，那么，一个合理的猜测是某个 append log 请求卡在 Host::appendLogsInternal() 上了。这个函数本质上干的活是：
通过
sendAppendLogRequest()向 raft peer 发起 append log rpc 请求回调处理 append log rpc 的结果，处理完了顺便在这里吧
requestOnGoing_变量设置为 false
卡住的一种可能是 rpc 回调一直没有返回，但是这边不大可能。因为我们给 rpc 链接请求都设置了超时，所以这一点基本可以排除。再观察这个函数，我们可以看到 sendAppendLogRequest(eb, req) 和它的回调处理用的都是在同一个 eb（EventBase，即 IO 线程）中执行，会不会是回调线程中的操作导致死锁了？
翻了无数遍代码，看不出明显的关联关系，最后想到一个办法是通过打日志进一步观察运行细节。appendLogsInternal() 调用 sendAppendLogRequest() 并在 eb 这个 IO 线程中执行，我们把每个 appendLogsInternal() 请求和当前的时间戳关联。然后设法把 eb 的线程 id 打印出来，并在 sendAppendLogRequest() 处理结果的回调中也打印出对应的 tid（这里还要考虑跑异常的情况）。这样一来，如果 appendLogsInternal() 中没有发生死锁，我们必然能看到结果回调中打印的 eb 的 tid：
重新跑测试，很快我们又观察到死锁的情况。通过死锁进程的日志，我们看到 Host::appendLogsInternal() 确实卡住了：
1635908526021106910 对应的 append 请求运行在线程 2470665 上，处理结果的时候卡住了，gdb attach 进去看 2470665 这个进程在干嘛：
从堆栈上看，它被调度去处理 Raft heartbeat 请求了，然后它卡在 /root/nebula-workspace/nebula/src/kvstore/raftex/RaftPart.cpp:1650 上了，1650 这行代码正要获取 raftLock_ 锁，raft 完美死锁了：
NebulaGraph 大量使用线程池来处理异步回调任务。总结以上问题就是在两个线程池工作线程中：
worker thread 1 执行以下回调
拿到锁 lock，等待在条件变量上；
worker thread 2 执行以下回调
尝试获取，然后执行后续任务；
修改数据并激活条件变量；
因为 worker thread 2 先执行任务 a 也就是需要先获取所，再执行回调 b 以激活条件变量，这种调用顺序构成了一个非常隐蔽的死锁场景。在使用线程池处理异步回调的设计中，如果并发加锁的处理稍不留意可能就会踩到类似的坑上，而 NebulaGraph Raft 各项操作都是构建在异步线程池的基础上，并且包含各种复杂的加锁操作。我们在修复这个问题后又陆陆续续在 NebulaGraph 上修复了多起类似的故障。
Raft 缓冲区死锁问题
这也是 v2.6 之前我们通过 Chaos 测试用例发现的一个问题。运行一段时间后终止测试程序，等系统 CPU、磁盘 IO 等各项负载都空闲下来后，我们在 NebulaGraph 执行以一些简单的查询操作，我们发现 NebulaGraph 永远都返回 Leader change 错误。查看 NebulaGraph 日志，我们发现它在疯狂报 Raft buffer overflow 错误：
rate.replicatingLogs_ :0 表示 raft 没有在复制日志。raft 缓冲区溢出说明有大量数据等待复制，但它却没有在复制日志，看起来就是个 bug。 我们发现稳定下来后 Raft 集群主节点稳定，没有出现切主行为，至少说明 Raft 选举模块还是正常的。所以，从上面的日志看来大概率是日志复制模块被 Chaos 测试玩坏了。
首先我们看 NebulaGraph Raft 中的对 append log 的处理：
这个函数一旦看到 bufferOverFlow_ 变量值是 true，便认为缓冲区满了，直接报错返回了。否则把要复制的日志先塞到缓冲区 logs_ 中。如果缓冲区满了就设置 bufferOverFlow_ = true。接下来，测试 replicatingLogs_ 这个变量，true 说明已经有活动的异步回调在执行日志复制可以直接返回，否则在函数末尾调用 appendLogsInternal() 真正启动 raft 日志复制操作。另一方面，当向 peer 节点复制日志的操作收到成功的响应后 NebulaGraph raft 会调用 checkAppendLogResult() 来处理结果。这个函数清空 raft 日志缓冲区，把 bufferOverFlow_ 和 replicatingLogs_ 重置为 false。
以上是 raft 日志复制的核心操作逻辑。需要注意的是，appendLogAsync() 和 checkAppendLogResult() 都是异步并发执行的，最后意味着 bufferOverFlow_ 和 replicatingLogs_ 变量的更新需要锁的保护，这里用的是 logsLock_ 这个锁。了解这个信息后，我们再来看 checkAppendLogResult() 这个函数就会发现一个非常微妙的加锁问题：replicatingLogs_ = false 这行代码是在没有 logsLock_ 锁保护的情况下执行的。如果客户端的并发请求足够高，那么在 checkAppendLogResult() 释放锁和执行 replicatingLogs_ = false 这个间隙完全有可能把缓冲区打满，然后把 bufferOverFlow_ 设置为 true。这个也就是我们开头看到的，日志缓冲区满了但 raft 却没有在执行日志复制场景，这种情况下所有的操作都会报缓冲区溢出错误，这个几点基本就报销了只能重启。修复也非常容易，把 checkAppendLogResult() 中的 replicatingLogs_ = false 语句放在 logsLock_ 锁的保护下执行即可。
Raft 选举死锁问题
这又是通过 Chaos 测试跑出来的一个 NebulaGraph Raft v2.6 之前版本的故障。我们构造了一个七节点的 Raft 集群，在测试中我们发现，系统挂了三个节点后，另外四个节点再也无法选主了。我们把四个无法选主的节点和对应的服务端口筛选出来：
通过日志发现了一些很有意思的事情：
从日志上 storage.0 拒绝了 storage.5 的 vote request，因为 storage.5 的 term 1836 远远落后于其他节点的 term 1967、1968，投票请求被拒绝是意料之中。另一方面 storage.5 上的日志比其他三个节点都新，根据 raft 的选举规则只有 storage.5 才能当选 leader。为什么 storage.5 的 term 上不去，按道理在 storage.5 收到其他节点的 request vote 请求后就应该立即更新本地的 term 了？我们 review NebulaGraph Raft 中对 vote 请求的处理发现了其中的问题：
我们发现 NebulaGraph Raft 处理选举请求的时候，如果 candidate 的 log 比自己的 log 旧，raft 会直接拒绝这个请求。这个操作逻辑上没问题，但是 Raft 论文里要求一个 Raft 实例一旦遇到比自己 term 大的请求要立马 update 自己的 term，这个函数里执行这步操作了吗？显然没有，判断日志比自己旧后就直接 return 了，这种处理导致集群永远无法选出主节点。这个问题的修复也容易，再处理 request vote 请求的时候及时更新本地 term 即可。不过，如果在集群出问题的时候放任 term 无序递增也不是个好办法。所以，我们在修复这个问题的时候顺便把 Raft prevote 特性也加上去，让 NebulaGraph 的 Raft 更加稳定。
Raft 数据不一致问题
我们的 Chaos 测试发现 v2.6 版本之前的 NebulaGraph Raft 中存在数据不一致的问题，而且可以稳定复现！以下是在一次测试中发现的 NebulaGraph Raft 日志数据和 NebulaGraph 数据不一致的情况：
可以看到，同一个 index 下，raft 日志的 term 和 size 值都存在差异，有 19 条 raft log 不一致！
NebulaGraph 写入的数据有 18 条不一致，和 Raft log 中的不一致的数据条目非常接近。Raft 数据不一致的问题处理起来非常棘手。不过，我们通过不断地优化 Chaos 测试用例，让问题可以在短时间内稳定复现。不管是日志还是 gdb 一时都没有太清晰的策略去对付这个问题。后来我们想到了 Mozilla RR。RR 可以把整个程序的执行过程录制下来，然后重复播放执行，而且产生相同的执行结果。我们可以用 RR 把 Raft 数据不一致的故障录制下来。通过 RR 的执行过程回放，我们发现 NebulaGraph Raft 在处理选举请求的时候会错误地把一个本应该变成 follower 的 leader 节点升级成下一个 term 的 leader：
看以上代码，一个 leader 的 term 可能直接被 update 变成下一个 term 的 leader，它本应当变成 follower 的。这样以来 Raft 直接脑裂了，脑裂的两个 leader 分别提交了不一样的数据上去，也就造成了上面的数据不一致问题。
以上。
谢谢你读完本文 (///▽///)
如果你想尝鲜图数据库 NebulaGraph，记得去 GitHub 下载、使用、(^з^)-☆ star 它 -> GitHub；和其他的 NebulaGraph 用户一起交流图数据库技术和应用技能，留下「你的名片」一起玩耍呀~
版权声明: 本文为 InfoQ 作者【NebulaGraph】的原创文章。
原文链接:【http://xie.infoq.cn/article/3e9c87f3bd590c45b084a3b65】。
本文遵守【CC BY-NC-ND】协议，转载请保留原文出处及本版权声明。
一款开源的分布式图数据库 2020-04-28 加入
Follow me, here is my GitHub profile: https://github.com/vesoft-inc/nebula
评论