面向單記錄的混合負載下物化視圖異步增量維護任務生成

孫洋洋，姚俊萍，李曉軍，范守祥，王自維

（1.火箭軍工程大學 301教研室，西安 710025；2.中國人民解放66133部隊，北京 100043；3.火箭軍工程大學 205教研室，西安 710025）

0 引言

由于全量維護僅適用于大量數據被修改的情形［1］、同步維護將會降低事務的速度［2］、定期維護無法滿足實時性需求［3］以及混合負載（Hybrid Transaction/Analytical Processing，HTAP）避免復雜耗時的抽取-轉換-加載（Extract-Transform-Load，ETL）進而消除聯機分析處理（On-Line Analytical Processing，OLAP）滯后性的優勢［4］，因此HTAP 物化視圖異步增量維護已經成為物化視圖維護研究的熱點。

HTAP 物化視圖異步增量維護任務生成是HTAP 物化視圖異步增量維護的核心步驟，但是現有研究［5］主要為面向多記錄的HTAP 物化視圖異步增量維護任務生成（簡稱為多記錄維護任務生成），無法實現面向單記錄的HTAP 物化視圖異步增量維護任務生成（簡稱為單記錄維護任務生成），導致磁盤IO 開銷的增加，進而降低HTAP 物化視圖異步增量維護性能。基于此，本文開展了單記錄維護任務生成研究，實現了面向單記錄的HTAP 物化視圖異步增量維護任務生成，研究成果彌補了現有研究的不足。

1 相關研究

物化視圖的維護是在候選視圖物化代價預測、物化視圖選擇［6］之后需要解決的第3 個問題，目前已經開展了十分豐富的研究。從維護時機方面，可以分為同步維護、異步維護和定期維護，后兩者也稱為延遲維護。在Vinh 等［7］開展的針對結構化查詢語言（Structured Query Language，SQL）遞歸查詢的維護研究中，不難發現同步維護的特征為當基表中數據變化后維護任務立即執行。蔡磊等［8］開展的面向區塊鏈的維護研究中，在CPU 空閑時依次執行維護任務隊列內容，當查詢到來時優先維護與查詢相關的物化視圖，因此異步維護的特點是將維護任務推遲至合適時機執行。定期維護在一段固定的時間后執行，例如一天執行一次維護［3］。從維護技術方面，可以分為全量維護和增量維護。全量維護是增量維護的替代方案，全量維護意味著一旦基表發生變化，物化視圖需要被完全覆蓋，因此僅僅適用于大量數據被修改的情形［1］。從Solank［9］基于輔助關系設計的維護過程中，可以得出增量維護的特點是僅僅維護“凈更改（net changes）”對應的物化視圖。從服務對象方面，可以分為服務于OLAP 的維護和服務于HTAP 的維護。傳統的物化視圖維護任務是服務于OLAP 的，但是此時聯機事務處理（On-Line Transaction Processing，OLTP）與OLAP 之間存在隔閡，需要ETL 實現兩者的連接，導致OLAP 及其采用的物化視圖存在滯后性［10］。隨著工業界與學術界研究的不斷深入，同時支持OLTP 與OLAP 的HTAP 的出現解決了上述問題［11］。綜上，鑒于同步維護將會降低事務的速度［2］、定期維護無法滿足實時性需求［3］、全量維護僅適用于大量數據被修改的情形［1］以及HTAP 消除OLAP 滯后性的優勢［4］，HTAP 物化視圖異步增量維護已經成為物化視圖維護研究的熱點。

