TiDB 简述及 TiKV 的数据结构与存储 | 京东物流技术团队
![TiDB简述及TiKV的数据结构与存储 | 京东物流技术团队](https://static001.geekbang.org/infoq/b4/b404f0f3ad81f89f486e073431fbb61c.png)
1 概述
TiDB 是 PingCAP 公司自主设计、研发的开源分布式关系型数据库,是一款同时支持在线事务处理与在线分析处理 (Hybrid Transactional and Analytical Processing, HTAP) 的融合型分布式数据库产品,具备水平扩容或者缩容、金融级高可用、实时 HTAP、云原生的分布式数据库、兼容 MySQL 5.7 协议和 MySQL 生态等重要特性。目标是为用户提供一站式 OLTP (Online Transactional Processing)、OLAP (Online Analytical Processing)、HTAP 解决方案。TiDB 适合高可用、强一致要求较高、数据规模较大等各种应用场景。
总结一下,Tidb 是个高度兼容 MySQL 的分布式数据库,并拥有以下几个特性:
高度兼容 MySQL:掌握 MySQL,就可以零基础使用 TIDB
水平弹性扩展:自适应扩展,基于 Raft 协议
分布式事务:悲观锁、乐观锁、因果一致性
真正金融级高可用:基于 Raft 协议
一站式 HTAP 解决方案:单个数据库同时支持 OLTP 和 OLAP,进行实时智能处理的能力
其中 TiDB 的核心特性是:水平扩展、高可用。
本文主要从 TiDB 的各类组件为起点,了解它的基础架构,并重点分析它在存储架构方面的设计,探究其如何组织数据,Table 中的每行记录是如何在内存和磁盘中进行存储的。
2 组件
先看一张 Tidb 的架构图,里面包含 TiDB、Storage(TiKV、TiFlash)、TiSpark、PD。其中的 TiDB、TiKV、PD 是核心组件;TIFlash、TiSpark 是为了解决复杂 OLAP 的组件。
TiDB 是 Mysql 语法的交互入口,TiSpark 是 sparkSAL 的交互入口。
![](https://static001.geekbang.org/infoq/b7/b7945f42a195c24a2b846a14e7bfbed1.png)
2.1 TiDB Server
SQL 层,对外暴露 MySQL 协议的连接 endpoint,负责接受客户端的连接,执行 SQL 解析和优化,最终生成分布式执行计划。
TiDB 层本身是无状态的,实践中可以启动多个 TiDB 实例,通过负载均衡组件(如 LVS、HAProxy 或 F5)对外提供统一的接入地址,客户端的连接可以均匀地分摊在多个 TiDB 实例上以达到负载均衡的效果。TiDB Server 本身并不存储数据,只是解析 SQL,将实际的数据读取请求转发给底层的存储节点 TiKV(或 TiFlash)。
2.2 PD (Placement Driver) Server
整个 TiDB 集群的元信息管理模块,负责存储每个 TiKV 节点实时的数据分布情况和集群的整体拓扑结构,提供 TiDB Dashboard 管控界面,并为分布式事务分配事务 ID。
PD 不仅存储元信息,同时还会根据 TiKV 节点实时上报的数据分布状态,下发数据调度命令给具体的 TiKV 节点,可以说是整个集群的“大脑”。此外,PD 本身也是由至少 3 个节点构成,拥有高可用的能力。建议部署奇数个 PD 节点。
2.3 存储节点
2.3.1 TiKV Server
负责存储数据,从外部看 TiKV 是一个分布式的提供事务的 Key-Value 存储引擎。
存储数据的基本单位是 Region,每个 Region 负责存储一个 Key Range(从 StartKey 到 EndKey 的左闭右开区间)的数据,每个 TiKV 节点会负责多个 Region。
TiKV 的 API 在 KV 键值对层面提供对分布式事务的原生支持,默认提供了 SI (Snapshot Isolation) 的隔离级别,这也是 TiDB 在 SQL 层面支持分布式事务的核心。
TiDB 的 SQL 层做完 SQL 解析后,会将 SQL 的执行计划转换为对 TiKV API 的实际调用。所以,数据都存储在 TiKV 中。另外,TiKV 中的数据都会自动维护多副本(默认为三副本),天然支持高可用和自动故障转移。
2.3.2 TiFlash
TiFlash 是一类特殊的存储节点。和普通 TiKV 节点不一样的是,在 TiFlash 内部,数据是以列式的形式进行存储,主要的功能是为分析型的场景加速。假如使用场景为海量数据,且需要进行统计分析,可以在数据表基础上创建 TiFlash 存储结构的映射表,以提高查询速度。
以上组件互相配合,支撑着 Tidb 完成海量数据存储、同时兼顾高可用、事务、优秀的读写性能。
3 存储架构
3.1 TiKV 的模型
前文所描述的 Tidb 架构中,其作为存储节点的有两个服务,TiKV 和 TiFlash。其中 TiFlash 为列式存储的形式实现的,可以参考 ClickHouse 的架构思路,二者具有相似性。本章节主要讨论 TiKV 的实现。
![](https://static001.geekbang.org/infoq/aa/aa72a15ad82a45aa72e1d7880966acf2.png)
在上图中,TiKV node 所描述的就是 OLTP 场景下 Tidb 的存储组件,而 TiFlash 则是应对的 LOAP 场景。TiKV 选择的是 Key-Value 模型,作为数据的存储模型,并提供有序遍历方法进行读取。
TiKV 数据存储有两个关键点:
是一个巨大的 Map(可以参考 HashMap),也就是存储的是 Key-Value Pairs(键值对)。
这个 Map 中的 Key-Value pair 按照 Key 的二进制顺序有序,也就是可以 Seek 到某一个 Key 的位置,然后不断地调用 Next 方法,以递增的顺序获取比这个 Key 大的 Key-Value。
需要注意的是,这里描述的 TiKV 的 KV 存储模型,与 SQL 中的 Table 无关,不要有任何代入。
在图中 TiKV node 内部,有 store、Region 的概念,这是高可用的解决方案,TiDB 采用了 Raft 算法实现,这里细分析。
3.2 TiKV 的行存储结构
在使用 Tidb 时,依然以传统“表”的概念进行读写,在关系型数据库中,一个表可能有很多列。而 Tidb 是以 Key-Value 形式构造数据的,因此需要考虑,将一行记录中,各列数据映射成一个 key-value 键值对。
首先,在 OLTP 场景,有大量针对单行或者多行的增、删、改、查操作,要求数据库具备快速读取一行数据的能力。因此,对应的 Key 最好有一个唯一 ID(显示或隐式的 ID),以方便快速定位。
其次,很多 OLAP 型查询需要进行全表扫描。如果能够将一个表中所有行的 Key 编码到一个区间内,就可以通过范围查询高效完成全表扫描的任务。
3.2.1 表数据的 KV 映射
Tidb 中表数据与 Key-Value 的映射关系,设计如下:
为了保证同一个表的数据会放在一起,方便查找,TiDB 会为每个表分配一个表 ID,用 TableID 表示,整数、全局唯一。
TiDB 会为每行数据分配一个行 ID,用 RowID 表示,整数、表内唯一。如果表有主键,则行 ID 等于主键。
基于以上规则,生成的 Key-Value 键值对为:
其中 tablePrefix 和 recordPrefixSep 都是特定的字符串常量,用于在 Key 空间内区分其他数据。
这个例子中,是完全基于 RowID 形成的 Key,可以类比 MySQL 的聚集索引。
3.2.2 索引数据的 KV 映射
对于普通索引,在 MySQL 中是有非聚集索引概念的,尤其 innodb 中,通过 B+Tree 形式,子节点记录主键信息,再通过回表方式得到结果数据。
在 Tidb 中是支持创建索引的,那么索引信息如何存储? 它同时支持主键和二级索引(包括唯一索引和非唯一索引),且与表数据映射方式类似。
设计如下:
Tidb 为表中每个索引,分配了一个索引 ID,用 IndexID 表示。
对于主键和唯一索引,需要根据键值快速定位到 RowID,这个会存储到 value 中
因此生成的 key-value 键值对为:
由于设计的 key 中存在 indexedColumnsValue,也就是查询的字段值,因此可以直接命中或模糊检索到。再通过 value 中的 RowID,去表数据映射中,检索到 RowID 对应的行记录。
对于普通索引,一个键值可能对应多行,需要根据键值范围查询对应的 RowID。
根据字段值,可以检索到具有相关性的 key 的列表,在根据 key 中包含的 RowID,再拿到行记录。
3.2.3 映射中的常量字符串
上述所有编码规则中的 tablePrefix、recordPrefixSep 和 indexPrefixSep 都是字符串常量,用于在 Key 空间内区分其他数据,定义如下:
在上述映射关系中,一个表内所有的行都有相同的 Key 前缀,一个索引的所有数据也都有相同的前缀。这样具有相同的前缀的数据,在 TiKV 的 Key 空间内,是排列在一起的。
因此,只需要设计出稳定的后缀,则可以保证表数据或索引数据,有序的存储在 TiKV 中。而有序带来的价值就是能够高效的读取。
3.2.4 举例
假设数据库的一张表,如下:
表中有 3 行记录:
这张表中有一个主键 ID、一个普通索引 idxAge,对应的是列 Age.
假设该表的 TableID=10,则其表数据的存储如下:
其普通索引 idxAge 的存储如下:
3.3 SQL 与 KV 映射
TiDB 的 SQL 层,即 TiDB Server,负责将 SQL 翻译成 Key-Value 操作,将其转发给共用的分布式 Key-Value 存储层 TiKV,然后组装 TiKV 返回的结果,最终将查询结果返回给客户端。
举例,“select count(*) from user where name=’tidb’;”这样的 SQL 语句,在 Tidb 中进行检索,流程如下:
根据表名、所有的 RowID,结合表数据的 Key 编码规则,构造出一个[StartKey,endKey)的左闭右开区间。
根据[StartKey,endKey)这个区间内的值,到 TiKV 中读取数据
得到每一行记录后,过滤出 name=’tidb’的数据
将结果进行统计,计算出 count(*)的结果,进行返回。
![](https://static001.geekbang.org/infoq/cc/ccf9363307ca5ae5a9079a67ba4d20ed.png)
在分布式环境下,为了提高检索效率,实际运行过程中,上述流程是会将 name=’tidb’和 count( *)下推到集群的每个节点中,减少无异议的网络传输,每个节点最终将 count( *)的结果,再由 SQL 层将结果累加求和。
4 RockDB 持久化
4.1 概述
前文所描述的 Key-Value Pairs 只是存储模型,是存在于内存中的,任何持久化的存储引擎,数据终归要保存在磁盘上。TiKV 没有选择直接向磁盘上写数据,而是把数据保存在 RocksDB 中,具体的数据落地由 RocksDB 负责。
这个选择的原因是开发一个单机存储引擎工作量很大,特别是要做一个高性能的单机引擎,需要做各种细致的优化,而 RocksDB 是由 Facebook 开源的一个非常优秀的单机 KV 存储引擎,可以满足 TiKV 对单机引擎的各种要求。这里可以简单的认为 RocksDB 是一个单机的持久化 Key-Value Map。
4.2 RocksDB
TiKV Node 的内部被划分成多个 Region,这些 Region 作为数据切片,是数据一致性的基础,而 TiKV 的持久化单元则是 Region,也就是每个 Region 都会被存储在 RocksDB 实例中。
![](https://static001.geekbang.org/infoq/33/3337e37b7505fc2cf2329aaa48f6949e.png)
以 Region 为单元,是基于顺序 I/O 的性能考虑的。而 TiKV 是如何有效的组织 Region 内的数据,保证分片均匀、有序,这里面用到了 LSM-Tree,如果有 HBase 经验一定不模式。
4.2.1 LSM-Tree 结构
LSM-Tree(log structured merge-tree)字面意思是“日志结构的合并树”,LSM-Tree 的结构是横跨磁盘和内存的。它将存储介质根据功能,划分磁盘的 WAL(write ahead log)、内存的 MemTable、磁盘的 SST 文件;其中 SST 文件又分为多层,每一层数据达到阈值后,会挑选一部分 SST 合并到下一层,每一层的数据是上一层的 10 倍,因此 90%的数据会存储在最后一层。
![](https://static001.geekbang.org/infoq/cf/cf2776c42fe91cb6e4ee3aba2f530594.png)
WAL:是预写 Log 的实现,当进行写操作时,会将数据通过 WAL 方式备份到磁盘中,防止内存断电而丢失。
Memory-Table:是在内存中的数据结构,用以保存最近的一些更新操作;memory-table 可以使用跳跃表或者搜索树等数据结构来组织数据,以保持数据的有序性。当 memory-table 达到一定的数据量后,memory-table 会转化成为 immutable memory-table,同时会创建一个新的 memory-table 来处理新的数据。
Immutable Memory-Table:immutable memory-table 在内存中是不可修改的数据结构,它是将 memory-table 转变为 SSTable 的一种中间状态。目的是为了在转存过程中不阻塞写操作。写操作可以由新的 memory-table 处理,而不用因为锁住 memory-table 而等待。
SST 或 SSTable:有序键值对集合,是 LSM 树组在磁盘中的数据的结构。如果 SSTable 比较大的时候,还可以根据键的值建立一个索引来加速 SSTable 的查询。SSTable 会存在多个,并且按 Level 设计,每一层级会存在多个 SSTable 文件。
4.2.2 LSM-Tree 执行过程
写入过程
首先会检查每个区域的存储是否达到阈值,未达到会直接写入;
如果 Immutable Memory-Table 存在,会等待其压缩过程。
如果 Memory-Table 已经写满,Immutable Memory-Table 不存在,则将当前 Memory-Table 设置为 Immutable Memory-Table,生成新的 Memory-Table,再触发压缩,随后进行写入。
写的过程会先写入 WAL,成功后才会写 Memory-Table,此刻写入才完成。
数据存在的位置,按顺序会依次经历 WAL、Memory-Table、Immutable Memory-Table、SSTable。其中 SSTable 是数据最终持久化的位置。而事务性写入只需要经历 WAL 和 Memory-Table 即可完成。
查找过程
1.根据目标 key,逐级依次在 Memory-Table、Immutable Memory-Table、SSTable 中查找
2.其中 SSTable 会分为几个级别,也是按 Level 中进行查找。
Level-0 级别,RocksDB 会采用遍历的方式,所有为了查找效率,会控制 Level-0 的文件个数。
而 Level-1 及以上层级的 SSTable,数据不会存在交叠,且由于存储有序,会采用二分查找提高效率。
RocksDB 为了提高查找效率,每个 Memory-Table 和 SSTable 都会有相应的 Bloom Filter 来加快判断 Key 是否可能在其中,以减少查找次数。
删除和更新过程
当有删除操作时,并不需要像 B+树一样,在磁盘中的找到相应的数据后再删除。
首先会在通过查找流程,在 Memory-Table、Immuatble Memory-Table 中进行查找。
如果找到则对结果标记为“删除”。
否则会在结尾追加一个节点,并标记为“删除”
在真正删除前,未来的查询操作,都会先找到这个被标记为“删除”的记录。
之后会在某一时刻,通过压缩过程真正删除它。
更新操作和删除操作类似,都是只操作内存区域的结构,写入一个标志,随后真正的更新操作被延迟在合并时一并完成。由于操作是发生在内存中,其读写性能也能保障。
4.3 RockDB 的优缺点
优点
将数据拆分为几百 M 大小的块,然后顺序写入
首次写入的目的地是内存,采用 WAL 设计思路,加上顺序写,提高写入的能力,时间复杂度近似常数
支持事务,但 L0 层的数据,key 的区间有重叠,支持较差
缺点
读写放大严重
应对突发流量的时候,削峰能力不足
压缩率有限
索引效率较低
压缩过程比较消耗系统资源,同时对读写影响较大
5 总结
以上针对 TiDB 的整体架构进行建单介绍,并着重描述了 TiKV 是如何组织数据、如何存储数据。将其 Key-Value 的设计思路,与 MySQL 的索引结构进行对比,识别相似与差异。TiDB 依赖 RockDB 实现了持久化,其中的 Lsm-Tree,作为 B+Tree 的改进结构,其关注中心是“如何在频繁的数据改动下保持系统读取速度的稳定性”,以顺序写磁盘作为目标,假设频繁地对数据进行整理,力求数据的顺序性,带来读性能的稳定,同时也带来了一定程度的读写放大问题。
作者:京东物流 耿宏宇
来源:京东云开发者社区 自猿其说 Tech
版权声明: 本文为 InfoQ 作者【京东科技开发者】的原创文章。
原文链接:【http://xie.infoq.cn/article/502d28fe2f7b64e4551f9bf7d】。文章转载请联系作者。
评论