邊緣計算系統中基于UCBM算法的緩存預取優化*

孫 波,郭祖華

(1.河南工學院 計算機科學與技術學院,河南 新鄉 453003;2.河南工學院 教學質量監控與評估中心,河南 新鄉 453003)

0 引言

邊緣計算是一種使計算機數據存儲更接近需要位置的分布式計算模式,它能夠在網絡邊緣端為接近終端用戶提供計算、存儲資源等服務[1],目前已廣泛應用于眾多領域,例如實時數據處理、自動駕駛、虛擬現實和智能家居等。隨著智能終端設備和云服務的高速發展,網絡邊緣端會產生海量的數據,如果將所有數據上傳至云端,那么從終端設備傳輸數據到云服務器將會產生長時間的延遲,而某一種單獨的云計算模式往往并不能起到良好的效果[2]。

預取技術是一種通過預測將要訪問的數據并將其提前讀取到緩存中的技術,緩存預取是提高存儲系統性能的重要手段,已經被證明是一種擴展邊緣計算能力的有效方法,如程小輝[3]等提出了一種基于馬爾可夫鏈的內存預測分配算法,該算法利用內存分配的轉移量統計信息及其概率矩陣對嵌入式系統內存動態分配進行預測,減少了內存創建的時間,但該方法在緩存命中率方面存在不足;石星[4]采用深度學習設計了緩存預取算法,以存儲塊相關研究為基礎提出挖掘技術,同時預測數據序列,將順序預測與數據序列預測有效結合以完成算法設計,但該方法存在精度不高的問題;王朝[5]等提出一種基于博弈論的數據協作緩存策略,首先多區域劃分邊緣計算環境,然后區域之間相互協作緩存數據資源,對不同區域的緩存價值進行計算與對比,制定緩存策略,該方法整體策略較好,但緩存精度有待提高;CESELLI[6]等為移動接入網絡提出了一種全面的移動邊緣云網絡設計框架,從整體視角研究了霧計算、移動邊緣計算和移動云計算的邊緣范式,并且分析了這些邊緣范式存在的安全威脅、挑戰和機制;HU[7]等針對通過WiFi接入點輔助的電視點播內容,提出了一種基于學習的內容預取方法,用以解決邊緣網絡中服務器負載的時變問題,但存在預取動態性較差、預取命中率低以及帶寬利用率不足等問題;WANG[8]等研究了移動網絡中的緩存相關技術,并且提出了一種基于以內容為中心網絡或者以信息為中心網絡概念的新的邊緣緩存策略,但對于研究數據的覆蓋不夠全面。

針對終端用戶希望加速數據訪問和減少用戶感知延時的相關請求,本文提出一種在邊緣計算環境中基于貝葉斯網絡和馬爾可夫鏈的用戶分類(User Classification based on Bayesian network and Markov chain,UCBM)算法的緩存預取優化策略,該策略可以提前將所需文件置于邊緣服務器緩存中,并能提高預取的精確率、覆蓋率,從而有效地降低時延,加速終端用戶訪問[9-12]。

1 基于UCBM的邊緣計算系統模型

在基于UCBM的邊緣計算系統模型中,預取技術的主要任務是來預測用戶的訪問對象。在這種模型中,通過貝葉斯網絡和馬爾可夫鏈對用戶的下一步訪問對象進行分類與預測。

1.1 用戶訪問假設

在預測模型中,用戶的訪問行為被看作一項任務,依據其訪問的特征,執行訪問一系列相關文件的任務。設計兩個用戶訪問假設如下:

假設1:依據不同用戶在請求訪問文件時的不同情況,用戶可以分為K個類別,集合U={u1,u1…uk}用來表示一類用戶。然后,P=(U=uk)是具體用戶屬于分類uk的概率。根據以上內容,公式1可以定義為:

(1)

假設2:相同類型用戶的瀏覽進程將會以不同的方式顯示相同或相似的特征,并且他們的瀏覽過程是一種隨機過程,可以描述為一種同構離散的馬爾可夫鏈。