HTAP 物化視圖異步增量維護任務生成是HTAP 物化視圖異步增量維護的核心步驟，相關研究尚處于起步階段，目前僅有華東師范大學的Duan 等［5］于2020 年開展了相關研究，他們基于貪心算法在每一輪迭代中對多記錄維護任務生成所需的訪問任務（簡稱為多記錄訪問任務，單記錄維護任務生成所需的訪問任務簡稱為單記錄訪問任務）進行匹配，目標是發現磁盤訪問范圍最為相似即多記錄維護任務生成效益最高的一組多記錄訪問任務和事務。Duan 等的研究［5］實現了在執行成本增長約束下盡可能多地合并執行多記錄訪問任務和事務，一定程度上減少了磁盤IO 開銷，提高了HTAP 物化視圖異步增量維護性能；但是當訪問任務和事務涉及單記錄時，Duan 等的研究［5］無法根據訪問范圍計算維護任務生成代價，訪問任務和事務的獨立執行消耗大量的磁盤IO 開銷，進而降低HTAP 物化視圖異步增量維護性能，因此，單記錄維護任務生成已經成為HTAP 物化視圖異步增量維護任務的研究重點。

已有多記錄維護任務生成算法主要基于貪心算法［5］，貪心算法靜態設置的約束條件無法適應維護任務生成過程中存在的HTAP 的變化、數據量的增減和硬件的更新等負載和環境的動態變化。隨著強化學習的不斷發展，數據庫領域與強化學習相結合已經成為必然的趨勢；因此將單記錄維護任務生成過程建模為馬爾可夫決策過程（Markov Decision Process，MDP）并基于智能體與環境交互實現自適應負載和環境的動態變化，將是單記錄維護任務生成未來十分具有前景的研究方向。

強化學習是與無監督學習、有監督學習并列的第三種機器學習范式，具體可以分為無模型強化學習［12］和模型化強化學習［13］。模型化強化學習首先利用智能體與環境交互獲得的數據建立環境模型［14］，然后利用環境模型決定下一步動作。當面對的問題具有復雜的狀態動作空間時，準確估計環境模型存在巨大挑戰［15］，無模型強化學習中智能體通過與未知環境交互并根據反饋決定下一步動作，因此無需提前擬合出環境模型。無模型強化學習具體可以分為基于策略梯度和基于價值函數兩種類型［16］。基于策略梯度的無模型強化學習廣泛應用于連續型強化學習問題之中［17］，并不適用于具有離散動作空間的單記錄維護任務生成問題；基于價值函數的無模型強化學習主要分為狀態-動作-獎勵-狀態-動 作（State-Action-Reward-State-Action，SARSA）算法和Q-learning 算法［15］。SARSA 算法于1994 年提出，是一種同軌策略算法，采用ε-貪心算法更新動作與價值函數［18］；Q-learning 算法最早由Watkins［19］于1989 年提出，是一種離軌策略算法，采用ε-貪心算法更新動作，采用貪心算法更新價值函數。SARSA 算法和Q-learning 算法的區別在于價值函數的更新［20］：前者采用ε-貪心算法，后者采用貪心算法。雖然SARSA 算法具有更快的收斂速度，但是其容易陷入局部最優解［21］，因此本文采用Q-learning 算法進行單記錄維護任務生成研究。

2 面向單記錄的HTAP 物化視圖異步增量維護任務生成效益模型

本文研究的目標為通過合并執行單記錄訪問任務和事務來減少磁盤IO 開銷，因此在2.1 節首先需要對基于單記錄訪問任務和事務生成單記錄維護任務過程進行形式化；與此同時，單記錄訪問任務和事務的匹配是否合理，需要相關效益模型進行量化評價，因此在2.2 節對單記錄維護任務生成效益模型進行詳細闡述。

2.1 形式化基于單記錄訪問任務和事務生成單記錄維護任務過程

在實際應用中，物化視圖往往基于多個基表構建，第x個查詢Qx可以表示為：

其中：??表示連接運算。對于包含GROUP、LIMIT 等運算類型的查詢，可以在式（1）的基礎上進行元素的豐富，例如包含GROUP 的查詢可以表示為：

其中：Gx表示Qx中GROUP 部分包含的元素。結合式（1），物化視圖Mx表示為：

其中：π表示投影運算。結合式（2），可以將式（4）改寫為：

1）插入事務觸發的單記錄維護任務生成。

當向基表中的i位置插入記錄時，的增量出現，此時表示為：

此時基表的集合Tx產生的增量dnewTx代表著插入事務觸發生成的單記錄維護任務，表示為：

2）刪除事務觸發的單記錄維護任務生成。

