孫 波,郭祖華

(1.河南工學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,河南 新鄉(xiāng) 453003;2.河南工學(xué)院 教學(xué)質(zhì)量監(jiān)控與評(píng)估中心,河南 新鄉(xiāng) 453003)

0 引言

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

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

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

1 基于UCBM的邊緣計(jì)算系統(tǒng)模型

在基于UCBM的邊緣計(jì)算系統(tǒng)模型中,預(yù)取技術(shù)的主要任務(wù)是來預(yù)測(cè)用戶的訪問對(duì)象。在這種模型中,通過貝葉斯網(wǎng)絡(luò)和馬爾可夫鏈對(duì)用戶的下一步訪問對(duì)象進(jìn)行分類與預(yù)測(cè)。

1.1 用戶訪問假設(shè)

在預(yù)測(cè)模型中,用戶的訪問行為被看作一項(xiàng)任務(wù),依據(jù)其訪問的特征,執(zhí)行訪問一系列相關(guān)文件的任務(wù)。設(shè)計(jì)兩個(gè)用戶訪問假設(shè)如下:

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

(1)

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

基于以上兩種假設(shè),研究者建立了貝葉斯網(wǎng)絡(luò)用來對(duì)用戶瀏覽行為進(jìn)行預(yù)測(cè),并構(gòu)建了馬爾可夫鏈模型用來通過用戶分類進(jìn)行文件緩存預(yù)取。

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

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

(2)

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

(3)

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

(4)

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

(5)

為了實(shí)現(xiàn)任務(wù)預(yù)測(cè),可以對(duì)用戶進(jìn)行分類之后,通過馬爾可夫鏈描述用戶的瀏覽特征。同時(shí),為了提高模型的預(yù)測(cè)精度,研究者在模型中引入用戶在請(qǐng)求訪問過程中的歷史信息,并利用多階加權(quán)組合進(jìn)行預(yù)測(cè):

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

(6)

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

1.3 緩存預(yù)取過程設(shè)計(jì)

用戶分類完成后,通過用戶請(qǐng)求,系統(tǒng)在完成一個(gè)訪問任務(wù)后再繼續(xù)執(zhí)行下一個(gè)任務(wù),該過程中產(chǎn)生的變量稱為任務(wù)的轉(zhuǎn)移概率Ak。當(dāng)前的訪問任務(wù)是tv(t),系統(tǒng)會(huì)將擁有最高轉(zhuǎn)移概率的任務(wù)作為預(yù)取任務(wù)。然后將預(yù)測(cè)任務(wù)的相應(yīng)文件預(yù)取至緩存,從而減少重復(fù)請(qǐng)求延遲,提高系統(tǒng)訪問效率。因此研究者設(shè)計(jì)了根據(jù)用戶任務(wù)預(yù)測(cè)提前將所需文件進(jìn)行緩存的方式,從而提高預(yù)取效率,實(shí)現(xiàn)緩存預(yù)取。具體緩存預(yù)取過程如下。

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

圖1 緩存預(yù)取過程圖

在緩存得到所需文件后,若長(zhǎng)時(shí)間不發(fā)生預(yù)取行為則需要進(jìn)行替換。具體執(zhí)行過程為:在被替換之前,如果預(yù)取文件在時(shí)間間隔Tphc之間從沒有被訪問,預(yù)取命中率的效率將會(huì)降低。通過分析,新的預(yù)取文件將替換之前在時(shí)間間隔Tphc從來未被訪問的預(yù)取文件。為了優(yōu)化緩存過程,研究者設(shè)置了以下規(guī)則:

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

如果預(yù)取文件可以處理用戶請(qǐng)求,文件預(yù)取將會(huì)命中緩存。此時(shí)這個(gè)預(yù)取文件的counte是1,這個(gè)預(yù)取文件的CreateTime是當(dāng)前時(shí)間,并且這個(gè)預(yù)取文件的AccessTime為空。當(dāng)緩存空間不足,有兩種可能:如果AccessTime-Createtime

在歷史執(zhí)行任務(wù)基礎(chǔ)上,任務(wù)預(yù)測(cè)算法預(yù)測(cè)出下一個(gè)將執(zhí)行的任務(wù)。然后找到任務(wù)要訪問的所有文件。對(duì)于每一個(gè)文件,本算法計(jì)算出緩存的成本-利潤(rùn)和垃圾收集成本,選擇擁有更高緩存利益和更低垃圾回收成本的文件作為預(yù)取文件。

2 UCBM算法描述

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

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

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

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

2zc←通過UC模型預(yù)測(cè)下一個(gè)要執(zhí)行的任務(wù)

3F←通過UCBM算法預(yù)測(cè)下一個(gè)執(zhí)行任務(wù)zc對(duì)應(yīng)的候選預(yù)取文件

4count=0

5foreachf'∈Fdoes

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

9f←f'∥f'是選擇的預(yù)取文件

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″是預(yù)取文件)

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

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

3 實(shí)驗(yàn)過程及結(jié)果分析

3.1 實(shí)驗(yàn)環(huán)境

本實(shí)驗(yàn)通過構(gòu)建校園網(wǎng)中的邊緣計(jì)算系統(tǒng)來驗(yàn)證緩存預(yù)取的優(yōu)化策略的有效性。整個(gè)系統(tǒng)包含一個(gè)作為主節(jié)點(diǎn)的邊緣協(xié)調(diào)器(EO),負(fù)責(zé)邊緣服務(wù)器管理和計(jì)算服務(wù)協(xié)調(diào);多個(gè)作為仆從節(jié)點(diǎn)的邊緣服務(wù)器(ESs),擁有計(jì)算/存儲(chǔ)資源并且提供邊緣計(jì)算服務(wù)。

