浅谈分布式一致性：Raft 与 SOFAJRaft

397次阅读  |  发布于3年以前

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

1 如何理解分布式共识? 多个参与者针对某一件事达成完全一致：一件事，一个结论。 已达成一致的结论，不可推翻。

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

二 Raft 介绍

1 特点：Strong Leader

另外，身为 leader 必须保持一直 heartbeat 的状态。

2 复制状态机

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

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

3 Raft 中的基本概念

Raft-node 的 3 种角色/状态

Message 的 3 种类型

任期逻辑时钟

4 Raft 功能分解

Leader 选举

超时驱动：Heartbeat / Election timeout

随机的超时时间：降低选举碰撞导致选票被瓜分的概率

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

选举动作：

New Leader 选取原则 (最大提交原则)：

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

影响 raft 选举成功率的几个时间参数：

随机选主触发时间：Random(ET, 2ET)

日志复制

Raft 日志格式：

Log replication关键点：

Followers 日志有效性检查：

Followers 日志恢复：

Commit Index 推进

CommitIndex (TermId, LogIndex) ：

CommitIndex推进：

AppendEntries RPC

阶段小结：现在我们能用 raft 做什么?

三 SOFAJRaft

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

1 SOFAJRaft 整体功能

功能支持

Leader election：选主。 Log replication and recovery：日志复制和日志恢复，log recovery就是要保证已经被 commit 的数据一定不会丢失，log recovery 包含两个方面

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：容错性，少数派故障，不影响系统整体可用性。

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

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

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

性能优化

Batch：SOFAJRaft 中整个链路都是 batch 的，依靠 disruptor 中的 MPSC 模型批量消费，包括但不限于

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 组成的复制状态机集群提交新任务应用到业务状态机。 存储：

状态机：

复制：

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

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 协议

有什么问题?

3）ReadIndex Read 这是 raft 论文中提到过的一种优化方案，具体来说：

通过ReadIndex，也可以很容易在 followers 节点上提供线性一致读：

ReadIndex小结：

4）Lease Read

Lease read 与 ReadIndex 类似，但更进一步，不仅省去了 log，还省去了网络交互。它可以大幅提升读的吞吐也能显著降低延时。

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

实现方式：

5）更进一步：Wait Free

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

我们想想前面的实现方案的本质是什么? 当前节点的状态机达到“读”这一刻的时间点 相同或者更新的状态。

那么更严格一点的约束就是：当前时刻，当前节点的状态机就是最新的。

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

小结：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 可以做什么

2 用户案例

3 简单实践：基于 SOFAJRaft 设计一个简单的 KV Store

到目前为止，我们似乎还没看到 SOFAJRaft 作为一个 lib 有什么特别之处, 因为 SOFAJRaft 能办到的 zk，etcd 似乎基本上也都可以办到, 那么 SOFAJRaft 算不算重复造轮子？

为了说明 SOFAJRaft 具有很好的想象空间以及扩展能力，下面再介绍一个基于 SOFAJRaft 的复杂一些的实践。

4 复杂一点的实践：基于 SOFAJRaft 的 Rhea KV 的设计

功能名词

特点

Copyright© 2013-2020

All Rights Reserved 京ICP备2023019179号-8