论文《TiDB:A Raft-based HTAP Database》阅读感悟

作者： 数据源的 TiDB 学习之路原文来源：https://tidb.net/blog/a4cd2256

人到中年，越来越发现一个道理，那就是人要不断的学习、不停的卷自己，才不至于被落后。35 岁开始，加强两件事：读书和锻炼。读书可以丰富知识，锻炼可以强身健体。身体和灵魂，总有一个在路上！

最近在学习国产数据库 TiDB，找到论文《TiDB:A Raft-based HTAP Database》，通读了一遍，也算是对 TiDB 有了初步的了解。本篇就根据阅读理解谈谈自己的认知。

一. 前序

1．TiDB 的设计初衷是什么？

换句话说，TiDB 这款数据库主要是解决什么问题。简单理解 TiDB 是为了解决“one size fill all”这个问题。

最初的关系型数据库系统 RDBMS 因其关系模型、强大的事务保证和 SQL 接口而流行，它们在传统的业务系统中被广泛应用，但传统 RDBMS 无法提供可伸缩性和高可用性。21 世纪初，互联网应用更喜欢 NoSQL 系统，如 Google BigTable 和 DynamoDB 等，NoSQL 放宽了一致性要求，提供了高可伸缩性和可替代的数据模型，如键值对、图和文档。然而，许多应用程序还是需要强大的事务、数据一致性和 SQL 接口，因此又出现了 NewSQL 系统，比如 CockroachDB 和 Google Spanner 等。除此之外，联机分析处理（OLAP）也在迅速发展，比如诸多 SQL-on-Hadoop 系统如 Hive、Impala 或一些 MPP 数据库如 Greenplum、Teradata 等。

那么有没有一款数据库产品可以同时兼容 NewSQL 的特性，同时又能满足 OLAP 的需求呢？这就是 TiDB 的由来，其设计初衷是要做一款 NewSQL+OLAP 结合起来的 HTAP 数据库，产品理念是来自于 NewSQL 数据库。

2．HTAP 系统需要解决什么问题？

为了更好的同时满足 OLTP 和 OLAP 业务，HTAP 系统设计需要考虑两个重要的特性：新鲜度和隔离性。

新鲜度：通常是针对 OLAP 来说的，即怎么保证 OLAP 业务处理的数据是最新的。如今，实时分析最新数据会产生巨大的商业价值。以前我们通过提取 - 转换 - 加载（ETL）工具如 Kettle、DataX 等将 OLTP 中的数据定期刷新到 OLAP 系统的方案，存在较大的延迟，通常耗时数小时或数天。后来有了流式传输方案如 Flink、Kafka，减少了同步时间，但这种方案仍然缺乏全局的数据治理模型，与多个系统接口带来额外的开销。

隔离性：指为单独的 OLTP 和 OLAP 查询保证隔离的性能。虽然业内也有一些 HTAP 的数据库，比如 SAP HANA、Greenplum 等，数据都是部署在相同的服务器上的（可能是不同的存储引擎，比如 Greenplum 中使用 heap 表来满足 OLTP，使用 AO 表来满足 OLAP），尽管能提供最新的数据，但是不能同时实现 OLTP 和 OLAP 的高性能。如果能在不同的硬件资源上分别运行 OLTP 和 OLAP，就能很好的隔离开两种业务的相互影响。

3．TiDB 是怎么解决上述问题的？

从论文的标题我们也可以看出，TiDB 实现 HTAP 能力的根基在于 Raft。大家知道，Paxos 和 Raft 是两种最有名的共识算法，Raft 算法易于理解和工程实现，因此 TiDB 选择了 Raft。关于 Raft 本身的概念和原理，笔者在此不做过多说明（分享一张之前整理的 PPT）。

那么 TiDB 到底在 Raft 上面做了什么，使得它可以满足 HTAP 能力呢？简单理解就是：增加 Learner 角色，Learner 异步从 Leader 同步日志，不参与选举，Learner 采用列式存储。