此時Tx產生的增量doldTx代表著刪除事務觸發生成的單記錄維護任務，表示為：

3）更新事務觸發的單記錄維護任務生成。

此時Tx產生的增量dupdTx代表著更新事務觸發生成的單記錄維護任務，表示為：

2.2 單記錄維護任務生成效益模型

結合式（7）（9）和（11），基于多個基表構建的物化視圖在單個或多個基表發生插入、刪除和更新時失效，此時單個基表的增量并不等價于單記錄維護任務，還需要訪問其他基表與對應的部分，此時單記錄訪問任務產生。對于大量的單記錄訪問任務，可以通過在處理后續事務的過程中順帶完成，即通過合并執行單記錄訪問任務與事務，實現共享磁盤IO，進而提高HTAP 物化視圖異步增量維護性能。

本文研究的目標為通過匹配執行單記錄訪問任務和事務減少磁盤IO 開銷。每秒進行讀寫操作次數（Input/output Operations Per Second，IOPS）是衡量磁盤IO 開銷的主要指標，IOPS 越低，單記錄訪問任務和事務合并執行后占用的系統資源越低。IOPS 的計算方式［22］如下：

其中：Tseek代表尋道時間，Trotation代表旋轉延遲。因此面向單記錄的HTAP 物化視圖異步增量維護任務生成效益模型可以表示為：

3 基于Q-learning 的面向單記錄的HTAP 物化視圖異步增量維護任務生成算法

3.1 Q-learning算法

Q-learning 算法主 要由環 境（Environment）、智能體（Agent）、狀態（State）、動作（Action）和獎勵（Reward）這5 部分組成，如圖1 所示。

圖1 Q-learning算法結構Fig.1 Structure of Q-learning algorithm

Agent 做 出Action，Environment 的State 發生轉 移，Environment 隨后對Agent 的Action 給予Reward。Agent 通 過不斷地與Environment 進行交互，從每個State 的累積收益值中選擇最大值對應的Action 形成其最優策略。接下來詳述Q-learning 算法的各個組成部分［23］。

1）Environment。

本文通過單記錄訪問任務與事務的匹配生成單記錄維護任務，由于單記錄訪問任務和事務發生在數據庫之中，因此本文將支持HTAP 和物化視圖的數據庫作為Environment。

2）Agent。

單記錄維護任務生成本質上屬于計算機操作系統（Operating System，OS）的磁盤存儲器管理問題。當進程即本文中的單記錄訪問任務和事務試圖從磁盤訪問數據時，OS 使用磁盤調度算法將磁頭從當前位置移動到包含所需扇區的磁盤面。由于磁頭的Action 是唯一可以與Environment進行交互的元素，因此本文將磁頭設置為Agent。

3）Action。

Agent 負責做出Action，即磁頭負責在各個扇區移動，實現了單記錄訪問任務和事務的合并執行，進而決定了單記錄維護任務的生成；因此是否將單記錄訪問任務和事務進行的合并是Agent 的Action，即Action=｛合并，不合并｝。

4）State。

Agent 做出Action，Environment 的State 發生轉移，State 所發生的轉移本質上是單記錄訪問任務和事務的匹配情況，因此本文將單記錄訪問任務和事務的匹配情況視為State。

5）Reward。

Environment 的State 發生轉移，Environment 隨后對Agent的Action 給予Reward，本文將單記錄維護任務生成效益即式（13）等價于Reward。

3.2 MVM_QL

通過將單記錄維護任務生成過程建模為MDP。基于Q-learning 的面向單記錄的HTAP 物化視圖異步增量維護任務生成算法（Materialized View Asynchronous Incremental Maintenance Task Generation Algorithm under HTAP for Single Record based on Q-learning，MVAIMTGAHTAPSRQ）為便于表述，本文后續部分將MVAIMTGAHTAPSRQ 簡寫為MVM_QL。MVM_QL 可以基于智能體與環境的交互，實現自適應HTAP的變化、數據量的增減和硬件的更新等負載和環境的動態變化。MVM_QL 的具體流程如算法1 所示。

算法1 MVM_QL。

4 實驗與結果分析

