基于“推薦-學習”的兩階段數據布局策略

梁 楊,丁長松,胡志剛

(1.湖南中醫藥大學信息科學與工程學院,湖南 長沙 410208)(2.湖南省中醫藥大數據分析實驗室,湖南 長沙 410208)(3.中南大學計算機學院,湖南 長沙 410083)

近年來,智能手機、聯網汽車、AR/VR等智能設備快速普及,各類移動終端產生的數據量呈爆炸式增長[1]. 多接入邊緣計算(multi-access edge computing,MEC)作為一種鄰近計算范式,其本質是云計算向邊緣網絡的延伸. MEC允許邊緣服務器分布在不同的地理位置,將計算和存儲資源部署在移動用戶附近,因此可以提供比云計算服務更低延遲[2]. MEC框架在滿足訪問時延的前提下,在節省網絡帶寬、提高服務質量(quality of service,QoS)、緩解數據中心壓力等方面具有天然的優勢. 然而,在數據密集型應用場景下因資源受限所帶來的一系列問題正引起研究者們的廣泛關注[3]. 由于邊緣節點存儲資源有限,數據密集型應用會頻繁地進行遠程數據訪問,從而導致較高的往返延遲,甚至完全抵消MEC的優勢[4].

在MEC環境中,大量移動邊緣設備將不斷產生和消費各類數據,不恰當的副本管理策略極易導致網絡資源浪費和通信延遲過高[5]. 一方面,當處理本地用戶任務的數據訪問請求時,由于邊緣節點存在嚴重自治,通常需要分別創建副本以減少遠程數據訪問的次數,很容易出現副本的高冗余存儲和高頻次更新,導致“副本泛濫”、資源浪費等問題[6];另一方面,云邊網絡用戶對數據副本的多邊高并發請求具有隨機性和區域性,增加了“副本管理失控”的風險[7]. 因此對數據副本進行全局部署時,需要綜合權衡局部和全局的資源互補與沖突,進而確定最佳副本布局.

一般,不合理的副本部署不僅會增加任務響應延遲,還會增加網絡和存儲開銷[8]. 為解決上述問題,本文提出一種基于“推薦-學習”的兩階段數據布局策略(two-stage data placement strategy,TDPS),通過“推薦”階段和“學習”階段對副本放置規則進行深度優化. TDPS綜合考慮了副本流行度和用戶移動性,旨在實現訪問延遲和成本開銷的權衡優化. 綜上所述,本文的主要貢獻包括4個方面:

(1)提出了一種基于“推薦-學習”的兩階段副本管理框架,通過將MEC環境下副本決策過程分解為“邊緣推薦”和“整體學習”兩個階段,有效整合了邊緣端的局部信息和云端的全局信息,優化了副本管理機制;

(2)對目標問題進行形式化描述并構建了數學模型,將MEC中的副本放置決策問題描述為具有延遲和成本約束的雙目標優化問題;

(3)在“推薦”階段,提出一個基于移動預測和反饋優化的副本推薦引擎,一定程度上解決了盲目創建副本的問題;在“學習”階段,提出一個基于A3C強化學習的副本放置規則學習模型,從全局視角下進一步保證了云邊系統的數據服務性能最優;

(4)實驗結果表明,本文基于“推薦-學習”的兩階段數據布局策略可以有效降低數據管理成本并改善用戶QoS滿意度.

1 相關工作

隨著云計算和邊緣計算逐步融合,如何提高云邊系統的副本管理效率成為一個新興的研究熱點,引起國內外研究者的廣泛關注[9]. 一些研究學者提出了基于數據流行度的靜態副本策略[10],在指定的存儲節點上設置固定的副本數量;而另外一些研究人員則提出了動態副本策略[11-12],允許根據用戶的行為特征動態地調整副本數量和位置. Jin等[13]提出了一種邊端協作存儲框架,在邊緣計算環境中協作存儲必要的數據,以提高邊緣層的性能,減少將任務轉移到云數據中心的可能性. Vales等[14]提出一個將移動設備的存儲資源和霧節點集中起來的解決方案,有效解決了用戶訪問遠程云時面臨的訪問延遲、帶寬受限、通信開銷和位置盲目性等問題. Chang等[15]通過分析邊緣服務器的數據副本收入、成本和利潤,提出了面向MEC的自適應副本機制,有效地縮短了任務平均響應時間,提高了數據分組的服務質量.