基于以上兩種假設,研究者建立了貝葉斯網絡用來對用戶瀏覽行為進行預測,并構建了馬爾可夫鏈模型用來通過用戶分類進行文件緩存預取。

1.2 基于馬爾可夫鏈模型的用戶分類

基于馬爾可夫鏈模型的用戶分類可以用一個五元組表示:。這里X是一個同構離散的變量,域是{x1,x2,…,xn},它們中的每一個xi對應一個文件資源,也被稱為一個模型狀態,K是用戶的分類數量,P(U)是屬于不同用戶不同分類的概率分布,KA={A1,A2,…Ak}和Kλ={λ1,λ2,…λk}分別是分類馬爾可夫鏈的轉移概率矩陣和初始狀態概率分布。每一個元素Ak代表屬于一個具體分類uk的用戶轉移概率矩陣。λk代表用戶在這個分類中的初始狀態概率,MU={mu1,mu2,…muk}是分類馬爾可夫鏈的集合,每一個元素muk是描述用戶分類瀏覽特征的馬爾可夫鏈。據此,給出轉移矩陣和馬爾可夫鏈的初始狀態分布如下:

(2)

假設(x1,x2,…,xl)是用戶訪問序列,用來預測用戶的下一個狀態,包括用戶分類判斷和任務預測。在判斷用戶類別時,依據貝葉斯理論,確定用戶是否屬于某一類別的概率表示為:

(3)

其中P(x1,x2…,xl)是對于任意用戶瀏覽序列的概率,這個概率定義為:

(4)

其中P(x1,x2…,xl|U=uk)代表在用戶分類uk瀏覽序列中的發生概率:

(5)

為了實現任務預測,可以對用戶進行分類之后,通過馬爾可夫鏈描述用戶的瀏覽特征。同時,為了提高模型的預測精度,研究者在模型中引入用戶在請求訪問過程中的歷史信息,并利用多階加權組合進行預測:

V(t)=w1H(t-1)×A1+w2H(t-1)×A2…+whH(t-1)×Ah

(6)

然后引入一個新的變量Ah來表示馬爾可夫鏈的h階轉換矩陣,wi是權值,并且滿足等式w1+w2…+wh=1。設置閾值γ,如果V(t)≥γ,將這個任務視為主要任務,由此完成用戶分類。

1.3 緩存預取過程設計

用戶分類完成后,通過用戶請求,系統在完成一個訪問任務后再繼續執行下一個任務,該過程中產生的變量稱為任務的轉移概率Ak。當前的訪問任務是tv(t),系統會將擁有最高轉移概率的任務作為預取任務。然后將預測任務的相應文件預取至緩存,從而減少重復請求延遲,提高系統訪問效率。因此研究者設計了根據用戶任務預測提前將所需文件進行緩存的方式,從而提高預取效率,實現緩存預取。具體緩存預取過程如下。

首先,通過分析字節網絡,計算具體用戶瀏覽序列的發生可能性,然后將預取文件加入緩存中。如果沒有足夠的緩存空間,一些文件將通過替換策略被移除出去。緩存預取的過程如圖1所示。

圖1 緩存預取過程圖

在緩存得到所需文件后,若長時間不發生預取行為則需要進行替換。具體執行過程為:在被替換之前,如果預取文件在時間間隔Tphc之間從沒有被訪問,預取命中率的效率將會降低。通過分析,新的預取文件將替換之前在時間間隔Tphc從來未被訪問的預取文件。為了優化緩存過程,研究者設置了以下規則:

將一個計數器分配給一個文件。計數器的值counte是一個變量,用來記錄緩存命中數量,并且設初始值為零。如果文件預取命中緩存,這個文件的counte加1。CreateTime是預取文件的創建時間,AccessTime是訪問預取文件的最近時間,ReplaceTime是緩存替換執行的時間。

如果預取文件可以處理用戶請求,文件預取將會命中緩存。此時這個預取文件的counte是1,這個預取文件的CreateTime是當前時間,并且這個預取文件的AccessTime為空。當緩存空間不足,有兩種可能:如果AccessTime-Createtime

