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

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

在正式開始前，先給上期簡(jiǎn)單收個(gè)尾践磅，報(bào)告中提到 HTAP 數(shù)據(jù)庫(kù)除了以下四種：

• 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)入正文，本篇報(bào)告中主要介紹了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ù)）」

Overview of HTAP Techniques

這些關(guān)鍵技術(shù)被最先進(jìn)的 HTAP 數(shù)據(jù)庫(kù)采用逻淌。然而，它們?cè)诟鞣N指標(biāo)上各有利弊喇聊，例如效率恍风、可擴(kuò)展性和數(shù)據(jù)新鮮度。

An Overview of HTAP Techniques

事務(wù)處理 (TP) 技術(shù)

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

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

Standalone Transaction Processing with In-Memory Delta Update

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

• 通過(guò)MVCC協(xié)議進(jìn)行單機(jī)事務(wù)處理
• 通過(guò)內(nèi)存增量更新進(jìn)行insert/delete/update操作

相關(guān)數(shù)據(jù)庫(kù)：Oracle窜骄、SQL Server锦募、SAP HANA和StoneDB等

Standalone TP for insert/delete/update operations

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

一般有三種方式來(lái)實(shí)現(xiàn)內(nèi)存增量存儲(chǔ)过椎，分別是：「Heaptable(堆表)「、」Index organized table（索引組織表）」 和 「L1 cache（一級(jí)緩存）」戏仓，具體區(qū)別如下表：

Three implementations for an in-memory delta store

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

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

Distributed Transaction Processing with Log Replay

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

