在最新一屆國際數(shù)據(jù)庫頂級會議 ACM SIGMOD 2022 上，來自清華大學(xué)的李國良和張超兩位老師發(fā)表了一篇論文：《HTAP Database: What is New and What is Next》,并做了?《HTAP Database：A Tutorial》?的專項報告。這幾期學(xué)術(shù)分享會的文章，StoneDB將系統(tǒng)地梳理一下兩位老師的報告，帶讀者了解 HTAP 的發(fā)展現(xiàn)狀和未來趨勢。

在深度干貨！一篇Paper帶您讀懂HTAP這期分享中我們已經(jīng)把HTAP產(chǎn)生的背景和現(xiàn)有的HTAP數(shù)據(jù)庫及其技術(shù)棧做了一個簡單的介紹，這一期，我們將著重講一講報告中對HTAP關(guān)鍵技術(shù)的解讀。

在正式開始前，先給上期簡單收個尾，報告中提到 HTAP 數(shù)據(jù)庫除了以下四種：

• Primary Row Store + InMemory Column Store

• Distributed Row Store + Column Store Replica

• Disk Row Store + Distributed Column Store

• Primary Column Store + Delta Row Store

還補(bǔ)充了3種，感興趣的讀者可以自行了解：

• Row-based HTAP systems：如 Hyper（Row）、BatchDB等

• Column-based HTAP systems：如 Caldera、RateupDB等

• Spark-based HTAP systems：如 Splice Machine、Wildfire等

下面進(jìn)入正文，本篇報告中主要介紹了HTAP的五大類關(guān)鍵技術(shù)，分別是：

1. Transaction Processing（事務(wù)處理技術(shù)）

2. Analytical Processing（查詢分析技術(shù)）

3. Data Synchronization（數(shù)據(jù)同步技術(shù)）

4. Query Optimization（查詢優(yōu)化技術(shù)）

5. Resource Scheduling（資源調(diào)度技術(shù)）

這些關(guān)鍵技術(shù)被最先進(jìn)的HTAP數(shù)據(jù)庫采用。然而，它們在各種指標(biāo)上各有利弊，例如效率、可擴(kuò)展性和數(shù)據(jù)新鮮度。

一、事務(wù)處理技術(shù)（OLTP）

HTAP數(shù)據(jù)庫中的OLTP工作負(fù)載是通過行存儲處理的，但不同的架構(gòu)會導(dǎo)致不同的TP技術(shù)。它主要由兩種類型組成。

1使用內(nèi)存增量更新的單機(jī)事務(wù)處理

Standalone Transaction Processing with In-Memory Delta Update

關(guān)鍵技術(shù)點：

• 通過MVCC協(xié)議進(jìn)行單機(jī)事務(wù)處理

• 通過內(nèi)存增量更新進(jìn)行insert/delete/update操作

相關(guān)數(shù)據(jù)庫：Oracle、SQL Server、SAP HANA 和?StoneDB?等。

上面這張圖介紹了單機(jī)事務(wù)處理執(zhí)行insert/delete/operations操作的一個邏輯過程，總體上是借助MVCC+logging，它依賴于MVCC協(xié)議和日志記錄技術(shù)來處理事務(wù)。具體來說，每個插入首先寫入日志和行存儲，然后附加到內(nèi)存中的增量存儲。更新創(chuàng)建具有新生命周期的行的新版本，即開始時間戳和結(jié)束時間戳，即舊版本在刪除位圖中被標(biāo)記為刪除行。因此，事務(wù)處理是高效的，因為 DML 操作是在內(nèi)存中執(zhí)行的。請注意，某些方法可能會將數(shù)據(jù)寫入行存儲 或增量行存儲 ，并且它們可能僅在事務(wù)提交時寫入日志。

一般有三種方式來實現(xiàn)內(nèi)存增量存儲，分別是：Heaptable(堆表)、Index organized table（索引組織表）?和?L1 cache（一級緩存），具體區(qū)別如下表：

三者主要的區(qū)別在于插入（insertion）速度、查詢（lookup）速度和容量（capacity）大小上。

2使用日志回放的分布式事務(wù)處理

Distributed Transaction Processing with Log Replay

關(guān)鍵技術(shù)點：

