TiKV是什么

一个全局有序的分布式 Key-Value 引擎

起初，看到这句话的时候并没有深刻的体会，现在回过头看这句话，每个词都是有用的。有序、分布式、kv存储构成了TiKV的核心元素。

TiKV 的特性

• 多副本
• 具有水平扩展能力
• 提供分布式事务支持

Key有序

首先，需要解释的是全局有序。这点很重要，作为数据库底层的存储有很多场景需要全局有序。
当我们想快速的获取某一行的数据的时候，基于主键可以迅速的找到对应的key，这个我们之前已经说过; 但是还有很多场景需要找一批数据，比如where id > 1 and id < 100 , 全局的有序可以帮出我们迅速的定位到数据存在于什么地方，省去了全局扫表的过程。

现在问题来了，如何实现全局有序呢？
答案其实很简单，rocksdb。 那我们就按图索骥，看看rocksdb是什么。

rocksdb

在我看来，选择rocksdb 也是一个误打误撞的结果。从出发点上，rocksdb来源于leveldb，都是想解决传统硬盘IO吞吐问题，因此使用了Sorted String Table + LSM tree 来做存储。
选择这种结构的基础假设是随机访问要比块访问慢，因此尽量将数据连续的存储下来。数据连续的存储，那么它势必是有序的结构。在这个场景下rocksdb天然是一个有序key 的存储，而这个也恰恰是TiKV需要的东西。

我们不妨简单的看一下rocksdb的API：

  std::string value;
  rocksdb::Status s = db->Get(rocksdb::ReadOptions(), key1, &value);
  if (s.ok()) s = db->Put(rocksdb::WriteOptions(), key2, value);
  if (s.ok()) s = db->Delete(rocksdb::WriteOptions(), key1);

for (it->Seek("hello"); it->Valid(); it->Next()) {
  // Do something with it->key() and it->value().
}

auto iter = db->NewIterator(ReadOptions());
iter->Seek("a1");        // iter->Key() == "a1";
iter->Seek("a3");        // iter->Key() == "a3";
iter->SeekForPrev("c4"); // iter->Key() == "c4";
iter->SeekForPrev("c3"); // iter->Key() == "c2";

从这几个接口可以简单的看出来，rocksdb天然的有序属性。使用这样的存储，相似的key 会分布在相似的地方，对SQL查询中的order， range查询有非常大的效率的提升。

分布式kv

如果没有分布式，失去了横向的扩展能力，那么整个地基都将不复存在，分布式数据库也无从谈起。
分布式系统区别于单机系统或者集群是缺少排它锁资源。多线程程序，在需要同步的时候，无论获取数据库锁，redis锁，都是因为这些系统是单机系统。假象一下，多线程程序分布在不同的机器上，在整个系统中缺少单点资源来做锁，同步是多么难的事情。

在我看来，分布式要解决的问题是两个：

1. 副本一致性
2. 分布式事务的一致性

副本一致性是用来解决可用性问题的，而分布式事务是用来解决一致性的，加上分布式的网络分区，这就构成了CAP。

那么，从宏观往细节看，我们首先看看分布式事务是什么东西

分布式事务

TiKV 分布式事务采用了Google 的Percolator系统的实现。在Percolator中，google为了解决索引批处理任务时间周期长的问题，将创建倒排索引索引的MapReducee 任务拆成了一系列的小任务。假设只有一个网站的数据有更新，那么倒排索引只会影响到有限的一些相关网页，那么这个任务可以非常快速的完成，不需要重新启动一个全量的MapReduce任务。

Percolator 中的分布式事务其实很容易明白，设计也很巧妙。它采用的是主从锁，从锁标记主锁来源达到了事务的最终一致性。

搬运一下论文中的转账流程

Bob 有10元钱， Joe有2元钱，现在Bob 要给Joe 转账7元钱

PreWrite 操作

第一步， Bob 账户减少7元

此时 Bob在version7上将数据变更，同时加上主锁，这个时候其他的客户端读数据发现7是空，会往下找6,6指向的数据是version5, 因此依然是10.

第二步 Joe 账户上增加7元

此时， 同第一步一样，金额增加，不同的是锁加入的是从锁，这个从锁指向了主锁对应的行。

Commit 操作

第三步，将删除主锁

第四步， 删除从锁

几个思考

在这里，思考问题的时候，不要去想副本的一致性问题，TiKV的副本一致性是由raft 协议来保证的，具体后续会有介绍。目前转账模型可以简单的看作Bob, Joe 数据在两台电脑上。解释两个问题

1. 为什么要多版本

如果没有多版本是否可以？ 当然可以。我可以将同一个数据分成两份，A和B。读取的时候直接那读的A，写的时候开启一个事务，读取一下数据，备份到B里，在事务期间，读写都在这里进行。事务结束的时候将数据覆盖到A里面。实时上确实有开源的分布式数据库采用这种方式。 或者更极端一些，数据只保留一份，那么仅仅是在事务发生的过程中，所有的读请求都需要排队，等待事务完成。多版本并非是 Percolator中特有的东西。MVCC (多版本访问控制)可以将读写分离开，是用来提高整个系统的吞吐量的。与此同时，配合一些技巧，可以达到RR的事务隔离级别。

2. 锁放在了多版本的行上？