显而易见，这种实现方式有多方面好处。首先，Learner 是从 Leader 异步同步日志，这种方法开销低，并且保持数据一致性。其次，复制到 Learner 的数据被转换为列式存储，列式存储可以更高效的处理 OLAP（OLTP 业务仍然采用行式存储）。通过把 Learner 部署在单独的硬件资源上，就能很好的隔离 OLTP 和 OLAP 业务了。除此之外，TiDB 还实现了多项优化，比如如何在行存和列存中自动选择一个最优的执行计划等。

二. TiDB 的架构

TiDB 的整体架构可以划分为四大模块：客户端、计算引擎层、分布式存储层、Placement Driver（PD）。我们依次了解这几大模块的关键特性，

（1）客户端：TiDB 兼容 MySQL 协议，可以被 MySQL 兼容的客户端访问。世面上有不少国产数据库也是以兼容 MySQL 为主，比如 OceanBase、GBase 8a、Doris、Clickhouse 等。

（2）计算引擎层：也称为 TiDB，它是无状态的，可方便扩展。其主要工作就是将接收的客户端 SQL 请求进行查询解析并生成执行计划。在事务处理上，主要实现基于 Percolator 的两阶段提交协议（2PC）。内置的查询优化器可以自动选择从底层的 TiKV 存储还是 TiFlash 存储中获取数据以达到性能最优。为了集成 Hadoop，还增加了 TiSpark，它是一个优化的 Spark 组件。

（3）分布式存储层：包括行存储（TiKV）和列存储（TiFlash）两部分。TiKV 中的数据是一个有序的键值映射，每条记录映射为一个键值对。键由表 ID 和行 ID 组成，值是实际的行数据，如下图所示：

Key:{table{tableID} record{rowID}}

Value: {col0, col1, col2, col3}

为了向外扩展，默认采用范围分区策略，将大的键值映射拆分为多个连续的范围（Region），每个 Region 有多个副本用于实现高可用性。每个 Region 及其副本组成一个 Raft 组。TiFlash 的数据是异步复制于 TiKV，并转储为列式存储。由于多个 Raft 组在分布式存储层中管理数据，因此我们称之为 multi-Raft 存储。

（4）Placement Driver（PD）：PD 可以认为是集群的大脑，它的主要作用包括：管理 Regions（提供 Key 所在的 Region 以及地理位置，对 Region 进行负载均衡等）；提供全局时间戳（TSO）。为了实现高可用，PD 包含多个 PD 成员。

实际上，TiDB 的每个组件都设计为具有高可用性和可伸缩性。存储层，使用 Raft 算法来实现数据副本之间的一致性，TiKV 和 TiFlash 之间的低延迟复制使分析查询可以获得新数据。查询优化器以及 TiKV 和 TiFlash 之间的强一致性数据提供了快速的分析查询处理，对事务处理影响较小。

三. 关于 TiKV

行存储 TiKV 由多个 TiKV 服务器组成，使用 Raft 在 TiKV 服务器之间复制 Regions。每个 TiKV 服务器都包含不同 Region 的 Leader 或 Follower。在每个 TiKV 上，数据和元数据被持久化到 RocksDB，RocksDB 是一个可嵌入的、持久化的键值存储。每个 Region 有一个可配置的最大大小，默认为 96MB。每个服务器的 Raft Leader 负责处理相应 Region 的读 / 写请求。

Raft 算法响应读写请求时，在 Leader 和 Follower 之间的基本执行过程为：

（1）      Region Leader 接收来自 SQL 引擎层的请求。

（2）      Leader 将请求追加到它的日志中。

（3）      Leader 将新的日志条目发送给 Followers，Followers 将这些条目追加到自己的日志中。

（4）      Leader 等待 Followers 做出反应，如果半数以上节点成功响应，Leader 就提交请求并在本地应用它。

（5）      Leader 将结果发送给客户端，并继续处理传入的请求。

