关于Raft算法中分区出现脏读的解决方案探讨

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

本作品 (李兆龙 博文, 由 李兆龙 创作)，由 李兆龙 确认，转载请注明版权。

Raft固然是一个经过严格证明的线性一致性算法，理论来讲一切都按论文走就不会有什么安全性问题，但很可惜，我们为了真的能在现实环境中使用Raft，必然需要一些优化。

这其中有一点就是所谓的Read Index以及Lease Read，其实也就是为了读操作效率更高而使得读操作实际不需要去做为Raft日志传播，只要保证读取的节点是leader就可以满足顺序一致性的读取，此时我们还并未引入时间这个棘手的问题，所以看起来一切都好。问题的关键在于如何确定节点是leader，自身状态？当然不行，出现分区的时候可能出现多个节点自身状态都为leader；或者向follow发送一个RPC确定自己是leader，这法子没问题，但是开销堪比直接把读操作当作日志；好了，机智的人们想出了一个好办法，就是所谓Lease Read的机制，既不需要把读当作日志，也不需要每次读操作发送RPC确定自己是leader。

leader发送RPC的时候，会首先记录一个时间点 start，当系统大部分节点都回复哪个RPC时，我们就可以认为 leader 的 lease 有效期可以到 start + election timeout + clock drift bound（正负未知）这个时间点。因为 follower 至少在 election timeout的时间之后，才会重新发生选举，所以正常来讲这套机制是有效的，如下情况：

1. T1时刻代表Leader收到了一个读请求
2. T2时刻leader向follow发送RPC，确定自己是leader，并生成lease
3. T3a，T3b时刻两个follow收到RPC，并在T4a，T4b重置自己的选举定时器
4. T5 leader收到了两个follow的回复，并使得lease生效
5. T6返回成功

看起来没什么大问题，但是如果出现分区呢？我们考虑如下情况：

此时T7时刻leader和其他节点出现分区，T8时刻任意节点成为leader，并提交日志，注意提交日志时落后leader的lease在T10时刻才过期，租约的持续时长小于等于Election timeout，也就是说实际follow的开始选举时间是可能早于这个旧leader的租约的，极其悲观的思考，lease read有点扯淡的，没有正确性的保证，因为可以看到这里不仅需要考虑时钟偏移，还需要考虑RTT，而这两个东西没办法保证。

这个落后leader仍然会提供读服务。假设T9时刻新leader提交一条新日志，其中内容为x=3，并立马读取，然后再去读旧leader，他会先看到x = 3，然后是x = 1；但是如果一个节点先访问旧节点，看到x = 1，然后访问新节点看到x = 3，这不满足顺序一致性的定义。

为了不出现这种情况，我们需要设置读超时，读超时的设置需要满足如下条件：Election Timeout > Read Timeout > T6 - T1 >= T6 - T4

这个式子的意义就是要满足旧leader返回成功之前没有一个节点发起发起选举，我们需要使得Read Timeout > T6 - T4，但是T6 - T4附带一个RTT，没办法估算Read Timeout 下界，意味着应用的读取超时没办法设置以保证正确性。

[1]中提到了一种方法可以解决这个问题，即所有的读取操作附带一个相关日志的Term，然后利用这个Term解决冲突，比如前面读取了x = 3以后再读取x = 1，此时这个x = 1就会因为Term的落后而被客户端拒绝。

但是最大的问题是客户端一般需要读取状态机中的信息而不是日志中的数据，状态机中的数据基本不可能去维护一个相关日志的Term。

所以如何解决这个问题，一个是忽略这些误差，就像TiKV一样，或者放弃这种优化，使用read index。

可以参考[2]，etccd对于一致性的保证如下：

etcd ensures linearizability for all other operations by default. Linearizability comes with a cost, however, because linearized requests must go through the Raft consensus process. To obtain lower latencies and higher throughput for read requests, clients can configure a request’s consistency mode to serializable, which may access stale data with respect to quorum, but removes the performance penalty of linearized accesses’ reliance on live consensus.

总而言之，不存在银弹，要正确性没性能；要性能没一致性保证；现在令我不解是TiKV和TiFlash之间数据的转移是基于Lease Read，他们是如何选择的呢？也许TiFlash开源时就有答案了。

参考：

1. https://github.com/etcd-io/etcd/issues/741
2. etcd KV API guarantees
3. https://groups.google.com/g/golang-china/c/-Lb8p1Zaz3c
4. 共识、线性一致性与顺序一致性
5. TiKV 功能介绍 - Lease Read