TiDB的单机存储是基于RocksDB的，然后在RocksDB的基础使用Multi-raft实现了数据的分布式存储。为了更好地理解TiDB，让我们先来看看RocksDB。

RocksDB

RocksDB是一个嵌入式的全局有序的KV存储系统，底层基于LSM Tree（Log Structured Merge Tree）存储。RocksDB的核心结构如下所示：



可以看出，RocksDB主要由以下部分组成：

• Mutable Memtable：一种内存数据结构（默认使用的SkipList，还有Vector Memtable跟Prefix-hash Memtable；Vector Memtable在写到L0的时候才进行排序，适合需要大量插入操作，但查询操作很少的场景；Prefix-hash Memtable适合前缀操作比较频繁的场景），新写的数据首先会被写到Mutable Memtable

• Immutable Memtable：Mutable Memtable写满了后转为Immutable Memtable，在内存中默认使用的是SkipList来组织数据的

• Block Cache：数据缓存

• Index and Bloom Filter：Index主要是Block的索引，Bloom Filter主要是用来查询Key是否在SST中

• SST File Index：由于RocksDB是全局有序的（SST File之间也是有序的），因此在Compact后可以建立SST File Index来加快查询

• WAL：Write Ahead Log，顺序写的日志文件

• SST：Sorted String Table，Immutable Memtable的数据首先会写到L0层，经Compact后会下沉到Ln层（n > 0）

• MANIFEST：RocksDB内部状态元数据，在系统异常重启后能够用MANIFEST来恢复到一个一致性状态，可以认为每一次MANIFEST的更新都代表一次Snapshot。MANIFEST维护了一个Version列表，Version包含了在这个版本下的LSM树的结构，每个Version都会有引用计数，当这个Version的引用计数为0的时候，这个版本就可以删除了（可以参考：How we keep track of SST files）。

SST主要由以下部分组成：

• Data Block：具体的KV数据

• Bloom Filter：用来快速查询Key是否在SST中

• Binary Seek Index：二分搜索索引，根据Key快速定位Data Block

• Hash Index：Binary Seek Index的索引，减少需要二分查找的次数，如果哈希冲突则退化到二分查找

RocksDB主要的接口有：

• Get：根据Key获取Value

• Put：保存一个Key、Value到RocksDB

• Delete：删除一个Key

• NewIterator：打开一个游标

RocksDB支持Column Family，不同的Column Family共享WAL（因此能保证不同Column Family之间操作的原子性，默认的Column Family是 default），而都有自己的Memtable跟SST，即是一个逻辑分区的功能。不同的Column Family可以使用不同的Compaction配置、不同的比较算法、不同的压缩算法等。

写数据流程

RocksDB的写流程比较简单，数据先往WAL写，成功后就往Mutable Memtable写；当Mutable Memtable写满后就变为Immutable Memtable，然后Immutable Memtable就会被异步写到L0层的SST。可以看出，L0层只有SST文件内的Key是有序的，L0层不同SST文件Key的范围是有可能重叠的。

查找数据流程



RocksDB查找数据的流程比较复杂。可以看出，LSM优化了写，放大了读。一次查找RocksDB可能会依次查找Mutable Memtable、所有的Immutable Memtable、所有L0的SST、部分L1~n的SST。

每个Memtable跟SST都会有相应的Bloom Filter来加快判断Key是否可能在其中，Bloom Filter有一定的错误率（不存在的情况才会出错），当判断Key可能在其中时，就会在Memtable或者SST中进行查找。

在Memtable中查找默认使用的SkipList；在SST中查找是通过Hash Index跟Binary Seek Index找到对应的Data Block，然后加载Data Block到内存中进行查找的。

L0层由于Key范围会有重叠，因此，需要搜索所有L0层的SST。在L1~n层，由于每一层的SST之间都是有序的，并且Key范围不会有重叠，因此，RocksDB在Compact的时候创建了SST File Index来加快查询。SST File Index有点类似区间树，通过SST File Index可以找到Key可能在哪些SST，然后查找相应的SST即可，不用查找所有的SST。SST File Index如下所示：

                                         file 1                                          file 2
                                      +----------+                                    +----------+
level 1:                              | 100, 200 |                                    | 300, 400 |
                                      +----------+                                    +----------+
           file 1     file 2      file 3      file 4       file 5       file 6       file 7       file 8
         +--------+ +--------+ +---------+ +----------+ +----------+ +----------+ +----------+ +----------+
level 2: | 40, 50 | | 60, 70 | | 95, 110 | | 150, 160 | | 210, 230 | | 290, 300 | | 310, 320 | | 410, 450 |
         +--------+ +--------+ +---------+ +----------+ +----------+ +----------+ +----------+ +----------+



Compaction

RocksDB目前主要支持以下类型的Compaction：

• Leveled Compaction

• Universal Compaction

• FIFO Compaction

Leveled Compaction



L0层的SST虽然也是有序的，但L0层的SST之间可能会有重叠。因此，需要将L0层所有的SST与L1层所有的SST进行Compact（使用归并排序），Compact的结果将会替换所有L1层的SST。

当L1层的SST超过限制时，RocksDB就会挑一个L1层的SST与L2层重叠的SST进行Compact，Compact的结果将会替换所选择的L2层的SST。L1~n层都一样，可以进行部分Compact。

从上面流程可以看出，Leveled Compact的瓶颈可能在L0层Compact到L1层这里。当写入的速度非常快时，L0层Compact到L1层的速度可能跟不上写入的速度，这样就会超成L0层的SST变得很多。由于查找一个Key需要查找所有L0层的SST，又会导致查找的速度变慢。因此，为了解决写入过快的问题，RocksDB又引入了Universal Compaction。

