关于raft:浅谈分布式一致性Raft-与-SOFAJRaft

简介：SOFAJRaft 已开源

作者 | 家纯
起源 | 阿里技术公众号

1 如何了解分布式共识?

多个参与者针对某一件事达成完全一致：一件事，一个论断。

已达成统一的论断，不可颠覆。

2 有哪些分布式共识算法?

Paxos：被认为是分布式共识算法的基本，其余都是其变种，然而 paxos 论文中只给出了单个提案的过程，并没有给出复制状态机中须要的 multi-paxos 的相干细节的形容，实现 paxos 具备很高的工程复杂度（如多点可写，容许日志空洞等）。
Zab：被利用在 zookeeper 中，业界应用宽泛，但没用形象成通用 library。
Raft：以容易了解著称，业界也涌现出很多 raft 实现，比方 etcd、braft、tikv 等。

1 特点：Strong Leader

零碎中必须存在且同一时刻只能有一个 leader，只有 leader 能够承受 clients 发过来的申请。
Leader 负责被动与所有 followers 通信，负责将“提案”发送给所有 followers，同时收集多数派的 followers 应答。
Leader 还需向所有 followers 被动发送心跳维持领导位置（放弃存在感）。
另外，身为 leader 必须放弃始终 heartbeat 的状态。

2 复制状态机

对于一个有限增长的序列 a[1, 2, 3…]，如果对于任意整数 i，a[i]的值满足分布式一致性，这个零碎就满足一致性状态机的要求。

基本上所有的实在零碎都会有源源不断的操作，这时候独自对某个特定的值达成统一显然是不够的。为了让实在零碎保障所有的正本的一致性，通常会把操作转化为 write-ahead-log(WAL)。而后让零碎中所有正本对 WAL 保持一致，这样每个正本依照程序执行 WAL 里的操作，就能保障最终的状态是统一的。

Client 向 leader 发送写申请。
Leader 把“操作”转化为 WAL 写本地 log 的同时也将 log 复制到所有 followers。
Leader 收到多数派应答，将 log 对应的“操作”利用到状态机。
回复 client 处理结果。

3 Raft 中的基本概念

Raft-node 的 3 种角色 / 状态

Follower：齐全被动，不能发送任何申请, 只承受并响应来自 leader 和 candidate 的 message, node 启动后的初始状态必须是 follower。
Leader：解决所有来自客户端的申请，以及复制 log 到所有 followers。
Candidate：用来竞选一个新 leader (candidate 由 follower 触发超时而来)。

Message 的 3 种类型

RequestVote RPC：Candidate 收回。
AppendEntries (Heartbeat) RPC：Leader 收回。
InstallSnapshot RPC：Leader 收回。

任期逻辑时钟

工夫被划分为一个个任期(term)，term id 按时间轴枯燥递增。
每一个任期的开始都是 leader 选举，选举胜利之后，leader 在任期内治理整个集群, 也就是“选举 + 惯例操作”。
每个任期最多一个 leader，能够没有 leader (spilt-vote 导致)。

4 Raft 性能合成

Leader 选举

超时驱动：Heartbeat / Election timeout

随机的超时工夫：升高选举碰撞导致选票被瓜分的概率

选举流程：Follower –> Candidate (选举超时触发)

博得选举：Candidate –> Leader
另一个节点博得选举：Candidate –> Follower
一段时间内没有任何节点器博得选举：Candidate –> Candidate

选举动作：

Current term++
发送 RequestVote RPC

New Leader 选取准则 (最大提交准则)

Candidates include log info in RequestVote RPCs(index & term of last log entry)
During elections, choose candidate with log most likely to contain all committed entries
Voting server V denies vote if its log is“more complete”：(lastTermV > lastTermC) ||((lastTermV == lastTermC) && (lastIndexV > lastIndexC))
Leader will have“most complete”log among electing majority

安全性：一个 term，最多选出一个 leader，能够没 leader，下一个 term 再选。

影响 raft 选举成功率的几个工夫参数

RTT(Round Trip Time)：网络延时
Heartbeat timeout：心跳距离，通常应该比 election timeout 小一个数量级，目标是让 leader 可能继续发送心跳来阻止 followers 触发选举
Election timeout：Leader 与 followers 间通信超时触发选举的工夫
MTBF(Meantime Between Failure)：Servers 间断惯例故障工夫距离 RTT << Heartbeat timeout < Election timeout(ET) << MTBF

