摘要

混合事务和分析处理（HTAP）数据库处理事务查询和分析查询时需要隔离，以消除它们之间的干扰。要实现这一点，需要维护这两种查询指定的不同数据副本。然而，为存储系统内的分布式副本提供一致的视图是具有挑战性的，其中分析请求可以高效地从大规模的事务性工作负载中读取一致和新的数据，并具有高可用性。

为了应对这一挑战，我们建议扩展基于复制状态机的共识算法，为HTAP工作负载提供一致的副本。基于这一新颖的思想，我们提出了一个基于Raft的HTAP数据库：TiDB。在数据库中，我们设计了一个由行存储和列存储组成的 Multi-Raft 存储系统。行存储是基于Raft算法构建的。它是可伸缩的，可以从具有高可用性的事务请求实现更新。特别是，它异步复制Raft日志到 learners，learners将元组的行格式转换为列格式，形成一个实时可更新的列存储。这个列存储允许分析查询高效地读取一致的新数据，与行存储上的事务有很强的隔离。基于这个存储系统，我们构建了一个SQL引擎来处理大规模分布式事务和昂贵的分析查询。SQL引擎可以最优地访问行格式和列格式的数据副本。我们还包括一个强大的分析引擎TiSpark，帮助TiDB连接到Hadoop生态系统。综合实验表明，TiDB在CH-benCHmark下实现了隔离的高性能，CH-benCHmark是一个专注于HTAP工作负载的基准。

1. 简介

关系型数据库管理系统（RDBMS）因其关系模型、强事务保证和SQL接口。它们在传统应用中被广泛采用，比如业务系统。然而，旧的RDBMS不能提供可伸缩性和高可用性。因此，在21世纪初，互联网应用更喜欢谷歌Bigtable和DynamoDB这样的NoSQL系统。NoSQL系统放松了一致性要求，并提供了高可伸缩性和替代数据模型，如键值对、图模型和文档模型。然而，许多应用程序也需要强大的事务、数据一致性和SQL接口，因此出现了NewSQL系统。像CockroachDB和谷歌Spanner这样的NewSQL系统为在线事务处理（OLTP）读写工作负载提供了NoSQL的高可伸缩性，同时仍然保证了事务的ACID。此外，基于SQL的联机分析处理（OLAP）系统正在快速发展中，比如许多SQL-on-hadoop系统。

这些系统遵循"一刀两得"的范例，针对OLAP和OLTP的不同，而使用不同的数据模型和技术。然而，多系统的开发、部署和维护成本非常昂贵。此外，实时分析最新版本的数据也很有吸引力。这催生了工业和学术界的HTAP系统，即混合OLTP和OLAP。HTAP系统应该像NewSQL系统一样实现可伸缩性、高可用性和跨国一致性。此外，HTAP系统需要高效地读取最新的数据，以保证OLTP和OLAP请求的吞吐量和延迟，另外还有两个要求：新鲜度和隔离度。

新鲜度指的是分析查询如何处理最近的数据。实时分析最新数据具有很大的商业价值。但在一些HTAP解决方案中并不能保证，比如那些基于Extraction-Transformation-Loading（ETL）处理的解决方案。通过ETL过程，OLTP系统定期将一批最新的数据刷新到OLAP系统。ETL需要数小时或数天的时间，因此无法提供实时分析。ETL阶段可以通过流传输的方法将最新的更新同步到OLAP系统，以减少同步时间。然而，由于这两种方法缺乏全局数据治理模型，考虑一致性语义就更加复杂。与多个系统的接口进行传输会引入额外的开销。

隔离度指的是保证单独的OLTP和OLAP查询的隔离性能。一些内存中的数据库（如HyPer）使分析查询能够从同一服务器上的事务处理中读取最新版本的数据。虽然这种方法提供了新的数据，但它无法同时实现OLTP和OLAP的高性能。这是由于数据同步带来的性能问题和工作负载之间的干扰。通过运行HyPer和SAP HANA上的HTAP基准CH-benCHmark，许多项目研究了这种影响。结果发现，当系统协同运行分析查询时，其可达到的最大OLTP吞吐量是减少是相当明显的。SAP HANA吞吐量至少降低了3倍，HyPer至少降低了5倍。类似的结果在MemSQL中也得到了证实。此外，内存中的数据库如果只部署在单个服务器上，则无法提供高可用性和可伸缩性。

为了保证隔离的性能，需要在不同的硬件资源上运行OLTP和OLAP请求。最根本的困难是在单个系统中维护来自OLTP工作负载的OLAP请求的最新副本。此外，系统需要在多个副本之间保持数据的一致性。注意，维护一致的副本对于可用性也是必需的。高可用性可以通过使用众所周知的共识算法来实现，如Paxos和Raft。它们基于复制状态机来同步副本。可以扩展这些共识算法，为HTAP工作负载提供一致的副本。据我们所知，这个想法之前还没有被研究过。

按照这个思路，我们提出了一个基于Raft的HTAP数据库：TiDB。它在Raft共识算法中引入了专用节点（称为 learner）。learner从 leader 节点异步复制事务日志，为OLAP查询构造新的副本。特别是，learner将日志中的行格式元组转换为列格式，以便副本更适合于分析查询。这样的日志复制对运行在leader节点上的事务性查询产生的开销很小。而且，这种复制的延迟非常短，可以保证OLAP的数据新鲜度。我们使用不同的数据副本来分别处理OLAP和OLTP请求，以避免它们之间的干扰。我们还可以基于行格式和列格式的数据副本来优化HTAP请求。基于Raft协议，TiDB提供了高可用性、可扩展性和数据一致性。

TiDB提出了一种创新的解决方案，帮助基于共识算法的NewSQL系统进化为HTAP系统。新的SQL系统通过复制它们的数据库，如谷歌Spanner和CockroachDB，确保OLTP请求的高可用性，可伸缩性和数据持久性。它们通过来自共识算法的复制机制在数据副本之间同步数据。基于日志复制，NewSQL系统可以提供一个专用于OLAP请求的列式副本，这样它们就可以像TiDB一样独立地（隔离地）支持HTAP请求。贡献如下：

•提出建立一个基于共识算法的HTAP系统，并实现了一个基于Raft的HTAP数据库TiDB。它是一个开源项目，为HTAP工作负载提供高可用性、一致性、可扩展性、数据新鲜度和隔离性。

•在Raft算法中引入了learner角色，为实时OLAP查询生成一个列式存储。

•实现了一个多Raft存储系统，并优化其读写，使系统在扩展到更多节点时提供高性能。

•为大规模HTAP查询定制了一个SQL引擎。引擎可以最优地选择使用基于行式存储和列式存储。

•使用CH-benCHmark（一种HTAP基准）进行全面的实验来评估TiDB关于OLTP、OLAP和HTAP的性能。

本文的其余部分组织如下。在第2节描述了主要思想，基于Raft的HTAP，并在第3节说明了TiDB的架构。TiDB的多Raft存储和HTAP引擎将在第4节和第5节详细阐述。第6节介绍了实验评估。在第7节总结了相关工作。最后，在第8节总结了我们的论文。

2. 基于 Raft 的 HTAP

Raft和Paxos等共识算法是构建一致、可伸缩、高可用的分布式系统的基础。它们的优势在于，使用复制状态机在服务器之间实时可靠地复制数据。我们采用这个功能，将数据复制到不同的服务器，以适应不同的HTAP工作负载。通过这种方式，保证了OLTP和OLAP工作负载相互隔离，同时也保证了OLAP请求对数据有一个新鲜一致的视图。据我们所知，之前并没有使用这些共识算法来构建HTAP数据库的工作。

