这篇论文是TiDB在今年被VLDB收录，论文中TiDB的定位是Real-time HTAP，难点是：既要实现TP和AP的隔离，执行期间互不干扰；又要实现TP和AP之间的数据延迟，能够基于最新鲜的数据做AP分析。

TiDB的核心想法是：

1. 在raft的learner副本上构建OLAP，实时的把行存转成TiFlash集群中的列存，实现TP和AP在物理上隔离，同时通过multi-raft group的并行复制能保证AP的数据实时性；

2. 列存引擎实现了不同于LSM的DeltaTree，避免大范围读取的多路归并的读放大问题，牺牲了一定的写入性能；

3. 通过Raft中的ReadIndex实现TiFlash和TiKV的一致性读（有一定的延时，但是很低，参考第一点），进而就可以实现同一条sql既可以读取行存，又可以读取列存。因此，优化器的物理扫描路径除了能探索TiKV的seqscan和indexscan，还能探索TiFlash的列存读；

下面进入正文，

ABSTRACT

HTAP数据库的挑战：

1. 如何隔离TP和AP两类查询，防止相互干扰；
2. 如何使AP能尽量读取新的一致性的数据；

TiDB是一个基于Raft算法实现的HTAP系统。核心思想是提供两套存储引擎：

1. TiKV：通过multi-Raft算法实现行存引擎，处理TP的更新和查询；
2. TiFlash：给raft算法增加learner角色，异步地从leader同步log到列存引擎TiFlash，把行存格式转成列存。learner不参与raft算法多数派的表决，因此不会影响TP的写入性能；
3. 对于一条SQL，优化器可以选择行存还是列存，并不是TP一定走TikKV， AP一定走TiFlash。TP型查询有时可能走TiFlash性能更好（检查约束时选择列存读取数据量少），同理AP型查询走TP索引也许能更好（行存上有索引）；

1. INTRODUCTION

DBMS的强大在于：关系模型，事务，SQL。传统的DBMS不原生提供扩展性和高可用性。在2000年开始，互联网中出现了NoSQL系统，比如：Google Bigtable和DynamoDB。NoSQL放宽了一致性的要求，提供了扩展性和丰富的数据模型（kv，graph，document）。然而有很多系统仍然需要事务，数据一致性和SQL的支持。于是NewSQL出现了，如：CockroachDB和Google Spanner。相比传统DB，NewSQL提供了扩展性，同时维护ACID。同一时期，基于SQL的Onlie Analytical Processinging（OLAP)也迅速的发展，比如各种SQL-on-Hadoop方案。

这些系统遵循“one size does not fit all”，OLTP和OLAP对应不同的数据模型和查询技术。对于业务同时需要TP和AP时，就需要开发维护两套技术栈。另外，部分业务需要对对最新的数据进行OLAP分析。这就是HTAP技术产生的背景。HTAP系统应该提供扩展性，高可用性，事务。相比单独的TP和AP产品，HTAP有2个不同的要求：freshness和isolation

freshness意味尽可能的分析最新的数据，实时分析最新的数据有巨大的业务价值。现有的HTAP并不能保证freshness，比如通过ETL来导数据的HTAP。尽管能通过定期的小批量的导数据，仍然需要小时级别。另外，也可以用streaming的方式同步来减小同步时间。然而这两种方式都缺少全局数据管理模型，如何保证数据的一致性很复杂。多个系统之间通过导数据的方式也引入了额外的负载和复杂度。

isolation意味着OLTP和OLAP互不影响性能。一些in-memory的系统比如：HyPer，为了AP能读取最新的数据，AP和TP在相同的物理server上处理，这种方式虽然能读取最新的数据，但是不能同时使AP和TP达到高性能。在SAP HANA上进行的测试，OLTP和OLAP在相同机器上混合跑，会使得TP性能下降3到5倍。MemSQL也是相同的测试数据。

为了实现隔离，TP和AP要跑在不同的机器上，那就需要维护AP和TP之间的数据同步，数据一致性和高可用性。高可用可以通过分布式一致性算法来实现，如：Paxos，Raft。基于复制状态机同步副本数据，同时，可以对副本扩展，使其能提供AP的读服务。

TiDB就是基于Raft的HTAP。在Raft算法中引入了learner角色，异步的从leader同步日志，构造新的副本来提供OLAP的查询。learner把leader上的行存转成列存，更好的利用AP相关优化技术。同时learner和leader之间复制延迟足够低（multi raft group），保证能提供最新的数据。不同的副本服务于OLAP和OLTP，从物理上隔离这种不同的负载，同时通过Raft算法，提供高可用，扩展性和数据一致性。

