0
2
2
0
专栏/.../

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

 数据源的TiDB学习之路  发表于  2024-01-04

人到中年,越来越发现一个道理,那就是人要不断的学习、不停的卷自己,才不至于被落后。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)。

image.png

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

image.png

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

二. TiDB的架构

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

图-TiDB的架构

image.png

(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存储

图-multi-Raft存储架构

image.png

(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中。

image.png

2.Delta Tree

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

image.png

新写入的增量数据是插入或删除范围的原子批处理。这些增量缓存在内存中并物化到磁盘。增量按写入顺序存储,实现了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.png

乐观事务处理流程为:

(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的数据库专家!

0
2
2
0

版权声明:本文为 TiDB 社区用户原创文章,遵循 CC BY-NC-SA 4.0 版权协议,转载请附上原文出处链接和本声明。

评论
暂无评论