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

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

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

0 引言

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

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

1 相關(guān)研究

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 Q-learning算法

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

圖1 Q-learning算法結(jié)構(gòu)Fig.1 Structure of Q-learning algorithm

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

1）Environment。

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

2）Agent。

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

3）Action。

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

4）State。

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

5）Reward。

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

3.2 MVM_QL

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

算法1 MVM_QL。

4 實驗與結(jié)果分析

4.1 參數(shù)設置

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

表1 AnalyticDB PostgreSQL 參數(shù)設置Tab.1 Parameter setting of AnalyticDB PostgreSQL

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

表2 MVM_QL參數(shù)設置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 在不同數(shù)據(jù)量下的性能，實驗采用的TPC-H 基表的數(shù)據(jù)量依次為0.03 GB、0.09 GB、0.15 GB、0.21 GB 和0.27 GB。實驗過程中數(shù)據(jù)量與環(huán)境的設置見表3。

表3 數(shù)據(jù)量與環(huán)境的設置Tab.3 Setting of data size and environment

4.2 結(jié)果分析

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

表4 平均IOPSTab.4 Average IOPS

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

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

表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 仍然顯著優(yōu)于無算法。id 為7 的實驗中，MVM_QL 展現(xiàn)出了最優(yōu)性能，低于無算法2.19 個百分點。MVM_QL 和無算法的平均CPU（2 核）利用率隨著數(shù)據(jù)量的增加而明顯上升。

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

表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 仍然顯著優(yōu)于無算法。id 為2 的實驗中，MVM_QL 展現(xiàn)出了最優(yōu)性能，低于無算法1.08 個百分點。

5 結(jié)語

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