在歷史執行任務基礎上,任務預測算法預測出下一個將執行的任務。然后找到任務要訪問的所有文件。對于每一個文件,本算法計算出緩存的成本-利潤和垃圾收集成本,選擇擁有更高緩存利益和更低垃圾回收成本的文件作為預取文件。

2 UCBM算法描述

本文所用的UCBM算法是通過偽代碼來描述任務預測和文件過濾的。首先,在歷史執行任務的基礎上,通過UCBM算法預測下一個將要執行的任務,然后找出任務要訪問的所有文件(算法的第2—3行)。對于每個文件,計算緩存成本-收益和垃圾收集成本(算法的第5—6行)。選擇緩存收益高、垃圾回收成本低的文件作為預取文件(算法的第7—9行)。算法要避免驅逐從未被使用過的預取文件并滿足某些特定條件(算法的第12—27行)。UCBM算法的偽代碼具體描述如下:

Input: 歷史任務集:Z={z1,z2,…,zn}.

Output:預取文件:f={f1,f2,…,fm},FileContent.∥FileContent包括count,Createtime和AccessTime

1 1.初始化歷史任務集 {z1,z2,…,zn}

2zc←通過UC模型預測下一個要執行的任務

3F←通過UCBM算法預測下一個執行任務zc對應的候選預取文件

4count=0

5foreachf'∈Fdoes

6CPf′=Pr*(tloc+tread) ∥f'的緩存成本-收益

9f←f'∥f'是選擇的預取文件

10endif

11endfor

12foreachf”∈Fdoes

13if(f″isincachefile)then∥f″是用戶訪問文件

14f″.count=1

15f″.CreateTime=now

16f″.AccessTime=null

17else

18f″.count++

19f″.CreateTime=null

20

21endif

22endfor

23if(緩存空間不足)then

24foreach(f″是預取文件)

25if(f″.AccessTime-f”.CreateTime≥T)then

26 基于替換策略來替換f”

27endif

28endfor