以上过程虽然可以保证数据的一致性和高可用性，但由于这些步骤是顺序发生，因此并不能提供高效的性能。为了实现高读 / 写吞吐量，在 TiKV 中实现了多项优化。

1．写优化

优化点 1：上述过程中的（2）和（3）可以并行执行，如果一定数量的 Follower 成功追加日志而即使 Leader 追加日志失败，此时仍然可以提交。

优化点 2：Leader 发送日志后不需要等待 Follower 响应，可以假设成功，并使用预测的日志索引发送进一步的日志。如果出现错误，Leader 调整日志索引，重新发送复制请求。

优化点 3：应用已提交日志条目的 Leader 可以由另一个线程异步处理。

基于以上优化，Raft 流程更新为：

（1）      Leader 接收 SQL 引擎层的请求。

（2）      Leader 将相应日志发送给 Follower，并在本地并行追加日志。

（3）      Leader 继续接收来自客户端的请求并重复步骤（2）。

（4）      Leader 提交日志并发送给另外一个线程来应用。

（5）      Leader 应用日志后，将结果返回给客户端。

2．读优化

为了保证从 Leader 读取数据的序列化语义，需要为每个读请求发出一个日志条目，并在返回之前等待该条目被提交。但这个过程比较昂贵，为了提高性能，可以避免日志同步阶段。Raft 保证一旦 Leader 写入成功后就可以响应任何读请求，而不需要跨服务器同步日志。但 Leader 选举后可能会发生 Leader 角色在 Raft 组中移动的情况，为了实现对 Leader 的读取，TiKV 实现以下读取优化。

（1）读索引。当 Leader 响应读请求时，将当前提交索引记录为本地读索引，并向 Follower 发送心跳以确认其 Leader 角色。一旦它的应用索引大于或等于读索引，就可以返回该值。这种方法提高了读性能，但会带来一定的网络开销。

（2）租约读取。Leader 和 Follower 约定一个租期，在租期内 Follower 不发出选举请求，这样 Leader 就不会被改变。在租期内，Leader 可以在不连接 Follower 的情况下响应任何读请求。如果每个节点的 CPU 时钟相差不大，这种方法比较合适。

（3）跟随者读（Follower read）。Follower 响应客户端读请求，当 Follower 收到读请求后，它会向 Leader 请求最新的读索引，如果本地应用的索引大于或等于读索引，则 Follower 可以将该值返回给客户端，否则必须等待应用日志。跟随者读可以减轻热点 Leader 的压力，从而提高读性能。

3．管理海量 Regions

海量 Regions 分布在不同服务器上，可能存在节点之间不均衡的情况。服务器也可能会出现被添加或移出的情况。TiDB 使用 Placement Driver（PD）调度 Regions 的副本数量及位置。PD 初始化时通过心跳从存储引擎上获取 Region 的位置信息，之后监视每个服务器上的工作负载，并在不影响应用的情况下将热 Regions 迁移到不同的服务器。

维护大量 Regions 涉及心跳和管理元数据，导致大量网络和存储开销。为优化此问题，可以根据 Region 负载繁忙程度，调整发送心跳的频率。

4．动态 Region 拆分与合并

当 Region 访问过多会导致负载不均，这样的 Region 应该分割成更小的 Region 便于均衡负载。另一方面，太多小的 Region 可能很少访问但是系统仍然需要维护心跳和元数据，这些 Region 应该进行合并。注意，为了保持 Region 之间的顺序，只合并键空间相邻的 Region。Region 的拆分和合并由 PD 动态的向 TiKV 发送命令完成。

Region 拆分过程类似 Raft 中的普通更新请求，步骤如下：

（1）PD 向 Region 的 Leader 发出 split 命令。

（2）Leader 接收到 split 命令后，将命令转换为日志，并将日志复制到所有 Follower 节点。