由于邊緣端存儲資源和通信帶寬都存在一定限制,副本優化機制需要充分考慮資源受限條件下的副本管理. Teranishi等[16]提出了一種面向邊緣環境下物聯網應用的動態數據流平臺,不僅能夠使物聯網應用實現較小的延遲,而且可以避免物聯網應用對網絡和計算資源造成過載;研究者還提出了一個具有多因素最少使用算法的分布式多級存儲模型[17],為處理海量物聯網數據時可能面臨的存儲受限和網絡擁塞等問題提供了有效的解決方案;Aral等[18]提出了一種智能分布式數據部署方案,解決了數據訪問延遲和副本放置成本等問題.

以上早期研究雖然考慮了邊緣端資源的有限性,但主要不足之處在于沒有充分利用云端已有的高性能資源. 對此,一些研究者針對云邊系統的副本管理優化提出了若干新方法,其中最為突出的是基于機器學習的副本管理. Wang等[19]提出了一種基于強化學習的副本緩存框架,用于激勵邊緣設備為周邊用戶提供副本存儲服務;為了能夠自適應地利用網絡資源并降低任務響應時間,研究者還提出了一種基于深度強化學習的智能資源分配方案[20]. 以上研究顯示,機器學習技術在實現“在線副本服務”方面具有較好的自適應性和魯棒性.

綜上所述,優化數據布局既需要考慮邊緣資源的受限性,還需要考慮網絡傳輸速度的差異性. 本文從以上兩個方面來分析現有系統數據服務的性能瓶頸,并提出基于“推薦-學習”的兩階段數據布局策略來動態協調云端和邊緣端的存儲資源分配,以期充分利用云端的高性能來彌補邊緣端的資源短缺.

2 系統框架和數學模型

根據云邊環境下面向移動用戶的典型應用場景,本節提出了一個兩階段副本管理框架,并對目標問題進行模型構建.

2.1 基于“推薦-學習”的兩階段副本管理框架

在云邊協同系統中,一個有效的數據布局策略必須充分考慮云端和邊緣端資源性能的差異. 針對由此導致的一系列性能瓶頸問題,本文提出了一種基于“推薦-學習”的兩階段副本管理機制TDPS,其整體架構如圖1所示.

圖1 基于“推薦-學習”的兩階段副本管理架構

在圖1中,TDPS架構從邏輯上自下而上主要包含3層:用戶設備層、邊緣節點層和中心節點層.

(1)用戶設備層:主要包含各種具有移動性的用戶設備,需要向邊緣云或中心云請求數據服務.

(2)邊緣節點層:主要由分布式邊緣節點組成,各邊緣節點部署有副本推薦引擎、邊緣資源管理器和本地狀態信息表,負責向中心節點層推薦熱點副本.

(3)中心節點層:云數據中心是本層的重要組件,主要包括副本放置規則學習模型、全局資源管理器和全網資源狀態表,負責對全網數據布局進行決策.

2.2 問題描述與系統建模

假設E={e1,e2,…,en}表示所有邊緣節點的集合,n為邊緣節點的總數;F={f1,f2,…,fm}表示所有可訪問的文件全集,m為文件總數;SZfi表示文件fi的大小.用戶所感知的訪問延遲主要依賴于用戶和待訪問文件之間的距離,則用戶和其對應邊緣節點之間的平均等待延遲如式(1)所示.

(1)

式中,VE表示邊緣節點的數據傳輸速率;NRfi表示用戶請求訪問文件fi的總次數.Xfi,ej是一個二進制變量,用以表示fi的副本是否位于ej上,如果fi的副本位于ej上,則Xfi,ej=1;否則Xfi,ej=0.

簡化起見,假設云數據中心存儲了所有文件的副本,如果用戶對fi的訪問請求沒有在本地得到滿足,則必須向遠程云請求fi,用戶與云數據中心之間的平均等待延遲可以表示為式(2).

(2)

此外,資源開銷同樣制約著數據布局問題的決策.本文主要考慮副本放置過程中網絡傳輸成本和邊緣存儲成本對總成本的影響.網絡傳輸成本是指文件從云數據中心傳輸到邊緣節點所產生的網絡傳輸開銷,如式(3)所示.

(3)

式中,Tunit表示從云數據中心到邊緣節點的單位數據傳輸成本,Ctx表示總傳輸開銷.

此外,因副本放置造成的存儲開銷亦不容忽視,則邊緣節點的副本存儲成本可以表示為式(4)所示.