由于Raft算法被设计为易于理解和实现，所以我们将我们的Raft扩展的重点放在实现一个可用于生产的HTAP数据库上。如图1所示，在较高的层次上，我们的思想如下：数据使用行格式存储在多个Raft组中，以服务事务性查询。每个组由一个leader和followers组成。我们为每个组添加了一个learner角色，以异步复制来自leader的数据。这种方法开销低，并保持数据的一致性。复制给learner的数据被转换为基于列的格式。查询优化器被扩展为同时访问基于行和基于列的副本的物理计划。

在标准的Raft组中，每个follower都可以成为leader来服务读写请求。因此，简单地增加更多的follower，并不会隔离资源。而且，添加更多的follower会影响共识组的性能，因为leader在响应客户端之前必须等待更大的节点仲裁的响应。因此，我们在Raft共识算法中引入了一个learner角色。learner不参与leader选举，也不是日志复制的quorum的一部分。从leader到learner的日志复制是异步的;leader在响应客户端之前不需要等待成功。在read时间里，leader和learner之间的强一致性得到了加强。通过设计，leader和learner之间的日志复制滞后较低，这在评估部分得到了证明。

事务性查询需要高效的数据更新，而连接或聚合等分析性查询需要读取列的子集，但这些列需要读取大量行。基于行的格式可以利用索引来有效地服务于事务性查询。基于列的格式可以有效地利用数据压缩和向量化处理。因此，在复制到Raft learner时，数据从基于行的格式转换为基于列的格式。而且，learner可以部署在单独的物理资源中。因此，事务查询和分析查询在隔离的资源中处理。

系统设计还提供了新的优化机会。因为数据在基于行的格式和基于列的格式之间保持一致，我们的查询优化器可以生成访问其中一个或两个存储的物理计划。

我们提出了扩展Raft以满足HTAP数据库的新鲜度和隔离需求的想法。为了让HTAP数据库生产做好准备，我们克服了很多工程上的挑战，主要包括：

（1）如何构建一个可扩展的Raft存储系统来支持高并发读写?如果数据量超过了Raft算法管理的节点的可用空间，我们就需要一个分区策略来将数据分布到服务器上。此外，在基本的Raft过程中，请求是按顺序处理的，任何请求在响应客户端之前都必须经过Raft节点的quorum批准。这个过程涉及到网络和磁盘操作，因此耗时较长。这种开销使得leader成为处理请求的瓶颈，尤其是在大型数据集上。

（2）如何将日志同步到低延迟的learner中以保持数据的新鲜度?正在进行的事务可以生成一些非常大的日志。这些日志需要在learner中快速重放和具化，以便能够读取新鲜的数据。由于schema不匹配，将日志数据转换为列格式可能会遇到错误。这可能会延迟日志同步。

（3）如何在保证性能的前提下高效地处理事务性查询和分析性查询?大型事务性查询需要读写分布在多个服务器上的大量数据。分析性查询也会消耗大量资源，应该不会影响在线事务。为了减少执行开销，还需要在行格式存储和列格式存储上选择最优方案。

在下面的章节中，将详细阐述TiDB的设计和实现，以应对这些挑战。

3. TiDB 架构

在这一节中，我们描述TiDB的高级结构，如图2所示。TiDB支持MySQL协议，可以通过与MySQL兼容的客户端访问。它有三个核心组件：分布式存储层、Placement Driver（PD）和计算引擎层。

分布式存储层由行存储（TiKV）和列存储（TiFlash）组成。逻辑上，存储在TiKV中的数据是一个有序的键值映射。每个元组被映射成一个键值对。键由它的表ID和行ID组成，值是实际的行数据，其中表ID和行ID是唯一的整数，行ID将来自一个主键列。例如，一个四列的元组被编码为：

Key:{table{tableID}_record{rowID}}
Value:{col0, col1, col2, col3}

为了向外扩展，我们采用范围分区策略，将大的键值映射分割成许多连续的范围，每个范围称为一个region。为了获得高可用性，每个region都有多个副本。使用Raft共识算法来维护每个region的副本之间的一致性，形成一个Raft组。不同Raft组的leader将数据从TiKV异步复制到TiFlash。TiKV和TiFlash可以部署在单独的物理资源中，从而在处理事务性查询和分析性查询时提供隔离。

放置驱动程序（PD）负责管理区域，包括提供每个键的region和物理位置，并自动移动region以平衡工作负载。PD也是Timestamp oracle，提供严格递增且全局唯一的时间戳。这些时间戳也作为事务id。为了健壮性和性能，PD可以包含多个PD成员。PD没有持久的状态，启动时PD成员从其他成员和TiKV节点收集所有必要的数据。

计算引擎层是无状态的，并且是可扩展的。我们量身定制的SQL引擎有一个基于成本的查询优化器和一个分布式查询执行器。TiDB实现了基于Percolator的两阶段提交（2PC）协议，以支持分布式事务处理。查询优化器可以根据查询优化选择从TiKV和TiFlash读取数据。

TiDB的体系结构符合HTAP数据库的要求。TiDB的每个组件都被设计成具有高可用性和可扩展性。存储层使用Raft算法实现数据副本之间的一致性。TiKV和TiFlash之间的低延迟复制使得新鲜数据可用于分析查询。查询优化器，加上TiKV和TiFlash之间的强一致性数据，提供了快速的分析查询处理，对事务性处理影响很小。

除了上面提到的组件，TiDB还集成了Spark，这有助于将存储在TiDB中的数据与Hadoop分布式文件系统（HDFS）进行集成。TiDB拥有一套丰富的生态系统工具，可以将数据导入到TiDB中、从TiDB中导出数据、将其他数据库中的数据迁移到TiDB中。

在接下来的章节中，我们将对分布式存储层、SQL引擎和TiSpark做一个深入的探讨，来展示TiDB这一可用于生产的HTAP数据库的能力。

4. Multi-Raft 存储

图3展示了TiDB中分布式存储层的架构，相同形状的对象扮演着相同的角色。存储层由一个基于行的存储TiKV和一个基于列的存储TiFlash组成。存储层将一个大的表映射成一个大的键值映射，这个键值映射被分割成许多region存储在TiKV中。每个region使用Raft共识算法来保持副本之间的一致性，以实现高可用性。当数据复制到TiFlash时，多个region可以合并成一个分区，方便表扫描。TiKV和TiFlash之间的数据通过异步日志复制保持一致。多个Raft组在分布式存储层管理数据，称之为Multi-Raft存储。在接下来的章节中，我们将对TiKV和TiFlash进行详细的描述，重点介绍如何进行优化，使TiDB成为一个可用于生产的HTAP数据库。

4.1 行存储（TiKV）

一个TiKV部署由许多TiKV服务器组成。使用Raft在TiKV服务器之间复制区域。每个TiKV服务器既可以是Raft的leader，也可以是不同region的follower。在每个TiKV服务器上，数据和元数据被持久化到RocksDB，一个可嵌入的、持久化的、键值存储。每个region都有一个可配置的最大大小，默认为96 MB。Raft leader的TiKV服务器处理相应region的读/写请求。

当Raft算法响应读写请求时，基本的Raft进程在leader和follower之间执行：

(1) region leader接收来自SQL引擎层的请求。

(2) leader将请求追加到自己的日志中。

(3) leader将新的日志条目发送给follower, follower又将这些条目追加到自己的日志中。