4.1 參數設置

實驗采用的數據倉庫為某云服務供應商提供的支持HTAP 的AnalyticDB PostgreSQL，參數設置見表1。實驗采用的數據來源于美國交易處理效能委員會提供的商業智能計算測試數據集TPC-H。

表1 AnalyticDB PostgreSQL 參數設置Tab.1 Parameter setting of AnalyticDB PostgreSQL

MVM_QL 的回合數max_episodes、學習率α、折扣因子γ、貪婪度ε等參數設置如表2 所示。

表2 MVM_QL參數設置Tab.2 Parameter setting of MVM_QL

為了模擬HTAP 的變化，本文開展了10 組實驗，每組實驗需要完成隨機生成的7 個單記錄訪問任務和7 個事務的匹配。為了模擬硬件的更新，1、3、5、7 和9 號實驗硬件配置為2C16GB，2、4、6、8 和10 號實驗硬件配置為4C32GB。為了研究MVM_QL 在不同數據量下的性能，實驗采用的TPC-H 基表的數據量依次為0.03 GB、0.09 GB、0.15 GB、0.21 GB 和0.27 GB。實驗過程中數據量與環境的設置見表3。

表3 數據量與環境的設置Tab.3 Setting of data size and environment

4.2 結果分析

表4 展示了基于MVM_QL 與無算法指導的單記錄維護任務生成在平均IOPS 方面的對比，MVM_QL 整體上顯著優于無算法。

表4 平均IOPSTab.4 Average IOPS

平均IOPS 的最大值和最小值方面，MVM_QL 次數分別為8.85 和8.22，無算法次數分別為18.65 和17.31，因此在平均IOPS 的最大值和最小值方面MVM_QL 仍然顯著優于無算法。id 為7 的實驗中，MVM_QL 展現出了最優性能，低于無算法10.07 次。綜上，本研究已經取得了較好的效果。

同時對CPU 利用率進行了觀察，表5 展示了基于MVM_QL 與無算法指導的單記錄維護任務生成在平均CPU（2 核）利用率方面的對比，MVM_QL 整體上顯著優于無算法。

表5 平均CPU（2核）利用率 單位：%Tab.5 Average utilization of CPU（2-core） unit：%

平均CPU（2 核）利用率的最大值和最小值方面，MVM_QL 分別為1.81%和1.45%，無算法分別為4.00%和3.49%，因此在平均CPU（2 核）利用率的最大值和最小值方面MVM_QL 仍然顯著優于無算法。id 為7 的實驗中，MVM_QL 展現出了最優性能，低于無算法2.19 個百分點。MVM_QL 和無算法的平均CPU（2 核）利用率隨著數據量的增加而明顯上升。

表6 展示了基于MVM_QL 與無算法指導的單記錄維護任務生成在平均CPU（4 核）利用率方面的對比，MVM_QL 整體上顯著優于無算法。

表6 平均CPU（4核）利用率 單位：%Tab.6 Average utilization of CPU（4-core）unit：%

平均CPU（4 核）利用率的最大值和最小值方面，MVM_QL 分別為0.89%和0.71%，無算法分別為1.91%和1.73%，因此在平均CPU（4 核）利用率的最大值和最小值方面MVM_QL 仍然顯著優于無算法。id 為2 的實驗中，MVM_QL 展現出了最優性能，低于無算法1.08 個百分點。

5 結語

本文建立了面向單記錄的HTAP 物化視圖異步增量維護任務生成的效益模型，設計了基于Q-learning 的面向單記錄的HTAP 物化視圖異步增量維護任務生成算法。實驗結果表明，本文提出的MVM_QL 實現了面向單記錄的HTAP 物化視圖異步增量維護任務生成，減小了IOPS、CPU 利用率等系統資源利用率，減少了磁盤IO，對于進一步提升HTAP 物化視圖異步增量維護性能具有的重要理論和應用價值。本文僅采用IOPS 作為評價生成的單記錄維護任務優劣的指標，因此發掘IOPS、內存利用率、CPU 利用率等內在關系并建立多元評價模型，將是下一步的研究重點。