TiDB贡献如下：

1. 提出基于一致性算法构建HTAP系统，并relase了基于Raft 的HTAP数据库；
2. Raft算法增加learner角色，同步log，并转成列存，提供实时数据OLAP服务；
3. 实现multi-Raft的存储，同时优化读写，提供高性能和高扩展；
4. 构建HTAP的优化器，根据代价选择行存还是列存；
5. 深入测试TiDB的OLAP，OLTP，HTAP的性能数据；

2. RAFT-BASED HTAP

通过一致性算法构建HTAP系统，既能TP和AP物理上隔离，又能保证数据复制的实时性。

Multi-Raft group中每个group都有一个leader和多个follwer，增加一个learner角色，从leader同步log，并转成列存。该learner不参与多数派的投票，因此不会阻塞TP的写入。

对优化器进行扩展，根据代价模型能选择行存或列存，或者在一条SQL同时使用两种存储。

leader和follower之间的log同步是实时的，leader和learner之间的日志同步是异步的，可能会落后很多，由于是多个Raft Group并行的复制，实际上延迟很低。

3. ARCHITECTURE

3个核心组件：分布存储层，Placement Driver，计算引擎层；

存储层分为行存的TiKV和TiFlash。逻辑上，TiKV中是有序的kv对。每个数据库概念中的tuple都应一条kv。

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

Region： 把key值空间按照range分区，每个分区称为一个Region。每个Region对应一个Raft Group，每个Raft Group中有且仅有一个leader，多个follwer，leader异步的将log同步给TiFlash集群。

Placement Driver负责维护Region：每个Region部署在哪几台机器上，自动的对region进行迁移，达到负载均衡；分发timestamp，提供严格递增且全局唯一的timestamp，这些timestamp做为事务ID。为了避免PD单点，PD也是多节点部署，但是PD上不持久化任何状态，当PD启动时从其他PD上和TiKV上获取并且比对元信息。

SQL引擎层是无状态化可扩展的，基于cost-based的优化器和分布式执行器。基于Percolator实现2PC协议用于事务commit过程。

可以看到TiDB中每个组件满足高可用和扩展性。

除了上面的3个组价，TiDB还适配了Spark，集成TiDb的数据和HDFS生态。

4. MULTI-RAFT STORAGE

TiKV在同步log到TiFlash允许将多个Region合并成一个大的TiFlash的Region。

4.1 Row-based Storage (TiKV)

TiKV将tuple分成多region，每个region的副本分散在不同的机器上，因此每个机器上既有leader，也有follower（其他region），这是一个典型的multi-raft group存储系统。

每个TiKV server上使用RocksDB存储数据和元数据。每个region默认大小是96MB，只有leader能提供读写服务。

4.1.1 Optimization between Leaders and Followers

原生Raft算法在工程实践上可以进行优化：pipeline复制+顺序commit+异步apply

发生错误：由于是顺序commit，可以从出错的位置resend，可能会覆盖follower上的日志；

4.1.2 Accelerating Read Requests from Clients

提供线性一致性读：

1. read index：leader收到client的读请求后，记录当前log index为该请求的read index，然后需要确定2件事情：

1. 发送quorum请求，确认自己此时还是leader（避免stale leader，确认自己是leader之后仍然会发生leader选举，自己变成stale leader，但是仍有权处理该read请求）；
2. 等待该leader上日志的commit位点超过read index，这是为了满足复制状态机的要求；

2. lease read：为了避免每次读都要进行quorum确认自己是leader，因此通过租约来续约，保证一段之内自己是唯一leader，因此当触发leader选举后，需要等待一个租约的时间，等老leader自动降级；
3. follower read：follower也可以提供读服务，每次都需要到自己的leader上去确认当前的read index，并等待，只不过第1步的后续过程发生在follower上。

4.1.3 Managing Massive Regions

维护server的拓扑均衡：

1. 经过多轮次选leader，可能某个TiKV server上leader数目比其他server上多，出现热点server；
2. 动态的增加移除servers；
   PD通过心跳从region上收集信息，并收集server信息用来决策如何均衡。

4.1.4 Dynamic Region Split and Merge

维护region的均衡：

