关于存储:DatenLord-Xline-Geodistributed-KV-Storage

简介和背景

随着分布式业务从单数据中心向多数据中心倒退，多地多活部署的需要也越来越广泛。这带来最大的挑战就是跨数据中心跨地区的 metadata 治理，metadata 对数据的稳定性和强一致性有极高要求。在单数据中心场景下，metadata 的治理曾经有很多成熟的解决方案，etcd 就是其中的佼佼者，然而在多数据中心场景下，etcd 的性能受 Raft 共识协定的限度，它的性能和稳定性都大打折扣。DatenLord 作为 高性能跨云跨数据中心的存储 ，对 metadata 治理有了跨云跨数据中心的要求。DatenLord 目前应用 etcd 作为 metadata 的治理引擎，然而思考到 etcd 无奈齐全满足 DatenLord 的跨云跨数据中心的场景，咱们决定实现本人的 metadata 治理引擎。Xline 应运而生，Xline 是一个 分布式的 KV 存储，用来治理大量的关键性数据，并在跨云跨数据中心的场景下依然保障高性能和数据强一致性。思考到兼容性问题，Xline 会兼容 etcd 接口，让用户应用和迁徙更加晦涩。

Xline 的架构

Xline 的架构次要分为 RPC server，KV server，其余 server，CURP 共识协定模块和 Storage 模块

• RPC server：次要负责承受用户的申请并转发到相应的模块进行解决，并回复用户申请。
• KV Server 和其余 server：次要业务逻辑模块，如解决 KV 相干申请的 KV server，解决 watch 申请的 watch server 等。
• CURP 共识协定模块: 采纳 CURP 共识协定，负责对用户的申请进行仲裁，保证数据强一致性。
• Storage：存储模块，存储了 key value 的相干信息。

一次写申请的操作流程如下：

• RPC server 接管到用户写申请，确定是 KV 操作，将申请转发到 KV server。
• KV server 做根本申请做验证，而后将申请封装为一个 proposal 提交给 CURP 模块。
• CURP 模块执行 CURP 共识协定，当达成共识后，CURP 模块会调用 Storage 模块提供的 callback 将写操作长久化到 Storage 中。最初告诉 KV server 写申请曾经 commit。
• KV server 得悉申请曾经被 commit，就会封装申请回复，并通过 RPC server 返回给用户。

Xline 的外围：CURP 共识协定

CURP 共识协定的细节介绍请参考 DatenLord|Curp 共识协定的从新思考。CURP 协定的劣势是将非抵触的 proposal 达成共识所须要的 RTT 从 2 个降为 1，对于抵触的 proposal 依然须要两个 RTT，而 etcd 等支流分布式系统采纳的 Raft 协定在任何状况下都须要两个 RTT。从两个 RTT 降为一个 RTT 所带来的性能晋升在单数据中心场景下体现的并不显著，然而在多数据中心或者跨云场景下，RTT 个别在几十到几百 ms 的数量级上，这时一个 RTT 的性能晋升则相当显著。

Storage 和 Revision

Xline 作为一个兼容 etcd 接口的分布式 KV 存储，etcd 重要的 revision 个性须要齐全兼容。简略介绍一下 etcd 的 revision 个性，etcd 保护了一个全局枯燥递增的 64bit 的 revision，每当 etcd 存储的内容产生扭转，revision 就会加一，也就是说每一次批改操作就会对应一个新的 revision，旧的 revision 不会立马删除，会按需延时回收。一个简略的例子，两个写操作 A -> 1，A -> 2，假如最后的 revision 是 1，etcd 会为 A = 1 生成 revision 2，为 A = 2 生成 revision 3。revision 的设计使 etcd 对外提供了更加丰盛的性能，如反对历史 revision 的查找，如查问 revision 是 2 的时候 A 的值，通过比拟 revision 能够失去批改的先后顺序等。以下是 etcd 对一个 KeyValue 的 proto 定义

message KeyValue {
  bytes key = 1;
  int64 create_revision = 2;
  int64 mod_revision = 3;
  int64 version = 4;
  bytes value = 5;
  int64 lease = 6;
}

一个 KeyValue 关联了三个版本号，

• create_revision: 该 key 被创立时的 revision
• mod_revision：该 key 最初一次被批改时候的 revision
• version：该 key 在最近一次被创立后经验了多少个版本，每一次批改 version 会加一

因为须要反对 revision 个性，Xline 的 Storage 模块参考了 etcd 的设计，分为 Index 和 DB 两个子模块。Index 模块存储的是一个 key 到其对应的所有 revision 数组的 mapping，因为须要反对范畴查找，Index 采纳了 BTreeMap，并会放在内存中。DB 模块存储的是从 revision 到实在 KeyValue 的 mapping，因为有长久化和存储大量的历史 revision 的数据的需要，DB 模块会将数据存到磁盘（目前 prototype 阶段 DB 依然存在内存当中，在将来会对接长久化的 DB）。那么一次查找流程是先从 Index 中找到对应的 key，而后找到须要的 revision，再用 revision 作为 key 到 DB 中查找 KeyValue 从而拿到残缺数据。这样的设计能够反对历史 revision 的存取，拆散 Index 和 DB 能够将 Index 放在内存当中减速存取速度，并且能够利用 revision 的存储个性即每一次批改都会产生一个新的 revision 不会批改旧的 revision，能够不便 DB 实现高并发读写。