(4)

式中,Sunit表示邊緣節點上單位數據的存儲成本,Csto表示總存儲開銷.

目標問題進一步轉化為式(5)所示.

Ψ=μ(ALE+ALC)+η(Ctx+Csto),

(5)

式中,μ+η=1,0<μ,η<1.

基于上述分析,為表示延遲和成本敏感的數據布局問題,構建了如式(6)所示的雙目標優化函數.

(6)

3 基于“推薦-學習”的兩階段副本管理機制

本節提出一種基于“推薦-學習”的兩階段副本管理機制,綜合權衡全網的QoS和資源開銷,進而確定當前工作周期內最優的全局副本放置規則. 在副本推薦階段,通過在邊緣節點上構建副本推薦引擎快速、準確地量化邊緣層副本訪問價值,縮小存在副本需求的局部文件規模,避免云端/邊緣端盲目創建副本,使服務提供商在保證QoS的同時減少不必要的資源開銷;在副本放置階段,云數據中心基于強化學習構建全局副本放置規則學習模型,優化數據布局,以期指導副本管理中間件進行副本放置和替換,在QoS和成本開銷間達到最佳折中,從整體上改進云邊環境下副本服務的各類性能指標.

3.1 基于移動預測和反饋優化的副本推薦引擎

為了快速、準確地量化邊緣端副本價值,最大程度減小副本規模,本文首先在邊緣節點上構建副本推薦引擎,從局部層面上避免副本的盲目創建.

一方面,推薦引擎必須充分考慮用戶移動性和文件訪問特性,從而準確評估文件訪問概率;另一方面,引入反饋機制及時修正誤差,提高推薦引擎自適應性. 基于此,副本推薦引擎的框架如圖2所示.

圖2 基于移動預測和反饋優化的副本推薦引擎

由圖2可以看出,副本推薦引擎主要由輸入層、預測層、反饋層和推薦層組成. 其中,輸入層負責對數據進行預處理以滿足模型輸入的要求;預測層根據文件歷史流行度和用戶移動性來預測本地節點上不同副本的期望訪問概率;反饋層負責將副本的預測誤差輸入到反饋優化器,計算誤差期望并確定補償系數,及時反饋給預測層優化預測精度;推薦層負責篩選滿足條件的副本,從中選擇價值排名靠前的若干副本,構成副本推薦序列.

(7)

(8)

由此可見,副本推薦引擎同時考慮了邊緣節點上的文件歷史訪問流行度和用戶移動性的影響.

為改善價值評估模型性能,提高模型自適應能力,本文在推薦引擎中引入反饋層,對預測層結果進行誤差分析,通過補償系數進一步對模型進行修正,則式(8)進一步改進為式(9)所示.

(9)

式中,λtc表示在時段tc時的模型補償系數,且λtc>0.

最后,推薦引擎將根據副本期望訪問概率進行推薦,具體推薦過程如算法1所示.

首先,將tc時段邊緣節點es上的所有文件的期望訪問概率集作為推薦層的輸入;其次,根據價值閾值篩選出期望訪問概率不低于該閾值的文件;最后,如果存在滿足閾值要求的文件,則返回期望訪問概率中排名前K(K>0)的副本標識符列表.

算法1 副本推薦算法

② fori=1 tomdo

⑤ else

⑥FPPNew[i]=0;

⑦ end if

⑧ end for

⑨ ifFPPNew!=NULL then

⑩FPPTopK[·]=TopK(FPPNew);

3.2 基于A3C強化學習的副本放置規則學習模型

邊緣端推薦的副本序列存在一定的局部性限制,為保證全局層面的QoS和系統性能最優,本文提出一種基于異步優勢行動者-評論家算法(asynchronous advantage actor-critic,A3C)的副本放置規則學習模型,采用基于多線程機制的異步訓練框架,引入優勢函數對策略網絡(Actor)和價值網絡(Critic)進行更新,使模型在訓練速度、收斂性能和預測精度等方面具有更好的表現. 該模型由多個并行子線程和一個全局網絡組成,每個子線程由一個Actor和一個Critic組成,負責獨立運行Actor-Critic算法和并行進行參數探索,既獨立更新全局網絡參數,又從全局網絡獲取參數指導;全局網絡主要包括一個全局Actor和一個全局Critic,負責匯總子線程與環境交互的結果,異步更新全局網絡參數.

(10)

