VLDB'22 HiEngine極致RTO論文解讀

摘要：《Index Checkpoints for Instant Recovery in In-Memory Database Systems》是由華為云資料庫創新Lab一作發表在資料庫領域頂級會議VLDB'2022的學術論文，

本文分享自華為云社區《VLDB'22 HiEngine極致RTO論文解讀》，作者：云資料庫創新Lab ，

1. HiEngine簡介

HiEngine是華為云自研的一款面向云原生環境的OLTP型資料庫， HiEngine在標準TPC-C事務模型下， 端到端單節點(華為2488H V5機型)性能可以達到663w+的tpmC， 多節點擴展性線性度超過0.8， 其核心架構關鍵詞如下:

• 計算，記憶體，存盤三層分離式云原生架構
• 華為云原生的分布式記憶體資料庫
• 同時包含分離式記憶體池和分離式存盤池

具體HiEngine詳細的技術架構和性能表現，可以參考我們團隊發表在SIGMOD2022 [1]的論文作業，

2. HiEngine對日志恢復的優化

此外， HiEngine還擁有極致的RTO恢復性能，在100GB資料集下，可以達到10s級別的恢復時間， 本文將詳細闡述HiEngine在追求極致RTO程序中提出的若干技術，

2.1 記憶體資料庫的經典恢復流程

回溯學術界現有的作業， 我們可以把記憶體資料庫的恢復大體劃分為幾大步驟:

• STEP1: 加載最近一次成功執行的元組檢查點資料;
• STEP2: 回放檢查點到故障點期間的日志資料;
• STEP3: 掃描元組資料，重建記憶體索引結構;

我們團隊充分結合HiEngine架構的特點和學術界State of the art的一些作業， 提出了結合HiEngine Indirection array結構特點的dataless checkpoint和indexed logging恢復技術， 因此需要首先介紹一下什么是HiEngine的Indirection array，

2.2 Indirection Array

與大多數工業/學術系統一般， HiEngine內部采用多版本的方式維護Tuple元組資料， 并且Tuple并沒有按頁面進行組織，而是按照版本鏈的方式組織， 每個邏輯元組用一個全域唯一的RowID標識， 所有的RowID以一個全域的陣列進行組織， 該陣列我們姑且稱作Indirection Array， 并且， HiEngine索引中每個葉子節點存盤的是RowID而不是具體的tuple address，

Indirection Array的設計有如下幾點好處:

1. 更新操作不用修改索引;
2. 非唯一索引可以通過添加RoWID后綴轉換為唯一索引;
3. 記憶體元組和日志記錄統一編址， Indirection Array中存放的address既可以是記憶體元祖的頭指標地址， 也可以是record對應的log record的offset地址;
4. Indexed-Logging;
5. Dataless Checkpoint;

下一章節我們將對Indexed logging和Dataless checkpoint展開描述，

2.3 Indexed-logging

HiEngine繼承了"the log is the database"日志即資料庫的概念， 具體來說Indirection Array中存放的地址既可以是記憶體的tuple，也可以是一個對應在記憶體中的log offset， (我們使用uint64的最高一個bit標識是記憶體地址還是磁盤偏移， 因為對于64bit的作業系統的指標高12bit都為0)，

另一方面， 多版本系統在恢復后， 只需要恢復最新版本的資料即可， 因為舊版本的資料在系統重啟后對事務不再可見， 因此， 在系統一旦故障時， HiEngine只需要并行掃描日志流， 把對應的log record的offset偏移設定到Indirection array的對應位置即可， 注意這一程序中還可以對多個日志流采用并行掃描和并行設定log offset的方式加速，

一旦系統恢復時，把最新版本的log offset設定到對應的Indirection Array的TID位置后， HiEngine系統即可開始作業， 對于首次訪問到某一TID時， 系統會加載offset位置的record， 在線生成一個新版本的tuple資料， 我們稱作為bringOnline Lazily，

并且在系統運行期間， HiEngine可以識別冷Tuple資料， 對Tuple資料進行凍結并轉存成log record， 同時修改對應RoWID的address為log record的offset

2.4 Dataless checkpoint