• Two-Phase Commit(2PC)`+Paxos 用于分布式TP和數(shù)據(jù)復(fù)制

• 使用Log replay(日志回放)更新行存儲和列存儲

相關(guān)數(shù)據(jù)庫：F1 Lightning

注：這里有稍有不同的分布式TP方案，就是采用主從復(fù)制（Master-slave replication）的方式實現(xiàn)HTAP，比如 Singlestore。

如上圖所示，這種主從復(fù)制的方式下，主節(jié)點處理事務(wù)，然后將日志復(fù)制到從節(jié)點再做分析。

另外就是通過2PC+Raft+logging，它依賴于分布式架構(gòu)。

它通過分布式事務(wù)處理提供了高可擴(kuò)展性。ACID事務(wù)在分布式節(jié)點上使用兩階段提交 (2PC) 協(xié)議、基于Raft的共識算法和預(yù)寫日志 (WAL) 技術(shù)進(jìn)行處理。特別是leader節(jié)點接收到SQL引擎的請求，然后在本地追加日志，異步發(fā)送日志給follower節(jié)點。如果大多數(shù)節(jié)點（即法定人數(shù)）成功附加日志，則領(lǐng)導(dǎo)者提交請求并在本地應(yīng)用它。與第一種內(nèi)存增量更新的方式相比，這種基于日志的方式由于分布式事務(wù)處理效率較低。

3對比

最后我們將提到事務(wù)處理技術(shù)做一個對比：

二、查詢分析技術(shù)（OLAP）

對于HTAP數(shù)據(jù)庫，OLAP負(fù)載使用面向列的技術(shù)執(zhí)行，例如壓縮數(shù)據(jù)上的聚合和單指令多數(shù)據(jù) (SIMD) 指令。這里介紹兩大類型和三種方式：

1?內(nèi)存增量遍歷 + 單機(jī)列掃描

Standalone Columnar Scan with In-Memory Delta Traversing

關(guān)鍵技術(shù)點：

• 單指令多數(shù)據(jù)(SIMD)，向量化處理

• 內(nèi)存增量遍歷（In-Memory Delta Traversing） 相關(guān)數(shù)據(jù)庫：Oracle、SQL Server

舉幾個例子：

在（a）里，我們查詢訂單表中名稱為JASON的花了多少錢，那么基于SIMD的查詢方式，是可以通過CPU把數(shù)據(jù)Load到寄存器中，只需要一個CPU執(zhí)行的周期，就可以同時去掃描查到滿足條件的兩個數(shù)據(jù)。

如果基于傳統(tǒng)的火山模型，用的是一種迭代模型，就需要訪問四行數(shù)據(jù)，而基于這種列存的方式，只要訪問一次就可以得到結(jié)果。

同樣的，還可以通過這種方式做基于Bloom Filter的向量化連接，也可以提交查詢分析的效率。

除此之外，我們在做列存掃描的同時要去掃描一些可見的增量數(shù)據(jù)來實現(xiàn)實時數(shù)據(jù)的分析，也去掃描刪除表中是否有過期的數(shù)據(jù)，最終達(dá)到數(shù)據(jù)是新鮮的。

2?日志文件掃描 + 分布式列掃描

Distributed Columnar Scan with Log File Scanning

關(guān)鍵技術(shù)點：

• 列段上的分布式查詢處理

• 基于磁盤的日志文件歸并與掃描 相關(guān)數(shù)據(jù)庫：F1 Lightning

Distributed Columnar Scan

如上圖所示的分布式列掃描，傳統(tǒng)方法就是基于多個Worker來做并發(fā)的多節(jié)點下進(jìn)行算子下推，掃描之后，在上層做一些聚集、HASH、排序等一些操作。

Log File Scanning

與分布式列掃描同時進(jìn)行的還有日志文件掃描，我們還要基于列存儲來做算子下推來查到當(dāng)前增量存儲中最新的數(shù)據(jù)，再進(jìn)行數(shù)據(jù)合并。上圖里的F1 Lighting就可以支持把10個小時的數(shù)據(jù)合并到Delta中。

3?技術(shù)總結(jié)

內(nèi)存中增量和列掃描

將內(nèi)存中的增量和列數(shù)據(jù)一起掃描，因為增量存儲可能包括尚未合并到列存儲的更新記錄。由于它已經(jīng)掃描了最近可見的delta tuples in內(nèi)存，因此OLAP的數(shù)據(jù)新鮮度很高。

基于日志的增量和列掃描

將基于日志的增量數(shù)據(jù)和列數(shù)據(jù)一起掃描以獲取傳入查詢。與第一種類似，第二種使用列存儲掃描最新的增量用于OLAP。但是，由于讀取可能尚未合并的delta文件，這樣的過程更加昂貴。因此，數(shù)據(jù)新鮮度較低，因為發(fā)送和合并delta文件的高延遲。

列掃描

只掃描列數(shù)據(jù)以獲得高效率，因為沒有讀取任何增量數(shù)據(jù)的開銷。但是，當(dāng)數(shù)據(jù)在行存儲中經(jīng)常更新時，這種技術(shù)會導(dǎo)致新鮮度低。

4?對比

對于第一種單機(jī)列掃描+內(nèi)存增量遍歷來說，優(yōu)點是數(shù)據(jù)新鮮度較高，缺點是需要比較多的內(nèi)存空間。對第二種分布式列掃描+日志文件掃描來說，優(yōu)點是擴(kuò)展性高，缺點是效率比較低。

三、數(shù)據(jù)同步技術(shù)（DS）

由于在查詢時讀取增量數(shù)據(jù)的成本很高，因此需要定期將增量數(shù)據(jù)合并到主列存儲中。這個時候，數(shù)據(jù)同步（Data Synchronization）技術(shù)，就非常重要了，也是分為兩大類型。

1?類型一：內(nèi)存增量合并

關(guān)鍵技術(shù)：

• 基于閾值的合并（Threshold-based merging）

• 兩階段數(shù)據(jù)遷移（Two-phase data migration）

• 基于字典的遷移（Dictionary-based migration）

相關(guān)數(shù)據(jù)庫：Oracle、SQL Server、SAP HANA

Threshold-based merging

舉個例子，如果閾值達(dá)到列存儲90%的容量時，我們就把Delta Table中的數(shù)據(jù)合并到Column Store當(dāng)中，當(dāng)然這種方式有個缺點——如果閾值設(shè)置的太大可能會導(dǎo)致AP的性能發(fā)生抖動，所以看到圖里我們加了一個Trick-based，最好是定小量按期地去合并，做一個權(quán)衡。

Two-phase data migration

兩階段數(shù)據(jù)的遷移，可以拿SQL Server舉例，如圖所示：

• 第一階段：遷移準(zhǔn)備

• 第（1）步先插入RID去把需要隱藏的數(shù)據(jù)寫入到刪除表當(dāng)中；

• 第（2）步把這些數(shù)據(jù)分配RID后生成Delta Colunm Store；

• 第二階段：遷移操作

• 第（3）步，把剛剛插入進(jìn)去的RID刪除；

• 第（4）步，最后真正把Delta中相關(guān)的數(shù)據(jù)刪除，最后才把生成的增量列存合并到主列存中，達(dá)到了數(shù)據(jù)遷移的效果。

Dictionary-based migration

第三種基于字典的遷移，SAP HANA就是采用這種方式。如圖所示，它第一階段主要是針對每一列的數(shù)據(jù)做一個本地字典的方式映射過去增加對應(yīng)的數(shù)據(jù)向量，第二階段，才會把這個字典加入到全局的字典，做一個全局的排序，最后合并到數(shù)據(jù)向量當(dāng)中。

2?類型二：基于日志的增量合并

關(guān)鍵技術(shù)：LSM-tree 和 B-tree

相關(guān)數(shù)據(jù)庫：F1 Lighting

這種類型分兩層：

• Memory-resident deltas（駐留內(nèi)存的增量），主要是row-wise

• Disk-resident deltas（駐留磁盤的增量），主要是column-wise

如圖所示，第一階段會把小文件、小delta按它到來的順序合并到增量的文件當(dāng)中，第二階段會通過查找B+樹來做一個有序合并，最終讓合并的Chunk是有序的。這主要涉及解決基于多版本的一些Log怎么去做合并和折疊，其中B+樹主要的作用就是在有序合并時去加速數(shù)據(jù)查找的過程。

3?技術(shù)總結(jié)

可歸類為有3種數(shù)據(jù)合并技術(shù)。分別是：

1. 內(nèi)存中增量合并；

2. 基于磁盤的增量合并；

3. 從主行存儲重建。

第一個類別定期將新插入的內(nèi)存中增量數(shù)據(jù)合并到主列存儲。引入了幾種技術(shù)來優(yōu)化合并過程，包括兩階段基于事務(wù)的數(shù)據(jù)遷移、字典編碼排序合并和基于閾值的變化傳播。

第二類 將基于磁盤的增量文件合并到主列存儲。為了加快合并過程，增量數(shù)據(jù)可以通過B+樹進(jìn)行索引，因此可以通過鍵查找有效地定位增量項。

第三類從主行存儲重建內(nèi)存列存儲。這對于增量更新超過某個閾值的情況很典型，因此重建列存儲比合并這些具有大內(nèi)存占用的更新更有效。

4?對比

總體來看，基于內(nèi)存的增量合并效率比較高，擴(kuò)展性差點兒；基于日志的合并，擴(kuò)展性好，但是多重合并的代價會比較高。

HTAP中查詢優(yōu)化技術(shù)主要涉及三個維度，包括：

1?In-Memory Column Selection

• 解決的問題：要從行存儲區(qū)中選擇哪些列進(jìn)入內(nèi)存呢？簡單的做法是全部選擇進(jìn)去，但那樣存儲和更新的代價會很高，所以一般是基于歷史的統(tǒng)計信息和現(xiàn)有內(nèi)存的預(yù)算來做權(quán)衡選擇。

• 解決方式：有兩種，第一種是熱力圖（Heatmap），第二種是整數(shù)規(guī)劃（Integer programming）

基于Heatmap，比如Oracle

通過訪問頻度來管理列存并進(jìn)行熱力圖的制作。

如圖所示，首先根據(jù)最下方持久化行存（Persistent Storage）來選定一些候選列集（Candidate Columns），通過記錄候選集的訪問頻度。有些列就會變?yōu)镠ot Columns，那么就可以把最新的數(shù)據(jù)Load進(jìn)去（圖中左下方的Populating）來達(dá)到加速查詢的效果；慢慢地也有一些列會變?yōu)镃old Columns，那么就把這些冷列進(jìn)行壓縮（Compressed Columnar data），然后最后排除（圖中右下方的Evicating）到內(nèi)存當(dāng)中，再選取其他被高頻訪問的列重復(fù)進(jìn)行。

基于Integer programming，比如Hyrise

Integer programming for?0/1 Knapsack problem，第一種基于熱力圖的方式完全沒有考慮選擇列的代價，那么第二種就是把代價函數(shù)（cost-based optimization problem）考慮進(jìn)去，再從二級存儲中選擇列。

這個目標(biāo)函數(shù)就是要去優(yōu)化所有的查詢代價函數(shù)，而每個查詢代價函數(shù)要去衡量所選擇列的代價。總目標(biāo)是最小化這個代價，要小于這個最大的預(yù)算。（這里不展開講了，感興趣可以閱讀這篇論文，也比較經(jīng)典）

2?Hybrid Row and Column Scan

• 解決的問題：內(nèi)存中選擇好列之后，如何利用混合行/列掃描加速查詢呢？這個比較前沿了，像Google的AlloyDB也支持這個特性。

• 解決方式：基于規(guī)則的計劃選擇（Rule-based）或者基于代價（Cost-based）的計劃選擇。主要決定查詢優(yōu)化器要把哪些算子下推到列存引擎當(dāng)中。

Rule-based Optimization(RBO)

先定義一些掃描的規(guī)則，比如先看列掃描，再看行掃描。相關(guān)數(shù)據(jù)庫：Oracle、SQL server。

舉個例子，上圖中我們查找一些北京車子注冊的證書和顏色，在這種規(guī)則下就可以生成一個邏輯計劃樹，在這個邏輯計劃樹里，我們先去查找底層表到底是行存還是列存，如果是列存，就做列存的方式處理，如果是行存就做一個B+樹的掃描。最后合并做一個連接再返回最終結(jié)果。

Cost-based Optimization(CBO)

基于代價的方式，解決的方式是先去對比列存掃描和行存/索引掃描的代價分別是多少，然后再決定查詢算子在哪里執(zhí)行。

3 CPU/GPU Acceleration for HTAP

這個基于硬件去做HTAP的加速。比如，基于CPU/GPU異構(gòu)處理器的方式進(jìn)行HTAP的處理。相關(guān)數(shù)據(jù)庫：RateupDB、Caldera。

• Task-parallel nature of CPUs for handling OLTP

• CPU任務(wù)并行的特性可以用來處理OLTP

• Data-parallel nature of GPUs for handling OLAP

• GPU數(shù)據(jù)并行的特性可以用來處理OLAP

涉及到一些并行計算的知識，感興趣可以了解了解~

4?技術(shù)總結(jié)

主要涉及三大技術(shù)：

1. HTAP的列選擇；

2. 混合行/列掃描；

3. HTAP 的 CPU/GPU加速。

第一種類型依靠歷史工作負(fù)載和統(tǒng)計數(shù)據(jù)來選擇從主存儲中提取的頻繁訪問的列到內(nèi)存中。因此，可以將查詢下推到內(nèi)存中的列存儲以進(jìn)行加速。缺點是可能沒有選擇新查詢的列，導(dǎo)致基于行的查詢處理?，F(xiàn)有方法依靠歷史工作負(fù)載的訪問模式來加載熱數(shù)據(jù)并驅(qū)逐冷數(shù)據(jù)。

第二種類型利用混合行/列掃描來加速查詢使用這些技術(shù)，可以分解復(fù)雜的查詢以在行存儲或列存儲上執(zhí)行，然后組合結(jié)果。這對于可以使用基于行的索引掃描和完整的基于列的掃描執(zhí)行的 SPJ 查詢來說是典型的。我們引入了基于成本的方法來選擇混合行/列訪問路徑。

第三種技術(shù)利用異構(gòu)CPU/GPU架構(gòu)來加速HTAP工作負(fù)載。這些技術(shù)分別利用CPU的任務(wù)并行性和GPU的數(shù)據(jù)并行性來處理OLTP和OLAP。然而，這些技術(shù)有利于高OLAP吞吐量，同時具有低OLTP吞吐量。

5對比

五、資源調(diào)度技術(shù)

對于 HTAP 數(shù)據(jù)庫，資源調(diào)度是指為 OLTP 和OLAP 工作負(fù)載分配資源。當(dāng)前可以動態(tài)控制OLTP 和 OLAP 工作負(fù)載的執(zhí)行模式，以更好地利用資源。

1 基于工作負(fù)載驅(qū)動的調(diào)度

Workload-driven Scheduling for HTAP，就是根據(jù)HTAP工作負(fù)載的執(zhí)行性能進(jìn)行動態(tài)的調(diào)度，線程和內(nèi)存這些根據(jù)OLTP和OLAP的性能需求動態(tài)分配資源。相關(guān)數(shù)據(jù)庫: SAP HANA。

• Assign more threads to OLTP or OLAP

舉個栗子，第一種方式會分配更多的線程給OLTP或者OLAP，怎么分配呢？會在Scheduler里配置一個Watch-dog監(jiān)測器，來監(jiān)測當(dāng)前的Worker，有一些被阻塞的Worker就分配多一些Thread，有一些比較活躍的的，就讓它繼續(xù)執(zhí)行。

• Isolate the workload execution and assign more cache for OLAP

如表所示，在第三層Cache當(dāng)中進(jìn)行一些調(diào)度，通過實驗可以得知增加OLTP存儲資源時，OLAP的顏色是會變深的，這意味著影響越嚴(yán)重，所以還是建議在第三層盡量給OLAP多分配一些資源。

2 基于新鮮度驅(qū)動的調(diào)度

Freshness-driven Scheduling for HTAP

• Switches the execution modes {S1, S2, S3}

• Default S2; When freshness < threshold, jump to S1 or S3

調(diào)度技術(shù)有兩種類型，工作負(fù)載驅(qū)動的方法和新鮮度驅(qū)動的方法。前者根據(jù)執(zhí)行工作負(fù)載的性能調(diào)整OLTP和OLAP任務(wù)的并行度。例如，當(dāng)CPU資源被OLAP線程飽和時，任務(wù)調(diào)度器可以在增大OLTP線程的同時降低OLAP的并行度。后一個切換了OLTP和OLAP的資源分配和數(shù)據(jù)交換的執(zhí)行模式。例如，調(diào)度程序單獨控制OLTP和OLAP的執(zhí)行以實現(xiàn)高吞吐量，然后定期同步數(shù)據(jù)。一旦數(shù)據(jù)新鮮度變低，它就會切換到共享 CPU、內(nèi)存和數(shù)據(jù)的執(zhí)行模式。其他與 HTAP 相關(guān)的技術(shù)，還有新的 HTAP 索引技術(shù)和橫向擴(kuò)展技術(shù)。

4 對比

第一種優(yōu)點是比較容易實現(xiàn)，但是新鮮度較低；第二種方式優(yōu)點是新鮮度高，但來回切換容易導(dǎo)致系統(tǒng)震蕩。

六、其他相關(guān)的HTAP技術(shù)

這里不展開介紹了，感興趣可以看看相關(guān)的Paper。

1Multi-Versioned Indexes for HTAP

• Parallel Binary Tree (P-Tree)

• Multi-Version Partitioned B-Tree (MV-PBT)

2 Adaptive Data Organization for HTAP

• H2O?[Alagiannis et al, SIGMOD 2014],?Casper?[Athanassoulis et al, VLDB 2019]

• Peloton?[Arulraj et al, SIGMOD 2016],?Proteus?[Abebe et al, SIGMOD 2022]

責(zé)編：宇亭

HTAP的基準(zhǔn)測試

下一期我們將介紹針對HTAP基準(zhǔn)測試的相關(guān)進(jìn)展，在我們的第二期學(xué)術(shù)分享會里，也介紹過來自慕尼黑工業(yè)大學(xué)（TMU）數(shù)據(jù)庫組的研究，感興趣可以前往查看，這篇文章只是其中一種基準(zhǔn)測試的方法，想了解還有哪些方法么？歡迎關(guān)注StoneDB公眾號，我下期見~