在最新一屆國際資料庫頂級會議 ACM SIGMOD 2022 上,來自清華大學的李國良和張超兩位老師發表了一篇論文:《HTAP Database: What is New and What is Next》,並做了 《HTAP Database:A Tutorial》 的專項報告。這幾期學術分享會的 ...
在最新一屆國際資料庫頂級會議 ACM SIGMOD 2022 上,來自清華大學的李國良和張超兩位老師發表了一篇論文:《HTAP Database: What is New and What is Next》,並做了 《HTAP Database:A Tutorial》 的專項報告。這幾期學術分享會的文章,StoneDB將系統地梳理一下兩位老師的報告,帶讀者瞭解 HTAP 的發展現狀和未來趨勢。
在第一期分享中:StoneDB:深度乾貨!一篇Paper帶您讀懂HTAP | StoneDB學術分享會第①期
我們已經把HTAP產生的背景和現有的HTAP資料庫及其技術棧做了一個簡單的介紹,這一期,我們將著重講一講報告中對HTAP關鍵技術的解讀。
在正式開始前,先給上期簡單收個尾,報告中提到 HTAP 資料庫除了以下四種:
- Primary Row Store + InMemory Column Store
- Distributed Row Store + Column Store Replica
- Disk Row Store + Distributed Column Store
- Primary Column Store + Delta Row Store
還補充了3種,感興趣的讀者可以自行瞭解:
- Row-based HTAP systems:如 Hyper(Row)、BatchDB等
- Column-based HTAP systems:如 Caldera、RateupDB等
- Spark-based HTAP systems:如 Splice Machine、Wildfire等
下麵進入正文,本篇報告中主要介紹了HTAP的五大類關鍵技術,分別是:
- Transaction Processing(事務處理技術)
- Analytical Processing(查詢分析技術)
- Data Synchronization(數據同步技術)
- Query Optimization(查詢優化技術)
- Resource Scheduling(資源調度技術)
Overview of HTAP Techniques
這些關鍵技術被最先進的 HTAP 資料庫採用。然而,它們在各種指標上各有利弊,例如效率、可擴展性和數據新鮮度。
An Overview of HTAP Techniques
Part1 事務處理 (TP) 技術
HTAP 資料庫中的 OLTP 工作負載是通過行存儲處理的,但不同的架構會導致不同的 TP 技術。它主要由兩種類型組成。
1. 使用記憶體增量更新的單機事務處理
Standalone Transaction Processing with In-Memory Delta Update
關鍵技術點:
- 通過MVCC協議進行單機事務處理
- 通過記憶體增量更新進行insert/delete/update操作
相關資料庫:Oracle、SQL Server和SAP HANA等
Standalone TP for insert/delete/update operations
上面這張圖介紹了單機事務處理執行insert/delete/operations操作的一個邏輯過程,總體上是藉助 MVCC+logging,它依賴於 MVCC 協議和日誌記錄技術來處理事務。具體來說,每個插入首先寫入日誌和行存儲,然後附加到記憶體中的增量存儲。更新創建具有新生命周期的行的新版本,即開始時間戳和結束時間戳,即舊版本在刪除點陣圖中被標記為刪除行。因此,事務處理是高效的,因為 DML 操作是在記憶體中執行的。請註意,某些方法可能會將數據寫入行存儲 或增量行存儲 ,並且它們可能僅在事務提交時寫入日誌。
一般有三種方式來實現記憶體增量存儲,分別是:Heaptable(堆表)、Index organized table(索引組織表) 和 L1 cache(一級緩存),具體區別如下表:
Three implementations for an in-memory delta store
三者主要的區別在於插入(insertion)速度、查詢(lookup)速度和容量(capacity)大小上。
2. 使用日誌回放的分散式事務處理
Distributed Transaction Processing with Log Replay
關鍵技術點:
- Two-Phase Commit(2PC)`+Paxos 用於分散式TP和數據複製
- 使用Log replay(日誌回放)更新行存儲和列存儲
相關資料庫:F1 Lightning
註:這裡有稍有不同的分散式TP方案,就是採用主從複製(Master-slave replication)的方式實現HTAP,比如 Singlestore。
如上圖所示,這種主從複製的方式下,主節點處理事務,然後將日誌複製到從節點再做分析。
另外就是通過 2PC+Raft+logging,它依賴於分散式架構。
Modified Raft Protocol for TP and AP nodes
它通過分散式事務處理提供了高可擴展性。 ACID 事務在分散式節點上使用兩階段提交 (2PC) 協議、基於 Raft 的共識演算法和預寫日誌 (WAL) 技術進行處理。特別是 leader 節點接收到 SQL 引擎的請求,然後在本地追加日誌,非同步發送日誌給 follower 節點。如果大多數節點(即法定人數)成功附加日誌,則領導者提交請求併在本地應用它。與第一種記憶體增量更新的方式相比,這種基於日誌的方式由於分散式事務處理效率較低。
3. 對比
最後我們將提到事務處理技術做一個對比:
Comparisons of TP techniques in HTAP Databases
Part2 查詢分析(AP)技術
對於 HTAP 資料庫,OLAP負載使用面向列的技術執行,例如壓縮數據上的聚合和單指令多數據 (SIMD) 指令。這裡介紹兩大類型和三種方式:
1. 記憶體增量遍歷 + 單機列掃描
Standalone Columnar Scan with In-Memory Delta Traversing
關鍵技術點:
- 單指令多數據(SIMD),向量化處理
- 記憶體增量遍歷(In-Memory Delta Traversing) 相關資料庫:Oracle、SQL Server
舉幾個例子:
在(a)里,我們查詢訂單表中名稱為JASON的花了多少錢,那麼基於SIMD的查詢方式,是可以通過CPU把數據Load到寄存器中,只需要一個CPU執行的周期,就可以同時去掃描查到滿足條件的兩個數據。
如果基於傳統的火山模型,用的是一種迭代模型,就需要訪問四行數據,而基於這種列存的方式,只要訪問一次就可以得到結果。
同樣的,還可以通過這種方式做基於Bloom Filter的向量化連接,也可以提交查詢分析的效率。
在增量表中獲取可見值,並跳過刪除表中的陳舊數據
除此之外,我們在做列存掃描的同時要去掃描一些可見的增量數據來實現實時數據的分析,也去掃描刪除表中是否有過期的數據,最終達到數據是新鮮的。
2. 日誌文件掃描 + 分散式列掃描
Distributed Columnar Scan with Log File Scanning
關鍵技術點:
- 列段上的分散式查詢處理
- 基於磁碟的日誌文件歸併與掃描 相關資料庫:F1 Lightning
Distributed Columnar Scan
Samwel, Bart, et al. "F1 query: Declarative querying at scale."PVLDB 11(12) , 2018: 1835-1848.
如上圖所示的分散式列掃描,傳統方法就是基於多個Worker來做併發的多節點下進行運算元下推,掃描之後,在上層做一些聚集、HASH、排序等一些操作。
Log File Scanning
Yang, Jiacheng, et al. "F1 Lightning: HTAP as a Service." PVLDB 13(12), 2020: 3313-3325.
與分散式列掃描同時進行的還有日誌文件掃描,我們還要基於列存儲來做運算元下推來查到當前增量存儲中最新的數據,再進行數據合併。上圖裡的F1 Lighting就可以支持把10個小時的數據合併到Delta中。
3. 技術總結
記憶體中增量和列掃描
將記憶體中的增量和列數據一起掃描,因為增量存儲可能包括尚未合併到列存儲的更新記錄。由於它已經掃描了最近可見的 delta tuples in記憶體,因此 OLAP 的數據新鮮度很高。
基於日誌的增量和列掃描
將基於日誌的增量數據和列數據一起掃描以獲取傳入查詢。與第一種類似,第二種使用列存儲掃描最新的增量用於OLAP。但是,由於讀取可能尚未合併的 delta 文件,這樣的過程更加昂貴。因此,數據新鮮度較低,因為發送和合併 delta 文件的高延遲。
列掃描
只掃描列數據以獲得高效率,因為沒有讀取任何增量數據的開銷。但是,當數據在行存儲中經常更新時,這種技術會導致新鮮度低。
4. 對比
Comparisons of AP techniques in HTAP Databases
對於第一種單機列掃描+記憶體增量遍歷來說,優點是數據新鮮度較高,缺點是需要比較多的記憶體空間。對第二種分散式列掃描+日誌文件掃描來說,優點是擴展性高,缺點是效率比較低。
Part3 數據同步(DS)技術
由於在查詢時讀取增量數據的成本很高,因此需要定期將增量數據合併到主列存儲中。這個時候,數據同步(Data Synchronization)技術,就非常重要了,也是分為兩大類型。
類型一:記憶體增量合併
關鍵技術:
- 基於閾值的合併(Threshold-based merging)
- 兩階段數據遷移(Two-phase data migration)
- 基於字典的遷移(Dictionary-based migration)
相關資料庫:Oracle、SQL Server、SAP HANA
Threshold-based merging
舉個例子,如果閾值達到列存儲90%的容量時,我們就把Delta Table中的數據合併到Column Store當中,當然這種方式有個缺點——如果閾值設置的太大可能會導致AP的性能發生抖動,所以看到圖裡我們加了一個Trick-based,最好是定小量按期地去合併,做一個權衡。
Two-phase data migration
兩階段數據的遷移,可以拿SQL Server舉例,如圖所示:
- 第一階段:遷移準備
- 第(1)步先插入RID去把需要隱藏的數據寫入到刪除表當中;
- 第(2)步把這些數據分配RID後生成Delta Colunm Store;
- 第二階段:遷移操作
- 第(3)步,把剛剛插入進去的RID刪除;
- 第(4)步,最後真正把Delta中相關的數據刪除,最後才把生成的增量列存合併到主列存中,達到了數據遷移的效果。
Dictionary-based migration
第三種基於字典的遷移,SAP HANA就是採用這種方式。如圖所示,它第一階段主要是針對每一列的數據做一個本地字典的方式映射過去增加對應的數據向量,第二階段,才會把這個字典加入到全局的字典,做一個全局的排序,最後合併到數據向量當中。
類型二:基於日誌的增量合併
關鍵技術:LSM-tree 和 B-tree
相關資料庫:F1 Lighting
這種類型分兩層:
- Memory-resident deltas(駐留記憶體的增量),主要是row-wise
- Disk-resident deltas(駐留磁碟的增量),主要是column-wise
Log-based delta merge
如圖所示,第一階段會把小文件、小delta按它到來的順序合併到增量的文件當中,第二階段會通過查找B樹來做一個有序合併,最終讓合併的Chunk是有序的。這主要涉及解決基於多版本的一些Log怎麼去做合併和摺疊,其中B樹主要的作用就是在有序合併時去加速數據查找的過程。
3. 技術總結
可歸類為有3種數據合併技術。分別是:
- 記憶體中增量合併;
- 基於磁碟的增量合併;
- 從主行存儲重建。
第一個類別定期將新插入的記憶體中增量數據合併到主列存儲。引入了幾種技術來優化合併過程,包括兩階段基於事務的數據遷移、字典編碼排序合併和基於閾值的變化傳播。
第二類 將基於磁碟的增量文件合併到主列存儲。為了加快合併過程,增量數據可以通過B樹進行索引,因此可以通過鍵查找有效地定位增量項。
第三類從主行存儲重建記憶體列存儲。這對於增量更新超過某個閾值的情況很典型,因此重建列存儲比合併這些具有大記憶體占用的更新更有效。
4. 對比
Comparisons of DS techniques in HTAP Databases
總體來看,基於記憶體的增量合併效率比較高,擴展性差點兒;基於日誌的合併,擴展性好,但是多重合併的代價會比較高。
Part4 查詢優化技術
HTAP中查詢優化技術主要涉及三個維度,包括:
Query Optimization in HTAP databases
1. In-Memory Column Selection
- 解決的問題:要從行存儲區中選擇哪些列進入記憶體呢?簡單的做法是全部選擇進去,但那樣存儲和更新的代價會很高,所以一般是基於歷史的統計信息和現有記憶體的預算來做權衡選擇。
- 解決方式:有兩種,第一種是熱力圖(Heatmap),第二種是整數規劃(Integer programming) ·
基於Heatmap,比如Oracle
通過訪問頻度來管理列存併進行熱力圖的製作。
Oracle 21c. Automating Management of In-Memory Objects., 2021.
如圖所示,首先根據最下方持久化行存(Persistent Storage)來選定一些候選列集(Candidate Columns),通過記錄候選集的訪問頻度。有些列就會變為Hot Columns,那麼就可以把最新的數據Load進去(圖中左下方的Populating)來達到加速查詢的效果;慢慢地也有一些列會變為Cold Columns,那麼就把這些冷列進行壓縮(Compressed Columnar data),然後最後排除(圖中右下方的Evicating)到記憶體當中,再選取其他被高頻訪問的列重覆進行。
基於Integer programming,比如Hyrise
Integer programming for 0/1 Knapsack problem,第一種基於熱力圖的方式完全沒有考慮選擇列的代價,那麼第二種就是把代價函數(cost-based optimization problem)考慮進去,再從二級存儲中選擇列。
Boissier, Martin, et al. "Hybrid data layouts for tiered HTAP databases with paretooptimal data placements." ICDE, 2018.
這個目標函數F(x→)就是要去優化所有的查詢代價函數fj(x→),而每個查詢代價函數要去衡量所選擇列的代價。總目標是最小化這個代價,要小於這個最大的A預算。(這裡不展開講了,感興趣可以閱讀這篇論文,也比較經典)
2. Hybrid Row and Column Scan
- 解決的問題:記憶體中選擇好列之後,如何利用混合行/列掃描加速查詢呢?這個比較前沿了,像Google的AlloyDB也支持這個特性。
- 解決方式:基於規則的計劃選擇(Rule-based)或者基於代價(Cost-based)的計劃選擇。主要決定查詢優化器要把哪些運算元下推到列存引擎當中。
Rule-based Optimization(RBO)
先定義一些掃描的規則,比如先看列掃描,再看行掃描。相關資料庫:Oracle、SQL server。
舉個例子,上圖中我們查找一些北京車子註冊的證書和顏色,在這種規則下就可以生成一個邏輯計劃樹,在這個邏輯計劃樹里,我們先去查找底層表到底是行存還是列存,如果是列存,就做列存的方式處理,如果是行存就做一個B樹的掃描。最後合併做一個連接再返回最終結果。
Cost-based Optimization(CBO)
基於代價的方式,解決的方式是先去對比列存掃描和行存/索引掃描的代價分別是多少,然後再決定查詢運算元在哪裡執行。
Compare the cost of row/index scan with the cost of columnar scan
3. CPU/GPU Acceleration for HTAP
這個基於硬體去做HTAP的加速。比如,基於CPU/GPU異構處理器的方式進行HTAP的處理。相關資料庫:RateupDB、Caldera。
CPU/GPU processors for HTAP
- Task-parallel nature of CPUs for handling OLTP
- CPU任務並行的特性可以用來處理OLTP
- Data-parallel nature of GPUs for handling OLAP
- GPU數據並行的特性可以用來處理OLAP
涉及到一些並行計算的知識,感興趣可以瞭解瞭解~
4. 技術總結
- HTAP的列選擇;
- 混合行/列掃描;
- HTAP 的 CPU/GPU加速。
第一種類型依靠歷史工作負載和統計數據來選擇從主存儲中提取的頻繁訪問的列到記憶體中。因此,可以將查詢下推到記憶體中的列存儲以進行加速。缺點是可能沒有選擇新查詢的列,導致基於行的查詢處理。現有方法依靠歷史工作負載的訪問模式來載入熱數據並驅逐冷數據。
第二種類型利用混合行/列掃描來加速查詢使用這些技術,可以分解複雜的查詢以在行存儲或列存儲上執行,然後組合結果。這對於可以使用基於行的索引掃描和完整的基於列的掃描執行的 SPJ 查詢來說是典型的。我們引入了基於成本的方法來選擇混合行/列訪問路徑。
第三種技術利用異構CPU/GPU架構來加速HTAP工作負載。這些技術分別利用CPU的任務並行性和GPU的數據並行性來處理OLTP和OLAP。然而,這些技術有利於高OLAP吞吐量,同時具有低OLTP吞吐量。
5. 對比
Query Optimization in HTAP databases
Part5 資源調度技術
對於 HTAP 資料庫,資源調度是指為 OLTP 和OLAP 工作負載分配資源。當前可以動態控制OLTP 和 OLAP 工作負載的執行模式,以更好地利用資源。
Resource Scheduling
1. 基於工作負載驅動的調度
Workload-driven Scheduling for HTAP,就是根據HTAP工作負載的執行性能進行動態的調度,線程和記憶體這些根據OLTP和OLAP的性能需求動態分配資源。相關資料庫: 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.
舉個慄子,第一種方式會分配更多的線程給OLTP或者OLAP,怎麼分配呢?會在Scheduler里配置一個Watch-dog監測器,來監測當前的Worker,有一些被阻塞的Worker就分配多一些Thread,有一些比較活躍的的,就讓它繼續執行。
- 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當中進行一些調度,通過實驗可以得知增加OLTP存儲資源時,OLAP的顏色是會變深的,這意味著影響越嚴重,所以還是建議在第三層儘量給OLAP多分配一些資源。
2. 基於新鮮度驅動的調度
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.
3. 技術總結
調度技術有兩種類型,工作負載驅動的方法和新鮮度驅動的方法。前者根據執行工作負載的性能調整OLTP和OLAP任務的並行度。例如,當CPU資源被OLAP線程飽和時,任務調度器可以在增大OLTP線程的同時降低OLAP的並行度。後一個切換了OLTP和OLAP的資源分配和數據交換的執行模式。例如,調度程式單獨控制OLTP和OLAP的執行以實現高吞吐量,然後定期同步數據。一旦數據新鮮度變低,它就會切換到共用 CPU、記憶體和數據的執行模式。其他與 HTAP 相關的技術,還有新的 HTAP 索引技術和橫向擴展技術。
4. 對比
Resource Scheduling in HTAP databases
第一種優點是比較容易實現,但是新鮮度較低;第二種方式優點是新鮮度高,但來回切換容易導致系統震蕩。
Part6 其他相關的HTAP技術
這裡不展開介紹了,感興趣可以看看相關的Paper。
1. 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.
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]
Abebe, Michael, Horatiu Lazu, and Khuzaima Daudjee. Proteus: Autonomous Adaptive Storage for Mixed Workloads. In SIGMOD, 2022.
Part7 HTAP的基準測試
下一期我們將介紹針對HTAP基準測試的相關進展,在我們的第二期學術分享會裡,也介紹過來自慕尼黑工業大學(TMU)資料庫組的研究:StoneDB:解讀《Benchmarking Hybrid OLTP&OLAP Database Systems》| StoneDB學術分享會
感興趣可以前往查看,這篇文章只是其中一種基準測試的方法,想瞭解還有哪些方法麽?歡迎關註StoneDB公眾號,我們下期見~