随机选主触发工夫：Random(ET, 2ET)

日志复制

Raft 日志格局

(TermId, LogIndex, LogValue)
其中 (TermId, LogIndex) 能确定惟一一条日志

Log replication 关键点

连续性：日志不容许呈现空洞
有效性：

不同节点，领有雷同 term 和 logIndex 的日志 value 肯定雷同
Leader 上的日志肯定是无效的
Follower 上的日志是否无效，通过 leader 日志比照判断 (How?)

Followers 日志有效性查看

AppendEntries RPC 中还会携带前一条日志的惟一标识 (prevTermId, prevLogIndex)
递归推导

Followers 日志复原

Leader 将 nextIndex 递加并重发 AppendEntries，直到与 leader 日志统一

Commit Index 推动

CommitIndex (TermId, LogIndex)

所谓 commitIndex，就是已达成多数派，能够利用到状态机的最新的日志地位
日志被复制到 followers 后，先长久化，并不能马上被利用到状态机
只有 leader 晓得日志是否达成多数派，是否能够利用到状态机
Followers 记录 leader 发来的以后 commitIndex，所有小于等于 commitIndex 的日志均能够利用到状态机

CommitIndex 推动

Leader 在下一个 AppendEntries RPC (也包含 Heartbeat)中携带以后的 commitIndex
Followers 查看日志有效性通过则承受 AppendEntries 并同时更新本地 commitIndex, 最初把所有小于等于 commitIndex 的日志利用到状态机

AppendEntries RPC

残缺信息：(currentTerm, logEntries[], prevTerm, prevLogIndex, commitTerm, commitLogIndex)
currentTerm, logEntries[]：日志信息，为了效率，日志通常为多条
prevTerm, prevLogIndex：日志有效性查看
commitTerm, commitLogIndex：最新的提交日志位点(commitIndex)

阶段小结：当初咱们能用 raft 做什么?

间断确定多个提案，确保集群中各个系统节点状态完全一致
主动选主，保障在只有少数派宕机的状况下继续可用
日志强同步，宕机后零数据失落

一个纯 Java 的 raft 算法实现库，应用 Java 重写了所有性能，并有一些改良和优化。

1 SOFAJRaft 整体性能

性能反对

Leader election：选主。

Log replication and recovery：日志复制和日志复原，log recovery 就是要保障曾经被 commit 的数据肯定不会失落，log recovery 蕴含两个方面

Current term 日志复原，次要针对一些 follower 节点重启退出集群或者是新增 follower 节点
Prev term 日志复原，次要针对 leader 切换前后的日志一致性

Snapshot and log compaction：定时生成 snapshot，实现 log compaction 减速启动和复原，以及 InstallSnapshot 给 followers 拷贝数据。

Membership change：集群线上配置变更，减少节点、删除节点、替换节点等。

Transfer leader：被动变更 leader，用于重启保护，leader 负载平衡等。

Symmetric network partition tolerance：对称网络分区容忍性。

Pre-Vote：如上图 S1 为以后 leader，网络分区造成 S2 一直减少本地 term，为了防止网络复原后 S2 发动选举导致正在良心工作的 leader step-down, 从而导致整个集群从新发动选举，在 request-vote 之前会先进行 pre-vote(currentTerm + 1，lastLogIndex, lastLogTerm)，多数派胜利后才会转换状态为 candidate 发动真正的 request-vote，所以分区后的节点，pre-vote 不会胜利，也就不会导致集群一段时间内无奈失常提供服务。

Asymmetric network partition tolerance：非对称网络分区容忍性。

如上图 S1 为以后 leader，S2 一直超时触发选主，S3 晋升 term 打断以后 lease，从而回绝 leader 的更新，这个时候能够减少一个 trick 的查看，每个 follower 保护一个工夫戳记录收到 leader 上数据更新的工夫(也包含心跳)，只有超过 election timeout 之后才容许承受 request-vote 申请。

Fault tolerance: 容错性，少数派故障，不影响零碎整体可用性：

机器掉电
强杀利用
慢节点(GC, OOM 等)
网络故障
其余各种奇葩起因导致 raft 节点无奈失常工作