檢查點執行的頻率決定了需要恢復的日志量的上限， 因此為了追求盡可能快的恢復時間， 檢查點執行的頻度必須得高， 這就對檢查點演算法本身提出了更高的性能需求:(1) 單次檢查點執行時間必須要快; (2) 檢查點不能導致前端事務性能明顯的抖動;

因為記憶體元組支持多版本的優勢， 可以極其容易獲取事務一致性的快照資料， 常規的檢查點演算法是獲取該快照資料并對快照存盤， 但常規的方式必然導致需要存盤的快照資料量大， 進而導致checkpoint時間較長，

而HiEngine的做法不甚相同， (1) HiEngine在事務預提交階段， 把存盤日志的offset反向回填到對應tuple資料的header中存放， (2) 因此在Checkpoint獲取事務一致性快照后， 并不是把快照中的tuple資料存盤， 而是把對應tuple header中的offset進行持久化， 并且以一個序列化的Indirection Array存盤，

總結: HiEngine這種將快照對應的log offset存盤的checkpoint方法叫做DataLess Checkpoint， 其相比于對快照進行存盤的方式， 需要序列化存盤的資料量少， 對前端事務影響的時間也更短， 恢復時加載檢查點的時間也更短，

2.5 階段性優化與遺留瓶頸

Indexed Logging和Dataless checkpoint只是解決了章節2.1提到的STEP1和STEP2的性能瓶頸， 這也是當下很多學術作業關注的優化重心， 我們通過實驗對比， 在百GB規模的TPCC資料集下， 沒采用Indexed logging和Dataless checkpoint技術的恢復時間在310s左右， 采用了Indexed logging和Dataless checkpoint技術后，可以把恢復時間減少到50+ s，

但是50+ s離HiEngine期望的目標仍有距離， 因此我們的作業重心需要聚焦到如何優化STEP3中索引重建的時間， 進一步追求極致的RTO時間目標，

3. HiEngine對索引恢復的優化

3.1 索引檢查點的必要性

首先， 需要指出的是元組資料可以通過加載檢查點并回放日志的方式得以恢復， 但索引資料則需要重建的方式才能得以恢復，

必要性: 主要原因在于索引并沒有檢查點， 如果索引也存在索引檢查點資料， 索引資料的恢復也可以加載索引檢查點資料， 然后通過重做insert和delete的log record恢復checkpoint之后的index索引項，

因此宏觀樸素的想法是通過索引檢查點對HiEngine索引重建的耗時問題進行優化， 但是:

(1) 索引本身并不支持多版本， 因此無法無阻塞的獲取事務一致性的快照資料， 換句話說， 索引檢查點必然是模糊Fuzzy型別的檢查點，

(2) 而HiEngine的日志只有redo沒有undo， 如何保證恢復出來的資料沒有臟資料，并且不丟失索引項， 總之， 如何保證資料的正確性，

(3) 并且由于索引不支持快照隔離， 如何無阻塞的獲取索引檢查點也是一項重要的性能問題，VLDB這篇論文針對正確性和性能兩個維度展開討論HiEngine的索引檢查點，

3.2 索引檢查點的正確性

我們通過一個示例展示， HiEngine如何保證檢查點資料的正確性，

如圖所示， 我們假設存在一個理想化的演算法能夠獲取快照隔離級別并且事務一致性的索引檢查點資料， 對應的元組檢查點和快照檢查點分別標識為TS和IS1， 此種情況資料元祖檢查點和索引檢查點獲取的都是時間戳在180時刻的事務一致性的快照資料， 恢復后很容易保證資料的正確性，

但是現實的情況是索引只能"嘗試"捕獲當前觸發檢查點時刻的資料， 此時在索引中必然存在尚未提交事務的索引項， 因此捕獲到的檢查點資料必然是非事務一致的， 或者說是模糊的(Fuzzy checkpoint)， 我們用IS2標識，

對比IS1和IS2可以發現， IS2相比于IS1差異的索引項是來自于phase2階段的操作， 前文已經說過， 因為Indirection array的設計， update操作不會修改索引， 因此我們需要針對insert和delete操作提出資料正確性保證的措施:

(1) 插入操作: 對于在phase2階段的插入操作， 一旦系統恢復時加載檢查點后， 我們應該能識別出phase2節點插入的臟資料， 因為tuple資料是可以保證事務一致性和資料正確性的， 在系統訪問index時，我們需要對index和對應tuple不匹配的索引認定為"臟資料"， 并觸發補償性洗掉動作， 同時給客戶端回傳不存在該索引項，