无论是论文，还是代码的实现，的确如此。但是我们来看本质，Bob的数据，无论在任何时间点上，要么没有锁，要么就是最高的版本上有一个写锁。这个完全可以将锁和版本分割开。Bob有多版本，一个锁，存储在不同的地方，也是可以的。

在TiKV的实现上也比较巧妙。如果按照论文的方法，我们很有可能就会在TiDB上为每个表偷偷的创建两列lock、write。
之前我们也说过，TiDB将数据库表的行作为value，保存在TiKV中。TiKV并不关心value具体内容是什么。那么TiDB创建这两列，自己来维护lock也是很自然的想法。
TiKV 并没有这么做，而是将事务处理的相关内容下移到了TiKV中来做。那么问题来了，TiKV不应该理解value中的结构，TiKV是怎么实现的呢？
rocksdb在3.0后引入了一个新特性Column Families，kv并非是平铺的，而是使用cf当作容器来存储，在一个cf中，key 是唯一的，但是在多个cf 中可以有同样的key。这样做到了一定的隔离性。这个特性很redis的db的概念一样。

查看代码可以看到， TiKV 使用了三个cf, 一个用来存储kv, 一个用来存储锁， 一个用来存储data的数据指针。同一个key, 在cf中可以获取到value, lock, write，这样就实现了逻辑上的Percolator的行结构。

pub type CfName = &'static str;

pub const CF_DEFAULT: CfName = "default";

pub const CF_LOCK: CfName = "lock";

pub const CF_WRITE: CfName = "write";

pub const CF_RAFT: CfName = "raft";

pub const LARGE_CFS: &[CfName] = &[CF_DEFAULT, CF_WRITE];

pub const ALL_CFS: &[CfName] = &[CF_DEFAULT, CF_LOCK, CF_WRITE, CF_RAFT];

pub const DATA_CFS: &[CfName] = &[CF_DEFAULT, CF_LOCK, CF_WRITE];

注意代码中最后一样DATA_CFS，就是Percolator行结构的视图。

代码的实现

我们先简单的看一小段代码是如何调用write的

    pub fn async_raw_put(
        &self,
        ctx: Context,
        cf: String,
        key: Vec<u8>,
        value: Vec<u8>,
        callback: Callback<()>,
    ) -> Result<()> {
        if key.len() > self.max_key_size {
            callback(Err(Error::KeyTooLarge(key.len(), self.max_key_size)));
            return Ok(());
        }
        self.engine.async_write(
            &ctx,
            vec![
                Modify::Put(Storage::rawkv_cf(cf)?, Key::from_encoded(key), value),
            ],
            box |(_, res): (_, engine::Result<_>)| callback(res.map_err(Error::from)),
        )?;
        KV_COMMAND_COUNTER_VEC.with_label_values(&["raw_put"]).inc();
        Ok(())
    }

在这里Modify::Put，会异步的发送Put消息，有接收消息的代码来处理相关逻辑，它会将数据写到存储中。其中需要三个参数：cf，key, value。

其中代码在storage/mvcc/write.rs 中定义了一个Write结构

pub enum WriteType {
    Put,
    Delete,
    Lock,
    Rollback,
}

const FLAG_PUT: u8 = b'P';
const FLAG_DELETE: u8 = b'D';
const FLAG_LOCK: u8 = b'L';
const FLAG_ROLLBACK: u8 = b'R';


pub struct Write {
    pub write_type: WriteType,
    pub start_ts: u64,
    pub short_value: Option<Value>,
}


pub type Value = Vec<u8>;

感觉就是用来处理value的，但是为什么保存的时候加上了 write_type start_ts ，这个还没有弄明白。

本质是什么

在我看来分布式事务逃不过2PC，为什么这么说呢？在一个分布式系统中，每个节点无法有效的获取全局状态。这个时候需要一个协调者他来记录每个人的状态，并对其发号施令。而为什么是两阶段呢？我感觉是为了让rollback过程逻辑上是可以成功的。

我们不防举一个简单的小例子：

假设需要给用户做一次退款，退款由两部分组组成，其中一部分是账户余额，一部分是优惠劵。如果不使用2PC，账户余额直接增加退款金额后，优惠劵退款失败了。这个时候用户已经看到了账户余额的变更，如果这个时候用户做了一笔提现操作，那么rollback 是不会成功的。
如果是用2PC, prepare阶段给用户账户上加锁，禁止其他任何账户的变更请求，必须等待当前事务处理完成后才可以执行。那么rollback 是可以成功的。不会出现一致性问题。

我们生活中有大量的场景使用2PC，跑步比赛，预备-----开始！ 预备就是大家都在上锁，开始就是在执行任务。

所以，分布式事务本质是在第一个阶段各个节点需要加锁来为整个事务做准备。等所有人都准备好了，那么开始执行事务。

Percolator中使用的事务方法巧妙的地方在于除去了中间的协调者，使用主从锁、从锁维持主锁的引用，在任意一个时期，每个节点都知道当前事务是否执行完成（或者应该怎么redo 或者rollback）。看明白这个，TiKV中分布式事务的本质就弄明白了。

PS:

1. TiKV, TiDB 中大量参考了Google 论文中的相关内容，吸收了本质原理，排除无用东西。 Percolator论文中介绍Percolator是一个大型系统，其中使用了上述的主从锁来解决分布式事务问题。因此，在我看来，Percolator不能跟主从锁的分布式事务划等号.