29if(f″.AccessTime-f″.CreateTime

30f″←cache.find Min Countmax Access Time( )

31f″

32endif

33endif

在整個算法執行過程中,邊緣服務器先要對數據進行預處理操作,即通過UCBM算法對接入用戶進行分類,確定預取文件,然后再計算每個候選預取文件的緩存成本-收益和垃圾收集成本。如果預取的文件在內存緩存中,用戶的需求將得到響應;否則,預取的文件將從云端緩存到邊緣服務器,暫時不響應用戶需求。

3 實驗過程及結果分析

3.1 實驗環境

本實驗通過構建校園網中的邊緣計算系統來驗證緩存預取的優化策略的有效性。整個系統包含一個作為主節點的邊緣協調器(EO),負責邊緣服務器管理和計算服務協調;多個作為仆從節點的邊緣服務器(ESs),擁有計算/存儲資源并且提供邊緣計算服務。

邊緣協調器的配置為Intel(R) Core W(TM) i7-9700K@3.60GHz CPU和32GB RAM。每一個邊緣服務器的配置為Intel(R) Core (TM) i5-9600KF@3.7GHz CPU和8GB RAM。終端用戶通過鄰近部署的邊緣服務器請求服務。研究者部署Apache Hadoop3.2.1作為邊緣計算系統的基礎系統,每個節點都有Java JDK11.0.5運行在Ubuntu14.04.1 LTS之上,基本開發環境設置為Linux Eclipse 4.5.0。

3.2 數據來源

實驗使用工作負載合成工具Hibench生成五組工作負載套件(Bin1—Bin5),它們作為終端用戶提交到邊緣計算服務器的計算任務數據。表1描述了這五組工作負載套件的特點。

表1 工作負載套件特征值

這些工作負載套件中的精確率、覆蓋率指標可以驗證基于UCBM算法的緩存預取的性能。

3.3 評價指標

本文提出的評估測度策略可以分析算法的預測性能。該策略的評估指標包括精確率、覆蓋率。

3.3.1 預取精確率

精確率是指正確被緩存預取的文件集合與實際緩存預取的文件集合的比值,定義為Accuracy=R-LS/LS。

3.3.2 覆蓋率

覆蓋率是指用戶訪問的文件集合與預測系統文件的比值,可定義為coverage=R-LS/RS。

3.4 進行過程

研究者在評估基于預測的緩存預取算法時使用了上述的五組工作負載套件,這些工作負載套件由Hibench同步。為了展示本文算法的相關性能,實驗分別與文獻[4]所使用的——結合“最近使用流行度”替換策略的基于馬爾可夫鏈的緩存命中率算法和文獻[5]所使用的——基于深度學習的預取算法進行了測試對比。

3.5 結果分析

3.5.1 預取精確率

圖2和圖3分別顯示了訓練數據集文件大小和文件數量對精確率的影響。如圖2所示,橫坐標為Filesize to cache size(緩存文件大小)、縱坐標為Prefetching Accuracy Rate(預取精確率)。隨著文件的增大,精確率下降。因為緩存空間有限,訪問文件越大,預測系統文件中可容納的訪問文件數越小,因此系統精確率越低。本文算法比文獻[4]和文獻[5]算法有更好的精確率,平均精確率分別提高48.3%和13.95%。

如圖3所示,橫坐標為File size to cache(緩存文件大小)、縱坐標為Prefetching Accuracy Rate(預取精確率)。隨著訓練數據集中文件數量的增加,不同算法的精確率均得到提升,并且當文件數量達到一定值時趨于穩定。這是因為訓練數據集中包含的文件越多,可以從緩存中獲取的文件就越多,因此精確率也就越高。從圖中可以明顯看出,本文算法的最低精確率為0.66,最高精確率為0.78,而其他兩種算法的最高精確率均不超過0.7,明顯低于本文算法。因此,本文算法的性能明顯優于文獻中的兩種算法。

圖2 文件大小對預取精確率的影響 圖3 文件數量對預取精確率的影響

3.5.2 覆蓋率

圖4和圖5分別顯示了文件大小和文件數量對覆蓋率的影響。如圖4所示,橫坐標為File Size to Cache(緩存文件大小)、縱坐標為Coverage Rate(覆蓋率)。當文件增大,覆蓋率下降。因為緩存空間有限,訪問文件越大,在預測系統文件中可以提供的訪問文件數量越少,因此系統精確率越低。對比文獻[4]和文獻[5]的算法,本文算法擁有更好的覆蓋率,最低覆蓋率為0.52,而其他兩種算法的最低覆蓋率為0.4和0.3。這是因為在文件預取之前,本文算法通過預測和掃描已經過濾掉了一些不必要的文件,只有下一次執行任務并且滿足預定義預取條件的文件才能預取到緩存中,因此占用的內存最少。

如圖5所示,橫坐標為The Number of Files(文件數量)、縱坐標為Coverage Rate(覆蓋率)。隨著文件數量的增加,覆蓋率增加。這是因為隨著任務的執行,系統中被加入緩存的訪問文件會越來越多。但是本文算法在預測系統文件集合中能夠提供更多的訪問文件,通過UCBM預測和預取條件的過濾,避免了不必要的文件預取,因此最高覆蓋率達到0.73,具有明顯的優勢。

圖4 文件大小對覆蓋率的影響 圖5 文件數量對覆蓋率的影響

4 結論

針對從終端設備傳輸數據到云服務器將會產生長時間延遲的問題,本文提出了一種基于貝葉斯網絡和馬爾可夫鏈算法的緩存預取優化策略。在該策略中,預取文件通過馬爾可夫鏈的預測來確定下一個要執行的任務。然后對于緩存效益更高的和垃圾收集成本更低的文件,實施進一步過濾,并確定進行緩存的邊緣服務器,如果緩存空間不足,會進行緩存替換。在邊緣計算系統中對算法的性能進行了評價。實驗結果表明,與已有算法相比,本文算法有效地提高了預取精確率和覆蓋率,最高精確率為0.78,最高覆蓋率達到了0.73,具有明顯的優勢。

由于本文所提出的策略是基于響應式方法,這對于分布式決策是適用的,但對于集中式緩存決策適用性不高。未來將改進替換策略,對緩存預取做進一步的優化。