共计 9834 个字符,预计需要花费 25 分钟才能阅读完成。
简介:SOFAJRaft 已开源
作者 | 家纯
起源 | 阿里技术公众号
一 分布式共识算法 (Consensus Algorithm)
1 如何了解分布式共识?
多个参与者针对某一件事达成完全一致:一件事,一个论断。
已达成统一的论断,不可颠覆。
2 有哪些分布式共识算法?
Paxos:被认为是分布式共识算法的基本,其余都是其变种,然而 paxos 论文中只给出了单个提案的过程,并没有给出复制状态机中须要的 multi-paxos 的相干细节的形容,实现 paxos 具备很高的工程复杂度(如多点可写,容许日志空洞等)。
Zab:被利用在 zookeeper 中,业界应用宽泛,但没用形象成通用 library。
Raft:以容易了解著称,业界也涌现出很多 raft 实现,比方 etcd、braft、tikv 等。
二 Raft 介绍
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 做什么?
- 间断确定多个提案,确保集群中各个系统节点状态完全一致
- 主动选主,保障在只有少数派宕机的状况下继续可用
- 日志强同步,宕机后零数据失落
三 SOFAJRaft
一个纯 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()));
}
}
});
}
四 SOFAJRaft 利用场景
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 本身的性能来实现。
原文链接
本文为阿里云原创内容,未经容许不得转载。