CURP 共识协定带来的挑战

CURP 协定的全称是 Consistent Unordered Replication Protocal。从名字能够看出 CURP 协定是不保障程序的，什么意思呢？比方两条不抵触的 proposal，A -> 1，B-> 2，在 CURP 协定中，因为这两条 proposal 是不抵触的，所以它们能够并发乱序执行，核心思想是执行的程序并不会影响各个 replica 状态机的最终状态，不会影响一致性。这也是 CURP 协定用一个 RTT 就能够达成共识的要害。然而对于抵触的 proposal，如 A -> 1, A -> 2，CURP 协定就须要一个额定的 RTT 来确定这两条 proposal 的执行程序，否则在各个 replica 上 A 最终的值会不一样，一致性被突破。

因为 Xline 须要兼容 etcd 的 revision 个性也肯定须要兼容。Revision 个性要求每一次批改都有一个全局惟一递增的 revision，然而 CURP 协定恰好是无奈保障不抵触 proposal 的程序，它会容许不抵触的 proposal 乱序执行，比方后面的例子 A -> 1，B -> 2，如果批改前存储的 revision 是 1，那么哪一个批改的 revision 是 2 哪一个是 3 呢？如果须要确定程序那么就须要一个额定的 RTT，那么 CURP 协定仅需一个 RTT 就能够达成共识的劣势将依然如故，进化成和 Raft 一样的两个 RTT。

解决方案

解决这个问题的思路是将达成共识和确定程序即 revision 分成两个阶段，即通过一个 RTT 来达成共识，这时候就能够返回用户申请曾经 commit，而后再通过一个异步的 RTT 来确定申请的 revision。这样既能够保障一个 RTT 就能够达成共识并返回给用户，又能够保障为每一个批改申请生成全局对立的 revision。确定 revision 用异步 batching 的形式来实现，这一个额定的 RTT 会平摊到一段时间内的所有申请上并不会影响零碎的性能。

Storage 模块会实现如下两个 callback 接口供 CURP 模块调用，execute()会在共识达成后调用，告诉 proposal 能够执行了，after_sync()会在 proposal 的程序确定下来后再调用，以告诉 proposal 的程序，after_sync()接口会依照确定好的 proposal 程序顺次调用。

/// Command executor which actually executes the command.
/// It usually defined by the protocol user.
#[async_trait]
pub trait CommandExecutor<C>: Sync + Send + Clone + std::fmt::Debug
where
    C: Command,
{
    /// Execute the command
    async fn execute(&self, cmd: &C) -> Result<C::ER, ExecuteError>;

    /// Execute the after_sync callback
    async fn after_sync(&self, cmd: &C, index: LogIndex) -> Result<C::ASR, ExecuteError>;
}

为了配合 CURP 模块的两阶段操作，Storage 模块的设计如下：

/// KV store inner
#[derive(Debug)]
struct KvStoreInner {
    /// Key Index
    index: Index,
    /// DB to store key value
    db: DB,
    /// Revision
    revision: Mutex<i64>,
    /// Speculative execution pool. Mapping from propose id to request
    sp_exec_pool: Mutex<HashMap<ProposeId, Vec<Request>>>,
}

当 execute() 回调被调用时，批改 Request 会被预执行并存到 sp_exec_pool 中，它存储了 ProposeId 到具体 Request 的 mapping，这个时候该操作的 revision 并没有确定，然而能够告诉用户操作曾经 commit，此时只需一个 RTT。当操作程序被确定后，after_sync()会被调用，Storage 模块会从 sp_exec_pool 找到对应的 Request 并将它长久化，并把全局 revision 加 1 作为该操作的 revision。

接下来咱们用一次写申请 A -> 1 和一次读申请 Read A 来解说整个流程。假如以后的 revision 是 1，当 KV server 申请收到写申请，它会生成一个 proposal 发给 CURP 模块，CURP 模块通过一个 RTT 达成共识后会调用 execute() callback 接口，Storage 模块会将该申请放到sp_exec_pool 中，这时候 CURP 模块会告诉 KV server 申请曾经 commit，KV server 就会返回给用户说操作已实现。同时 CURP 会异步的用一个额定的 RTT 来确定该写申请的程序后调用 after_sync() callback 接口，Storage 会把全局 revision 加 1，而后从sp_exec_pool 中讲写申请读出来并绑定 revision 2，而后更新 Index 并长久化到 DB 当中，这时候 DB 存储的内容是 revision 2：{key: A, value：1, create_revision: 2, mod_revision: 2, version: 1}。当读申请达到时，就能够从 Storage 模块中读到 A = 1，并且 create_revision = 2，mod_revision = 2。

总结

本文次要介绍了 Geo-distributed KV Storage Xline 的架构设计，以及为了兼容 etcd 的 revision 个性，咱们对 CURP 共识协定和 Storage 模块做的设计，从而实现了在跨数据中心跨地区场景下的高性能分布式 KV 存储。具体代码请参考 datenlord/Xline，欢送大家来探讨。