Universal Compaction



Universal Compaction的Compact只会发生在相邻的SST之间。

相比Leveled Compaction，Universal Compaction写放大较小，但空间放大较大。

FIFO Compaction



如果使用FIFO Compaction，那么所有的SST都在L0层。当总的数据量超过配置的 max_table_files_size 时，RocksDB就会删除最老的SST。因此，使用FIFO Compaction可能会有数据被清理掉，需要小心使用，确保老的数据可以删除。可以看出，FIFO Compaction适合用来做日志系统。

事务

在RocksDB中，事务分为两种：悲观（Pessimistic）锁事务和乐观（Optimistic）锁事务。悲观锁事务在每次写操作之前对Key加锁，Commit后释放锁；乐观锁事务在写数据时不加锁，在Commit的时候检查是否有写冲突，如果有则失败。在RocksDB中是通过Snapshot + Lock来实现并发控制的。

RocksDB主要有以下三种写策略：

• WriteCommitted：数据首先写缓存，等事务提交的时候再写Memtable，不能实现Read Uncommitted的事务隔离级别

• WritePrepared：在2PC事务的提交阶段写入Memtable

• WriteUnprepared：在调用 Put 接口修改数据的时候写入Memtable

TiDB

TiDB架构

TiDB是一个分布式的HTAP（Hybrid Transactional and Analytical Processing）数据库。TiDB的总体架构如下所示：



TiDB主要由以下几部分组成：

• PD：Placement Driver，主要负责提供时钟服务（TSO）、存储元数据、Region调度等

• TiKV：负责数据的存储，底层默认使用的是Facebook开源的一个KV数据库RocksDB

• TiDB：计算层，负责SQL解析、制定查询计划、生成执行器等

• TiFlash：TiKV的列存扩展，通过Raft Learner协议异步同步数据，适合大规模的OLAP计算

我们再看一下TiKV的架构：



可以看出，TiKV底层默认使用了RocksDB，在RocksDB的基础上使用Multi-raft实现了数据的分布式存储，每一个Region就是一个Raft Group。TiKV使用了两个RocksDB实例，一个用来存储Raft Log，一个用来存储实际的数据。TiDB分布式事务的实现使用的Percolator算法。

在TiDB中，数据的编码规则如下：

• 表数据Key：tablePrefix_rowPrefix_$tableID_$rowIDValue：[$col1, $col2, $col3, $col4]

• Unique IndexKey：tablePrefix_idxPrefix_$tableID_$indexID_$indexColumnsValueValue：$rowID

• 非Unique IndexKey：tablePrefix_idxPrefix_$tableID_$ColumnsValue_$rowIDValue：null

TiDB查找数据流程

我们看一下简化版的数据查找流程：



可以看出，对于事务型查找，TiDB首先会从PD获取start_ts，然后再获取数据所在的regions等信息，然后请求TiKV获取具体的数据。

TiDB事务

TiDB的事务使用的是Percolator算法，流程如下所示：

流程跟Percolator差不多，具体可以参考：分布式事务研究（图也是在这个基础上微调）

TiDB Region调度策略

PD会根据从TiKV收集来的信息做为调度的依据。

TiDB有如下调度策略：

• 一个Region的Replica数量正确

• 一个Raft Group中的多个Replica不在同一个位置

• 副本在Store之间均匀分布

• Leader数量在Store之间均匀分布

• 访问热点数量在Store之间均匀分布

• 各个Store的存储空间占用大致相等

• 控制调度速度，避免影响在线服务

多数据中心部署方案

TiDB可以对服务器进行打标签（Labels），从而支持跨数据中心调度。Labels根据部署的物理结构来定义可以分为DC、ZONE、RACK、HOST四个等级。例如：

tikv_servers:
  - host: 10.63.10.30
    config:
      server.labels: { dc: "1", zone: "1", rack: "1", host: "30" }
  - host: 10.63.10.31
    config:
      server.labels: { dc: "1", zone: "2", rack: "2", host: "31" }
  - host: 10.63.10.32
    config:
      server.labels: { dc: "1", zone: "3", rack: "3", host: "32" }


同城三中心



TiDB可以设置调度策略，将Region Leader跟PD Leader都调度到同一个数据中心，这样可以不受数据中心间网络的影响。

两地三中心



两地三中心通过在异地备份数据（TiDB官方推荐使用五副本备份数据），可以应对城市级自然灾害。

引用

TiDB Docs

TiDB自增ID

MPP and SMP in TiDB

三篇文章了解 TiDB 技术内幕 - 说计算

三篇文章了解 TiDB 技术内幕 - 说存储

三篇文章了解 TiDB 技术内幕 - 谈调度

TiKV 源码解析系列 - Raft 的优化

TiKV 源码解析系列——multi-raft 设计与实现

TiKV 源码解析系列——如何使用 Raft

基于 Raft 构建弹性伸缩的存储系统的一些实践

TiKV 源码解析系列 - PD Scheduler

TiKV 的 MVCC（Multi-Version Concurrency Control）机制

TiKV 源码解析系列——Placement Driver

A Deep Dive into TiKV

Deep Dive TiKV

十问 TiDB ：关于架构设计的一些思考

TiDB Best Practice

TiDB 中的全局唯一 ID

Power of the Log: LSM & Append Only Data Structures

Scylladb Compaction Strategies

RocksDB Wiki

Improving Point-Lookup Using Data Block Hash Index

RocksDB 笔记