邊緣協(xié)調(diào)器的配置為Intel(R) Core W(TM) i7-9700K@3.60GHz CPU和32GB RAM。每一個(gè)邊緣服務(wù)器的配置為Intel(R) Core (TM) i5-9600KF@3.7GHz CPU和8GB RAM。終端用戶通過鄰近部署的邊緣服務(wù)器請(qǐng)求服務(wù)。研究者部署Apache Hadoop3.2.1作為邊緣計(jì)算系統(tǒng)的基礎(chǔ)系統(tǒng),每個(gè)節(jié)點(diǎn)都有Java JDK11.0.5運(yùn)行在Ubuntu14.04.1 LTS之上,基本開發(fā)環(huán)境設(shè)置為L(zhǎng)inux Eclipse 4.5.0。

3.2 數(shù)據(jù)來源

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

表1 工作負(fù)載套件特征值

這些工作負(fù)載套件中的精確率、覆蓋率指標(biāo)可以驗(yàn)證基于UCBM算法的緩存預(yù)取的性能。

3.3 評(píng)價(jià)指標(biāo)

本文提出的評(píng)估測(cè)度策略可以分析算法的預(yù)測(cè)性能。該策略的評(píng)估指標(biāo)包括精確率、覆蓋率。

3.3.1 預(yù)取精確率

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

3.3.2 覆蓋率

覆蓋率是指用戶訪問的文件集合與預(yù)測(cè)系統(tǒng)文件的比值,可定義為coverage=R-LS/RS。

3.4 進(jìn)行過程

研究者在評(píng)估基于預(yù)測(cè)的緩存預(yù)取算法時(shí)使用了上述的五組工作負(fù)載套件,這些工作負(fù)載套件由Hibench同步。為了展示本文算法的相關(guān)性能,實(shí)驗(yàn)分別與文獻(xiàn)[4]所使用的——結(jié)合“最近使用流行度”替換策略的基于馬爾可夫鏈的緩存命中率算法和文獻(xiàn)[5]所使用的——基于深度學(xué)習(xí)的預(yù)取算法進(jìn)行了測(cè)試對(duì)比。

3.5 結(jié)果分析

3.5.1 預(yù)取精確率

圖2和圖3分別顯示了訓(xùn)練數(shù)據(jù)集文件大小和文件數(shù)量對(duì)精確率的影響。如圖2所示,橫坐標(biāo)為Filesize to cache size(緩存文件大小)、縱坐標(biāo)為Prefetching Accuracy Rate(預(yù)取精確率)。隨著文件的增大,精確率下降。因?yàn)榫彺婵臻g有限,訪問文件越大,預(yù)測(cè)系統(tǒng)文件中可容納的訪問文件數(shù)越小,因此系統(tǒng)精確率越低。本文算法比文獻(xiàn)[4]和文獻(xiàn)[5]算法有更好的精確率,平均精確率分別提高48.3%和13.95%。

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

圖2 文件大小對(duì)預(yù)取精確率的影響 圖3 文件數(shù)量對(duì)預(yù)取精確率的影響

3.5.2 覆蓋率

圖4和圖5分別顯示了文件大小和文件數(shù)量對(duì)覆蓋率的影響。如圖4所示,橫坐標(biāo)為File Size to Cache(緩存文件大小)、縱坐標(biāo)為Coverage Rate(覆蓋率)。當(dāng)文件增大,覆蓋率下降。因?yàn)榫彺婵臻g有限,訪問文件越大,在預(yù)測(cè)系統(tǒng)文件中可以提供的訪問文件數(shù)量越少,因此系統(tǒng)精確率越低。對(duì)比文獻(xiàn)[4]和文獻(xiàn)[5]的算法,本文算法擁有更好的覆蓋率,最低覆蓋率為0.52,而其他兩種算法的最低覆蓋率為0.4和0.3。這是因?yàn)樵谖募A(yù)取之前,本文算法通過預(yù)測(cè)和掃描已經(jīng)過濾掉了一些不必要的文件,只有下一次執(zhí)行任務(wù)并且滿足預(yù)定義預(yù)取條件的文件才能預(yù)取到緩存中,因此占用的內(nèi)存最少。

如圖5所示,橫坐標(biāo)為The Number of Files(文件數(shù)量)、縱坐標(biāo)為Coverage Rate(覆蓋率)。隨著文件數(shù)量的增加,覆蓋率增加。這是因?yàn)殡S著任務(wù)的執(zhí)行,系統(tǒng)中被加入緩存的訪問文件會(huì)越來越多。但是本文算法在預(yù)測(cè)系統(tǒng)文件集合中能夠提供更多的訪問文件,通過UCBM預(yù)測(cè)和預(yù)取條件的過濾,避免了不必要的文件預(yù)取,因此最高覆蓋率達(dá)到0.73,具有明顯的優(yōu)勢(shì)。

圖4 文件大小對(duì)覆蓋率的影響 圖5 文件數(shù)量對(duì)覆蓋率的影響

4 結(jié)論

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

由于本文所提出的策略是基于響應(yīng)式方法,這對(duì)于分布式?jīng)Q策是適用的,但對(duì)于集中式緩存決策適用性不高。未來將改進(jìn)替換策略,對(duì)緩存預(yù)取做進(jìn)一步的優(yōu)化。