式中,T表示矩陣轉置,πj表示ej上的副本放置模式,πj,i表示fi的副本放置在ej上的概率,πj,i∈[0,1].πj,i=0表示fi的副本不能放置在ej上;反之,πj,i=1.

為有效度量智能體所選動作策略的優劣,本文提出一個延遲-成本組合獎勵函數,如式(11)所示.

(11)

式中,Lt(St,At)和Ct(St,At)分別表示在狀態-動作對(St,At)下的訪問延遲和成本開銷,LCt(St,At)表示組合獎勵.基于此,長期累計獎勵如式(12)所示.

(12)

式中,γ∈(0,1]為折扣因子,表示從環境狀態St開始,未來環境獎勵對累計獎勵的影響權重.顯然,模型訓練目標可以表示為最大化長期累計獎勵的期望,如式(13)所示.

(13)

式中,環境狀態S服從先驗分布F0,π表示在環境狀態St下選擇的副本放置策略,則此時狀態價值函數如式(14)所示.

Vπ(St)=Eπ[Rt|St=S],

(14)

類似地,智能體的動作價值函數如式(15)所示.

Qπ(St,At)=LCt(St,At)+γVπ(St+1),

(15)

為尋找使長期累計獎勵期望最大化的副本放置策略π,需要不斷更新策略參數θ,對此,智能體采用優勢函數來評價某一策略動作所產生的增益大小,如式(16)所示.

Aπ(St,At)=Qπ(St,At)-Vπ(St),

(16)

式中,Vπ(S)的值由Critic網絡訓練獲得,若Aπ(S,A)>0,則表示在狀態St下執行的動作有利于獎勵的增加,策略參數可以朝梯度方向更新以改進副本放置策略;反之,則不建議更新策略參數.為加快長期累計獎勵期望收斂,通過梯度上升法更新Actor策略網絡參數θ,如式(17)所示.

θ=θ+μθlogπ(At|St;θ)Aπ(St,At),

(17)

式中,π(At|St;θ)∈[0,1]表示在St和θ條件下執行At的概率,logπ(At|St;θ)∈[0,+∞)避免了梯度消失.μ為學習率,μ∈[10e-6,1].另外,為避免過早陷入局部收斂,在策略函數的損失函數中需增加π的交叉熵項,則式(17)可改進為式(18)所示.

θ=θ+μθlogπ(At|St;θ)Aπ(St,At)+ηθH[π(St;θ)],

(18)

式中,η為交叉熵權重因子,η∈[0,1].基于時間差分方法進行Critic價值網絡參數更新,其價值函數的損失函數如式(19)所示.

LOSS=(Qπ(St,At)-Vπ(St))2,

(19)

為加快式(19)所示損失函數收斂,通過梯度下降法更新Critic策略網絡參數θv,如式(20)所示.

(20)

式中,ε為學習率,ε∈[10e-6,1].對此,副本放置規則的A3C子線程學習算法偽代碼如算法2所示.

算法2 A3C子線程學習算法

輸入:環境狀態集合S,智能體動作集合A,A3C全局網絡的全局Actor參數θ和全局Critic參數θv,A3C子線程的Actor參數θ′和Critic參數θ′v,全局最大迭代次數Tmax和全局迭代計數器T,子線程單次迭代最大時間序列tmax和本地線程時間序列計數器t,折扣因子γ,學習率μ、ε,交叉熵權重因子η;

輸出:A3C全局神經網絡參數θ、θv.

①T=0 andt=1

② repeat

③ dθ←0 and dθv←0;

④θ′←θandθ′v←θv;

⑤tstart=tandSt=getState(t);

⑥ repeat

⑦ 基于π(At|St;θ′)執行動作At;

⑧ 獲得LCt(St,At) andSt+1;

⑨t←t+1 andT←T+1;

⑩ untilt-tstart==tmaxorSt==ST

4 結果與討論

為評價和分析所提出算法的性能,本文引入副本命中率、平均訪問延遲和成本節約率等[22]3項測試指標作為評估標準,將TDPS策略與其他基準算法進行比較,驗證所提算法在副本決策方面的有效性.

4.1 實驗環境設置

本文采用EdgecloudSim[23]平臺進行仿真實驗,模擬云邊環境. 邊緣節點的位置分布由BRITE[24]拓撲生成器給出,中心節點設置為距離各邊緣較遠的數據中心. 為了便于比較和分析,假定所有待訪問文件的大小相等,用戶提交的作業請求近似服從泊松分布,初始數據位置近似服從齊夫分布,用戶優先向附近邊緣節點提出訪問請求,實驗參數的詳細設置如表1所示.