(4) leader等待follower的响应。如果quorum节点响应成功，那么leader提交请求并在本地应用。

(5) leader将结果发送给客户端，继续处理传入的请求。

这个过程保证了数据的一致性和高可用性。然而，它不能提供高效的性能，因为步骤是顺序发生的，并且可能会有较大的I/O开销（磁盘和网络）。下面几节将描述我们如何优化这个过程以实现高读/写吞吐量，即解决第2节中描述的第一个挑战。

4.1.1 leader和follower之间的优化

在上面描述的过程中，第二步和第三步可以并行发生，因为它们之间没有依赖关系。因此，leader会在本地追加日志，并同时向follower发送日志。如果leader追加日志失败，但follower的quorum组追加成功，则仍然可以提交日志。在第三步中，当向follower发送日志时，leader缓冲日志条目，并将其批量发送给follower。发送日志后，leader不必等待follower的响应。相反，它可以假设成功，并使用预测的日志索引发送进一步的日志。如果发生错误，leader调整日志索引并重新发送复制请求。在第四步中，应用已提交日志条目的leader可以由另一个线程异步处理，因为在这个阶段没有一致性的风险。基于上面的优化，Raft流程更新如下：

(1) leader接收来自SQL引擎层的请求。

(2) leader向follower发送相应的日志，并在本地并行追加日志。

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

(4) leader提交日志，并将日志发送给另一个线程应用。

(5) leader应用日志后，将结果返回给客户端。

在这个最优化过程中，来自客户端的任何请求仍然运行所有Raft步骤，但来自多个客户端的请求是并行运行的，因此整体吞吐量增加。

4.1.2 加速来自客户端的读请求

从TiKV leader读取数据提供了线性化的语义。这意味着当在时间t从region leader读取一个值时，leader一定不能返回t时刻之后版本的值。这可以通过使用上面描述的Raft来实现：为每个读请求发出一个日志条目，并在返回之前是等待该条目被提交。但是，这个过程代价很高，因为日志必须在Raft组中的大多数节点上复制，这会导致网络I/O开销。为了提高性能，我们可以避免日志同步阶段。

Raft保证，一旦leader成功写数据，leader可以响应任何读请求，而无需跨服务器同步日志。但是，leader选举之后，leader角色可能会在Raft组的服务器之间移动。为了实现leader的读取，TiKV实现了Raft论文中描述的读取优化。

第一种方法称为读索引。leader响应读请求时，会将当前提交索引记录为本地读索引，然后向follower发送心跳消息，确认自己的leader角色。如果确实是leader，一旦应用索引大于或等于读索引，它就可以返回该值。这种方法提高了读性能，尽管它会导致一些网络开销。

另一种方法是租约读，它减少了由读索引引起的心跳的网络开销。leader和follower商定一个租期，在租期内follower不会发出选举请求，这样leader就不会被改变。在租期内，leader可以响应任何读请求，而不需要连接follower。如果每个节点的CPU时钟相差不大，这种方法就能很好地工作。

除了leader, follower还可以响应来自客户端的读请求，这叫做follower read。follower收到读请求后，会向leader请求最新的读索引。如果本地应用的索引等于或大于读索引，follower可以将值返回给客户端;否则，就必须等待日志被应用。follower读取可以缓解热点区域leader的压力，从而提高读取性能。然后可以通过增加更多的follower来进一步提高读性能。

4.1.3 管理海量 Regions

海量 regions 分布在一个服务器集群上。服务器和数据大小是动态变化的，region可能在一些服务器上聚集，尤其是leader副本。这导致一些服务器的磁盘被过度使用，而另一些服务器的磁盘则是空闲的。此外，服务器可能会被添加到集群中或从集群中移出。

为了在服务器间平衡 region, PD 对region进行调度，并限制副本的数量和位置。一个关键的约束是在不同的TiKV实例上放置一个region的三个副本（至少），以确保高可用性。PD是通过心跳从服务器收集特定信息来初始化的。它还监控每个服务器的工作负载，并在不影响应用程序的情况下将热点区域迁移到不同的服务器上。

另一方面，维护大量的region需要发送心跳和管理元数据，这会造成大量的网络和存储开销。但是，如果一个Raft组没有任何工作负载，那么心跳是不必要的。根据regions的工作负载的繁忙程度，我们可以调整发送心跳的频率。这减少了出现网络延迟或节点过载等问题的可能性。

4.1.4 动态区域拆分和合并

一个较大的region可能会在合理的时间内变得太热而无法读写。为了更好地分配工作负载，应该将热的或大的region拆分为较小的region。另一方面，也有可能很多region很小，很少被访问;但是，系统仍然需要维护心跳和元数据。在某些情况下，维护这些小的region会导致大量的网络和CPU开销。因此，合并较小的region是必要的。注意，为了保持region之间的顺序，我们只合并键空间中相邻的region。PD根据观察到的工作负载，动态地向TiKV发送拆分和合并命令。

split操作将一个region划分为几个新的、更小的region，每个region覆盖原始region中连续的键范围。覆盖最右边范围的region重用原始region的Raft组。其他区域则使用新的Raft组。拆分过程类似于Raft过程中的普通更新请求：

(1) PD向一个region的leader发出分裂命令。

(2) leader收到分裂命令后，将命令转换成日志，并将日志复制到所有follower节点。日志中只包含一条分裂命令，而不是修改实际数据。

(3) 一旦仲裁复制了日志，leader就会提交分裂命令，该命令会应用到Raft组中的所有节点。应用过程涉及到更新原始region的范围和epoch元数据，并创建新的region来覆盖剩余的范围。请注意，该命令是原子应用的，并同步到磁盘。

(4) 对于split region的每个副本，都会创建一个Raft状态机并开始工作，形成一个新的Raft组。原始region的leader将分裂结果报告给PD。分裂过程完成。

注意，当大多数节点提交分裂日志时，分裂进程会成功。类似于提交其他Raft日志，而不是要求所有节点完成region的拆分。分裂后，如果对网络进行分区，则 epoch 最近的节点组获胜。区域分割的开销很低，因为只需要更改元数据。在一个分割命令完成后，由于PD的常规负载平衡，新分割的region可能会被跨服务器移动。

合并两个相邻的region与分裂一个region是相反的。PD移动两个region的副本，将它们放在单独的服务器上。然后，两个region的并置副本通过两阶段操作在每个服务器上本地合并;即停止一个region的服务，并将其与另一个region合并。这种方法不同于拆分region，因为它不能使用两个Raft组之间的日志复制过程来同意合并它们。

4.2 列存储（TiFlash）

尽管我们如上所述优化了TiKV的读取数据，但TiKV中的行式数据并不适合快速分析。因此，我们将列存储（TiFlash）合并到TiDB中。TiFlash由learner节点组成，它只接收Raft组的Raft日志，并将行格式的元组转换为列式数据。它们不参与Raft协议提交日志或选举leader，所以它们在TiKV上诱导的开销很小。用户可以使用SQL语句为表设置列格式的副本：

ALTER TABLE x SET TiFLASH REPLICA n;

其中x为表名，n为副本数。默认值为1。添加列副本类似于向表添加异步列索引。TiFlash中的每个表都被划分为许多分区，每个分区都覆盖了一个连续的元组范围，按照来自TiKV的几个连续的region。较大的分区便于范围扫描。

