TiDB数据存储实现简介

数据库从自身功能上可以简单划分为：数据存储、数据计算，如果是分布式数据库还会涉及到调度，完成数据自动化重分布等功能。继上次的

分布式数据库TiDB简介

之后，本次对TiDB的数据存储实现进行介绍。

数据存储是将数据持久化存放，并按照一定的方式组织，使得能支持数据计算。不同的数据库组织数据的方式会有很大不同，而且组织方式对用户而言透明的。比如TiDB是支持sql的，那么我们通过sql进行计算时，数据库是如何基于它的数据组织方式完成计算的，是由它的数据计算模块完成的，对普通用户透明。在本文中，核心关注点放在TiDB的数据存储方案，至于如何支持SQL以及表的概念则是在下一篇介绍。

根据上一篇文章的介绍可知，TiKV是TiDB的三个核心组件之一，它的存在就是为了解决数据存储问题。作为一个保存数据的分布式系统，依次解决：

A

数据存储模型

也就是数据以什么样的形式保存下来。TiKV的选择是Key-Value模型，并且提供有序遍历方法。简单来讲，可以将TiKV看做一个巨大的Map，其中Key和Value都是原始的Byte数组，在这个Map中，Key按照Byte数组总的原始二进制比特位比较顺序排列。对于TiKV重要的有下面两点：

1. 这是一个巨大的Map，也就是存储的是Key-Value pair。

2. 这个Map 中的Key-Value pair按照Key的二进制顺序有序，也就是我们可以Seek 到某一个Key的位置，然后不断的调用Next方法以递增的顺序获取比这个Key大的Key-Value。

B

单机持久化

TiKV没有选择直接向磁盘上写数据，而是把数据保存在RocksDB中，具体的数据落地由 RocksDB负责。这个选择的原因是开发一个单机存储引擎工作量很大，特别是要做一个高性能的单机引擎，需要做各种细致的优化，而RocksDB是一个非常优秀的开源的单机存储引擎，可以满足TiDB对单机引擎的各种要求，而且还有Facebook的团队在做持续的优化，只需要投入很少的精力，就能享受到一个十分强大且在不断进步的单机引擎。这里可以简单的认为RocksDB是一个能持久化的单机Key-Value Map。

C

集群高可用

作为一个分布式数据库，如果没有自带高可用也太low了。那么在单机失效的情况下，如何保证数据不丢失，不出错？一般是把数据复制到多台机器上，这样一台机器挂了，还有其他的机器上的副本，因此这个数据复制方案是否可靠、高效就决定了数据库的品质。TiDB采用的是Raft 协议来完成数据复制。

Raft 是一个一致性算法，它和Paxos等价，但是更加易于理解。简单理解就是多个节点构成一个组，组里选出一个leader，发生写入时：

1.Leader收到client发送的request。

2.Leader将request append到自己的log。

3.Leader将对应的log entry发送给其他的follower。

4.Leader等待follower的结果，如果大多数节点提交了这个log，则生效。

5.Leader将结果返回给client。

6.Leader继续处理下一次request。

这里可以看出不需要所有的follower都写入完成才算成功，可以有效避免被比较慢的猪队友拖累。同时上面只是Raft一个基本流程，性能比较差，TiDB团队对Raft 协议的实现做了大量的优化，具体的优化细节可参考TiKV 源码解析系列 - Raft 的优化

至此，通过单机的RocksDB，可以将数据快速地存储在磁盘上；通过Raft，可以将一个数据复制到多台机器上做副本，以防单机失效。数据的写入是通过Raft 这一层的接口写入，而不是直接写RocksDB。通过实现Raft，就拥有了一个分布式的KV，不用担心某台机器挂掉了。

D

数据分区

这里会涉及一个非常重要的概念：Region。前面提到，我们将TiKV 看做一个巨大的有序的KV Map，那么为了实现存储的水平扩展，我们需要将数据分散在多台机器上。这里的数据分散和Raft 的数据复制不是一个概念，这里是把一份大数据分散在多台服务器，Raft是为这一份大数据创建多个副本放在多台服务器。

对于一个KV 系统，将数据分散在多台机器上有两种比较典型的方案：一种是按照Key 做Hash，根据Hash 值选择对应的存储节点；另一种是分Range，某一段连续的Key都保存在一个存储节点上。TiKV选择了第二种方式，将整个Key-Value空间分成很多段，每一段是一系列连续的Key，每一段叫做一个Region，并且每个Region中保存的数据不超过一定的大小(这个大小可以配置，目前默认是64mb)。每一个Region都可以用StartKey到EndKey这样一个左闭右开区间来描述。

将数据划分成Region 后，会做两件重要的事情：

1. 以Region 为单位，将数据分散在集群中所有的节点上，并且尽量保证每个节点上服务的Region 数量差不多

2. 以Region 为单位做Raft 的复制和成员管理

对于第二点，TiKV是以Region为单位做数据的复制，也就是一个Region的数据会保存多个副本，我们将每一个副本叫做一个Replica。Replica之间是通过Raft 来保持数据的一致，一个Region的多个Replica 会保存在不同的节点上，构成一个Raft Group。其中一个Replica会作为这个Group的Leader，其他的Replica作为Follower。所有的读和写都是通过Leader 进行，再由Leader复制给Follower。

自此，下面这张图，应该就可以轻松理解了。

以Region 为单位做数据的分散和复制，就有了一个分布式的具备一定容灾能力的KeyValue系统，不用再担心数据存不下，或者是磁盘故障丢失数据的问题。

E

MVCC

很多数据库都会实现多版本控制（MVCC），TiKV 也不例外。设想这样的场景，两个Client 同时去修改一个Key 的Value，如果没有MVCC，就需要对数据上锁，在分布式场景下，可能会带来性能以及死锁问题。TiKV 的MVCC 实现是通过在Key 后面添加Version 来实现，简单来说，没有MVCC 之前，可以把TiKV 看做这样的：

Key1 -> Value

Key2 -> Value

……

KeyN -> Value

有了MVCC 之后，TiKV 的Key 排列是这样的：

Key1-Version3 -> Value

Key1-Version2 -> Value

……

Key2-Version4 -> Value

Key2-Version3 -> Value

Key2-Version2 -> Value

Key2-Version1 -> Value

……

KeyN-Version2 -> Value

KeyN-Version1 -> Value

……

注意，对于同一个Key的多个版本，把版本号较大的放在前面，版本号小的放在后面（上文有提到Key是有序的排列），这样当用户通过一个Key + Version来获取Value的时候，可以将Key和Version构造出MVCC的Key，也就是Key-Version。然后可以直接Seek(Key-Version)，定位到第一个大于等于这个Key-Version的位置。

F

事务

TiKV的事务采用的是Percolator模型，并且做了大量的优化。事务的细节这里不详述，这里只提一点，TiKV的事务采用乐观锁，事务的执行过程中，不会检测写写冲突，只有在提交过程中，才会做冲突检测，冲突的双方中比较早完成提交的会写入成功，另一方会尝试重新执行整个事务。当业务的写入冲突不严重的情况下，这种模型性能会很好，比如随机更新表中某一行的数据，并且表很大。但是如果业务的写入冲突严重，性能就会很差，举一个极端的例子，就是计数器，多个客户端同时修改少量行，导致冲突严重的，造成大量的无效重试。

到这里，已经完成了TiKV 的基本概念和一些细节的介绍，理解了这个分布式带事务的KV 引擎的分层结构以及如何实现多副本容错。下一篇会介绍如何在KV 的存储模型之上，构建SQL 层，完成数据计算。