（3）当多数派复制日志完成后 Leader 提交 split 命令，并将命令应用于 Raft 组的所有节点。应用过程包括更新原始 Region 的范围和 epoch 元数据，并创建新的 Region 以覆盖剩余的范围。

（4）对于分割 Region 的每个副本，将创建一个 Raft 状态机并开始工作，形成一个新的 Raft 组。原始 Region 的 Leader 将拆分结果报告给 PD。此时分割完成。

如上，Region 分割因为只需要更改元数据，所以开销很低。Region 的合并过程是 PD 移动两个 Region 的所有副本，将它们放在不同的服务器上，然后通过两个阶段操作在每个服务器上本地合并两个 Region 的相同副本；之后停止一个 Region 的业务，并与另一个 Region 合并。

四. 关于 TiFlash

前面的介绍中，我们已经学习到 TiFlash 是由 Learner 节点组成，Learner 节点异步的接收 Raft 组的日志，并将行格式的元组转换为列数据。它们不参与 Leader 选举和仲裁，因此对 TiKV 的开销影响很小。在 TiDB 中，可以使用一条 SQL 命令为表增加列格式的副本（其中 n 代表副本的数量，缺省为 1）：

ALTER TABLE x SET TiFLASH REPLICA n;

给表增加列副本就像增加异步列索引一样，TiFlash 中的每个表被划分为多个分区，每个分区覆盖连续的行范围。在 TiFlash 实例初始化时，需要从相关的 Leader 复制数据到 Learners，如果要快速同步大量数据，则 Leader 通过发送数据快照的方式到 Learner。初始化完成后，TiFlash 则实时监听 Raft 组的更新，并将日志应用到本地状态机。

1．日志重放

日志重放的目的就是 TiFlash 在接收到 Raft 组发送的日志后将日志进行相关的操作，最终变为列格式的数据存储在磁盘上。具体分为以下几个步骤：

（1）压缩日志。事务的日志分为预写、提交或回滚三种状态。回滚日志中的数据不需要写入磁盘，因此压缩进程会根据回滚日志删除无效的预写日志，将有效的日志放入缓冲区。

（2）解码元组。缓冲区中的日志被解码为行格式的元组，删除有关事务的冗余信息。然后将解码的元组放入行缓冲区中。

（3）转换数据格式。当行缓冲区中的数据超过大小限制或持续时间超过时间间隔限制，将这些行格式元组转换为列数据并写入本地分区数据池。转换引用本地缓存的模式，这些模式定期与 TiKV 同步。

日志重放及解码过程如下表所示：原始日志包含 8 个条目，它们试图插入两个元组、更新一个元组和删除一个元组。但插入 k1 会回滚，因此只保留 8 个日志项中的 6 个，从中解码三个元组。最后，将三个解码元组转换为 5 列：操作类型、提交时间戳、键和两列数据。列数据被追加到 Delta Tree 中。

2．Delta Tree

Delta Tree 是一个列式存储引擎，它可以立即追加增量更新，然后将它们与每个分区之前的稳定版本合并。Delta Tree 存储引擎主要有两部分空间：增量空间（Delta space）及稳定空间（Stable space）。在稳定空间中，分区数据以块（Chunk）的形式存储，每个块覆盖一个范围的数据，数据按列存储。相反，增量则按照 TiKV 生成它们的顺序直接追加到增量空间。TiFlash 中的列存数据存储格式类似于 Parquet，使用常见的 LZ4 压缩数据文件，以节省磁盘大小。

新写入的增量数据是插入或删除范围的原子批处理。这些增量缓存在内存中并物化到磁盘。增量按写入顺序存储，实现了 WAL 的功能。增量数据一般存储在许多小文件中，为了降低读取的 IO 成本，定期合并多个小的增量到一个较大增量并刷新到磁盘，然后删除之前小的增量。

读取数据时，可能需要将增量空间中的增量文件以及稳定空间中的稳定元组合并读取（即读放大）。此外，许多增量文件可能包含无用的数据（即空间放大），会浪费存储空间并降低与稳定元组的合并效率。

