简介和背景

随着分布式业务从单数据中心向多数据中心倒退，多地多活部署的需要也越来越广泛。这带来最大的挑战就是跨数据中心跨地区的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::Debugwhere    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，欢送大家来探讨。