表1 實驗設置

4.2 實驗結果與分析

本實驗將TDPS分別與D-ReP[18]、RPME[25]和HRS[26]3種基準算法在副本命中率、平均訪問延遲和成本節約率等方面進行對比,每次對比實驗采用同一性能指標,分別進行10組獨立重復實驗,以評估TDPS策略的性能,具體實驗結果與分析如下:

(1)副本命中率

副本命中率(replica hit rate,RHR)表示本地副本訪問次數占本地用戶請求總數的比例,用以衡量該策略的本地化水平,如式(21)所示.

(21)

圖3 不同副本部署策略的副本命中率比較

圖3表明,當并發請求規模較小時,TDPS的副本命中率與其他算法差距不大,甚至略低于某些算法;隨著并發請求數的增加,副本命中率總體呈上升趨勢,而TDPS的增長幅度明顯高于其他算法,說明其具有更好的副本放置決策能力. 主要原因是TDPS同時考慮了文件歷史流行度和用戶移動性帶來的影響,通過預測用戶位置并提前放置數據副本,有效提高了副本命中率;當并發請求規模較大時,各算法副本命中率的變化幅度不明顯,原因在于邊緣節點存儲空間有限,當副本數增加到一定程度后,僅進行必要的副本替換,副本命中率趨于穩定.

(2)平均訪問延遲

平均訪問延遲(average access latency,AAL)表示從作業提交數據訪問請求到作業執行完成的平均持續時間,如式(22)所示.

(22)

式中,ti(end)和ti(start)分別表示作業i的完成時間和開始時間,Q表示用戶提交的作業總數. 圖4對比了TDPS與基準算法在平均訪問延遲方面的表現.

圖4 不同副本部署策略的平均訪問延遲比較

由圖4可以看出,當并發請求數較少時,不同方法的平均訪問延遲差別不大,TDPS的平均訪問延遲甚至高于HRS,這是因為不同策略創建的副本數量均處于較低水平,使得服務響應時間較為接近;當并發請求數達到500左右時,TDPS的平均訪問延遲比D-ReP減少約17.9%,比RPME減少約24.6%,原因在于TRMM具有更高的副本命中率;隨著并發請求的增加,TDPS平均訪問延遲的增長率明顯低于其他算法,進一步說明TDPS能夠有效增加用戶就近訪問數據的機會.

(3)成本節約率

成本節約率(cost saving rate,CSR)表示在所有作業請求中邊緣節點完成的作業總費用與中心節點完成的作業總費用之比,如式(23)所示.

(23)

圖5 不同副本部署策略的成本節約率比較

在圖5中,當并發請求規模較小時,TDPS與其他基準算法的成本節約率差距不大,各策略的成本節約率隨著并發請求數的增加而增加;當并發請求數達到500時,與HRS、D-ReP和RPME 3個基準算法相比,TDPS分別能夠節約2.68%、5.57%和8.43%的成本開銷;之后,隨著并發請求規模繼續增大,不同算法的成本節約率雖時有波動,但變化幅度始終處于一個較小范圍,總體維持動態平衡. 總體而言,TDPS能夠更顯著地提高成本節約率,原因在于:一方面,TDPS通過分布式副本推薦引擎為各邊緣節點推薦個性化副本序列,控制了局部副本規模;另一方面,TDPS基于副本放置規則學習模型優化面向全網的副本放置決策,控制了全局副本規模. 因此,TDPS采用“推薦-學習”的兩級副本管理機制在成本控制方面的表現更優.

5 結論

本文提出一種基于“推薦-學習”的兩階段數據布局策略TDPS,解決云邊環境下面向數據密集型應用如何改善用戶QoS滿意度并降低云邊協同集群的管理和維護成本等核心問題. 采用基于移動預測和反饋優化的副本推薦引擎挖掘局部熱點副本,通過基于A3C強化學習的副本放置規則學習模型有機整合邊緣推薦信息,優化全網數據布局. 將TDPS與其他基準算法對比,實驗結果表明,所提出策略在不同測試指標下都明顯優于其他算法,驗證了所提出方法的有效性. 下一步工作將考慮如何根據大規模分布式節點異構性調整數據布局策略,并在真實場景下對研究問題進行實驗驗證.