Workaround when quorate peers are dead：多数派故障时整个 grop 已不具备可用性, 平安的做法是期待少数节点复原，只有这样能力保障数据安全，然而如果业务更谋求可用性，放弃数据一致性的话能够通过手动 reset_peers 指令迅速重建整个集群，复原集群可用。

Metrics：SOFAJRaft 内置了基于 metrics 类库的性能指标统计，具备丰盛的性能统计指标。

Jepsen：除了单元测试之外，SOFAJRaft 还应用 jepsen 这个分布式验证和故障注入测试框架模仿了很多种状况，都已验证通过：

随机分区，一大一小两个网络分区
随机减少和移除节点
随机进行和启动节点
随机 kill -9 和启动节点
随机划分为两组，互通一个两头节点，模仿分区状况
随机划分为不同的 majority 分组

性能优化

Batch：SOFAJRaft 中整个链路都是 batch 的，依附 disruptor 中的 MPSC 模型批量生产，包含但不限于：

批量提交 task
批量网络发送
本地 IO batch 写入，要保障日志不丢，个别每一条 log entry 都要进行 fsync, 比拟耗时，SOFAJRaft 中做了合并写入的优化
批量利用到状态机

Replication pipeline：流水线复制，leader 跟 followers 节点的 log 同步是串行 batch 的形式，每个 batch 发送之后须要期待 batch 同步实现之后能力持续发送下一批(ping-pong), 这样会导致较长的提早。能够通过 leader 跟 followers 节点之间的 pipeline 复制来改良，无效升高更新的提早, 进步吞吐。

Append log in parallel：Leader 长久化 log entries 和向 followers 发送 log entries 是并行的。

Fully concurrent replication：Leader 向所有 follwers 发送 log 也是齐全并发的。

Asynchronous：Jraft 中整个链路简直没有任何阻塞，齐全异步的，是一个 callback 编程模型。

ReadIndex：优化 raft read 走 raft log 的性能问题，每次 read，仅记录 commitIndex，而后发送所有 peers heartbeat 来确认 leader 身份，如果 leader 身份确认胜利，等到 applied index >= commitIndex，就能够返回 client read 了，基于 ReadIndex 能够很不便的提供线性统一读，不过 commitIndex 是须要从 leader 那里获取的，多了一轮 RPC。

Lease Read：通过租约 (lease) 保障 leader 的身份，从而省去了 readIndex 每次 heartbeat 确认 leader 身份，性能更好, 然而通过时钟保护 lease 自身并不是相对的平安(jraft 中默认配置是 readIndex，因为 readIndex 性能已足够好)。

2 SOFAJRaft 设计
SOFAJRaft – Raft Node

Node：Raft 分组中的一个节点，连贯封装底层的所有服务，用户看到的次要服务接口，特地是 apply(task) 用于向 raft group 组成的复制状态机集群提交新工作利用到业务状态机。

存储

Log 存储，记录 raft 用户提交工作的日志，将从 leader 复制到其余节点上。LogStorage 是存储实现, LogManager 负责对底层存储的调用，对调用做缓存、批量提交、必要的检查和优化。
Metadata 存储，元信息存储，记录 raft 实现的外部状态，比方以后 term、投票给哪个节点等信息。
Snapshot 存储，用于寄存用户的状态机 snapshot 及元信息，可选. SnapshotStorage 用于 snapshot 存储实现，SnapshotExecutor 用于 snapshot 理论存储、近程装置、复制的治理。

状态机

StateMachine：用户外围逻辑的实现，外围是 onApply(Iterator) 办法，利用通过 Node#apply(task) 提交的日志到业务状态机。
FSMCaller：封装对业务 StateMachine 的状态转换的调用以及日志的写入等，一个无限状态机的实现, 做必要的查看、申请合并提交和并发解决等。

复制

Replicator：用于 leader 向 followers 复制日志，也就是 raft 中的 AppendEntries 调用，包含心跳存活查看等。
ReplicatorGroup：用于单个 raft group 治理所有的 replicator，必要的权限检查和派发。

RPC 模块用于节点之间的网络通讯

RPC Server：内置于 Node 内的 RPC 服务器，接管其余节点或者客户端发过来的申请, 转交给对应服务解决。
RPC Client：用于向其余节点发动申请，例如投票、复制日志、心跳等。

KV Store：SOFAJRaft 只是一个 lib，KV Store 是 SOFAJRaft 的一个典型的利用场景，把它放进图中以便更好的了解 SOFAJRaft。