当初始化一个TiFlash实例时，相关区域的Raft leader开始将他们的数据复制给新的learner。如果需要快速同步的数据太多，leader就会发送自己数据的快照。一旦初始化完成，TiFlash实例就开始监听来自Raft组的更新。在learner节点接收到日志包后，它将日志应用到本地状态机，包括重放日志、转换数据格式、更新本地存储中引用的值。

在接下来的章节中，我们将说明TiFlash如何高效地应用日志，并与TiKV保持一致的视图。这就满足了我们在第2节中描述的第二个挑战。

4.2.1 日志重放

根据Raft算法，learner节点接收到的日志可线性化。为了保持提交数据的线性化语义，它们按照先进先出（FIFO）策略被重放。日志重放有三个步骤：

(1) 压缩日志：根据后面5.1节中描述的事务模型，事务性日志被分为三种状态：预写、提交或回滚。回滚日志中的数据不需要写入磁盘，因此压缩过程根据回滚日志删除无效的预写日志，并将有效的日志放入缓冲区。

(2) 解码元组：将缓冲区中的日志解码为行格式的元组，去除冗余的事务信息。然后，解码后的元组被放入行格式的缓冲区中。

(3) 转换数据格式：如果行缓冲区中的数据大小超过大小限制或其持续时间超过时间间隔限制，这些行格式元组被转换为列格式数据，并写入本地分区数据池。转换指的是本地缓存的schema，这些schema会定期与TiKV同步，后面会有描述。