1. region数据集不均衡；
2. region负载不均衡；
   PD通过给TiKV server发送split或者merge指令来完成分裂或合并。
   merge时，只会合并相邻的region。
   split时，新产生的多个region中，最右侧的region仍然复用原先的raft group，其他region产生新的raft group对象，过程和新增raft group类似：
3. PD给待分裂region的leader发送spilt指令；
4. leader将split做为log复制给followers；
5. 达到多数派之后，leader commit这条split日志，所有副本在本地执行split过程：更新region的range，产生新的region，更新epoch meta，这个过程是原子的；
6. 新产生的region组成新的raft group，完成选主等过程，原leader汇报新的region到PD上；

3点需要注意：

1. split是在原replica上进行分裂，并不会移动数据，仅仅是操作metadata，因此过程很快，新的raftgroup向PD汇报；
2. 后续PD在进行负载均衡时会往新group上的移动数据，最终达到分裂+均衡的目的；
3. 在spilt过程中，如果发生了网络分区，落后的节点并没有收到split日志，它并不会split。当再次加入raft group中时，和原leader通信，也就是新region中最右侧的raft group。那么需要原leader兼容上一个epoch的拓扑，因为分区出去的follower它的region元信息还是之前老的。原leader会继续给这个分区的follower同步日志，直到它也apply了split日志，并执行了split过程。

4.2 Column-based Storage (TiFlash)

为了提高AP的性能，TiFlash是一个列存引擎。用户对一个table设置使用TiFlash的语法：

ALTER TABLE x SET TiFLASH REPLICA n;

列存类似表的索引；

同样的，在TiFlash中每个表分成多个region，它的region比tikv中的region要大，便于大范围的range scan；TiFlash副本刚刚创建出来后，TiKV中对应region的日志可能会回收了，无法从头复制日志到TiFlash中，此时直接同步snapshot data（raft中的概念）。

4.2.1 Log Replayer

只同步已经确定状态的事务日志：committed或者abort；

过程如下：

1）打包log：对一批次log进行打包，去除rollback相关的prewritten数据日志；

2）解码成行存格式，去除事务相关字段；

3）行存转成列存，当接收到的行存的数据量超过一定大小或者超过一定时间就开始转换。转换过程用的schema定期从tikv通过来过；

每条日志4部分组成：