SOFAJRaft – Raft Group

SOFAJRaft – Multi Raft Group

3 SOFAJRaft 实现细节

高效的线性统一读

什么是线性统一读?

所谓线性统一读，一个简略的例子就是在 t1 的时刻咱们写入了一个值, 那么在 t1 之后，咱们肯定能读到这个值，不可能读到 t1 之前的旧值 (想想 java 中的 volatile 关键字，说白了线性统一读就是在分布式系统中实现 volatile 语义)。

上图 Client A、B、C、D 均合乎线性统一读，其中 D 看起来是 stale read，其实并不是，D 申请横跨了 3 个阶段，而读可能产生在任意时刻，所以读到 1 或 2 都行。

重要：接下来的探讨均基于一个大前提，就是业务状态机的实现必须是满足线性一致性的, 简略说就是也要具备 java volatile 的语义。

1）间接点，是否能够间接从以后 leader 节点读？

怎么确定以后的 leader 真的是 leader(网络分区)？

2）最简略的实现形式：读申请走一遍 raft 协定

有什么问题?

不仅有日志写盘开销，还有日志复制的 RPC 开销，在读比重较大的零碎中是无奈承受的
还多了一堆的 raft“读日志”
3）ReadIndex Read

这是 raft 论文中提到过的一种优化计划，具体来说：

将以后本人 log 的 commit index 记录到一个 local 变量 ReadIndex 外面。
向其余节点发动一次 heartbeat，如果大多数节点返回了对应的 heartbeat response，那么 leader 就可能确定当初本人依然是 leader (证实了本人是本人)。
Leader 期待本人的状态机执行，直到 apply index 超过了 ReadIndex，这样就可能平安的提供 Linearizable Read 了, 也不用管读的时刻是否 leader 已飘走 (思考：为什么须要等到 apply index 超过了 ReadIndex 才能够执行读申请？)。
Leader 执行 read 申请，将后果返回给 Client。

通过 ReadIndex，也能够很容易在 followers 节点上提供线性统一读：

Follower 节点向 leader 申请最新的 ReadIndex。
Leader 执行下面 i ~ iii 的过程(确定本人真的是 leader)，并返回 ReadIndex 给 follower。
Follower 期待本人的 apply index 超过了 ReadIndex (有什么问题？慢节点？)。
Follower 执行 read 申请，将后果返回给 client。

ReadIndex 小结：

相比拟于走 raft log 的形式，ReadIndex 读省去了磁盘的开销，能大幅度晋升吞吐，联合 SOFAJRaft 的 batch + pipeline ack + 全异步机制，三正本的状况下 leader 读的吞吐靠近于 RPC 的下限。
提早取决于多数派中最慢的一个 heartbeat response，实践上对于升高延时的成果不会十分显著。

4）Lease Read

Lease read 与 ReadIndex 相似，但更进一步，不仅省去了 log，还省去了网络交互。它能够大幅晋升读的吞吐也能显著升高延时。

根本的思路是 leader 取一个比 election timeout 小的租期(最好小一个数量级)，在租约期内不会产生选举，这就确保了 leader 不会变，所以能够跳过 ReadIndex 的第二步，也就升高了延时。能够看到, Lease read 的正确性和工夫是挂钩的，因而工夫的实现至关重要，如果漂移重大，这套机制就会有问题。

实现形式：

定时 heartbeat 取得多数派响应, 确认 leader 的有效性 (在 SOFAJRaft 中默认的 heartbeat 距离是 election timeout 的十分之一)。
在租约无效工夫内，能够认为以后 leader 是 raft group 内的惟一无效 leader，可疏忽 ReadIndex 中的 heartbeat 确认步骤(2)。
Leader 期待本人的状态机执行，直到 apply index 超过了 ReadIndex，这样就可能平安的提供 Linearizable Read 了。

5）更进一步：Wait Free

到此为止 lease 省去了 ReadIndex 的第 2 步(heartbeat)，实际上还能再进一步，省去第 3 步。

咱们想想后面的实现计划的实质是什么? 以后节点的状态机达到“读”这一刻的工夫点雷同或者更新的状态。

那么更严格一点的束缚就是：以后时刻，以后节点的状态机就是最新的。

问题来了，leader 节点的状态机能保障肯定是最新的吗？

