第2章 TiDB的存储
1、Key-Value Pairs（键值对）
作为保存数据的系统，首先要决定的是数据的存储模型，也就是数据以什么样的形式保存下来。TiKV的选择是Key-Value模型，并且提供有序遍历方法。TiKV数据存储的两个关键点：
1）这是一个巨大的map（可以类比一下C++的 std::map），也就是存储的是Key-Value Pairs（键值对）；
2）这个map中的Key-Value pair按照Key的二进制顺序有序，也就是可以seek到某一个Key的位置，然后不断地调用Next方法以递增的顺序获取比这个Key大的Key-Value。
有人可能会问，这里讲的存储模型和SQL中表是什么关系？在这里有一件重要的事情需要强调：
TiKV的KV存储模型和SQL中的Table无关！
现在让我们忘记SQL中的任何概念，专注于讨论如何实现TiKV这样一个高性能、高可靠、分布式的Key-Value存储。
2、本地存储（RocksDB）
任何持久化的存储引擎，数据终归要保存在磁盘上，TiKV也不例外。但是TiKV没有选择直接向磁盘上写数据，而是把数据保存在RocksDB中，具体的数据落地由RocksDB负责。这个选择的原因是开发一个单机存储引擎工作量很大，特别是做一个高性能的单机引擎，需要做各种细致的优化，而RocksDB是由Facebook开源的非常优秀的单机KV存储引擎，可以满足TiKV对单机引擎的各种要求。这里可以简单的认为RocksDB是一个单机的持久化Key-Value Map。
3、Raft协议
接下来TiKV的实现面临一件更难的事情：如何保证单机失效的情况下，数据不丢失，不出错？
简单来说，需要想办法把数据复制到多台机器上，这样一台机器挂了，其他的机器上的副本还能提供服务；
复杂来说，还需要这个数据复制方案是可靠和高效的，并且能处理副本失效的情况。TiKV选择了Raft算法。Raft是一个一致性协议，它和Multi Paxos实现一样的功能，但是更加易于理解。Raft提供几个重要的功能：
1）Leader（主副本）选举
2）成员变更（如添加副本、删除副本、转移Leader等操作）
3）日志复制
TiKV利用Raft来做数据复制，每个数据变更都会落地为一条Raft日志，通过Raft的日志复制功能，将数据安全可靠地同步到复制组的每一个节点中。不过在实际写入中，根据Raft的协议，只需要同步复制到多数节点，即可安全地认为数据写入成功。
总结一下，通过单机地RocksDB,TiKV可以将数据快速地存储在磁盘上；通过Raft，将数据复制到多台机器上，以防单机失效。数据的写入是通过Raft这一层的接口写入，而不是直接写RocksDB。通过实现Raft，TiKV变成了一个分布式的Key-Value存储，少数几台机器宕机也能通过原生的Raft协议自动把副本补全，可以做到对业务无感知。
4、Region
讲到这里，我们需要提到一个非常重要的概念：Region。这个概念是理解后续一系列机制的基础。前面提到，我们将TiKV看做一个巨大的有序的KV Map，那么为了实现存储的水平扩展，我们需要将数据分散在多台机器上。这里提到的数据分散在多台机器上和Raft的数据复制不是一个概念，在这一节我们先忘记Raft，假设所有的数据都只有一个副本，这样更容易理解。对于一个KV系统，将数据分散在多台机器上有两种比较典型的方案：
1）Hash：按照Key做Hash，根据Hash值选择对应的存储节点
2）Range：按照Key分Range，某一段连续的Key都保存在一个存储节点上
TiKV选择了第二种方式，将整个Key-Value空间分成很多段，每一段是一系列连续的Key，将每一段叫做一个Region，并且会尽量保存每个Region中保存的数据不超过一定的大小，目前在TiKV中默认是96MB。每一个Region都可以用[StartKey，EndKey)这样一个左闭右开区间来描述。
注意：这里的Region还是和SQL中的表没什么关系！请各位继续忘记SQL，只谈KV。将数据划分成Region后，TiKV将会做两件重要的事情：
1）以Region为单位，将数据分散在集群中所有的节点上，并且尽量保证每个节点上服务的Region数量差不多
2）以Region为单位做Raft的复制和成员管理
这两点非常重要，我们一点一点来说。先看第一点，数据按照Key切分成很多Region，每个Region的数据只会保存在一个节点上面（暂不考虑多副本）。TiDB系统会有一个组件（PD）来负责将Region尽可能均匀的散布在集群中所有的节点上，这样一方面实现了存储容量的水平扩展（增加新的节点后，会自动将其他节点上的Region调度过来），另一方面也实现了负载均衡（不会出现某个节点有很多数据，其他节点上每什么数据的情况）。同时为了保证上层客户端能够访问所需要的数据，系统中也会有一个组件（PD）记录Region在节点上面的分布情况，也就是通过任意一个Key就能查询到这个Key在哪个Region中，以及这个Region目前在哪个节点上（即Key的位置路由信息）。至于负责这两项重要工作的组件（PD），会在后续介绍。
对于第二点，TiKV是以Region为单位做数据的复制，也就是一个Region的数据会保存多个副本，TiKV将每一个副本叫做一个Replica。Replica之间是通过Raft来保持数据的一致，一个Region的多个Replica会保存在不同的节点上，构成一个Raft Group。其中一个Replica会作为这个Group的Leader，其他的Replica作为Follower。所有的读和写都是通过Leader进行，读操作在Leader上即可完成，而写操作再由Leader复制给Follower。大家理解了Region之后，应该可以理解下面这张图：
以Region为单位做数据的分散和复制，就有了一个分布式的具备一定容灾能力的KeyValue系统，不用再担心数据存不下，或者是磁盘故障丢失数据的问题。
5、MVCC
很多数据库都会实现多版本并发控制（MVCC），TiKV也不例外。设想这样的场景，两个客户端同时去修改一个Key的Value，如果没有数据的多版本控制，就需要对数据上锁，在分布式场景下，可能会带来性能以及死锁问题。TiKV的MVCC实现是通过在Key后面添加版本号来实现，简单来说，没有MVCC之前，可以把TiKV看做这样的：
Key1 -> Value
Key2 -> Value
……
KeyN -> Value
有了MVCC之后，TiKV的Key排列是这样的：
Key1_Version3 -> Value
Key1_Version2 -> Value
Key1_Version1 -> Value
……
Key2_Version4 -> Value
Key2_Version3 -> Value
Key2_Version2 -> Value
Key2_Version1 -> Value
……
KeyN_Version2 -> Value
KeyN_Version1 -> Value
……
注意：对于同一个Key的多个版本，我们把版本号较大的放在前面，版本号小的放在后面（回忆一下Key-Value一节我们介绍过的Key是有序的排列），这样当用户通过一个Key+Version来获取Value的时候，可以通过Key和Version构造出MVCC的Key，也就是Key_Version。然后可以直接通过RocksDB的SeekPrefix(Key_Version)API，定位到第一个大于等于这个Key_Version的位置。
6、分布式ACID事务
TiKV的事务采用的是Google在Big Table中使用的事务模型：Percolator，TiKV根据这篇论文实现，并做了大量的优化。
在TiKV层的事务API的语义类似下面的伪代码：
tx = tikv.Begin()
tx.Set(Key1, Value1)
tx.Set(Key2, Value2)
tx.Set(Key3, Value3)
tx.Commit()
这个事务包含3条Set操作，TiKV能保证这些操作要么全部成功，要么全部失败，不会出现中间状态或脏数据。就如前面提到的，TiDB的SQL层会将SQL的执行计划转换成多个KV操作，对于上层的同一业务层的SQL事务，在底层也是对应一个KV层的事务，这是TiDB实现MySQL的事务语义的关键。