由于相关的键在增量空间中是无序的，合并增量代价较大，这种无序也减慢了增量与稳定块的合并读取。因此，在增量空间的顶部建立一个 B+ 树索引，每个增量按键和时间戳顺序插入到 B+ 树中，帮助读取时更快速查找到键，也使得增量与稳定块的合并更高效。

五. 关于事务

TiDB 的事务隔离级别支持快照隔离（SI）和可重复读（RR）。SI 允许事务中每个请求读取到数据的一致版本。事务中不同语句对同一个键可能会读取到不同的值（比如 RC 隔离级别），RR 将保证事务中对相同的键将始终读取相同的值。TiDB 同时实现了多版本并发控制（MVCC），避免了读写锁定并防止写写冲突。

TiDB 中一个事务会涉及到 SQL 引擎、TiKV 和 PD 之间的协同工作，其中：

（1）SQL 引擎：负责协调事务。接收客户端 SQL 请求，将数据转换为 KV 格式，并使用两阶段提交（2PC）将事务写入 TiKV。

（2）PD：负责管理逻辑 Regions 及物理位置；提供全局严格递增的时间戳。

（3）TiKV：提供分布式事务接口，实现 MVCC，并将数据持久化到磁盘。

TiDB 既实现了乐观锁，也支持悲观锁。锁的实现来自于 Percolator 模型，该模型选择一个键作为主键，并用它来表示事务的状态，并使用基本的两阶段提交来执行事务。

乐观事务处理流程为：

（1）当收到客户端的 begin 命令后，SQL 引擎向 PD 请求一个时间戳作为事务的开始时间戳 start_ts。

（2）SQL 引擎从 TiKV 读取数据并写入本地内存来执行 DML。TiKV 在事务的 start_ts 之前提供最近的提交时间戳 commit_ts。

（3）当 SQL 引擎从客户端接收到 commit 命令时，它启动 2PC 协议。它随机选择一个主键，并行锁定所有键，并向 TiKV 节点发送预写。

（4）如果所有预写成功，SQL 引擎向 PD 请求事务的 commit_ts，并向 TiKV 发送命令。TiKV 提交主键并向 SQL 引擎发送成功响应。

（5）SQL 引擎将成功返回给客户端。

（6）SQL 引擎通过向 TiKV 发送进一步的提交命令，以异步和并行的方式提交辅助键并清除锁。

对比悲观锁与乐观锁，其最大的区别在于何时获取锁。乐观事务中，锁是在预写阶段增量获取的；而悲观事务中，锁是在预写之前执行 DML 时获取。

在悲观事务中锁定键时，SQL 引擎获取一个新的时间戳 for_update_ts。如果 SQL 引擎无法获取锁，它可以重试从该锁开始的事务，而不是回滚并重试整个事务。在读取时，TiKV 使用 for_update_ts 而不是 start_ts 来决定可以读取键的哪些值。通过这种方式悲观事务保持 RR 隔离级别。悲观事务还允许使用读提交（RC）隔离级别，这样可以减少事务之间的冲突，从而提高性能。

时间戳是由 PD 分配的，每个时间戳包括物理时间和逻辑时间。物理时间为当前时间，精度为毫秒级别；逻辑时间为 18 bit。理论上，PD 每毫秒可以分配 2^18 个时间戳。为降低延迟，客户端按批次从 PD 申请时间戳。

六. 总结

论文是了解一个产品或一项技术最有效最快速的方式，阅读完论文并整理总结后自己对 TiDB 整体的理解豁然开朗，为后续进一步学习 TiDB 奠定了一个良好的基础。当然，论文只是一个概要的介绍，TiDB 的技术细节需要花更多的时间去一一掌握。好在 TiDB 的官方文档非常丰富全面，只要愿意花时间去学习，相信自己不久后也能成为一位 TiDB 的数据库专家！