(2) 洗掉操作: 對于在phase2階段洗掉的索引項， 因為恢復時只回放檢查點之后日志， 該索引項必將在恢復后丟失lost了， 因此我們應該需要阻止phase2階段的index洗掉動作的執行， 剛好， HiEngine和很多MVCC系統一樣， delete當做是交給GC模塊延后執行的， 我們只需要確保gc的watermark在檢查點觸發時滯后于checkpoint時間戳即可，也就是說 gc timestamp = min{minStartTs-1， minEndTs-1}， 詳細可以翻閱論文，

3.3 索引檢查點的性能目標

上一章節， 我們通過"恢復后識別并洗掉臟索引資料"和"阻止滯后gc"的方式能夠保證的正確性， 但如何保證索引檢查點的性能仍是一個問題，

樸素的想法是停掉前端事務并復制索引資料， 但這肯定會導致很長時間的阻塞， 因此， 我們首先給出一個優化的索引檢查點演算法應該滿足一下4個條件:(1) Wait Free processing; (2) Efficient index operations; (3) Fast and frequent checkpoints; (4) Load friendly checkpoint file format， 具體對性能需求的描述， 可以查閱我們的論文， 并且， 我們提出了三種Index checkpoint的演算法，

3.4 ChainIndex

ChainIndex通過多顆物理索引樹維護一個邏輯索引， 其按照每次checkpoint產生一個新的索引樹的方式產生一顆新的索引樹， 索引樹組織成一個鏈表的形式， 鏈表頭的索引作為寫入索引， 維護一個檢查點周期內的增量索引樹， 非鏈表頭的索引樹都作為只讀結構存盤， 并且ChainIndex會在后臺合并若干個delta樹，

檢查點程序: 在每次檢查點執行觸發時， HiEngine首先凍結鏈表頭的索引樹， 與此同時原子性產生一個新的索引結構用于接受新啟動事務的索引修改操作， 對于尚未結束的索引操作仍然寫入到凍結的索引樹， 待所有尚未提交的索引操作結束后， 我們采用后序遍歷的方式產生一個mmap友好的checkpoint檔案，

恢復程序: 每次恢復時HiEngine只需通過mmap的方式加載checkpoint檔案; 然后， 回放日志恢復checkpoint之后的索引項，

總結: ChainIndex總體架構啟發來自于LSM， 對寫操作友好， 但(1)存在嚴重的讀放大問題， (2) 并且ChainIndex只支持增量檢查點，不支持全量檢查點，

3.5 MirrorIndex

MirrorIndex在ChainIndex的基礎上， 通過引入一個額外的full tree或者說是mirror tree， 從而解決ChainIndex的讀放大缺點， 其在每一次insert或delete時， 同時對headTree和mirror tree進行修改， 可以確保headtree包含一個檢查點周期的增量資料， mirror tree包含全量資料， 因此， 讀操作直接訪問mirror index即可，

MirrorIndex的checkpoint流程和ChainIndex一樣， 但恢復流程有很大不同， 其恢復流程如下

1. mmap映射增量檢查點檔案到記憶體中
2. 回放日志恢復headTree的資料
3. 步驟2完成后， 系統便可以接受服務了，但此時性能表現和ChainIndex類似， 有嚴重的讀放大問題， 與此同時， HiEngine觸發后臺rebuild mirror index的程序， 待mirrorIndex重建完成后， 讀放大問題消失

總結: MirrorIndex相比ChainIndex消除了讀放大的問題， 但卻(1)存在一定的讀放大， (2)并且MirrorIndex需要引入額外的樹結構， 記憶體占用很多， (3) MirrorIndex只支持增量檢查點，(4)恢復后，有一個短暫的性能"爬坡"階段，

3.6 Indirection Array CoW

ChainIndex和MirrorIndex總體思想都是采用delta資料的思想，維護增量檢查點， 另一大類的策略是采用Copy On Write的思想， 針對樹結構的CoW演算法是Path Copying， 其修改拷貝節點時會導致父節點的指標發生修改， 從而導致級聯修改， 這會導致性能下降很多， 并且路徑拷貝會導致索引并發的lock free演算法需要適配， 作業量大，