为了说明日志回放过程的细节，考虑下面的例子。我们将每个Raft日志条目抽象为事务ID-operation类型[transac status][@start_ts][#commit ts]操作数据。根据典型的DMLs，操作类型包括插入、更新和删除元组。事务状态可以是预写、提交或回滚。操作数据可以是特定插入或更新的元组，也可以是删除的键。

在表1所示的示例中，原始日志包含8个条目，它们试图插入两个元组，更新一个元组，以及删除一个元组。但是插入k1是回滚的，所以8个原始日志项中只有6个被保留，其中3个元组被解码。最后，这三个解码后的元组被转换成五列：操作类型、提交时间戳、键和两列数据。这些列被追加到Delta Tree中。

4.2.2 Schema 同步

为了将元组实时转换为列格式，learner节点必须知道最新的schema。这样的schema处理不同于TiKV上的无schema操作，后者将元组编码为字节数组。最新的schema信息存储在TiKV中。为了减少TiFlash向TiKV请求最新schema的次数，每个learner节点都维护一个schema缓存。

缓存通过schema同步器与TiKV的schema同步。如果缓存的schema过期了，被解码的数据和本地schema就会不匹配，数据必须重新转换。在schema同步的频率和schema不匹配的次数之间有一个权衡。我们采取两阶段策略：

•定期同步：schema同步器定期从TiKV获取最新的schema，并将更改应用到其本地缓存中。在大多数情况下，这种随机同步降低了schema同步的频率。

•强制同步：如果schema同步器检测到不匹配的schema，它会主动从TiKV获取最新的schema。当元组和schema之间的列号不同或列值溢出时，会触发此操作。

4.2.3 列式的 Delta Tree

为了高效地读写具有高吞吐量的列式数据，我们设计了一个新的列式存储引擎Delta Tree，它会立即追加delta更新，然后将它们与每个分区之前稳定的版本合并。delta更新和稳定数据分别存储在Delta Tree中，如图4所示。在稳定空间中，分区数据以块的形式存储，每个块覆盖的分区元组范围更小。而且，这些行格式的元组是逐列存储的。相比之下，增量是按TiKV生成的顺序直接添加到增量空间的。TiFlash中列式数据的存储格式类似于parquet。它还将行组存储到列式块中。不同的是，TiFlash将行组的列数据及其元数据存储到不同的文件中，以并发更新文件，而不是在parquet中只有一个文件。TiFlash只是使用常见的LZ4压缩来压缩数据文件，以节省它们的磁盘大小。

新的传入增量是插入数据的原子批处理或删除的 range。这些增量缓存在内存中，并持久化到磁盘中。它们是按顺序存储的，因此它们实现了预写日志（WAL）的功能。这些增量通常存储在许多小文件中，因此在读取时引起较大的IO开销。为了降低成本，我们定期将这些小增量压缩成一个大增量，然后将较大的增量刷新到磁盘上，并替换之前具体化的小增量。传入的增量的内存副本方便读取最新的数据，如果旧的增量达到有限的大小，它们就会被删除。

当读取某些特定元组的最新数据时，有必要将所有的增量文件与其稳定的元组合并合并（即读取放大），因为相关的增量分布在哪里是事先不知道的。由于需要读取大量文件，这样的过程成本很高。此外，许多增量文件可能包含无用的数据（即空间放大），浪费存储空间，并降低了用稳定元组合并它们的速度。因此，我们周期性地将delta合并到稳定空间中。每个增量文件及其相关块被读入内存并合并。delta中插入的元组被添加到稳定的元组中，修改的元组替换原来的元组，删除的元组被移动。合并后的块会原子地替换磁盘中的原始块。

合并delta代价很高，因为相关键在delta空间中是无序的。这种无序也会减慢delta与稳定块的集成速度，从而减慢了读请求返回最新的数据的速度。因此，我们在delta空间的顶部构建了一个B+树索引。每个增量更新项都按键和时间戳顺序插入到B+树中。这种顺序优先级有助于高效地定位一系列键的更新，或者在响应读请求时在增量空间中查找单个键。此外，B+树中的有序数据很容易与稳定块合并。

我们进行了一个微观实验，将Delta Tree的性能与TiFlash中的日志结构合并（LSM）树进行比较，在TiFlash中，根据Raft日志更新数据时读取数据。我们设置了3个TiKV节点和1个TiFlash节点，硬件配置在实验部分列出。我们在TiKV上运行Sysbench唯一的写工作负载，并在TiFlash上运行"select count(id), count(k) from sbtest1"。为了避免数据压缩的大的数据写入放大问题，我们使用通用的压缩，而不是级别风格的压缩，来实现LSM存储引擎。在面向列的OLAP数据库ClickHouse中也采用了这种实现。

如表2所示，无论有1亿元组还是2亿元组，以及事务性工作负载，从Delta Tree读取数据的速度大约是LSM树的两倍。这是因为在增量树中，每次读取最多访问在B+树中索引的一级增量文件，而访问LSM树中更多的重叠文件。在不同的写工作负载下，性能几乎保持稳定，因为增量文件的比例几乎相同。虽然Delta Tree(16.11)的写放大比LSM Tree(4.74)大，但也可以接受。

和follower读取一样，learner节点提供快照隔离，因此我们可以从TiFlash中读取特定时间戳的数据。在接收到一个读请求后，learner节点会向leader发送一个读索引请求，以获取覆盖所请求的时间戳的最新数据。作为回应，leader将引用的日志发送给learner，learner回放并存储这些日志。一旦将日志写入到Delta Tree中，就读取来自Delta Tree的特定数据，以响应读取请求。

5. HTAP 引擎

解决第二节提到的第三个挑战，即处理大规模事务和分析查询，我们提供一个SQL引擎来评估事务和分析查询。SQL引擎采用Percolator模型，在分布式集群中实现乐观锁定和悲观锁定。SQL引擎通过使用基于规则和成本的（rule- and cost-based）优化器、索引和将计算下推到存储层来加速分析查询。我们还实现了TiSpark来连接Hadoop生态系统并增强OLAP能力。HTAP请求可以在独立的存储和引擎服务器中单独处理。特别是，SQL引擎和TiSpark受益于同时使用行存储和列存储，以获得最佳结果。

5.1 事务处理

TiDB为ACID事务提供了快照隔离（SI）或可重复读取（RR）语义。SI允许事务内的每个请求读取数据的一致版本。RR意味着一个事务中的不同语句可能会为同一个键读取不同的值，但重复一次读取（即两次读取具有相同的时间戳）将总是读取相同的值。我们的实现基于多版本并发控制（MVCC），避免了读写锁定和防止写写冲突。

在TiDB中，事务在SQL引擎、TiKV和PD之间是协作的。事务过程中各个组件的职责如下：

•SQL引擎：协调事务。它接收来自客户端的读写请求，将数据转换为键值格式，并使用两阶段提交（2PC）将事务写入TiKV。

•PD：管理逻辑区域和物理位置;提供全局的、严格递增的时间戳。

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

TiDB实现了乐观锁定和悲观锁定。它们改编自Percolator模型，该模型选择一个键作为主键，并使用它来代表事务的状态，并基于2PC来执行事务。图5左侧展示了一个乐观事务的过程。（为简单起见，图中忽略了异常处理。）

(1) 在从客户端接收到"begin"命令后，SQL引擎向PD请求一个时间戳，作为事务的开始时间戳（start ts）。

(2) SQL引擎通过从TiKV读取数据并写入本地内存来执行SQL DML。TiKV在事务操作开始ts之前提供最新提交时间戳（commit）的数据。

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

(4) 如果所有的预写都成功，SQL引擎向PD请求事务提交的时间戳，并向TiKV发送一个提交命令。TiKV提交主键，并向SQL引擎返回一个成功响应。

(5) SQL引擎向客户端返回成功响应。

(6) SQL引擎通过向TiKV发送进一步的提交命令来提交二级键并异步并行地清除锁。

乐观事务和悲观事务的主要区别在于获取锁的时间。在乐观事务中，锁是在预写阶段（上面的步骤3）逐步获得的。在悲观事务中，锁是在预写之前（步骤2的一部分）执行DML时获得的，这意味着一旦预写启动，事务就不会因为与另一个事务冲突而失败。（它仍然可能因为网络分区或其他问题而失败）

当给悲观事务中的键上锁时，SQL引擎会获得一个新的时间戳，称为for_update_ts。如果SQL引擎无法获得锁，它可以从该锁开始重试事务，而不是回滚并重新尝试整个事务。当读取数据时，TiKV使用for_update_ts而不是start_ts来决定一个键的哪些值可以被读取。通过这种方式，悲观事务保持RR隔离级别，即使有事务的部分重试。

对于悲观事务，用户还可以选择只要求读已提交（RC）隔离级别。这将减少事务之间的冲突，从而获得更好的性能，但代价是减少了隔离的事务。实现上的不同之处在于，对于RR TiKV，如果一个读尝试访问被另一个事务锁定的 key，则必须报告一个冲突;对于RC，读取时可以忽略锁。

TiDB实现了分布式事务，没有集中的锁管理器。锁存储在TiKV中，提供了高可伸缩性和可用性。此外，SQL引擎和PD服务器是可伸缩的，可以处理OLTP请求。跨服务器同时运行多个事务，实现了高度的并行性。

时间戳是从PD请求的。每个时间戳包括物理时间和逻辑时间。物理时间指的是精度为毫秒的当前时间，逻辑时间为18位。因此，理论上PD每毫秒可以分配2^18 时间戳。在实践中，由于分配时间戳只需要几个周期，它可以每秒生成约100万个时间戳。客户端每批请求一次时间戳，以摊销开销，尤其是网络延迟。目前，在我们的实验和许多生产环境中，获取时间戳并不是一个性能瓶颈。

5.2 分析处理

在本节中，我们描述了针对OLAP查询的优化，包括优化器、索引和定制的SQL引擎和TiSpark中的下推计算。

5.2.1 SQL引擎中的查询优化

TiDB通过两个查询优化阶段实现查询优化：基于规则的查询优化（rule-based optimization，RBO）产生逻辑计划，然后基于成本的优化（cost-based optimization，CBO）将逻辑计划转换为物理计划。我们的RBO有一套丰富的转换规则，包括裁剪不需要的列、消除projection、下推predicates、导出predicates、常量floding、消除"group by"或外连接、取消子查询嵌套。我们的CBO会根据执行成本从候选计划中选择最优的计划。注意，TiDB提供了TiKV和TiFlash两种数据存储，因此扫描表通常有三种选择：扫描TiKV中的行格式表，扫描TiKV中带索引的表，扫描TiFlash中的列。

索引对于提高数据库中的查询性能非常重要，数据库通常用于点查或范围查询，为哈希连接和合并连接提供了更优的数据扫描路径。TiDB实现了可伸缩的索引，可以在分布式环境中工作。因为维护索引会消耗大量资源，并且可能会影响在线事务和分析，所以我们在后台异步地构建或删除索引。索引按照与数据相同的方式划分区域，并作为键值存储在TiKV中。

唯一键索引上的索引项编码为：

Key:{table{tableID}_index{indexID}_indexedColValue} Value:{rowID}

非唯一索引上的索引项被解码为：

Key:{table{tableID}_index{indexID}_indexedColValue_rowID} Value:{null}

使用索引需要二分查找来定位包含索引相关部分的region。为了增加索引选择的稳定性并减少物理优化的开销，我们使用了skyline修剪算法来消除无用的候选索引。如果有多个候选索引匹配不同的查询条件，我们合并部分结果（一组符合条件的行id）以获得一个精确的结果集。

物理计划（CBO的结果）由SQL引擎层使用拉取迭代器模型（pulling iterator model）来执行。通过下推一些计算到存储层，可以进一步优化执行。在存储层中，执行计算的组件被称为coprocessor。coprocessor在不同的服务器上并行执行一个执行计划的子树。这减少了必须从存储层发送到引擎层的元组的数量。例如，通过对coprocessor中的过滤器进行评估，被拒绝的元组在存储层被过滤掉，只有被接受的元组才需要发送到引擎层。coprocessor可以对逻辑运算、算术运算以及其他常用函数进行求值。在某些情况下，它可以执行聚合和TopN。coprocessor可以通过向量化操作进一步提高性能：不再对整个行进行迭代，而是对行进行批处理，并按列组织数据，从而实现更高效的迭代。

5.2.2 TiSpark

为了帮助TiDB连接到Hadoop生态系统，TiDB在Multi-Raft存储上添加了TiSpark。除了SQL, TiSpark还支持机器学习库等强大的计算能力，可以处理TiDB之外的数据。

图6展示了TiSpark如何与TiDB集成。在TiSpark中，Spark驱动程序从TiKV读取元数据，构建Spark目录，包括表的schema和索引信息。Spark驱动向PD请求时间戳，从TiKV读取MVCC数据，以确保获取到数据库的一致的快照。和SQL引擎一样，Spark Driver可以将计算下推到存储层的coprocessor上，并使用可用的索引。这是通过修改Spark优化器生成的计划来实现的。我们还定制了一些读取操作，从TiKV和TiFlash中读取数据，并为Spark workers组装成行。比如，TiSpark可以同时从多个TiDB region读取数据，并且可以并行地从存储层获取索引数据。为了减少对特定版本Spark的依赖，这些函数大多在附加包中实现。

TiSpark与普通连接器的区别在于两个方面。它不仅可以同时读取多个数据 Regions，还可以从存储层并行获取索引数据。读取索引可以方便Spark中的优化器选择最优方案，降低执行成本。另一方面，TiSpark会修改计划由Spark中的原始优化器生成，将部分执行下推到存储层的coprocessor，这进一步降低了执行开销。除了从存储层读取数据，TiSpark还支持用事务在存储层加载大数据。为了实现这一点，TiSpark采用了两阶段提交和锁表。

5.3 隔离和协调

资源隔离是保证事务查询性能的有效方法。分析性查询经常消耗大量资源，如CPU、内存和I/O带宽。如果这些查询与事务查询一起运行，后者可能会严重延迟。这一普遍原则已经在BatchDB的工作中得到验证。为了在TiDB中避免这个问题，我们在不同的引擎服务器上调度分析查询和事务查询，并在单独的服务器上部署TiKV和TiFlash。事务查询主要访问TiKV，而分析性查询主要访问TiFlash。通过Raft维护TiKV和TiFlash之间的数据一致性的开销很低，所以用TiFlash运行分析查询对事务性处理的性能影响很小。

TiKV和TiFlash之间的数据是一致的，因此查询可以通过从TiKV或TiFlash读取来提供服务。因此，我们的查询优化器可以从更大的物理计划空间中进行选择，而最优计划可能同时从TiKV和TiFlash中读取。当TiKV访问一个表时，它提供行扫描和索引扫描，而TiFlash支持列扫描。

这三种访问路径在执行成本和数据顺序属性上各不相同。行扫描和列扫描按主键提供顺序;索引扫描提供来自键编码的几种排序。不同路径的代价取决于tuple/column/index的平均大小（Stuple/col/index）和tuples/Regions的估计数量（Ntuple/reg）。我们将数据扫描的I/O开销表示为fscan，文件查找开销为fseek。查询优化器根据式(1)选择最优访问路径，如式(2)所示，行扫描的代价来自于扫描连续的行数据和查找region文件。列扫描（式(3)）的代价是扫描m列的总和。如果被索引的列不满足表扫描所需的列，索引扫描（式(4)）应该考虑扫描索引文件的成本和扫描数据文件的成本（如双读）。注意，double read通常随机扫描元组，这涉及到在式(5)中寻找更多的文件。

例如，当查询优化器将选择行格式和列格式存储来访问同一查询中的不同表时，考虑"select T.*, S.a from T join S T.b=S.b where T.a between 1 and 100"。这是一个典型的连接查询，其中T和S在行存储的a列上有索引，以及列副本。使用索引从行存储中访问T，从列存储中访问S是最优的。这是因为查询需要一组来自T的完整元组，通过索引访问元组的数据比列存储的成本低。另一方面，在使用列存储时，获取S的两个完整列的成本更低。

TiKV和TiFlash的协同仍然可以保证独立的性能。对于分析查询，只有小范围扫描或点查扫描才能通过跟 follower read访问TiKV，对leader的影响不大。我们还将分析查询在TiKV上的默认访问表大小限制为最多500 MB，事务查询可能会访问TiFlash中的列数据，以检查一些约束，比如唯一性。我们为特定的表设置了多个列式副本，其中一个表副本专门用于事务查询。在单独的服务器上处理事务查询可以避免影响分析查询。

6. 实验

在本节中，我们首先分别评估TiDB的OLTP和OLAP能力。对于OLAP，我们考察SQL引擎选择TiKV和TiFlash的能力，并将TiSpark与其他OLAP系统进行比较。然后，我们测量TiDB的HTAP性能，包括TiKV和TiFlash之间的日志复制延迟。最后，我们将TiDB与MemSQL在隔离方面进行了比较。

6.1 实验装置

集群。我们在由6台服务器组成的集群上进行全面的实验;每个服务器有 188GB 内存和两个Intel R Xeon R CPU E5-2630 v4处理器，即 2个NUMA节点。每个处理器有10个物理核（20个线程）和一个25 MB的共享L3缓存。这些服务器运行Centos 7.6.1810版本，并通过10 Gbps以太网连接。

工作负载。我们的实验是在混合OLTP和OLAP工作负载下使用CH-benCHmark进行的。基准测试由标准OLTP和OLAP基准测试组成：TPC-C和TPC-H。它是由未修改的TPC-C基准构建而成的。OLAP部分包含了受TPC-H启发的22个分析查询，其schema由TPC-H改编为CH-benCHmark schema，再加上3个缺失的TPC-H关系。在运行时，这两个工作负载由多个客户端同时发布;在实验中，客户端的数量是不同的。吞吐量分别以每秒查询数（QPS）或每秒事务数（TPS）来衡量。CH-benCHmark中的数据单位称为仓库（warehouse），TPC-C也是如此。100个仓库大约需要 70GB 的内存。

6.2 OLTP性能

我们在CH- benCHmark的OLTP部分下使用乐观锁定或悲观锁定来评估TiDB的独立OLTP性能;即TPC-C基准。我们比较TiDB的对另一个分布式NewSQL数据库CockroachDB （CRDB）的性能。CRDB部署在6个同构服务器上。对于TiDB, SQL引擎和TiKV部署在6台服务器上，它们的实例分别绑定到每台服务器上的两个NUMA节点上。PD则部署在6台服务器中的3台上。为了平衡请求，TiDB和CRDB都是通过HAProxy负载均衡器访问的。我们使用不同数量的客户端来测量50,100和200个仓库的吞吐量和平均延迟。

图7(b)和图7(c)中的吞吐量图与图7(a)不同。在图7(a)中，对于小于256个客户机，无论是乐观锁定还是悲观锁定，TiDB的吞吐量都随着客户机数量的增加而增加。对于256个以上的客户端，乐观锁定的吞吐量保持稳定，然后开始下降，而悲观锁定的吞吐量在512个客户端时达到最大，然后下降。图7(b)和图7(c)中TiDB的吞吐量一直在增加。这个结果是可以预期的，因为在高并发和小数据量的情况下，资源争用最严重。

一般来说，乐观锁定的性能比悲观锁定好，除了较小的数据大小和高并发（1024个客户端在50或100个仓库上），在这些情况下，资源争用严重，并导致许多乐观事务被重试。由于200个仓库的资源争用较轻，乐观锁定仍然能产生更好的性能。

在大多数情况下，TiDB的吞吐量比CRDB高，尤其是在大型仓库上使用乐观锁定时。即使采用悲观锁定进行公平比较（CRDB总是使用悲观锁定），TiDB的性能仍然更高。我们认为TiBD的性能优势源于对事务处理和Raft算法的优化。

图7(d)显示，更多的客户端会导致更多的延迟，尤其是在达到最大吞吐量后，因为更多的请求必须等待更长的时间。这也解释了仓库越少，延迟越高的原因。对于某些客户端，更高的吞吐量导致TiDB和CRDB的延迟更少。对于50个和100个仓库也存在类似的结果。

我们评估了从PD请求时间戳的性能，因为这可能是一个潜在的瓶颈。我们使用1200个客户端来连续请求时间戳。客户端位于集群中不同的服务器上。模拟TiDB，每个客户端批量向PD发送时间戳请求。如表3所示，6台服务器每台每秒可以接收602594个时间戳，这是运行TPC-C基准时所需速率的100多倍。在运行TPC-C时，TiDB每台服务器每秒最多请求6000个时间戳。当增加服务器数量时，每台服务器上接收到的时间戳数量会减少，但时间戳总数几乎相同。这利率大大超过了现实生活中的任何需求。关于延迟，只有一小部分请求花费1 ms或2 ms。我们得出的结论是，从PD获取时间戳目前在TiDB中不是一个性能瓶颈。

6.3 OLAP 性能

我们从两个角度评估TiDB的OLAP性能。首先，我们评估SQL引擎在CH-benCHmark拥有100个仓库的OLAP部分下最优选择行存储或列存储的能力。我们设置了三种类型的存储：仅TiKV存储、仅TiFlash存储、以及TiKV和TiFlash两种存储。我们将每个查询运行5次，并计算平均执行时间。如图8所示，只从一种存储中获取数据，两种存储都不优越。同时从TiKV和TiFlash请求数据，性能总是更好。

Q8、Q12和Q22会产生有趣的结果。在Q8和Q12中，只使用TiKV的case比只使用TiFlash的case花费的时间更少，但在Q22中却花费了更多的时间。TiKV和TiFlash的case性能要优于仅TiKV和仅TiFlash的case。

Q12主要包含两表连接，但在每种存储类型中采用不同的物理实现。在只使用TiKV的情况下，它使用索引连接，从表ORDER LINE中扫描几个合格的元组，并使用索引查找表OORDER。在TiFlash-only的情况下，索引读取器的成本要低得多，比使用哈希连接要好，后者扫描两个表中所需的列。当同时使用TiKV和TiFlash时，成本进一步降低，因为它使用了从TiFlash中扫描ORDER LINE的更快的索引连接，并使用TiKV中的索引查找OORDER。在TiKV和TiFlash的情况下，读取列存储将只使用TiKV的情况的执行时间缩短了一半。

在Q22中，它的exists()子查询被转换为反半连接。它在只使用TiKV的情况下使用索引连接，在只使用TiFlash的情况下使用哈希连接。但与Q12中的执行不同的是，使用索引连接比哈希连接的开销更大。当从TiFlash中获取内部表，并使用TiKV中的索引查找外部表时，索引连接的成本会降低。因此，TiKV和TiFlash的情况再次花费最少的时间。

Q8则更为复杂。它包含一个包含9个表的连接。在只使用TiKV的情况下，它接受两个索引合并连接和六个散列连接，并使用索引查找两个表（CUSTOMER和OORDER）。这个计划耗时1.13秒，优于TiFlash-only情况下的8个哈希连接，后者耗时1.64秒。它的开销在TiKV和TiFlash的情况下进一步降低，在TiKV和TiFlash的情况下，除了在6个哈希连接中扫描来自TiFlash的数据外，物理计划几乎没有什么变化。这一改进将执行时间减少到0.55秒。在这三个查询中，只使用TiKV或TiFlash可以获得不同的性能，并将它们结合起来获得最佳结果。

对于Q1、Q4、Q6、Q11、Q13、Q14和Q19，只使用TiFlash的情况比只使用TiKV的情况性能更好，而TiKV和TiFlash的情况得到的性能与只使用TiFlash的情况相同。这7个查询的子节点是不同的。Q1和Q6主要由单个表上的聚合组成，因此在TiFlash中的列存储上运行时间更少，是最优选择。这些结果突出了之前工作中描述的列式存储的优势。Q4和Q11在每个案例中分别使用相同的物理计划执行。但是从TiFlash中扫描数据比TiKV开销更少，所以在TiFlash-only的情况下执行时间更少，也是一种最优选择。Q13、Q14和Q19都包含一个两表连接，以散列连接的形式实现。虽然只有TiKV的情况在探测哈希表时采用了索引读取器，但也比从TiFlash中扫描数据开销更高。

Q9是多连接查询。在只使用TiKV的情况下，它使用索引在一些表上进行索引合并连接。它比在TiFlash上进行哈希连接的开销更低，因此它成为了最优选择。Q7、Q20和Q21产生类似的结果，但由于空间有限，它们被省略了。22个TPC-H查询中的其余8个查询在3个存储设置中具有类似的性能。

此外，我们使用CH-benCHmark的22个分析查询和500个仓库将TiSpark与SparkSQL、PrestoDB和Greenplum进行比较。每个数据库安装在6台服务器上。对于SparkSQL和PrestoDB，数据以列式parquet文件的形式存储在Hive中。图9比较了这些系统的性能。TiSpark的性能可以与SparkSQL相媲美，因为它们使用的是相同的引擎。性能差距相当小，主要来自于访问不同的存储系统：扫描压缩的parquet文件更优，所以SparkSQL通常会outper- forms TiSpark。然而，在某些情况下，这种优势被抵消了，因为TiSpark可以将更多的计算推到存储层。将TiSpark与PrestoDB和Greenplum进行比较，就是将SparkSQL （TiSpark的底层引擎）与其他两个引擎进行比较。不过，这已经超出了本文的讨论范围，我们也不做详细的讨论。

6.4 HTAP 性能

除了调查事务处理（TP）和分析处理（AP）的性能，我们使用基于整个CH-benCHmark的混合工作负载评估TiDB，使用单独的事务客户端（TC）和分析客户端（AC）。这些实验在100个仓库中进行。数据被加载到TiKV中，并同时复制到TiFlash中。TiKV部署在三个服务器上，通过TiDB SQL引擎实例访问。TiFlash部署在另外3个服务器上，并与一个TiSpark实例进行搭配。这个配置分别服务分析查询和事务性查询。每次运行10分钟，有3分钟的预热期。我们测量了TP和AP工作负载的吞吐量和平均延迟。

图10(a)和10(b)分别显示了使用不同数量的TP客户端和AP客户端的事务的吞吐量和平均延迟。吞吐量随着TP客户端数量的增加而增加，但在略小于512个客户端时达到最大值。与相同数量的TP客户端，与没有AP客户端相比，更多的分析处理客户端最多降低10%的TP吞吐量。这证实了TiKV和TiFlash之间的日志复制实现了高度隔离，特别是与第6.6节中MemSQL的性能相比。这一结果与BatchDB中的结果类似。

事务的平均延迟在没有上限的情况下增加。这是因为即使更多的客户端发出更多的请求，它们也不能立即完成，必须等待。等待时间导致了延迟的增加。类似的吞吐量和延迟结果如图10(c)和10(d)所示，展示了TP对AP请求的影响。AP吞吐量很快就会在16个AP客户端下达到最大值，因为AP查询非常昂贵，并且会争夺资源。这样的争用会降低更多AP客户端的吞吐量。对于相同数量的AP客户端，吞吐量几乎保持不变，最多只下降5%。这说明TP对AP执行的影响并不显著。分析查询的平均延迟的增加源于更多的客户端等待时间的增加。

6.5 日志复制延迟

为了实现实时分析处理，事务更新应该对TiFlash立即可见。这样的数据新鲜度是由TiKV和TiFlash之间的日志复制延迟决定的。我们在使用不同数量的事务客户端和分析客户端运行CH-benCHmark时测量日志复制时间。在运行CH-benCHmark的10分钟内，我们记录了每次复制的延迟，并每10秒计算平均延迟。我们还计算了10分钟内日志复制延迟的分布，如表4所示。

如图11(a)所示，10个仓库的日志复制延迟始终小于300毫秒，大多数延迟小于100毫秒。图11(b)显示，100个仓库的延迟增加;大多数小于1000 Ms。表4给出了更精确的细节。使用10个仓库，无论客户端设置如何，几乎99%的查询成本低于500 ms。在100个仓库的情况下，大约99%和85%的查询在2个和32个分析客户端下所花费的时间分别小于1000 ms。这些指标突出表明，TiDB在HTAP工作负载下可以保证大约1秒的数据新鲜度。

当比较图11(a)和图11(b)时，我们观察到延迟时间与数据大小有关。仓库越多，延迟时间就越大，因为更多的数据会引入更多需要同步的日志。此外，延迟也取决于分析请求的数量，但由于事务性客户端数量较多，延迟受到的影响较小。在图11(b)中可以清楚地看到这一点。32个ACs引起的延迟比2个ACs要多。但是相同数量的分析客户端，延迟差别不大。我们在表4中展示了更精确的结果。对于100个仓库和2个ACs，超过80%的查询花费的时间小于100 ms，但是对于32个ACs少于50%的查询花费的时间小于100 ms。这是因为更多的分析查询会导致更高频率的日志复制。

6.6 与MemSQL的比较

我们使用CH-benC -Hmark将TiDB与MemSQL 7.0进行比较。这个实验旨在突出最先进的HTAP系统的隔离问题，而不是OLTP和OLAP性能。MemSQL是一个分布式的关系型数据库，可以大规模处理事务和实时分析。MemSQL部署在6台服务器上：1台主服务器、1台聚合服务器和4台叶子服务器。我们将100个仓库加载到MemSQL中，并用不同数量的AP和TP客户端运行基准测试。基准运行了10分钟，有5分钟的预热期。

与图10相比，图12说明了工作负载干扰对MemSQL的性能有显著影响。特别是，随着AP客户端数量的增加，事务吞吐量显著放缓，下降了5倍以上。AP吞吐量也会随着TP客户端数量的增加而下降，但这种影响并不明显，因为事务查询不需要分析查询那样大量的资源。

7. 相关工作

构建HTAP系统的常见方法有：从现有数据库演化、扩展开源分析系统或从头构建。TiDB是从零开始构建的，与其他系统在架构、数据来源、计算引擎、一致性保证等方面有所不同。

从现有的数据库演化而来。成熟的数据库可以在现有产品的基础上提供HTAP解决方案，它们特别注重加速分析查询。它们采用自定义方法分别实现数据一致性和高可用性。相比之下，TiDB自然受益于Raft中的日志复制，实现数据一致性和高可用性。

Oracle在2014年引入了Database in-memory选项，作为业界第一个双格式、内存中的RDBMS。该选项旨在打破分析查询工作负载的性能障碍，同时不影响（甚至提高）常规事务性工作负载的性能。列式存储是一个只读快照，在某个时间点上是一致的，它使用全在线重新填充机制进行更新。Oracle后期的作品展现了其分布式架构的高可用性方面，并提供容错的分析查询执行。

SQL Server在其核心中集成了两个专门的存储引擎：用于分析工作负载的Apollo列存储引擎和用于事务性工作负载的Hekaton内存引擎。数据迁移任务定期将数据从Hekaton表的尾部复制到压缩列存储中。SQL Server使用列存储索引和批处理来高效地处理分析查询，利用SIMD进行数据扫描。

SAP HANA支持高效地评估单独的OLAP和OLTP查询，并为每个查询使用不同的数据组织形式。为了扩展OLAP性能，它异步地将行存储数据复制到分布在服务器集群上的列式存储中。这种方法为MVCC数据提供了亚秒级的可见性。然而，它需要大量的努力来处理错误和保持数据的一致性。重要的是，事务引擎缺乏高可用性，因为它只部署在单个节点上。

改造开源系统。Apache Spark是一个用于数据分析的开源框架。它需要一个事务模块来实现HTAP。下面列出的许多系统都遵循这个思路。TiDB对Spark的依赖并不深，因为TiSpark是一个扩展。TiDB是一个没有TiSpark的独立HTAP数据库。

Wildfire构建了一个基于Spark的HTAP引擎。它在相同的列式数据组织上同时处理分析和事务性请求，即 parquet。对并发更新采用last-write-wins语义，对读取采用快照隔离。对于高可用性，分片日志不需要共识算法的帮助就可以复制到多个节点。分析查询和事务性查询可以在单独的节点上处理;然而，在处理最新的更新时会有明显的延迟。Wildfire对大规模HTAP工作负载使用统一的多版本和多域索引（multi-zone indexing）方法。

SnappyData为OLTP、OLAP和流分析提供了统一的平台。它集成了一个用于高吞吐量分析的计算引擎（Spark）和一个向外扩展的内存事务存储（GemFire）。最近的更新以行格式存储，然后将其存储为列式格式，用于分析查询。事务遵循2PC协议，使用GemFire的Paxos实现，以确保整个集群的共识和一致的视图。

从头开始构建。许多新的HTAP系统已经研究了混合工作负载的不同方面，包括利用内存计算来提高性能、优化数据存储和可用性。与TiDB不同，它们不能同时提供高可用性、数据一致性、可伸缩性、数据新鲜度和隔离性。

MemSQL拥有一个引擎，既可以用于可伸缩的内存OLTP，也可以用于快速分析查询。MemSQL可以以行或列的格式存储数据库表。它可以将部分数据保持为行格式，并将其转换为列格式，以便在将数据写入磁盘时进行快速分析。它将重复查询编译成低级机器代码，以加速分析查询，并使用许多无锁结构来辅助事务性处理。然而，在运行HTAP工作负载时，它不能为OLAP和OLTP提供隔离的性能。

HyPer使用操作系统的fork系统调用为分析工作负载提供快照隔离。它的新版本采用了MVCC实现，以提供可串行性、快速事务处理和快速扫描。ScyPer扩展了HyPer，通过使用逻辑或物理重做日志传播更新，在远程副本上大规模评估分析查询。

BatchDB是为HTAP工作负载设计的内存中的数据库引擎。它依赖于具有专用副本的主-从复制，每个副本针对特定的工作负载类型（即OLTP或OLAP）。它最大限度地减少了事务和分析引擎之间的负载交互，从而能够在严格的SLAs下对HTAP工作负载的新数据进行实时分析。请注意，它在行格式副本上执行分析查询，不承诺高可用性。

Lineage-based的数据存储（L-Store）通过引入更新友好、Lineage-based的存储架构，在单个统一引擎中结合了实时分析和事务性查询处理。这种存储在原生的、多版本的列式存储模型之上实现了无争用更新机制，以便将稳定数据从写优化的列式格式惰性地独立分段到读优化的列式布局中。

Peloton是一个自动驾驶的SQL数据库管理系统。它试图在运行时使数据初始加工适应HTAP工作负载。它使用无锁、多版本并发控制来支持实时分析。然而，它在设计上是一个单节点的、内存中的数据库。

CockroachDB是一种分布式SQL数据库，具有高可用性、数据一致性、可扩展性和隔离性。与TiDB一样，它建立在Raft算法之上，支持分布式事务。它提供了更强的隔离属性：序列化性，而不是快照隔离。但是，它不支持专用的OLAP或HTAP功能。

8. 结论

TiDB构建在分布式的、基于行的存储TiKV之上，它使用了Raft算法。我们引入了用于实时分析的列式learners，它从TiKV异步复制日志，并将行格式的数据转换为列格式。这种在TiKV和TiFlash之间的日志复制以很少的开销提供实时数据一致性。TiKV和TiFlash可以部署在单独的物理资源上，有效地处理事务性查询和分析性查询。当TiDB扫描表进行事务查询和分析查询时，它们可以被TiDB优选地选择来访问。实验结果表明TiDB在HTAP基准CH-benCHmark下性能良好。TiDB提供了一个通用的解决方案，将NewSQL系统演化为HTAP系统。