TiDB:一种基于Raft的HTAP数据库
原文名:TiDB: A Raft-based HTAP Database
原文地址:http://www.vldb.org/pvldb/vol13/p3072-huang.pdf
摘要
HTAP(在线事务处理与在线分析处理)数据库需要单独处理事务和分析查询,以消除它们的干扰。为了达到目的,必须在两者之间分别使用不同的数据副本进行查询。然而,为存储系统的分布式副本提供一致性视图任然是一个挑战,因为分析请求需要高效的从大规模、高可用的事务工作负载中读到一致性和新的数据。
为了迎接这个挑战,我们提议扩展基于复制状态机的共识算法为HTAP的工作负载提供一致性副本。基于这个新奇想法,我们有了一个基于Raft的HTAP数据库:TiDB。在数据库内,我们设计了一个多层Raft存储系统,由行存储和列存储组成。行存储使用Raft算法构建,它扩展性较好,用来实现高可用事务请求的更新。特别的,它异步地复制Raft日志到Learners中,Learners将行格式转换为列格式数组,从而实时的更新列存储。列存储允许分析请求从行存储的事务中高效的读到最新的与行存储隔离的一致性数据。基于这个存储系统,我们构建了一个SQL引擎去处理大规模的分布式事务和昂贵的分析查询。这个SQL引擎以最佳的方式访问行格式和列格式的副本数据。我们也包含一个强大的分析引擎,TiSpark,来帮助TiDB链接到Handoop生态。综合实验表明,TiDB达到了CH-benCHmark的隔离性与高性能标准,这是一个用来衡量HTAP工作负载的基准测试。
1. 引言
RDBMS(关系型数据库管理系统)因为其关系模型、强大的事务性和SQL接口受欢迎。它们被广泛的应用在传统应用中,比如业务系统。然而,旧的RDBMS不支持可伸缩性和高可用,因此,在2000年初[11],互联网应用首选NoSQL系统,比如Google的Bigtable[12]和DynamoDB[36]。NoSQL系统放松了对一致性的要求,提供了高扩展性和替代数据模型,像键值对、图形和文档。然而,许多应用也需要强事务、数据一致和SQL接口,因此NewSQL系统出现。NewSQL系统(如CockroachDB[38]和GoogleSpanner[14])为OLTP(在线事务处理)读/写负载提供了NoSQL的高扩展性,且仍能对交易的ACID有所保证[32]。此外,基于SQL的OLAP(在线分析处理)系统正在快速开发,就像SQL on Hadoop的一些系统一样[16]。
这些系统都遵循"一种形式不适用于所有"的范式[37],使用不同的数据模型和技术用于OLAP和OLTP的目的。然而,多个系统开发、部署和维护成本非常昂贵。此外,实时分析最新版本的数据也极具吸引。这就在工业和学术领域引起了一种混合OLTP和OLAP的系统[30]。HTAP系统应该像NewSQL一样可以实现可伸缩性、高可用以及事务一致性。此外,HTAP系统需要高效的读取最新数据,以确保OLTP和OLAP的吞吐量和延迟,满足两种特性:新鲜性和隔离性。
新鲜性的意思是用分析查询处理最近的数据的过程[34]。实时分析最新数据极具商业价值。但它不能保证有些HTAP的解决方案,如ETL(数据仓库技术, 抽取-转换-加载)技术。通过ETL的流程,OLTP系统定期像OLAP系统更新一批最新的数据。ETL花费几小时甚至几天的时间,因此无法提供实时分析。ETL阶段可以替换为通过流的方式更新到OLAP系统,以减小同步时间。然而,这两种方法缺乏全局的数据管理模型,考虑到一致性语义会更复杂。与多系统对接会有额外的性能开销。
隔离性指单独保证OLTP和OLAP查询的隔离性能。一些内存数据库(像HyPer[18])允许从同一服务器的事务处理读取最新的版本数据。尽管此方法提供了最新的数据,它不能同时达到OLTP和OLAP的高性能。这是由于数据同步惩罚和工作负载干扰,这个影响的研究[34]在CH-benCHmark[13](HyPer和SAP HANA的HTAP基准)。研究表明,当系统联合运行分析查询时,其最大可达到的OLTP吞吐量会显著降低。SPA HANA[22]的吞吐量减小了3倍,HyPer至少减小了5倍。类似的结果在MemSQL[24]中得到证实。此外,如果内存中的数据库仅部署在单个服务器上,则无法提供高可用和可伸缩性。
为了保持隔离性能,有必要在不同的硬件资源上运行OLTP和OLAP请求。基本难点在于单个系统中维护来自OLTP工作负载的OLAP请求的最新副本。此外,系统需要保持更多复制之间的数据一致性。请注意,可用性[29] 还需要维护一致的副本。可以使用众所周知的共识算法(如 Paxos[20]和Raft[29])实现高可用性。它们基于复制的状态计算机来同步副本。可以扩展这些共识算法,为HTAP 工作负载提供一致的副本。据我们所知,这个想法以前没有研究过。
按照这个想法,我们提出了一个基于Raft的HTAP数据库:TiDB。它将专用节点(称为学习者)引入Raft共识算法。leanners异步从领导节点复制事务日志,为OLAP查询构造新的副本。特别是,学员将日志中的行格式元数转换为列格式,以便副本更适合分析查询。这种日志复制在领导者节点上运行的事务查询上很少产生开销。此外,这种复制的延迟非常短,可以保证OLAP的数据新鲜度。我们使用不同的数据副本分别处理OLAP和OLTP请求,以避免它们之间的干扰。我们还可以基于行格式和列格式的数据副本优化HTAP请求。基于Raft协议,TiDB提供高可用性、可扩展性和数据一致性。
TiDB 提供了一个创新的解决方案,可帮助基于共识算法的NewSQL系统演变为HTAP系统。NewSQL系统通过复制Google Spanner和Cockroach DB等数据库,确保OLTP请求的高可用性、可扩展性和数据持久性。它们通过通常来自共识算法的复制机制跨数据副本同步数据。基于日志复制,NewSQL系统可以提供专用于OLAP请求的列副本,以便它们可以像TiDB那样单独支持HTAP请求。
我们的贡献如下:
- 我们提出了构建基于共识算法的HTAP系统和实现基于Raft协议的HTAP数据库,TiDB。它是一个开源项目[7],为HTAP工作负载提供高可用、一致性、高扩展性以及数据新鲜度和隔离性。
- 我们将学习者角色引入Raft算法,以生成用于实时OLAP查询的列存储。
- 我们实施了Mutil-Raft存储系统并优化读/写操作,以便扩展到更多节点时提供高性能。
- 我们为大型HTAP查询定制了SQL引擎。引擎可以最佳的选择使用基于行存储和列存储。
- 我们使用HTAP基准CH-benCHmark进行综合实验,以评估TiDB在OLTP、OLAP和HTAP方面的表现。
本文的其余部分按如下方式组织。我们在第2节中描述了主要思想,基于Raft的HTAP,并在第3节中说明了TiDB的体系结构。第4节第5节阐述了TiDB的多负载存储和HTAP引擎。实验评价在第6节中介绍。我们总结了第7节中的相关工作。最后,我们在第8节中结束我们的论文。
2. 基于Raft的HTAP
共识算法(如Raft和Paxos)是构建一致、可扩展且高度可用的分布式系统的基础。其优势在于使用复制的状态机在服务器之间实时可靠地复制数据。我们调整此功能,将数据复制到不同的服务器用于不同的HTAP工作负载。这样,我们保证OLTP和OLAP工作负载彼此隔离,但OLAP请求也会为数据提供全新且一致的视图。据我们所知,以前没有使用这些共识算法来构建HTAP数据库的工作。
由于Raft算法设计为易于理解和实现,我们可以专注于对Raft扩展,以实现生产就绪的HTAP数据库。如图1所示,在高级别上,我们的想法如下:数据存储在多个Raft组中,使用行格式提供事务查询。每个小组由一名领导者和追随者组成。我们将学习者角色添加到每个组,以异步地从领导者复制数据。这种方法低开销,并能保持数据一致性。复制到学习者的数据将转换为基于列的格式。扩展查询优化器以探索访问基于行和基于列的副本的物理计划。
图1:在Raft组列中添加学习者
在标准Raft组中,每个追随者都可以成为提供读写请求的领导者。简单地添加更多的追随者,因此不会隔离资源。此外,添加更多追随者将影响组的性能,因为领导者必须等待来自较大仲裁节点的响应,然后才能响应客户端。因此,我们向Raft共识算法引入了一个学习者角色。学习者不参与领导者选举,也不参与日志复制的投票。从领导者到学习者的日志复制是异步的,领导者不需要等待成功然后再响应客户端。领导者和学习者之间的强一致性在读取期间强制执行。根据设计,领导者和学习者之间的日志复制延迟较低,如评估部分所演示。
事务查询需要高效的数据更新,而分析查询(如联接或聚合)需要读取列的子集,但需要读取大量行。基于行的格式可以利用索引有效地为事务查询服务。基于列的格式可以有效地利用数据压缩和矢量化处理。因此,在复制给Raft的学习者时,数据会从基于行的格式转换为基于列的格式。此外,学习者可以部署在单独的物理资源中。因此,事务查询和分析查询在隔离资源中处理。
我们的设计也提供了新的优化机会。由于数据在基于行的格式和基于列的格式之间保持一致,因此我们的查询优化器可以生成访问两个存储区的物理计划。
我们提出了扩展Raft以满足HTAP数据库的新鲜度和隔离要求的想法。为使HTAP数据库生产准备就绪,我们克服了许多工程挑战,主要包括:
- 如何构建可扩展的Raft存储系统以支持高度并发读写?如果数据量超过Raft算法管理的每个节点上的可用空间,我们需要一个分区策略来在服务器上分发数据。此外,在基本Raft过程中,请求按顺序处理,并且任何请求都必须在响应客户端之前由Raft节点的仲裁批准。此过程涉及网络和磁盘操作,因此非常耗时。这种开销使领导者成为处理请求的瓶颈,尤其是在大型数据集上。
- 如何以低延迟将日志同步到学习者中,以保持数据新鲜性?正在执行的事务可以生成一些非常大的日志。这些日志需要在学习者中快速重播和实现,以便可以读取新的数据。将日志数据转换为列格式可能会由于架构不匹配而遇到错误。这可能延迟日志同步。
- 如何有效地处理和保证性能的事务和分析查询?大型事务查询需要读取和写入分布在多台服务器中的大量数据。分析查询也会消耗密集的重新源,不应影响联机事务。为了减少执行开销,他们还需要在行格式存储和列格式存储上选择最佳计划。
在以下各节中,我们将详细阐述TiDB的设计和实现,以应对这些挑战。
3. 体系结构
在本节中,我们将介绍TiDB的高级别结构,如图2所示。TiDB支持MySQL协议,并且可由与MySQL兼容的客户端访问。它有三个核心组件:分布式存储层、计划驱动器(PD)和计算引擎层。
图2:TiDB体系结构
分布式存储层由行存储(TiKV)和列存储(TiFlash)组成。从逻辑上讲,存储在TiKV中的数据是有序的键值对映射。每个元组都映射到键值对。键由其表ID和行ID组成,值是实际行数据,其中表ID和行ID是唯一的整数,行ID来自主键列。例如,包含四列的元组定义为:
Key:{table_record}
Value:{col0, col1, col2, col3}
为了横向扩展,我们采取范围分区策略(Region),将大键值映射拆分为许多连续范围,每个部分称为区域。每个区域都有多个副本,用于高可用性。Raft共识算法用于保持每个区域副本之间的一致性,从而形成一个Raft组。不同Raft组的领导者异步将数据从TiKV复制到TiFlash。TiKV和TiFlash可以部署在单独的物理资源中,因此在处理事务和分析查询时提供隔离。
PD(计划驱动器)负责管理区域,包括提供每个键的区域和物理位置,并自动移动区域以平衡工作负载。PD也是我们的Oracle时间戳,提供严格增加和全球唯一的时间戳。这些时间戳也用作我们的事务ID。PD可能包含多个PD成员,用于稳健性和性能。PD没有持久状态,在启动时,PD成员从其他成员和TiKV节点收集所有必要的数据。
计算引擎层是无状态的、可扩展的。我们定制的SQL引擎具有基于成本的查询优化器和分布式查询执行器。TiDB实现了基于Percolator[33]的2PC(2阶段提交)协议,以支持事务处理。查询优化器可以根据查询选择从TiKV和TiFlash读取。
TiDB的体系结构满足HTAP数据库的要求。TiDB的每个组件都设计为具有高可用性和可扩展性。存储层使用Raft算法实现数据副本之间的一致性。TiKV和TiFlash之间的低延迟复制使分析查询能够使用新的数据。查询优化器以及TiKV和TiFlash之间的强一致性数据可提供快速的分析查询处理,对事务处理影响很小。
除了上述组件外,TiDB还与Spark集成,这有助于集成存储在TiDB和Hadoop分布式文件系统(HDFS)中的数据。TiDB具有一组丰富的生态系统工具,用于将数据导入TiDB并导出数据,以及将数据从其他数据库迁移到TiDB。
在以下部分中,我们将对分布式存储层、SQL引擎和TiSpark进行深入探讨,以演示TiDB(一个生产就绪的HTAP数据库)的功能。
4. Multi-Raft的存储
图3显示了TiDB中分布式存储层的体系结构,其中相同形式的对象扮演相同的角色。存储层由基于行的存储TiKV和基于列的存储TiFlash组成。存储将一个大表映射到一个大键值映射,该映射被拆分为存储在TiKV中的多个区域。每个区域使用Raft共识算法来保持副本之间的一致性以实现高可用性。当数据复制到TiFlash时,多个区域可以合并到一个分区中,以便于表扫描。通过异步日志复制,TiKV和TiFlash之间的数据保持一致。由于多个Raft组管理分布式存储层中的数据,因此我们称之为Mutil-Raft存储。在以下各节中,我们将详细介绍TiKV和TiFlash,重点介绍优化,使TiDB成为生产就绪的HTAP数据库。
图3:Mutil-Raft存储的体系结构
4.1 基于行的存储(TiKV)
TiKV部署由许多TiKV服务器组成。使用Raft在TiKV服务器之间复制区域。每个TiKV服务器都可以是不同区域的Raft领导者或追随者。在每个TiKV服务器上,数据和元数据都保留到RocksDB[5],这是一个可嵌入的、持久的、键值存储。每个区域都有可配置的最大大小,默认情况下为96MB。Raft领导服务器的TiKV服务器处理相应区域的读/写请求。
当Raft算法响应读写请求时,在领导者及其追随者之间执行基本的Raft过程:
- 区域的领导者接收来自SQL引擎层的请求。
- 领导者将请求附加到其日志。
- 领导者将新的日志条目发送给其追随者,而追随者又将条目附加到其日志中。
- 领导者等待其追随者做出回应。如果节点的仲裁响应成功,则领导者将提交请求并在本地应用它。
- 领导者将结果发送给客户端,并继续处理传入的请求。
此过程可确保数据一致性和高可用性。但是,它不提供有效的性能,因为这些步骤按顺序执行,并且可能会产生较大的I/O开销(磁盘和网络)。以下各节介绍我们如何优化此过程以实现高吞吐量的读写,即解决第2节中描述的第一个挑战。
4.1.1 在领导者和追随者之间的优化
在上述过程中,第二步和第三步可以并行进行,因为它们之间没有依赖关系。因此,领导者在本地追加日志,并同时向追随者发送日志。如果在领导者追加日志失败,但追随者仲裁成功追加日志,则仍然可以提交日志。在第三步中,当向追随者发送日志时,领导者会缓冲日志条目,并分批将其发送给其追随者。发送日志后,领导者不必等待追随者响应。相反,它可以假设成功,并发送更多日志与预测的日志索引。如果发生错误,领导者将调整日志索引并重新发送复制请求。在第四步中,应用已提交日志条目的领导可以由不同的线程异步处理,因为在此阶段,一致性没有风险。根据上述优化,Raft过程将更新如下:
- 领导者接收来自SQL引擎层的请求。
- 领导者将相应的日志发送给关注者,并并行地在本地追加日志。
- 领导者继续收到客户的请求,并重新执行步骤2。
- 领导者提交日志并将其发送到要应用的另一个线程。
- 应用日志后,领导者将结果返回给客户端。
在优化后的流程中,客户端的任何请求仍按照Raft步骤执行;但来自多个客户端的请求则会并行运行,因此总体吞吐量会增加。
4.1.2 加速客户端的读请求
从TiKV领导者读取数据提供线性语义。这意味着,当值在时间t从区域领导者读取时,领导者不得在t之后返回读取请求值的早期版本。这可以通过使用如上所述的Raft实现:为每个读取请求发出日志条目,并等待该条目在返回前提交。但是,此过程非常昂贵,因为日志必须在Raft组中的大多数节点上复制,这会造成网络I/O的开销。为了提高性能,我们可以避免日志同步阶段。
Raft保证领导者成功写入数据后,领导者可以响应任何读取请求,而无需跨服务器同步日志。但是,在领导者选举后,领导者角色可能会在Raft组中的服务器之间移动。为了实现来自领导者的读取,TiKV实现了以下读取优化,如[29]中所述。
第一种方法称为读取索引。当领导者响应读取请求时,它会将当前提交索引记录为本地读取索引,然后向追随者发送心跳消息以表明其领导者角色。如果它确实是领导者,否则一旦其应用的索引值大于等于读取的索引值就会返回。
另一种方法是租约读取,它减少了由读取索引引起的网络心跳开销。领导者和追随者同意租赁期,在此期间,追随者不发出选举请求,以便不会更改领导者。在租赁期间,领导者可以响应任何读取请求,而无需连接到其追随者。如果每个节点上的CPU时钟差异并不很大,那么此方法效果良好。
除了领导者之外,追随者还可以响应来自客户的重新请求,这称为追随者阅读。跟随者收到读取请求后,它会向领导者询问最新的读取索引。如果本地应用的索引等于或大于读取索引,则跟随者可以将值返回给客户端;如果本地应用的索引等于或大于读取索引,则跟随者可以将值返回给客户端。否则,它必须等待日志的应用。追随者阅读可以减轻热点区域领导者的压力,从而提高阅读性能。然后,通过添加更多追随者,可以进一步提高读取性能。
4.1.3 管理大量的区域
大量区域分布在服务器群集上。服务器和数据大小在动态变化,区域可能会群集在某些服务器中,尤其是领导者副本。这会导致某些服务器的磁盘过度使用,而其他服务器磁盘则是免费的。此外,服务器可以添加到群集或从群集中移动。
若要在服务器之间平衡区域,PD(计划驱动器)会安排具有副本数量和位置限制的区域。一个关键的约束是将一个区域的至少三个副本放在不同的TiKV实例上,以确保高可用性。PD通过从服务器通过检测信号收集特定信息进行初始化。它还监视每台服务器的工作负载,并在不会影响应用程序的情况下将热区域迁移到不同的服务器。
另一方面,维护海量区域涉及发送检测信号和管理元数据,这可能会导致大量的网络工作和存储开销。但是,如果Raft组没有任何工作负荷,则不需要检测信号。根据区域工作负载的繁忙情况,我们可以调整发送检测信号的频率。这降低了出现网络延迟或节点过载等问题的可能性。
4.1.4 动态区域的分割和合并
一个大区域可能会变得过于热点,无法在合理的时间内阅读或书写。热区域或大区域应拆分为较小的区域,以便更好地分配工作负载。另一方面,许多区域可能很小且很少被访问;但是,系统仍然需要维护检测信号和元数据。在某些情况下,维护这些小区域会产生大量的网络和CPU开销。因此,有必要合并较小的区域。请注意,为了维护区域之间的顺序,我们仅在键空间中合并相邻区域。根据观察到的工作负荷,PD动态地向TiKV发送拆分和合并命令。
拆分操作将区域划分为几个新的较小区域,每个区域涵盖原始区域中的连续键范围。覆盖最右侧范围的区域可重用原始区域的Raft组。其他区域使用新的Raft组。拆分过程类似于Raft进程中的正常更新请求:
- PD向区域领导者发出拆分命令。
- 收到拆分命令后,领导者将该命令转换为日志,并将日志复制到所有跟随节点。日志仅包括拆分命令,而不是修改实际数据。
- 一旦仲裁复制日志,领导者将提交拆分命令,该命令将应用于Raft组中的所有节点。应用过程包括更新原始区域的范围和纪元元数据,以及创建新的区域以覆盖其余范围。请注意,该命令以原子方式应用并同步到磁盘。
- 对于拆分区域的每个副本,将创建一个Raft状态机并开始工作,从而形成一个新的Raft组。原始区域的领长将拆分结果报告给PD。拆分过程完成。
请注意,当大多数节点提交拆分日志时,拆分过程将成功。类似于提交其他Raft日志,而不是要求所有节点完成区域拆分。拆分后,如果对网络进行分区,则具有最近的节点组将获胜。由于只需要元数据更改,因此区域分割的开销较低。拆分命令完成后,由于PD的常规负载平衡,新拆分区域可能会跨服务器移动。
合并两个相邻区域与拆分一个区域相反。PD移动两个区域的副本,以在单独的服务器上协调它们。然后,通过两阶段操作,将两个区域的合并副本合并到每台服务器上的本地区域;也就是说,停止一个区域的服务,并将其与另一个区域合并。此方法与拆分区域不同,因为它不能使用两个Raft组之间的日志复制过程来商定合并它们。
4.2 基于列的存储(TiFlash)
尽管我们优化了上述TiKV的读取数据,但TiKV中的行格式数据并不适合快速分析。因此,我们将列存储(TiFlash)合并到TiDB中。TiFlash由学员节点组成,这些节点只从Raft组接收Raft日志,并将行格式的元组转换为列数据。他们不参与Raft协议来提交日志或选举领导者,因此它们很少在TiKV上产生开销。
用户可以使用SQL语句为表设置列格式副本:
ALTER TABLE × SET TiFLASH REPLICA n;
其中x是表的名称,n是副本的数量。默认值为1。添加列副本类似于向表添加异步列形索引。TiFlash中的每个表被划分为多个分区,每个分区根据TiKV的几个连续区域覆盖一个连续的元组范围。较大的分区便于范围扫描。
4.2.1 日志重放
根据Raft算法,学习者节点接收的日志是线性的。为了保持已提交数据的线性语义,根据先出先出(FIFO)策略重播它们。日志重播有三个步骤:
- 压缩日志:根据第5.1节中描述的事务模型,事务日志分为三种状态:预写、提交或回滚。回滚日志中的数据不需要写入磁盘,因此压缩进程会根据回滚日志删除无效的预先写入的日志,并将有效的日志放入缓冲区。
- 解码元数:缓冲区中的日志被解码为行格式的元数,删除有关事务的冗余信息。然后,将解码的元数放入行缓冲区中。
- 转换数据格式:如果行缓冲区中的数据大小超过大小限制或其时间持续时间超过时间间隔限制,则这些行格式的元数将转换为列数据并写入本地分区数据池。转换是指本地缓存架构,这些架构会定期与TiKV同步,如下文所述。
若要说明日志重播过程的详细信息,请考虑以下示例。我们抽象了每一条Raft日志项,像transaction ID-operation type[tansaction status][@start_ts][#commit_ts]
操作数据。根据典型的DML,操作类型包括插入、更新和删除元组。事务状态可能预先写、提交或回滚。操作数据可以作为特定插入或更新的元组,也可以是已删除的密钥。
在表1所示的示例中,原始日志包含八个项目,它们尝试插入两个元组、更新一个元组和删除一个元组。但是插入k1会回滚,因此仅保留了八个原始日志项中的六个,其中三个元组被解码。最后,三个解码的元组被转换成五列:操作类型、提交时间戳、键和两列数据。这些列将追加到DeltaTree中。
表1:日志重放和解码
4.2.2 模式同步
要实时将元组转换为列格式,学习者节点必须了解最新的模式。这种模式过程不同于TiKV上的无架构操作,它把元组编码为字节数组。最新的模式信息存储在TiKV中。为了减少TiFlash向TiKV请求最新模式的数量,每个学员节点都维护一个模式缓存。
缓存通过模式同步器与TiKV的架构同步。如果缓存的模式已过期,则要解码的数据与本地模式之间存在不匹配,并且必须重新转换数据。模式同步的频率和模式不匹配的数量之间有一个权衡。我们采取两阶段策略:
- 定期同步:模式同步器定期从TiKV提取最新的模式,并应用更改到其本地缓存。在大多数情况下,这种临时同步会降低同步模式的频率。
- 强制同步:如果模式同步器检测到不匹配的模式,它将主动从TiKV获取最新的模式。当元组和模式之间不同或列值溢出时,可以触发此情况。
4.2.3 Columnar Delta Tree
为了有效地高吞吐的写/读取的列数据,我们设计了一个新的列存储引擎,Delta Tree,它立即追加增量更新,然后将它们与每个分区的先前稳定版本合并。增量更新和稳定数据分别存储在增量树中,如图4所示。在稳定空间中,分区数据存储为块,每个区块都覆盖分区元组较小范围。此外,这些行格式的元对按列存储。相反,增量直接追加到增量空间中,以TiKV生成它们的顺序排列。TiFlash列数据的存储格式类似于Parquet[4]。它还将行组存储到列块中。不同地,TiFlash将行组的列数据及其元数据存储到不同的文件中以同时更新文件,而不是仅在Parquet中存储一个文件。TiFlash只是使用常见的LZ4 [2]压缩数据文件来保存。
图4:columnar delta tree
新的传入增量是插入数据的原子批处理或删除的范围。这些增量缓存到内存中并化为磁盘。它们按顺序存储,因此它们实现了提前写入日志(WAL)的功能。这些增量通常存储在许多小文件中,因此在读取时会导致较大的IO开销。为了降低成本,我们定期将这些小增量压缩成一个更大的增量,然后将较大的增量刷新到磁盘中,并替换以前实现的小增量。传入增量的内存副本便于读取最新数据,如果旧增量达到有限大小,则删除它们。
读取某些特定元组的最新数据时,有必要将所有增量文件及其稳定的元(即读取放)合并,因为相关增量分布的位置并不事先知道。由于读取大量文件,这样的过程非常昂贵。此外,许多增量文件可能包含无用的数据(即空间放大),这些数据会浪费存储空间并减慢将它们与稳定元组合并的速度。因此,我们定期将增量合并到稳定空间中。每个增量文件及其相关区块都读取到内存中并合并。增量中插入的元组将添加到稳定中,修改后的元组将替换原始元组,并移动已删除的元组。合并的区块以原子方式替换磁盘中的原始区块。
增量合并非常昂贵,因为相关键在增量空间中是无序的。这种混乱还减缓了将增量与稳定区块集成以返回读取请求的最新数据的速度。因此,我们在增量空间的顶部构建一个B+树索引。每个增量更新项都按其键和时间戳排序插入B+树中。此订单优先级有助于有效地查找一系列键的更新,或在响应读取请求时在增量空间中查找单个键。此外,B+树中的有序数据很容易与稳定区块合并。
我们进行一项微观实验,将Delta Tree的性能与TiFlash中的LSM(日志结构化合并)树[28]进行比较,在该树根据Raft日志更新数据时读取数据。我们设置了三个TiKV节点和一个TiFlash节点,在实验部分列出了硬件结构。我们在TiKV上运行Sysbench[6]的唯一写入工作负载,并在TiFlash上运行"select count(id) count(k) from sbtest1"。为了避免数据压缩的大量写入放大,我们使用通用压缩而不是水平样式压缩来实现LSM存储引擎。此实现在ClickHouse[1]中也采用,这是一个面向列的OLAP数据库。
如表2所示,无论有1亿还是2亿个元组以及事务工作负载,从增量树读取的速度比LSM树快两倍。这是因为在增量树中,每个读取访问最多在B+树中索引的增量文件的一个级别,同时访问LSM树中更多的过度映射文件。在不同的写入工作负载下,性能几乎保持稳定,因为增量文件的比例几乎相同。虽然Delta树(16.11)的写入放大大于LSM树(4.74),但它也是可以接受的。
表2:Delta Tree和LSM tree的读性能
4.2.4 读处理
与跟随者读取一样,学习者节点提供快照隔离,因此我们可以在特定时间戳中从TiFlash读取数据。收到读取请求后,学习者向其领导者发送读取索引请求,以获取涵盖请求的时间戳的最新数据。作为响应,领导者将引用的日志发送给学习者,学习者重播并存储日志。将日志写入Delta Tree后,将读取来自增量树的特定数据以响应读取请求。
5. HTAP引擎
为了解决第2节中提到的第三个挑战,即处理大型事务和分析查询,我们提供了一个SQL引擎来评估事务和分析查询。SQL引擎调整Percolator模型,在分布式群集中实现乐观和悲观锁定。SQL引擎通过使用基于规则和成本的优化器、索引和将计算推送到存储层来加速分析查询。我们还实施TiSpark与Hadoop生态系统连接,并增强OLAP能力。HTAP请求可以在隔离存储和引擎服务器中单独处理。特别是,SQL引擎和TiSpark受益于同时使用行和列存储,以获得最佳结果。
5.1 事务处理
TiDB 提供具有SI(快照隔离)或RR(可重复读取)语义的ACID事务。SI允许事务中的每个请求读取数据的一致版本。RR表示事务中的不同语句可能会读取同一键的不同值,但重复读取(即具有相同时间戳的两次读取)将始终读取相同的值。我们的实现基于多版本并发控制(MVCC),避免了读写锁定,并可防止写入冲突。在TiDB中,事务是SQL引擎、TiKV和PD之间的协作事务。在跨行动期间,每个组件的责任如下:
- SQL引擎:协调事务。它接收来自客户端的写入和读取请求,将数据转换为键值格式,并使用2PC(2阶段提交)将事务写入TiKV。
- PD:管理逻辑区域和物理位置;提供全局、严格增加的时间戳。
- TiKV:提供分布式事务接口,实现MVCC,并将数据保留到磁盘。
图5:乐观与悲观的事务流程
TiDB 实现乐观和悲观锁定。它们根据Percolator模型改编,该模型选择一个键作为主键,并使用它代表事务的状态,并基于2PC执行事务。乐观事务的过程图5的左侧说明了这一过程。(为简单起见,图中忽略了异常处理)。
- 从客户端收到"开始"命令后,SQL引擎要求PD使用时间戳作为事务的开始时间戳(start_ts)。
- SQL引擎通过从TiKV读取数据并写入本地内存来执行SQL DML。TiKV提供事务开始后(start_ts)的数据最近提交时间戳(commit_ts)。
- 当SQL引擎从客户端收到提交命令时,它将启动2PC协议。它随机选择主键,并行锁定所有密钥,并将预写入发送到TiKV节点。
- 如果所有预写成功,SQL引擎会向PD请求为事务的提交提供时间戳,并向TiKV发送提交命令。TiKV提交主密钥并将成功响应发送回SQL引擎。
- SQL引擎将成功返回给客户端。
- SQL引擎提交辅助键,通过向TiKV发送进一步的提交命令,以异步和并行方式清除锁。
乐观事务和悲观事务的主要区别在于获取锁时。在乐观事务中,锁在预写入阶段(上面的步骤3)以增量方式获取。在悲观事务中,锁是在预写前执行DML时获取的(步骤2的一部分)。这意味着,一旦预写开始,事务不会因为与另一个跨操作冲突而失败。(由于网络分区或其他问题,它仍可能失败)。
在悲观事务中锁定键时,SQL引擎将获取一个新的时间戳,称为for_update_ts。如果SQL引擎无法获取锁,它可以从该锁开始重试事务,而不是回滚和重试整个跨操作。读取数据时,TiKV使用for_update_ts而不是start_ts来决定可以读取键的哪些值。这样,悲观事务仍维持RR隔离级别,即使事务部分重试。
使用悲观事务,用户还可以选择仅要求读取提交(RC)隔离级别。这会导致事务之间的冲突减少,从而提高性能,而牺牲较少的独立事务。实现区别在于,如果读取尝试访问被另一个事务锁定的密钥,则RR TiKV 必须报告冲突;因此,如果读取内容尝试访问被另一事务锁定的密钥,则必须报告冲突。对于RC,可以忽略锁以进行读取。
TiDB实现分布式事务,无需集中式锁管理器。锁存储在TiKV中,具有很高的可扩展性和可用性。此外,SQL引擎和PD服务器可扩展,可处理OLTP请求。跨服务器同时运行多个事务实现了高度并行性。
从PD请求时间戳。每个时间戳都包含物理时间和逻辑时间。物理时间是指具有毫秒精度的当前时间,逻辑时间需要18位。因此,从理论上讲,PD可以分配218次的每毫秒。实际上,它每天可以产生大约 100万次的tamps,因为分配时间戳只需几个周期。客户端要求一次时间戳,以摊销开销,尤其是网络延迟。目前,获取时间戳并不是我们实验和许多生产环境中的性能瓶颈。
5.2 分析处理
在本节中,我们将介绍针对OLAP查询的优化,包括优化器、索引和推送我们定制的SQL引擎和TiSpark中的计算。
5.2.1 SQL引擎的查询优化
TiDB实现了一个查询优化器,具有两个阶段的查询优化:RBO(基于规则的查询优化),该优化生成逻辑计划,然后是CBO(基于成本的优化),将逻辑计划转换为物理计划。我们的RBO具有一组丰富的转换规则,包括裁剪不必要的列、预测消除、下推谓词、派生谓词、不断折叠、消除"group byy"或外联,以及取消取消子联接。我们的CBO根据执行成本从候选计划中选择最小代价的计划。请注意,TiDB支持使用两个数据存储库,TiKV和TiFlash,因此扫描表通常有三个选项:扫描TiKV中的行格式表、在TiKV中使用索引扫描表以及在TiFlash中扫描列。
索引对于提高数据库中的查询性能非常重要,这些查询通常用于点获取或范围查询,为哈希联接和合并联接提供更便宜的数据扫描路径。TiDB实现可扩展索引,以在分布式环境中工作。由于维护索引会消耗大量重新源,并且可能会影响联机事务和分析,因此我们在后台异步生成或删除索引。索引按区域按数据以相同的方式拆分,并存储于TiKV中的键值。唯一键索引上的索引项编码为:
Key: {table_index_indexedColValue}
Value:
非唯一索引项解码为:
Key: {table_index_indexedColValue_rowID}
Value:
使用索引需要二分搜索来查找包含索引相关部分的区域。为了提高索引选择的稳定性,减少物理优化的开销,我们使用skyline pruning算法来消除无用的候选索引。如果有多个候选索引匹配不同的查询条件,我们将合并部分结果(即一组合格的行ID)以获得精确的结果集。
物理计划(CBO的结果)由SQL引擎层使用pulling iterator model[17] 执行。通过将一些计算向下推送到存储层,可以进一步优化执行。在存储层中,执行计算的组件称为协处理器。协处理器并行在不同的服务器上执行执行计划的子树。这将减少必须从存储层发送到引擎层的元组数。例如,通过评估协处理器中的筛选器,在存储层中筛选出被拒绝的元组,并且只需要将接受的元组发送到引擎层。协处理器可以计算逻辑操作、算术运算和其他常见函数。在某些情况下,它可以执行聚合和TopN。协处理器可以通过矢量化操作进一步提高性能:而不是遍数整个行,对行进行批处理,按列组织数据,从而实现更高效的迭代。
5.2.2 TiSpark
为了帮助TiDB连接到Hadoop生态系统,TiDB在mutil-Raft存储上添加了TiSpark。除了SQL之外,TiSpark还支持强大的计算,如机器学习库,并且可以处理来自TiDB外部的数据。
图6显示了TiSpark如何与TiDB集成。在TiSpark中,Spark驱动程序从TiKV读取元数据以构造Spark目录,包括表架构和索引信息。Spark驱动程序要求PD提供时间戳,以读取来自TiKV的MVCC数据,以确保它获得数据库的一致快照。与SQL引擎一样,Spark驱动程序可以将计算推送到存储层上的共同处理器并使用可用的索引。这是通过修改Spark优化器生成的计划完成的。我们还自定义一些读取操作以从TiKV和TiFlash读取数据,并将它们组装成Spark工作人员的行。例如,TiSpark可以同时从多个TiDB区域读取,它可以并行从存储层获取索引数据。为了减少对Spark特定版本的依赖,大多数这些函数都是在附加包中实现的。
图6:TiSpark和TiDB的相互作用
TiSpark在两个方面不同于普通连接器。它不仅可以同时读取多个数据区域,还可以并行从存储层获取索引数据。读取索引有助于Spark中的优化器选择最佳计划以重新降低执行成本。另一方面,TiSpark修改了从Spark中的原始优化器生成的计划,将执行部分向下推送到存储层中的协处理器,从而进一步降低了执行开销。除了从存储层读取数据外,TiSpark还支持在存储层中加载具有事务的大型数据。为此,TiSpark采用两阶段提交和锁定表。
5.3 隔离和协同
资源隔离是保证事务查询性能的有效方法。分析查询通常消耗大量资源,如CPU、内存和I/O带宽。如果这些查询与事务查询一起运行,则后者可能会严重延迟。这一一般原则在以前的工作中已经得到验证[24,34]。为了避免在TiDB中出现此问题,我们在不同的引擎服务器上安排分析和事务查询,并在单独的服务器上部署TiKV和TiFlash。事务查询主要访问TiKV,而分析查询主要访问TiFlash。通过 Raft保持TiKV和TiFlash之间的数据一致性的开销较低,因此使用TiFlash运行分析查询对事务处理的性能影响很小。
数据在TiKV和TiFlash之间是一致的,因此可以通过从TiKV或TiFlash读取来提供查询。因此,我们的查询优化器可以从更大的物理计划空间进行选择,并且最佳计划可能同时从TiKV和TiFlash中读取。当TiKV访问表时,它提供行扫描和索引扫描,而TiFlash支持列扫描。
这三个访问路径的执行成本和数据顺序属性之间不同。行扫描和列扫描按主键提供顺序;索引扫描提供从键的编码中的多个排序。不同路径的成本取决于平均元组/列/索引大小(Stuple/col/index)和估计元数/区域数(Ntuple/reg)。我们表示数据扫描的I/O开销为fscan,以及寻求成本的文件为fseek 。查询优化器根据方程(1)选择最佳访问路径。如公式(2)所示,行扫描的成本来自扫描连续行数据和寻找区域文件。列扫描的成本(公式(3))是扫描m列的总和。如果索引列不能满足表扫描所需的列,则索引扫描(公式(4))应考虑扫描索引文件的成本和扫描数据文件的成本(即双重读取)。请注意,双读通常随机扫描元组,这涉及到在方程(5)中查找更多文件。
例如,当查询优化器将同时选择行格式和列格式存储以访问同一查询中的不同表时,请考虑"select T.*, S.a from T join S on T.b = S.b where T.a between 1 and 100"。这是一个典型的联接查询,其中T和S在行存储中的列a上具有索引,以及列副本。最好使用索引从行存储访问T,从列存储访问S。这是因为查询需要一系列来自T的完整元组,并且通过元组访问数据比列存储便宜。另一方面,使用列存储时获取两列完整的S更便宜。
TiKV和TiFlash的协调仍然可以保证隔离性能。对于分析查询,只有小范围扫描或点获取扫描只能通过跟随读取访问TiKV,这对领导者影响很小。我们还将TiKV上的默认访问表大小限制为最多500MB。事务查询可能会从TiFlash访问列数据,以检查某些约束,如唯一性。我们为特定表设置了多个列副本,一个表副本专用于事务查询。在单独的服务器上处理事务性查询可避免影响分析查询。
6. 实验
在本节中,我们首先分别评估TiDB的OLTP和OLAP能力。对于OLAP,我们调查SQL引擎选择TiKV和TiFlash的能力,并将TiSpark与其他OLAP系统进行比较。然后,我们测量TiDB的HTAP性能,包括TiKV和TiFlash之间的日志复制延迟。最后,我们将TiDB与MemSQL在隔离性方面进行对比。
6.1 实验步骤
集群。我们在六台服务器集群上执行全面的实验;每个处理器具有188 GB内存和两个IntelR© XeonR©CPU E5-2630 v4处理器,即两个NUMA节点。每个处理器有10个物理内核(20个线程)和一个25MB的共享L3cache。服务器运行Centos版本7.6.1810,并且通过10Gbps以太网网络连接。
工作负载。我们的实验是在混合OLTP和OLAP工作负载下使用CH-benCHmark进行的。源代码在线发布[7]。基准由标准OLTP和OLAP基准组成:TPC-C和TPC-H。它是根据TPC-C基准的未修改版本构建的。OLAP 部分包含22个分析查询,这些查询受TPC-H的启发,其架构从TPC-H调整为CH-benCHmark架构,外加三个缺失的TPC-H关系。在运行时,两个工作负载同时由多个客户端进行管理;在实验中,客户端的数量各不相同。吞吐量分别以QPS(查询/秒)或TPS(事务/秒)来衡量。CH-benCHmark中的数据单位称为仓库,与 TPC-C相同。100个仓库需要大约70GB的内存。
6.2 OLTP性能
我们评估TiDB的独立OLTP性能,在CH-benCHmark的OLTP部分下乐观锁定或悲观锁定;即TPC-C基准。我们比较了TiDB与Cockroach DB的性能(CRDB, 一种分布式NewSQL数据库)。CRDB部署在六台相同的服务器上。对于TiDB,SQL引擎和TiKV部署在六台服务器上,它们的实例分别绑定到每台服务器上的两个NUMA节点。PD 部署在六台服务器中的三台。为了平衡请求,通过HAProxy负载均衡器可以访问TiDB和CRDB。我们使用各种数量的客户端测量50、100和200个仓库的吞吐量和平均延迟。
图7(b)和图7(c)中的吞吐量图与图7(a)不同。在图7(a)中,对于少于256个客户端,TiDB的吞吐量随乐观锁定和悲观锁定的客户端数而增加。对于超过256个客户端,具有乐观锁定的吞吐量保持稳定,然后开始下降,而悲观锁定的吞吐量达到其最大512个客户端,然后下降。图7(b)和7(c)中的TiDB吞吐量不断增加。由于资源争用最激烈且并发性和小数据大小,因此预期会出现此结果。
图7:OLTP性能
图8:选择TiKV或TiFlash为查询分析
通常,在在小规模数据和高并发度的场景,乐观锁性能优于悲观锁(50或100个仓库的1024个客户端),其中资源争用很重,导致重试许多乐观事务。由于资源争用较轻,有200个仓库,因此乐观锁定仍会产生更好的性能。
在大多数情况下,TiDB的吞吐量高于CRDB,尤其是在对大型仓库使用乐观锁时。即使采用悲观锁进行公平比较(CRDB 始终使用悲观锁定),TiDB的性能仍然更高。我们相信TiBD的性能优势在于事务处理和对Raft算法的优化。
图7(d)显示,更多的客户端会导致更多的延迟,尤其是在达到最大吞吐量之后,因为更多的请求必须等待更长的时间。这也意味着延迟越高,仓库越少。对于某些客户端,较高的通投入可减少TiDB和CRDB的延迟。50个和100个仓库也存在类似的结果。
我们评估从PD请求时间戳的性能,因为这可能是一个潜在的瓶颈。我们使用1200个客户端持续请求时间戳。客户端位于群集中的不同服务器上。模拟TiDB,每个客户端分批向PD发送时间戳请求。如表3所示,六台服务器中每个服务器每台可接收602594次时间戳/秒,这是运行CH-benCHmark时所需速率的100倍以上。运行TPC-C时,TiDB请求每台服务器最多为6000次。增加服务器数量时,每台服务器上接收的时间戳数将减少,但时间戳总数几乎相同。这个比率大大超过任何实际需求。关于延迟,只有一小部分请求花费1ms或2ms。我们的结论是,从PD获取时间戳目前不是TiDB的性能瓶颈。
表3:生成时间戳性能
6.3 OLAP性能
我们评估从PD请求时间戳的性能,因为这可能是一个潜在的瓶颈。我们使用1200个客户端持续请求时间戳。客户端位于群集中的不同服务器上。模拟TiDB,每个客户端分批向PD发送时间戳请求。如表3所示,六台服务器中每个服务器每台可接收602594次时间戳/秒,这是运行CH-benCHmark时所需速率的100倍以上。运行TPC-C时,TiDB请求每台服务器最多为6000次。增加服务器数量时,每台服务器上接收的时间戳数将减少,但时间戳总数几乎相同。这个比率大大超过任何实际需求。关于延迟,只有一小部分请求花费1ms或2ms。我们的结论是,从PD获取时间戳目前不是TiDB的性能瓶颈。
Q8, Q12和Q22会产生有趣的结果。与Q8和Q22中仅TiFlash案例的时间成本要长,但Q22需要花费更多时间。TiKV和TiFlash案例的性能优于仅TiKV和仅TiFlash案例。
Q12主要包含两个表联接,但在每个存储类型中需要不同的物理实现。在仅TiKV的情况下,它使用索引联接,该联接从表ORDER_LINE
扫描多个合格的元组,并使用索引查找表OORDER
。索引读取器的成本低得多,因此它优于在TiFlash只例例中使用哈希联接,该案例扫描两个表中所需的列。使用TiKV和TiFlash时的成本进一步降低,因为它使用从TiFlash扫描ORDERLINE
的更便宜的索引联接,并使用TiKV中的索引搜索OORDER
。在TiKV和TiFlash案例中,读取列存储可将仅TiKV案例的执行时间减少一半。
在Q22中,exists()
子查询转换为反半联接。它在仅TiKV大小写例中使用索引联接,在仅TiFlash的情况下使用哈希联接。但与Q12中的执行不同,使用索引联接比哈希联接更昂贵。从TiFlash获取内部表并使用TiKV的索引查找外部表时,索引联接的成本会降低。因此,TiKV和TiFlash案例再次占用的时间最少。
Q8更为复杂。它包含一个包含九个表的联接。在仅TiKV的情况下,需要两个索引合并联接和六个哈希联接,并使用索引查询两个表(CUSTOMER和OORDER)。此计划需要1.13秒,优于在仅使用TiFlash的情况下使用8个哈希联接,该案例需要1.64秒。在TiKV和TiFlash案例中,其开销进一步减少,其中物理计划几乎保持不变,除了在六个哈希联接中扫描来自TiFlash的数据。此改进将执行时间缩短到0.55秒。在三个查询中,仅使用TiKV或Ti-Flash获得不同的性能,并组合它们可获得最佳结果。
对于Q1, Q4, Q6, Q11, Q13, Q14和Q19,仅TiFlash案例的性能优于仅TiKV案例,而TiKV和TiFlash案例的性能与仅TiFlash案例的性能相同。这七个查询的原因不同。Q1和Q6主要是单个表上的聚合组合,因此在TiFlash中的列存储上运行成本更低,是最佳选择。这些结果突出了先前工作中描述的柱存储的优点。Q4和Q11在每种情况下都使用相同的物理计划单独执行。但是,从TiFlash扫描数据比TiKV便宜,因此仅TiFlash情况下的执行时间更少,也是最佳选择。Q13、Q14和Q19都包含一个双表联接,该联接作为哈希联接实现。尽管仅TiKV-only在探测哈希表时采用索引读取器,但它也比从TiFlash扫描数据更昂贵。
Q9是多联接查询。在仅TiKV的情况下,它使用索引对某些表采用索引合并联接。它比在TiFlash上执行哈希联接便宜,因此它成为最佳选择。Q7、Q20和Q21会产生类似的结果,但由于空间有限,结果被消除。其余8个22个TPC-H查询在三个存储设置中具有可比的性能。
此外,我们使用500个仓库的CH-benCHmark的22个分析查询对TiSpark与SparkSQL、PrestoDB和Greenplum进行比较。每个数据库都安装在六台服务器上。对于SparkSQL和PrestoDB,数据存储为Hive中的列parquet文件。图9比较了这些系统的性能。TiSpark的性能可与SparkSQL媲美,因为它们使用相同的引擎。性能差距相当小,主要来自访问不同的存储系统:扫描压缩parquet文件花费代价更小,因此SparkSQL通常优于TiSpark。但是,在某些情况下,TiSpark可以将更多计算推送到存储层,但这种优势是抵消的。将TiSpark与PrestoDB和Greenplum进行比较是SparkSQL(TiSpark的基础引擎)与其他两个引擎的比较。但是,这超出了本文的范围,我们不会详细讨论。
图9:CH-benCHmark上的分析查询性能比较
6.4 HTAP性能
除了调查事务处理(TP)和分析处理(AP)性能,我们还根据整个CH-benCHmark以及单独的事务客户端(TC)和分析客户端(AC)评估TiDB的混合工作负载。这些实验是在100个仓库进行的。数据加载到TiKV中,并同时复制到TiFlash中。TiKV部署在三台服务器上,由TiDB SQL引擎实例访问。TiFlash部署在其他三台服务器上,并与其他TiSpark实例并合。此配置分别提供分析和事务查询。每次跑步时间为10分钟,热身时间为3分钟。我们测量了TP和AP工作负载的吞吐量和平均延迟。
图10(a)和10(b)显示了具有不同数量的TP客户端和AP客户端的事务的吞吐量和平均延迟(分别的)吞吐量随着TP客户端的增加而增加,但达到最大值时略低于512个客户端。对于相同数量的TP客户端,与没有AP客户端相比,更多的分析处理客户端最多会降低TP吞吐量10%。这证实了TiKV和TiFlash之间的日志复制实现了高隔离,尤其是与第6.6节中的MemSQL性能相反。此结果与[24]中的结果类似。
图10:TiDB的HTAP性能
事务的平均延迟在没有上限的情况下增加。这是因为即使更多的客户端发出更多的重任务,它们也不能立即完成,必须等待。等待时间是延迟增加的一部分。
图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 所示。
表4:分布计数的可视化延迟
图11:日志复制可视化的延迟
如图11(a)所示,10个仓库的日志复制延迟始终小于300ms,并且大多数延迟小于100毫秒。图11(b)显示,延迟增加与100个软件屋;大多数小于10ms。表4提供了更精确的细节。在10个仓库中,无论客户端设置如何,几乎99%的查询成本都低于500ms。在100个仓库中,分别有2个和32个分析客户端的查询量低于99%和85%。这些指标强调TiDB可以保证HTAP工作负载的数据新鲜度约为1秒。
在比较图11(a)和图11(b)时,我们观察到延迟时间与数据大小有关。仓库越大,延迟越大,因为更多的数据会引入更多的日志进行同步。此外,延迟还取决于分析请求的数量,但由于事务客户端的数量,因此损失较少。这可以在图11(b)中清楚地看到。32个AC比两个AC导致更多的延迟。但是,对于相同数量的分析客户端,延迟没有很大差异。我们在表4中显示更精确的结果。拥有100个仓库和两个AC,超过80%的查询需要小于100ms,但32个AC少于50%的查询需要不到100ms。这是因为更多的分析查询会以更高的频率诱导日志复制。
6.6 对比MemSQL
MemSQL的HTAP性能
我们使用CH-benC-Hmark将TiDB与MemSQL 7.0进行比较。本实验旨在强调最先进的HTAP系统的隔离问题,而不是OLTP和OLAP性能。MemSQL是一个分布式关系数据库,可大规模处理事务和实时分析。MemSQL部署在六台服务器上:一台主服务器、一台聚合器和四台服务器。我们将100个仓库加载到MemSQL中,并运行了各种数量的AP和TP客户端的基准。基准运行10分钟,5分钟的热身期。
与图10相比,图12说明了工作负载干扰对MemSQL的性能有显著影响。特别是,随着AP客户端数量的增加,事务吞吐量显著减慢,下降五倍以上。AP吞吐量也会随着TP客户端的增加而降低,但这种效果没有标记,因为事务查询不会重新询问分析查询的大量资源。
7. 相关工作
构建HTAP系统的常见方法包括:从现有数据库演变、扩展开源分析系统或从头开始构建。TiDB是从头开始构建的,在体系结构、数据发起、计算引擎和一致性保证方面与其他系统不同。
从现有数据库演变的数据库。成熟的数据库可以基于现有产品支持HTAP解决方案,并且它们尤其侧重于加速分析查询。他们采用自定义方法,分别实现数据一致性和高可用性。相比之下,TiDB自然会从Raft中的日志复制中获得好处,以实现数据一致性和高可用性。
Oracle[19]于2014年推出了数据库内存选项,成为业界首款双格式内存RDBMS。此选项旨在打破分析查询工作负荷中的性能障碍,同时不影响(甚至改善)常规事务工作负载的性能。列存储是只读快照,在时间点一致,并使用完全联机的重新填充机制进行更新。Oracle的后期工作[27]介绍了其分布式体系结构的高可用性方面,并提供容错分析查询执行。
SQL Server[21]将两个专用存储引擎集成到其核心中:用于分析工作负载的阿波罗列存储引擎和用于事务性工作负载的Hekaton内存引擎。数据迁移任务定期将数据从Hekaton表的尾部复制到压缩列存储区。SQL Server使用列存储索引和批处理来高效地处理分析查询,使用SIMD[15]进行数据扫描。
SAP HANA支持高效评估单独的OLAP和OLTP查询,并为每个查询使用不同的数据组织。为了扩展OLAP性能,它异步地将行存储数据复制到分布在服务器群集上的列存储[22]。此方法提供具有子秒可见性的MVCC数据。但是,处理错误和保持数据一致性需要付出大量努力。重要的是,事务引擎缺乏高可用性,因为它只部署在单个节点上。
开源数据库。Apache Spark是用于数据分析的开源框架。它需要一个事务模块来实现HTAP。下面列出的许多系统都遵循此理念。TiDB并不深深依赖于Spark,因为Tispark是一种扩展。TiDB是一个独立于TiSpark之外的HTAP数据库。
Wild-fire[10, 9]基于Spark构建HTAP引擎。它处理同一列数据组织(即Parquet)上的分析和事务请求。它采用乐观锁的语义进行并发更新,对读取采用快照隔离。对于高可用性,分片日志将复制到多个节点,无需共识算法的帮助。分析查询和事务查询可以在单独的节点上处理;但是,在处理最新更新时存在明显的延迟。对于大型HTAP工作负载,Wild-fire使用统一的多版本和多区域索引方法[23]。
SnappyData[25]为OLTP、OLAP和流分析提供了一个统一的平台。它集成了用于高吞吐量分析(Spark)的计算引擎和扩展内存事务存储(GemFire)。最近的更新以行格式存储,然后老化为分析查询的列格式。使用GemFire的Paxos实现遵循2PC协议,以确保在整个群集中达成共识和一致的观点。
从头开始构建的数据库。许多新的HTAP系统已经调查了混合工作负载的不同,包括利用内存计算来提高性能、优化数据存储和可用性。与TiDB不同,它们不能同时提供高可用性、数据一致性、可扩展性、数据新鲜度和隔离性。
MemSQL[3]具有可扩展的内存OLTP和快速分析查询的引擎。MemSQL可以以行或列格式存储数据库表。它可以以行格式保留部分数据,并将其转换为列格式,以在将数据写入磁盘时进行快速分析。它将重复查询编译为更低级机器代码以加速分析查询,并使用许多无锁结构来帮助事务处理。但是,在运行HTAP工作负载时,它不能为OLAP和OLTP提供隔离性能。
HtPer[18]使用操作系统的系统调用fork来为分析工作提供快照隔离。其较新版本采用MVCC实现,提供可序列化、快速的跨动作处理和快速扫描。ScyPer[26]扩展HyPer,通过使用逻辑或物理重做日志传播更新,在远程副本上大规模评估分析查询。
BatchDB[24]是专为HTAP工作负载设计的内存数据库引擎。它依赖于具有专用副本的初级辅助复制,每个副本针对特定工作负载类型(即OLTP或OLAP)进行了优化。它最大限度地减少了事务引擎和分析引擎之间的负载交互,从而在HTAP工作负载的严格SLA下,能够对全新数据进行实时分析。请注意,它在行格式副本上执行分析查询,并且不保证高可用性。
L-Store(Lineage-Based data store)[35]通过引入基于更新的、基于Lineage的存储体系结构,将实时分析和事务查询处理结合在一个统一引擎中。该存储在本机多版本列存储模型上启用无争用更新机制,以便从写入优化的列格式到读取优化的列式布局中,以平稳和独立地将稳定数据阶段为读取优化的列式布局。
Peloton[31]是一个自动驾驶的SQL数据库管理系统。它尝试在运行时调整HTAP工作负载的数据源[8]。它使用无锁的多版本并发控制支持端口实时分析。但它是单节点的内存数据库。
Cockroach DB[38]是一个分布式SQL数据库,提供高可用性、数据一致性、可扩展性和隔离性。与TiDB一样,它建立在Raft算法之上,支持分布式事务。它提供了更强的隔离属性:可序列化,而不是快照隔离。但是,它不支持专用OLAP或HTAP功能。
8. 结论
我们提出了一个可用于生产环境的HTAP数据库:TiDB。TiDB构建在TiKV之上,TiKV是一个分布式、基于行的存储,它使用Raft算法。我们引入列学习者角色进行实时分析,这些分析异步地从TiKV复制日志,并将行格式数据转换为列格式。TiKV和TiFlash之间的此类日志副本提供实时数据一致性,且开销很小。TiKV和TiFlash可以部署在不同的物理机上,以高效地处理事务查询和分析查询。TiDB尽可能的使用它们,以便在扫描事务查询和分析查询的表时访问它们。实验结果表明,TiDB在HTAP基准CH-benCHmark下表现良好。TiDB提供了一个通用解决方案,将NewSQL系统发展为HTAP系统。
9. 引用
- [1] Clickhouse. https://clickhouse.tech.
- [2] LZ4. https://github.com/lz4/lz4.
- [3] MemSQL. https://www.memsql.com.
- [4] Parquet. https://parquet.apache.org.
- [5] RocksDB. https://rocksdb.org.
- [6] Sysbench. https://github.com/akopytov/sysbench.
- [7] TiDB. https://github.com/pingcap/tidb.
- [8] J. Arulraj, A. Pavlo, and P. Menon. Bridging the Archipelago between Row-Stores and Column-Stores for Hybrid Workloads. In SIGMOD, pages 583–598. ACM, 2016.
- [9] R. Barber, C. Garcia-Arellano, R. Grosman, R. Muller, et al. ¨ Evolving Databases for New-Gen Big Data Applications. In CIDR. www.cidrdb.org, 2017.
- [10] R. Barber, M. Huras, G. M. Lohman, C. Mohan, et al. Wildfire: Concurrent Blazing Data Ingest and Analytics. In SIGMOD, pages 2077–2080. ACM, 2016.
- [11] R. Cattell. Scalable SQL and NoSQL data stores. SIGMOD Rec., 39(4):12–27, 2010.
- [12] F. Chang, J. Dean, S. Ghemawat, W. C. Hsieh, D. A. Wallach, M. Burrows, T. Chandra, A. Fikes, and R. Gruber. Bigtable: A Distributed Storage System for Structured Data. In OSDI, pages 205–218. USENIX Association, 2006.
- [13] R. L. Cole, F. Funke, L. Giakoumakis, W. Guy, et al. The mixed workload CH-benCHmark. In DBTest 2011, page 8. ACM, 2011.
- [14] J. C. Corbett, J. Dean, M. Epstein, A. Fikes, et al. Spanner: Google’s Globally Distributed Database. ACM Trans. Comput. Syst., 31(3):8:1–8:22, 2013.
- [15] Z. Fang, B. Zheng, and C. Weng. Interleaved Multi-Vectorizing. PVLDB, 13(3):226–238, 2019.
- [16] A. Floratou, U. F. Minhas, and F. Ozcan. SQL-on-Hadoop: ¨ Full Circle Back to Shared-Nothing Database Architectures. PVLDB, 7(12):1295–1306, 2014.
- [17] G. Graefe. Volcano - An Extensible and Parallel Query Evaluation System. IEEE Trans. Knowl. Data Eng., 6(1):120–135, 1994.
- [18] A. Kemper and T. Neumann. HyPer: A hybrid OLTP&OLAP main memory database system based on virtual memory snapshots. In ICDE, pages 195–206. IEEE Computer Society, 2011.
- [19] T. Lahiri, S. Chavan, M. Colgan, D. Das, A. Ganesh, et al. Oracle Database In-Memory: A dual format in-memory database. In ICDE, pages 1253–1258. IEEE Computer Society, 2015.
- [20] L. Lamport. The Part-Time Parliament. ACM Trans. Comput. Syst., 16(2):133–169, 1998.
- [21] P. Larson, A. Birka, E. N. Hanson, W. Huang, M. Nowakiewicz, and V. Papadimos. Real-Time Analytical Processing with SQL Server. PVLDB, 8(12):1740–1751, 2015.
- [22] J. Lee, S. Moon, K. H. Kim, D. H. Kim, S. K. Cha, W. Han, C. G. Park, H. J. Na, and J. Lee. Parallel Replication across Formats in SAP HANA for Scaling Out Mixed OLTP/OLAP Workloads. PVLDB, 10(12):1598–1609, 2017.
- [23] C. Luo, P. Toz¨ un, Y. Tian, R. Barber, et al. Umzi: Unified ¨ Multi-Zone Indexing for Large-Scale HTAP. In EDBT, pages 1–12. OpenProceedings.org, 2019.
- [24] D. Makreshanski, J. Giceva, C. Barthels, and G. Alonso. BatchDB: Efficient Isolated Execution of Hybrid OLTP+OLAP Workloads for Interactive Applications. In SIGMOD, pages 37–50. ACM, 2017.
- [25] B. Mozafari, J. Ramnarayan, S. Menon, Y. Mahajan, S. Chakraborty, H. Bhanawat, and K. Bachhav. SnappyData: A Unified Cluster for Streaming, Transactions and Interactive Analytics. In CIDR. www.cidrdb.org, 2017.
- [26] T. Muhlbauer, W. R ¨ odiger, A. Reiser, A. Kemper, and ¨ T. Neumann. ScyPer: A Hybrid OLTP&OLAP Distributed Main Memory Database System for Scalable Real-Time Analytics. In DBIS, volume P-214 of LNI, pages 499–502. GI, 2013.
- [27] N. Mukherjee, S. Chavan, M. Colgan, M. Gleeson, X. He, et al. Fault-tolerant real-time analytics with distributed Oracle Database In-memory. In ICDE, pages 1298–1309. IEEE Computer Society, 2016.
- [28] P. E. O’Neil, E. Cheng, D. Gawlick, and E. J. O’Neil. The Log-Structured Merge-Tree (LSM-Tree). Acta Inf., 33(4):351–385, 1996.
- [29] D. Ongaro and J. K. Ousterhout. In Search of an Understandable Consensus Algorithm. In USENIX ATC, pages 305–319. USENIX Association, 2014.
- [30] F. Ozcan, Y. Tian, and P. T ¨ oz¨ un. Hybrid ¨ Transactional/Analytical Processing: A Survey. In SIGMOD, pages 1771–1775. ACM, 2017.
- [31] A. Pavlo, G. Angulo, J. Arulraj, H. Lin, J. Lin, et al. Self-Driving Database Management Systems. In CIDR. www.cidrdb.org, 2017.
- [32] A. Pavlo and M. Aslett. What’s Really New with NewSQL? SIGMOD, 45(2):45–55, 2016.
- [33] D. Peng and F. Dabek. Large-scale Incremental Processing Using Distributed Transactions and Notifications. In OSDI, pages 251–264. USENIX Association, 2010.
- [34] I. Psaroudakis, F. Wolf, N. May, T. Neumann, A. Bohm, ¨ A. Ailamaki, and K. Sattler. Scaling Up Mixed Workloads: A Battle of Data Freshness, Flexibility, and Scheduling. In TPCTC, volume 8904, pages 97–112. Springer, 2014.
- [35] M. Sadoghi, S. Bhattacherjee, B. Bhattacharjee, and M. Canim. L-Store: A Real-time OLTP and OLAP System. In EDBT, pages 540–551. OpenProceedings.org, 2018.
- [36] S. Sivasubramanian. Amazon dynamoDB: a seamlessly scalable non-relational database service. In SIGMOD, pages 729–730. ACM, 2012.
- [37] M. Stonebraker and U. C¸ etintemel. “One Size Fits All”: An Idea Whose Time Has Come and Gone (Abstract). In ICDE, pages 2–11. IEEE Computer Society, 2005.
- [38] R. Taft, I. Sharif, A. Matei, N. VanBenschoten, J. Lewis, et al. CockroachDB: The Resilient Geo-Distributed SQL Database. In SIGMOD, pages 1493–1509. ACM, 2020.