這篇論文是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資料庫的挑戰：

如何隔離TP和AP兩類查詢，防止互相幹擾；
如何使AP能盡量讀取新的一緻性的資料；

TiDB是一個基于Raft算法實作的HTAP系統。核心思想是提供兩套存儲引擎：

TiKV：通過multi-Raft算法實作行存引擎，處理TP的更新和查詢；
TiFlash：給raft算法增加learner角色，異步地從leader同步log到列存引擎TiFlash，把行存格式轉成列存。learner不參與raft算法多數派的表決，是以不會影響TP的寫入性能；
對于一條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貢獻如下：

提出基于一緻性算法建構HTAP系統，并relase了基于Raft 的HTAP資料庫；
Raft算法增加learner角色，同步log，并轉成列存，提供實時資料OLAP服務；
實作multi-Raft的存儲，同時優化讀寫，提供高性能和高擴充；
建構HTAP的優化器，根據代價選擇行存還是列存；
深入測試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

提供線性一緻性讀：

read index：leader收到client的讀請求後，記錄目前log index為該請求的read index，然後需要确定2件事情：

1. 發送quorum請求，确認自己此時還是leader（避免stale leader，确認自己是leader之後仍然會發生leader選舉，自己變成stale leader，但是仍有權處理該read請求）；
2. 等待該leader上日志的commit位點超過read index，這是為了滿足複制狀态機的要求；

lease read：為了避免每次讀都要進行quorum确認自己是leader，是以通過租約來續約，保證一段之内自己是唯一leader，是以當觸發leader選舉後，需要等待一個租約的時間，等老leader自動降級；
follower read：follower也可以提供讀服務，每次都需要到自己的leader上去确認目前的read index，并等待，隻不過第1步的後續過程發生在follower上。

4.1.3 Managing Massive Regions

維護server的拓撲均衡：

經過多輪次選leader，可能某個TiKV server上leader數目比其他server上多，出現熱點server；
動态的增加移除servers；

PD通過心跳從region上收集資訊，并收集server資訊用來決策如何均衡。

4.1.4 Dynamic Region Split and Merge

維護region的均衡：

region資料集不均衡；
region負載不均衡；

PD通過給TiKV server發送split或者merge指令來完成分裂或合并。

merge時，隻會合并相鄰的region。

split時，新産生的多個region中，最右側的region仍然複用原先的raft group，其他region産生新的raft group對象，過程和新增raft group類似：
PD給待分裂region的leader發送spilt指令；
leader将split做為log複制給followers；
達到多數派之後，leader commit這條split日志，所有副本在本地執行split過程：更新region的range，産生新的region，更新epoch meta，這個過程是原子的；
新産生的region組成新的raft group，完成選主等過程，原leader彙報新的region到PD上；

3點需要注意：

split是在原replica上進行分裂，并不會移動資料，僅僅是操作metadata，是以過程很快，新的raftgroup向PD彙報；
後續PD在進行負載均衡時會往新group上的移動資料，最終達到分裂+均衡的目的；
在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中：

事務狀态；
事務ID；
資料的key；
資料的第一列；
資料的第二列；

4.2.2 Schema Synchronization

TiKV引擎程序無需感覺schema，僅僅負責存儲位元組流（SQL engine感覺schema）；
SQL engine使用的schema是存在tikv中的位元組流:
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（列存）：

将region中的tuple按照key分成一個個連續的chunk檔案；
以列存的形式組織，格式類似Parquet；
将一個chunk的列存和對應中繼資料存在不同的檔案中，并行的寫磁盤；
LZ4壓縮；

Delta space（行存）：

從TiKV同步過來的一個batch資料先進入memory；
memory滿了後append到Delta space，這些日志記錄了對TiFlash的更新和删除，是以起到了TiFlash 的WAL的作用；
TiKV變更頻繁時，TiFlash就有大量WAL，定期合并Delta小檔案；
記憶體中的Delta作用是，讀取最新的變更；

當讀取一個tuple時，需要逐個逆序的讀所有的Delta和chunk檔案，因為事先并不知道這個tuple存在哪些檔案中，會有很大的讀放大。

是以需要定期的把Delta合入Stable：把一個Delta檔案和它相關聯的chunk檔案讀入記憶體，并merge到一起。

TiDB引入了B+Tree來管理一個個的Delta檔案，

key=行存的key+timestamp

作用:

加速查詢range，直接從Delta樹中查找range的區間，并從葉子節點上定位到具體的Delta檔案和chunk檔案；
加速單個key的讀取，可以直接定位到這個key的所有更改；
加速Delta和chunk的合并，直接全部周遊B+Tree，使得Delta有序；

實驗效果：消耗的時間是LSM的1/2，而且在不同的負載下表現一緻；

缺點：維護B+Tree和Delta檔案，寫放大比LSM大，在AP場景下可以接收的。

4.2.4 Read Process

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

TiFlash收到讀請求；
TiFlash給leader發送目前的timestamp（資料包可能在網絡中阻塞了，但是隻需要第1步驟中的時間點資料）；
Leader傳回該timestamp對應的日志位點；
TiFlash等待Delta檔案同步到這個日志位點就可以開始進入讀取流程了；

5. HTAP ENGINES

SQL引擎層的優化：

對于TP，Percolator模型，實作了悲觀鎖和樂觀鎖；
對于AP，CBO優化器，計算下推到存儲層；

5.1 Transactional Processing

TiDB提供ACID事務特性，SI和RR隔離級别。實作上是基于MVCC，避免讀-寫鎖，同時W-W保護。

一個事務設計到SQL，TiKV，PD：

SQL引擎：做為協調者推動事務前進，從client接收讀寫請求，轉成TiKV能了解的kv，通過2PC寫入TiKV server；
PD：管理邏輯Region和實體機器的映射，提供全局嚴格遞增的timestamp；
TiKV：提供分布式事務接口，實作MVCC，持久化資料；

TiDB實作了樂觀鎖和悲觀鎖。Percolator模型，選擇一個key做為primary，用它來記錄事務的狀态，基于2PC來送出事務。

樂觀事務的過程如下：

SQL引擎收到"begin"後，從PD上擷取一個timestamp，做為事務的start_ts；
執行DML，從TiKV上讀取資料到本地記憶體，并修改，保證讀取到start_ts之前最新commit_ts的資料；
收到"commit"，開始2PC，随機選擇key做為primarykey，并發的鎖住所有的key（防止W-W沖突），并發的發送prewrite給TiKV節點；
當所有prewrites成功後，再請求PD擷取一個timestmap，做為commit_ts，給TiKV發送commit消息，TiKV标記primarykey為commit狀态；
SQL引擎傳回成功client；
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庫。

從TiKV讀取中繼資料，建構Spark的catalog；
Spark driver從PD擷取timestamp，以便從TiKV中讀取MVCC資料，提供一緻性快照；
為了是從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個列。

同樣的：

AP型查詢的小範圍或點查可以走tikv；
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之間的資料一緻性。可惜沒有提供和上述産品橫向的資料對比。

TiDB: A Raft-based HTAP Database》論文解讀ABSTRACT1. INTRODUCTION2. RAFT-BASED HTAP3. ARCHITECTURE4. MULTI-RAFT STORAGE5. HTAP ENGINES6. EXPERIMENTS7. RELATED WORK