• Two-Phase Commit(2PC)`+Paxos 用于分布式TP和數(shù)據(jù)復(fù)制
• 使用Log replay(日志回放)更新行存儲(chǔ)和列存儲(chǔ)

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

「注：這里有稍有不同的分布式TP方案柜去，就是采用主從復(fù)制（Master-slave replication）的方式實(shí)現(xiàn)HTAP灰嫉，比如 Singlestore∩ど荩」

Master node handles the transactions, then replicate the logs to slave nodes

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

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

Modified Raft Protocol for TP and AP nodes

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

對(duì)比

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

Comparisons of TP techniques in HTAP Databases

查詢分析（AP）技術(shù)

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

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

Standalone Columnar Scan with In-Memory Delta Traversing

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

• 單指令多數(shù)據(jù)(SIMD)仅父，向量化處理
• 內(nèi)存增量遍歷（In-Memory Delta Traversing） 相關(guān)數(shù)據(jù)庫(kù)：Oracle、SQL Server

舉幾個(gè)例子：

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

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

image.png

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

在增量表中獲取可見值往湿，并跳過(guò)刪除表中的陳舊數(shù)據(jù)

除此之外，我們?cè)谧隽写鎾呙璧耐瑫r(shí)要去掃描一些可見的增量數(shù)據(jù)來(lái)實(shí)現(xiàn)實(shí)時(shí)數(shù)據(jù)的分析惨好，也去掃描刪除表中是否有過(guò)期的數(shù)據(jù)煌茴，最終達(dá)到數(shù)據(jù)是新鮮的。

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

Distributed Columnar Scan with Log File Scanning

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

• 列段上的分布式查詢處理
• 基于磁盤的日志文件歸并與掃描 相關(guān)數(shù)據(jù)庫(kù)：F1 Lightning

Distributed Columnar Scan

Samwel, Bart, et al. "F1 query: Declarative querying at scale."PVLDB 11(12) , 2018: 1835-1848.

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

Log File Scanning

Yang, Jiacheng, et al. "F1 Lightning: HTAP as a Service." PVLDB 13(12), 2020: 3313-3325.

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

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

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

將內(nèi)存中的增量和列數(shù)據(jù)一起掃描葬燎，因?yàn)樵隽看鎯?chǔ)可能包括尚未合并到列存儲(chǔ)的更新記錄。由于它已經(jīng)掃描了最近可見的 delta tuples in內(nèi)存缚甩，因此 OLAP 的數(shù)據(jù)新鮮度很高谱净。

基于日志的增量和列掃描

將基于日志的增量數(shù)據(jù)和列數(shù)據(jù)一起掃描以獲取傳入查詢。與第一種類似擅威，第二種使用列存儲(chǔ)掃描最新的增量用于OLAP壕探。但是，由于讀取可能尚未合并的 delta 文件郊丛，這樣的過(guò)程更加昂貴李请。因此瞧筛，數(shù)據(jù)新鮮度較低，因?yàn)榘l(fā)送和合并 delta 文件的高延遲导盅。

列掃描

只掃描列數(shù)據(jù)以獲得高效率较幌，因?yàn)闆]有讀取任何增量數(shù)據(jù)的開銷。但是认轨，當(dāng)數(shù)據(jù)在行存儲(chǔ)中經(jīng)常更新時(shí)绅络，這種技術(shù)會(huì)導(dǎo)致新鮮度低。

對(duì)比

Comparisons of AP techniques in HTAP Databases

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

數(shù)據(jù)同步(DS)技術(shù)

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

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

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

• 基于閾值的合并（Threshold-based merging）
• 兩階段數(shù)據(jù)遷移（Two-phase data migration）
• 基于字典的遷移（Dictionary-based migration）

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

Threshold-based merging

舉個(gè)例子软瞎，如果閾值達(dá)到列存儲(chǔ)90%的容量時(shí)逢唤，我們就把Delta Table中的數(shù)據(jù)合并到Column Store當(dāng)中，當(dāng)然這種方式有個(gè)缺點(diǎn)——如果閾值設(shè)置的太大可能會(huì)導(dǎo)致AP的性能發(fā)生抖動(dòng)涤浇，所以看到圖里我們加了一個(gè)Trick-based鳖藕，最好是定小量按期地去合并，做一個(gè)權(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就是采用這種方式。如圖所示沪饺，它第一階段主要是針對(duì)每一列的數(shù)據(jù)做一個(gè)本地字典的方式映射過(guò)去增加對(duì)應(yīng)的數(shù)據(jù)向量躏敢，第二階段，才會(huì)把這個(gè)字典加入到全局的字典整葡，做一個(gè)全局的排序件余，最后合并到數(shù)據(jù)向量當(dāng)中。

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

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

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

這種類型分兩層：

• Memory-resident deltas（駐留內(nèi)存的增量）遭居，主要是row-wise
• Disk-resident deltas（駐留磁盤的增量）啼器，主要是column-wise

Log-based delta merge

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

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

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

1. 內(nèi)存中增量合并照捡；
2. 基于磁盤的增量合并；
3. 從主行存儲(chǔ)重建话侧。

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

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

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

對(duì)比

Comparisons of DS techniques in HTAP Databases

總體來(lái)看涩蜘，基于內(nèi)存的增量合并效率比較高嚼贡，擴(kuò)展性差點(diǎn)兒；基于日志的合并同诫，擴(kuò)展性好粤策，但是多重合并的代價(jià)會(huì)比較高。

查詢優(yōu)化技術(shù)

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

Query Optimization in HTAP databases

In-Memory Column Selection

• 「解決的問(wèn)題」：要從行存儲(chǔ)區(qū)中選擇哪些列進(jìn)入內(nèi)存呢叮盘？簡(jiǎn)單的做法是全部選擇進(jìn)去秩贰，但那樣存儲(chǔ)和更新的代價(jià)會(huì)很高，所以一般是基于歷史的統(tǒng)計(jì)信息和現(xiàn)有內(nèi)存的預(yù)算來(lái)做權(quán)衡選擇柔吼。
• 「解決方式」：有兩種毒费，第一種是熱力圖（Heatmap），第二種是整數(shù)規(guī)劃（Integer programming） · [圖片上傳失敗...(image-e95981-1663916784060)]

基于Heatmap愈魏，比如Oracle

通過(guò)訪問(wèn)頻度來(lái)管理列存并進(jìn)行熱力圖的制作觅玻。

Oracle 21c. Automating Management of In-Memory Objects., 2021.

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

基于Integer programming闺骚，比如Hyrise

Integer programming for 「0/1 Knapsack problem」彩扔，第一種基于熱力圖的方式完全沒有考慮選擇列的代價(jià)，那么第二種就是把代價(jià)函數(shù)（cost-based optimization problem）考慮進(jìn)去僻爽，再?gòu)亩?jí)存儲(chǔ)中選擇列虫碉。

Boissier, Martin, et al. "Hybrid data layouts for tiered HTAP databases with paretooptimal data placements." ICDE, 2018.

這個(gè)目標(biāo)函數(shù)[圖片上傳失敗...(image-b06700-1663916784060)] 就是要去優(yōu)化所有的查詢代價(jià)函數(shù)[圖片上傳失敗...(image-1102ae-1663916784060)] ，而每個(gè)查詢代價(jià)函數(shù)要去衡量所選擇列的代價(jià)胸梆《嘏酰總目標(biāo)是最小化這個(gè)代價(jià)，要小于這個(gè)最大的[圖片上傳失敗...(image-b947e6-1663916784060)] 預(yù)算碰镜。（這里不展開講了兢卵，感興趣可以閱讀這篇論文，也比較經(jīng)典）

Hybrid Row and Column Scan

• 「解決的問(wèn)題」：內(nèi)存中選擇好列之后绪颖，如何利用混合行/列掃描加速查詢呢秽荤？這個(gè)比較前沿了，像Google的AlloyDB也支持這個(gè)特性柠横。
• 「解決方式」：基于規(guī)則的計(jì)劃選擇（Rule-based）或者基于代價(jià)（Cost-based）的計(jì)劃選擇窃款。主要決定查詢優(yōu)化器要把哪些算子下推到列存引擎當(dāng)中。

Rule-based Optimization(RBO)

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

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

Cost-based Optimization(CBO)

基于代價(jià)的方式胜臊，解決的方式是先去對(duì)比「列存掃描」和「行存/索引掃描」的代價(jià)分別是多少，然后再?zèng)Q定查詢算子在哪里執(zhí)行伙判。

Compare the cost of row/index scan with the cost of columnar scan

CPU/GPU Acceleration for HTAP

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

!CPU/GPU processors for HTAP](https://upload-images.jianshu.io/upload_images/28401377-4bc078618d8a5621.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

• Task-parallel nature of CPUs for handling OLTP

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

• Data-parallel nature of GPUs for handling OLAP

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

涉及到一些并行計(jì)算的知識(shí)菇曲，感興趣可以了解了解~

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

1. HTAP的列選擇冠绢；
2. 混合行/列掃描；
3. HTAP 的 CPU/GPU加速常潮。

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

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

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

對(duì)比

Query Optimization in HTAP databases

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

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

Resource Scheduling

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

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

• Assign more threads to OLTP or OLAP

Psaroudakis, Iraklis, et al. "Task scheduling for highly concurrent analytical and transactional main-memory workloads." In ADMS, 2013.

舉個(gè)栗子违崇，第一種方式會(huì)分配更多的線程給OLTP或者OLAP阿弃，怎么分配呢？會(huì)在Scheduler里配置一個(gè)Watch-dog監(jiān)測(cè)器羞延，來(lái)監(jiān)測(cè)當(dāng)前的Worker渣淳，有一些被阻塞的Worker就分配多一些Thread，有一些比較活躍的的伴箩，就讓它繼續(xù)執(zhí)行入愧。

• Isolate the workload execution and assign more cache for OLAP

Sirin, Utku, Sandhya Dwarkadas, and Anastasia Ailamaki. "Performance Characterization of HTAP Workloads." In ICDE, 2021.

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

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

Freshness-driven Scheduling for HTAP

• Switches the execution modes {S1, S2, S3}
• Default S2; When freshness < threshold, jump to S1 or S3

Raza, Aunn, et al. "Adaptive HTAP through elastic resource scheduling." In SIGMOD, 2020.

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

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

對(duì)比

Resource Scheduling in HTAP databases

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

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

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

Multi-Versioned Indexes for HTAP

• Parallel Binary Tree (P-Tree)

Sun, Yihan, et al. "On supporting efficient snapshot isolation for hybrid workloads with multiversioned indexes." PVLDB 13(2), 2019.

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

Riegger, Christian, et al. "MV-PBT: multi-version indexing for large datasets and HTAP workloads." In EDBT, 2020.

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]

Abebe, Michael, Horatiu Lazu, and Khuzaima Daudjee. Proteus: Autonomous Adaptive Storage for Mixed Workloads. In SIGMOD, 2022.

責(zé)編：宇亭

StoneDB 已經(jīng)正式開源，歡迎關(guān)注我們
https://github.com/stoneatom/stonedb