首先 leader 节点的 log 肯定是最新的，即便新选举产生的 leader，它也肯定蕴含全副的 commit log，但它的状态机却可能落后于旧的 leader。
然而在 leader 利用了本人以后 term 的第一条 log 之后，它的状态机就肯定是最新的。
所以能够得出结论：当 leader 曾经胜利利用了本人 term 的第一条 log 之后，不须要再取 commit index，也不必等状态机，间接读，肯定是线性统一读。

小结：Wait Free 机制将最大水平的升高读提早，SOFAJRaft 暂未实现 wait free 这一优化，不过曾经在打算中。

在 SOFAJRaft 中发动一次线性统一读申请：

// KV 存储实现线性统一读
public void readFromQuorum(String key, AsyncContext asyncContext) {
    // 申请 ID 作为申请上下文传入
    byte[] reqContext = new byte[4];
    Bits.putInt(reqContext, 0, requestId.incrementAndGet());
    // 调用 readIndex 办法, 期待回调执行
    this.node.readIndex(reqContext, new ReadIndexClosure() {

        @Override
        public void run(Status status, long index, byte[] reqCtx) {if (status.isOk()) {
                try {
                    // ReadIndexClosure 回调胜利, 能够从状态机读取最新数据返回
                    // 如果你的状态实现有版本概念, 能够依据传入的日志 index 编号做读取
                    asyncContext.sendResponse(new ValueCommand(fsm.getValue(key)));
                } catch (KeyNotFoundException e) {asyncContext.sendResponse(GetCommandProcessor.createKeyNotFoundResponse());
                }
            } else {
                // 特定状况下, 比方产生选举, 该读申请将失败
                asyncContext.sendResponse(new BooleanCommand(false, status.getErrorMsg()));
            }
        }
    });
}

1 SOFAJRaft 能够做什么

选举
分布式锁服务，比方 zookeeper
高牢靠的元信息管理

分布式存储系统，如分布式音讯队列、分布式文件系统、分布式块零碎等等。

2 用户案例

AntQ Streams QCoordinator：应用 SOFAJRaft 在 coordinator 集群内做选举、元信息存储等性能。
Schema Registry：高牢靠 schema 治理服务，相似 kafka schema registry。
SOFA 服务注册核心元信息管理模块：IP 数据信息注册，要求写数据达到各个节点统一，并且在少数派节点挂掉时保障不影响数据失常存储。
RheaKV：基于 SOFAJRaft 和 rocksDB 实现的嵌入式、分布式、高可用、强统一的 KV 存储类库。

3 简略实际：基于 SOFAJRaft 设计一个简略的 KV Store

到目前为止，咱们仿佛还没看到 SOFAJRaft 作为一个 lib 有什么特别之处, 因为 SOFAJRaft 能办到的 zk，etcd 仿佛基本上也都能够办到, 那么 SOFAJRaft 算不算反复造轮子？

为了阐明 SOFAJRaft 具备很好的设想空间以及扩大能力，上面再介绍一个基于 SOFAJRaft 的简单一些的实际。

4 简单一点的实际：基于 SOFAJRaft 的 Rhea KV 的设计

性能名词

PD：全局的核心总控节点, 负责整个集群的调度, 不须要自治理的集群可不启用 PD (一个 PD 可治理多个集群，基于 clusterId 隔离)。
Store：集群中的一个物理存储节点，一个 store 蕴含一个或多个 region。
Region：最小的 KV 数据单元，每个 region 都有一个左闭右开的区间 [startKey, endKey)，可依据申请流量 / 负载 / 数据量大小等指标主动决裂以及主动正本搬迁。

特点

嵌入式
强一致性
自驱动：自诊断，自优化，自决策，自复原。以上几点 (尤其 2, 3) 根本都是依靠于 SOFAJRaft 本身的性能来实现。

原文链接
本文为阿里云原创内容，未经容许不得转载。

关于raft:浅谈分布式一致性Raft-与-SOFAJRaft

一分布式共识算法 (Consensus Algorithm)

二 Raft 介绍

三 SOFAJRaft

四 SOFAJRaft 利用场景

一 分布式共识算法 (Consensus Algorithm)

二 Raft 介绍

三 SOFAJRaft

四 SOFAJRaft 利用场景

一分布式共识算法 (Consensus Algorithm)