因此我們放棄了Path Copying的策略， 通過引入Indirection array的方式引入"邏輯索引節點"的概念， 從而消除級聯拷貝的問題， IACoW對每個index node分配一個唯一的node ID， 并且parent node的child pointer存放的不在是記憶體指標地址， 而是修改為子節點的node id， 此時修改拷貝節點時不需要修改父節點指標，

另外我們引入checkpoint epoch number來識別index node的新舊版本， 具體來說， 每次checkpoint全域epoch自動加一， 不同checkpoint周期因為copy on write產生的新版本用不同epoch number標識， checkpoint執行流程中， 我們通過掃描Indirection array， 并根據epoch number可以捕獲增量和全量兩種型別的檢查點資料， 恢復時， 通過mmap的方式即可恢復checkpoint資料， 具體的node版本管理， node的gc以及checkpoint資料組織形式等細節問題，可以查閱論文，

總結: IACoW同時支持增量和全量檢查點， 并且IACoW引入的額外記憶體并不多， 但是IACoW會因為pointer chasing導致少許讀放大，

4. HiEngine恢復性能評估

實驗程序中， 我們首先評估checkpoint對性能抖動的影響， 結果展示MirrorIndex和IACoW在checkpoint期間性能影響并不大， 但ChainIndex由于讀放大問題性能抖動嚴重，

同時我們測驗了在相同配置下， 不同演算法的恢復時間， 結果顯示在例外下點時， IACoW可以保證在10s的時間內完成恢復，

在正常下電時， IACoW可以保證在2s的時間內完成恢復，

并且我們在TPC-C和microbench負載下， 實驗反應MirrorIndex和IACoW對端到端性能的影響在10%以內， 但卻可以換取10s級別的RTO保障，

我們在控制相同事務性能的前提下， 測驗各自的索引記憶體空間開銷， 實驗表明， IACoW的額外記憶體開銷很小， 但MirrorIndex需要x2的記憶體開銷，

我們總結對比各種方案的優缺點如下:

5. 總結

論文首先發現記憶體資料庫的索引重建是一個性能瓶頸點， 并得到了評委們的一致認可， 摘錄VLDB Reviewers對論文的選題評價，

The authors observed that, in today’s systems, the performance bottleneck in recovery is in restoring indexes. This is a cute observation which I consider important to the system community.

Overall, it is an important contribution to point out index restoration as the new performance bottleneck - I wasn’t aware of this before.

As the techniques have been improved with database recovering, this work claims that index rebuilding becomes a bottleneck of in-memory database recovering. This observation is very interesting, and it motivates the need of fast index recovering (instead of fast index reconstruction).

針對索引重建的瓶頸點， 本文探討了索引正確性的保證，并提出了3個索引檢查點演算法， 最終在端到端的HiEngine系統中，對比評估了各自的優缺點， 實驗結果表明， IACoW演算法在100GB規模下可以達到10s級的恢復時間， 對于有極致RTO需求的場景， 可以引入該演算法提速恢復，

參考文獻:

[1] Yunus Ma, Siphrey Xie, Henry Zhong, Leon Lee, and King Lv. 2022. HiEngine: How to Architect a Cloud-Native Memory-Optimized Database Engine. In Proceedings of the 2022 International Conference on Management of Data (SIGMOD '22). Association for Computing Machinery, New York, NY, USA, 2177–2190. https://doi.org/10.1145/3514221.3526043

展現領先科研實力，華為云資料庫創新LAB三篇論文入選國際資料庫頂級會議VLDB'2022

華為云資料庫創新lab官網：https://www.huaweicloud.com/lab/clouddb/home.html

We Are Hiring：https://www.huaweicloud.com/lab/clouddb/career.html ，簡歷發送郵箱：[email protected]

華為云資料庫創新Lab 時序資料庫openGemini正式開源，開源地址：https://github.com/openGemini，誠邀開源領域專家加入！

點擊關注，第一時間了解華為云新鮮技術~

標籤：其它

上一篇：強擴展、強一致、高可用…GaussDB成為游戲行業的心頭愛

下一篇：MySQL DDL 、DML、DQL陳述句