{transaction ID}
{operation type}
[transaction status][@start ts][#commit ts]
{operation data}

上图中，在TiKV决定这8条日志做为一个批次进行打包，因为事务1进行rollback了，因此可以把这条日志和相关的prewritten删除掉，最后只剩下6条日志。

最终TiFlash转成5个列存数据文件，并应用到Delta Tree中：

1. 事务状态；
2. 事务ID；
3. 数据的key；
4. 数据的第一列；
5. 数据的第二列；

4.2.2 Schema Synchronization

1. TiKV引擎进程无需感知schema，仅仅负责存储字节流（SQL engine感知schema）；
2. SQL engine使用的schema是存在tikv中的字节流:
3. TiFlash需要感知最新的schema，它需要读取tikv中的字节流并deform：

1. TiFlash上有schema的cache来提高性能；
2. TiFlash上有schema syncer进程，定期从tikv主动拉取schema；
3. TiFlash 在发现同步过来的tuples类型和本地的schema不匹配时，主动拉取schema；

4.2.3 Columnar Delta Tree

一个region对应一个delta tree。

Stable space（列存）：

1. 将region中的tuple按照key分成一个个连续的chunk文件；
2. 以列存的形式组织，格式类似Parquet；
3. 将一个chunk的列存和对应元数据存在不同的文件中，并行的写磁盘；
4. LZ4压缩；

Delta space（行存）：

1. 从TiKV同步过来的一个batch数据先进入memory；
2. memory满了后append到Delta space，这些日志记录了对TiFlash的更新和删除，因此起到了TiFlash 的WAL的作用；
3. TiKV变更频繁时，TiFlash就有大量WAL，定期合并Delta小文件；
4. 内存中的Delta作用是，读取最新的变更；

当读取一个tuple时，需要逐个逆序的读所有的Delta和chunk文件，因为事先并不知道这个tuple存在哪些文件中，会有很大的读放大。

因此需要定期的把Delta合入Stable：把一个Delta文件和它相关联的chunk文件读入内存，并merge到一起。

TiDB引入了B+Tree来管理一个个的Delta文件，

key=行存的key+timestamp

作用:

1. 加速查询range，直接从Delta树中查找range的区间，并从叶子节点上定位到具体的Delta文件和chunk文件；
2. 加速单个key的读取，可以直接定位到这个key的所有更改；
3. 加速Delta和chunk的合并，直接全部遍历B+Tree，使得Delta有序；
   实验效果：消耗的时间是LSM的1/2，而且在不同的负载下表现一致；
   缺点：维护B+Tree和Delta文件，写放大比LSM大，在AP场景下可以接收的。

4.2.4 Read Process

和TiKV同样的，TiFlash也提供snapshot isolation：

1. TiFlash收到读请求；
2. TiFlash给leader发送当前的timestamp（数据包可能在网络中阻塞了，但是只需要第1步骤中的时间点数据）；
3. Leader返回该timestamp对应的日志位点；
4. TiFlash等待Delta文件同步到这个日志位点就可以开始进入读取流程了；

5. HTAP ENGINES

SQL引擎层的优化：

1. 对于TP，Percolator模型，实现了悲观锁和乐观锁；
2. 对于AP，CBO优化器，计算下推到存储层；

5.1 Transactional Processing

TiDB提供ACID事务特性，SI和RR隔离级别。实现上是基于MVCC，避免读-写锁，同时W-W保护。

一个事务设计到SQL，TiKV，PD：

1. SQL引擎：做为协调者推动事务前进，从client接收读写请求，转成TiKV能理解的kv，通过2PC写入TiKV server；
2. PD：管理逻辑Region和物理机器的映射，提供全局严格递增的timestamp；
3. TiKV：提供分布式事务接口，实现MVCC，持久化数据；

TiDB实现了乐观锁和悲观锁。Percolator模型，选择一个key做为primary，用它来记录事务的状态，基于2PC来提交事务。

乐观事务的过程如下：

1. SQL引擎收到"begin"后，从PD上获取一个timestamp，做为事务的start_ts；
2. 执行DML，从TiKV上读取数据到本地内存，并修改，保证读取到start_ts之前最新commit_ts的数据；
3. 收到"commit"，开始2PC，随机选择key做为primarykey，并发的锁住所有的key（防止W-W冲突），并发的发送prewrite给TiKV节点；
4. 当所有prewrites成功后，再请求PD获取一个timestmap，做为commit_ts，给TiKV发送commit消息，TiKV标记primarykey为commit状态；
5. SQL引擎返回成功client；
6. SQL引擎commit所有的secondarykey，并发的清空所有key的锁，发送commit消息；

悲观锁和乐观锁的区别是获取锁的时机，悲观锁是在执行事务提交之前2PC之前就尝试获取锁。

悲观锁实现中，在开始上锁前获取一个update_ts；如果上锁失败，不需要rollback并且重试整个事务，只需要重试事务，时间点使用update_ts做为start_ts。因此，其他事务读取数据是，可见性判断使用update_ts来判断，以实现RR隔离级别。

对于RC和RR的区别：TiKV的一个事务在上锁时，必须检测出读写冲突，另外一个事务尝试读取一个已经上锁的key；而RC可以忽略读写冲突，因此在悲观锁中，可以直观的实现RC。

TiDB的分布式事务不依赖中心化的锁管理器。锁信息是存在TiKV上，TiKV是分布式的，因此提供了高扩展性和可同性。同时SQL引擎和PD也可以扩展。

从PD获取的timestamp包含物理时间和逻辑时间2部分（类似HLC），物理时间精度是毫秒，18位来表示逻辑时间，因此理论上一个毫秒能处理65536个事务，这足够了。

5.2 Analytical Processing

5.2.1 Query Optimization in SQL Engine

TiDB实现了2阶段的优化器：rule-based + cost-based。

RBO：列裁剪，下推，表达式推导，常量展开，groupby下推，子查询去关联化；

物理优化时，优化器感知TiKV 扫描，TiKV索引扫描，TiFlash扫描；

索引能加速点查，但是索引的实时更新会影响事务的写入性能。

TiDB采用异步构建索引。每个region一份索引：

unique key在索引中的key

Key: {table{tableID} index{indexID} indexedColValue}
Value: {rowID}

non-unique key在索引中的key

Key: {table{tableID} index{indexID} indexedColValue rowID}
Value: {null}

在使用索引之前，需要通过2分搜索定位region包含到相关的索引，使用skyline剪枝算法消除不同查询条件中的无用候选索引。

执行模型是pulling模式。把计算下推到存储层，存储层也可以做简单的表达式计算，该组件称为coprocessor。coprocessor并行的执行计划树中的子树，减少了传给SQL 引擎的数据量。

目前，TiDB并没有实现MPP真正的并行计算，并行依靠存储层执行简单的表达式，结果还是需要汇总到单节点上。

5.2.2 TiSpark

TiDB适配了Spark，使得能够利用Spark的计算能力，比如machine learning库。

1. 从TiKV读取元数据，构建Spark的catalog；
2. Spark driver从PD获取timestamp，以便从TiKV中读取MVCC数据，提供一致性快照；
3. 为了是从coprocessor，支持从TiFlash读取列存数据，再组装成行存，返回给Spark workers；

5.3 Isolation and Coordination

由于MVCC的设计，以及learner上的read index机制，TiKV和TiFlash之间的数据是一致的。因此一条sql可以部分表从TiKV上读取，部分表从TiFlash读取。

优化在物流搜索空间可以扩大到：

1. row scan；
2. index scan；
3. column scan；

三种扫描方式有不同的代价和property。row scan和columnscan返回的数据primary key有序的，indexscan返回的数据索引key有序。代价取决于大小，以及每个region上有tuple数目（tikv和tiflash不同）。

行存和列存混合的场景：

select T.*, S.a from T join S on T.b=S.b where T.a between 1 and 100

T和S在a上都有索引和column，最优的计划是：使用行存scan表T，因为T上有范围过滤，使用索引更快速；使用列存scan表S，S只访问到了2个列。

同样的：

1. AP型查询的小范围或点查可以走tikv；
2. TP型的约束检查也可以走tiflash；

6. EXPERIMENTS

开发了CH-benCHmark用来构造AP和TP的混合负载：使用标准的TPC-C，TPC-H的schema适配到TPC-C。

100个warehouse需要70GB的内存。

6.2 OLTP Performance

CRDB是CockroachDB

图a：高并发+小数据量 导致冲突大，256时乐观锁性能开始下降；

通常乐观锁比悲观锁性能好，除非图a中的场景（高并发+小数据量）

tidb吞吐比CRDB高：

1）事务处理的优化；

2）raft算法的优化；

6.3 OLAP Performance

优化器在选择TiKV和TiFlash时性能几乎都是最优的。

Q8和Q12中tikv的耗时比tiflash少，而Q22则相反。在AP中列存并不总是比行存优。混合使用TiKV和TiFlash时性能是最好的。

对于Q12，2表join，TiKV使用了index join，TiFlash使用了hash joni。而同时使用TiKV和TiFlash时，从列存TiFlash中读取A的列，并到行存TiKV中查找B的索引，最大程度的减少读取量。整体消耗的时间缩小一半。

对于Q8，9个表join，对于TiKV，前面2个表使用index join，后面6个使用hashjoin。同样的物理计划，同时使用TiKV和TiFlash，后面6个表从tiflash读取，性能提升1倍；

使用500个warehouse的数据量，对别了TiSpark, SparkSQL, PrestoDB, Greenplum。

TiSpark和SparkSQL性能接近，比其他低，TiDB暂时还没有MPP的并行执行。

6.4 HTAP Performance

图a和b，增加TP的并发数，统计吞吐和延迟，同时在每个TP的并发度上，逐个增加个AC的并发度。

表明：在任何时候，AP的并发度增加对TP的性能只有不到10%影响。

图c和d，表明TP对AP的影响小于5%。

6.5 Log Replication Delay

延迟和数据量，AP并发相关；

AP会触发log频繁的同步（tiflash数据不够新时，主动的按拉取）

6.6 Comparison to MemSQL

随着AP增长，TP性能下降5倍。

7. RELATED WORK

Oracle在2014年推出了In-Memory列存，首次在业界提供了dual-format的HTAP方案。列存是在内存中的只读的，行存更新时后台进程异步的转成列存，并实现向量化，压缩等优化。后续Oracle又推出了高可用版本的ap执行引擎。

SQL server在存储层整合了2套存储：Apollo的列存，Hekaton in-memory的行存。数据定期从Hekaton的尾巴同步到Apollo。另外，还实现了批处理和向量化加速AP。

SAP HAHA支持AP和TP分离，从行存同步数据到列存。AP和TP数据一致性和出错处理比较复杂。

TiDB通过multi-Raft的learner，实现AP和TP分裂，也保证了AP和TP之间的数据一致性。可惜没有提供和上述产品横向的数据对比。