李昊天，盛益強(qiáng)

（1.中國科學(xué)院聲學(xué)研究所國家網(wǎng)絡(luò)新媒體工程技術(shù)研究中心，北京 100190；2.中國科學(xué)院大學(xué)電子電氣與通信工程學(xué)院，北京 100049）

0 概述

邊緣計(jì)算是一種將計(jì)算資源和服務(wù)部署在網(wǎng)絡(luò)邊緣的計(jì)算節(jié)點(diǎn)或智能終端設(shè)備上的分布式計(jì)算方法［1］，相較于云計(jì)算，邊緣計(jì)算可以為用戶提供更低延遲的服務(wù)，在未來的網(wǎng)絡(luò)發(fā)展中將發(fā)揮重要的作用。邊緣存儲(chǔ)技術(shù)是邊緣計(jì)算中的一個(gè)重要研究課題，其核心在于邊緣網(wǎng)絡(luò)合理分配存儲(chǔ)資源，從而更好地降低用戶請求或節(jié)點(diǎn)請求的計(jì)算時(shí)延。

目前，邊緣存儲(chǔ)按照存儲(chǔ)位置的不同可以分為基站存儲(chǔ)［2］和移動(dòng)設(shè)備存儲(chǔ)［3］，其中，由于基站的容量和存儲(chǔ)性能高于異構(gòu)的移動(dòng)存儲(chǔ)設(shè)備，因此對基站存儲(chǔ)進(jìn)行研究更具實(shí)用價(jià)值。在基站存儲(chǔ)策略中，現(xiàn)有的研究方案分為協(xié)同式和非協(xié)同式兩類［4］。

在非協(xié)同式的存儲(chǔ)策略中，各個(gè)存儲(chǔ)節(jié)點(diǎn)獨(dú)立地根據(jù)收到的請求來存儲(chǔ)和調(diào)配資源，無需和其他基站進(jìn)行互動(dòng)和信息傳遞。非協(xié)同式的存儲(chǔ)策略包含基于用戶偏好［5］、基于馬爾科夫過程［6］、基于增強(qiáng)學(xué)習(xí)［7］等單點(diǎn)存儲(chǔ)策略，它們可以很好地降低時(shí)延和傳輸代價(jià)，但是由于信息不共享，各個(gè)節(jié)點(diǎn)的相同資源副本數(shù)量在全局上不可控，對于一些熱點(diǎn)內(nèi)容，其爆炸式增長的副本數(shù)量會(huì)帶來嚴(yán)峻的一致性問題，而一致性問題所引起的時(shí)延開銷將嚴(yán)重影響用戶體驗(yàn)質(zhì)量。

協(xié)同式的存儲(chǔ)策略利用基站之間的信息傳遞，通過合作提供對外服務(wù)。文獻(xiàn)［8］利用基站間的協(xié)同作用，當(dāng)一個(gè)基站缺少內(nèi)容資源時(shí)，會(huì)向最近的擁有該內(nèi)容的基站發(fā)出請求，從而降低該基站向云計(jì)算中心的請求次數(shù)以及總請求延遲，但是，在面臨熱點(diǎn)問題時(shí)，由于熱點(diǎn)資源的存儲(chǔ)位置對各個(gè)存儲(chǔ)節(jié)點(diǎn)透明，導(dǎo)致整個(gè)網(wǎng)絡(luò)的副本數(shù)量依舊不可控，該策略在一致性問題上與非協(xié)同策略具有相同的局限性。文獻(xiàn)［9-10］分別提出基站間的協(xié)同策略，但它們未明確副本管理方法，如果采用中心化的管理方式，副本在各個(gè)節(jié)點(diǎn)中的存儲(chǔ)與刪除將大幅提升中心節(jié)點(diǎn)的計(jì)算壓力。此外，除了傳統(tǒng)IP 尋址，邊緣網(wǎng)絡(luò)中也會(huì)包含一些命名對象尋址方式［11］，如NDN（Named Data Networking）［12］的命名方式，這為副本管理帶來了更多的挑戰(zhàn)。因此，現(xiàn)有的存儲(chǔ)策略在解決副本一致性問題上都存在不足，在實(shí)際應(yīng)用場景中，一致性問題會(huì)帶來不可忽視的時(shí)延和影響。

本文提出一種基于虛擬傳播樹（Virtual Spread Tree，VST）的去中心化邊緣存儲(chǔ)算法，以解決熱點(diǎn)資源存儲(chǔ)中的多副本一致性問題，保證用戶的請求時(shí)延可控，同時(shí)維護(hù)資源的一致性。該算法建立和剪枝VST，限制樹的增長，通過貪心的淘汰算法逐漸找到近似最優(yōu)的資源存儲(chǔ)節(jié)點(diǎn)。算法中的最大延遲低于兩倍樹深的傳播時(shí)間，避免了其他算法中的副本爆炸式增長問題。各個(gè)節(jié)點(diǎn)只存儲(chǔ)少量相鄰數(shù)據(jù)，去中心化的方法能夠降低存儲(chǔ)和計(jì)算開銷。此外，各個(gè)節(jié)點(diǎn)的淘汰算法相互獨(dú)立，從而進(jìn)一步降低時(shí)間開銷。

1 相關(guān)知識(shí)

1.1 基站存儲(chǔ)模型與本文假設(shè)

基站存儲(chǔ)模型可以通過如下數(shù)學(xué)模型進(jìn)行描述：圖G=(V，U，E)表示邊緣存儲(chǔ)網(wǎng)絡(luò)，其中，V={v1，v2，…，vn}表示基站存儲(chǔ)節(jié)點(diǎn)，U={u1，u2，…，um}表示用戶節(jié)點(diǎn)，E={(x，y)|x∈V，y∈V∪U}表示基站和基站之間以及基站與用戶節(jié)點(diǎn)之間的距離，資源內(nèi)容用I={i1，i2，…，ik}表示，每個(gè)基站vj存儲(chǔ)的資源Ij(t)?I隨時(shí)間發(fā)生變化，所有的Ij(t)構(gòu)成資源存儲(chǔ)策略?；敬鎯?chǔ)模型結(jié)構(gòu)如圖1 所示。

圖1 基站存儲(chǔ)模型結(jié)構(gòu)Fig.1 Base station storage model structure

本文進(jìn)行如下假設(shè)：

1）基站與基站以及基站與用戶節(jié)點(diǎn)之間的傳輸時(shí)延與節(jié)點(diǎn)間的距離成正比。

2）基站之間采用協(xié)同式工作策略，即t時(shí)刻用戶節(jié)點(diǎn)u總是向最近的基站vj請求資源is，當(dāng)is?Ij(t)時(shí)，vj會(huì)向周圍基站節(jié)點(diǎn)進(jìn)行資源請求，直至找到最近的擁有資源is的節(jié)點(diǎn)vi，并將資源返回給用戶。

3）各個(gè)基站的存儲(chǔ)空間足夠大，除非主動(dòng)刪除，否則資源i在存儲(chǔ)到某個(gè)基站vj后將會(huì)一直保留。

1.2 分布式存儲(chǔ)一致性

分布式存儲(chǔ)的一致性模型可以分為兩類［13］：一類是面向數(shù)據(jù)的一致性模型，包括順序一致性［14］、因果一致性［15］和線性一致性［16］等，它們從并發(fā)進(jìn)程的角度來分析進(jìn)程讀寫的執(zhí)行順序，從而劃分不同的一致性等級(jí)；另一類是面向客戶的一致性模型，包括最終一致性、讀寫一致性和寫讀一致性等，它們是描述客戶對同一內(nèi)容進(jìn)行多次讀寫操作的一致性模型。

上述模型在理論上對一致性問題進(jìn)行了系統(tǒng)分析，但是在實(shí)際應(yīng)用中，較為常用的保證副本一致性的算法通常是Paxos［17］及改進(jìn)的節(jié)點(diǎn)協(xié)同算法，如Raft［18］算法等，它們通過存儲(chǔ)節(jié)點(diǎn)之間的選舉策略和消息傳遞方式，從而保證各個(gè)副本的執(zhí)行方式相同，即保證副本的一致性。在邊緣基站存儲(chǔ)中可以使用上述一致性算法，但相較于云分布式存儲(chǔ)方式而言，邊緣存儲(chǔ)中各個(gè)副本節(jié)點(diǎn)的位置并不固定，且副本數(shù)量可能在頻繁變化，導(dǎo)致Paxos 算法很難執(zhí)行。因此，需要通過擴(kuò)散的方式來將一致性信息傳遞給各個(gè)存儲(chǔ)節(jié)點(diǎn)，而此時(shí)副本數(shù)量和擴(kuò)散深度會(huì)影響各個(gè)副本達(dá)到一致性的時(shí)間，為了提高用戶獲得資源的準(zhǔn)確性，需要犧牲一定時(shí)間的可用性，這段時(shí)間便是一致性傳播時(shí)延。為了更好地提高用戶體驗(yàn)質(zhì)量，需要控制一致性恢復(fù)過程中的時(shí)延。

2 基于虛擬傳播樹的邊緣存儲(chǔ)算法

2.1 虛擬傳播樹結(jié)構(gòu)

VST 從全局來看是一棵K叉樹，點(diǎn)集VT?V，邊集ET?E，對于任意的資源內(nèi)容i，有且只有一棵VSTi與之對應(yīng)，VSTi的節(jié)點(diǎn)表示當(dāng)前時(shí)刻K所有擁有資源i的基站存儲(chǔ)節(jié)點(diǎn)。VST 本身是抽象的，任何節(jié)點(diǎn)都不存儲(chǔ)完整的VST 數(shù)據(jù)結(jié)構(gòu)，每個(gè)VST 節(jié)點(diǎn)只保存其父節(jié)點(diǎn)和子節(jié)點(diǎn)信息以及一些與資源i相關(guān)的訪問次數(shù)、最近訪問時(shí)間等少量統(tǒng)計(jì)數(shù)據(jù)信息，額外的存儲(chǔ)開銷遠(yuǎn)小于存儲(chǔ)整棵VST 的開銷。VST 結(jié)構(gòu)以及VST 節(jié)點(diǎn)的元數(shù)據(jù)結(jié)構(gòu)偽代碼如圖2 所示。

圖2 VST 結(jié)構(gòu)示意圖Fig.2 Schematic diagram of VST structure

2.2 VST 生成算法

VST 的生成是由用戶對資源的請求而驅(qū)動(dòng)的，當(dāng)基站vi收到一個(gè)資源is的請求時(shí)，若當(dāng)前節(jié)點(diǎn)沒有存儲(chǔ)資源is，則會(huì)向周圍基站節(jié)點(diǎn)擴(kuò)散尋找（若超過一定時(shí)間沒有找到，會(huì)向云存儲(chǔ)中心直接請求），直至找到最近的存儲(chǔ)該資源的基站節(jié)點(diǎn)vj，此時(shí)vi和vj建立父子關(guān)系，vj是vi的父節(jié)點(diǎn)，同時(shí)保存兩者之間的傳輸距離（延遲），并且vi從vj處復(fù)制資源is。以此類推，建立一棵傳播樹，同時(shí)，為了避免節(jié)點(diǎn)擁有的子節(jié)點(diǎn)個(gè)數(shù)過多，從而產(chǎn)生額外的查詢和存儲(chǔ)開銷，當(dāng)父節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)目達(dá)到閾值K時(shí)，會(huì)隱藏自己擁有資源is的特征，從而保證VST 是一棵K叉樹。VST 生成算法流程如圖3 所示。

圖3 VST 生成算法流程Fig.3 The procedure of VST generation algorithm

2.3 VST 節(jié)點(diǎn)淘汰算法

VST 生成算法并不能保證VST 樹深的穩(wěn)定，對于熱點(diǎn)資源，VST 的規(guī)模極為龐大，因此，需要相應(yīng)的節(jié)點(diǎn)淘汰算法，簡單且有效的方式是將最近訪問頻率最低的節(jié)點(diǎn)刪除，但是這對樹深的影響不可直接度量。本文采用如下方法進(jìn)行節(jié)點(diǎn)淘汰：當(dāng)新節(jié)點(diǎn)v0作為葉子節(jié)點(diǎn)插入VST 時(shí)，若樹深剛好超過閾值D，則對從該葉子節(jié)點(diǎn)到VST 根節(jié)點(diǎn)的路徑上的每個(gè)節(jié)點(diǎn)分別計(jì)算一個(gè)保留值Qj，計(jì)算公式如下：

式（1）中的n為最近一段時(shí)間內(nèi)該節(jié)點(diǎn)的被訪問次數(shù)，n越大，該節(jié)點(diǎn)越應(yīng)該被保留。式（2）中的表示之間的延遲，davg表示到其父、子節(jié)點(diǎn)的平均延遲，越高，說明該節(jié)點(diǎn)越不能被其下游節(jié)點(diǎn)替換。式（3）中的α是平衡系數(shù)，通常取值為0.5。

算法1VST 節(jié)點(diǎn)淘汰算法

2.4 一致性邊緣存儲(chǔ)策略

結(jié)合VST 的特性，可以設(shè)計(jì)一種解決邊緣存儲(chǔ)一致性問題的存儲(chǔ)策略。在邊緣存儲(chǔ)已建立最大深度為D的VST 后，當(dāng)某個(gè)節(jié)點(diǎn)觸發(fā)寫操作，需要將更新傳播到全部副本節(jié)點(diǎn)時(shí)，將執(zhí)行一致性邊緣存儲(chǔ)策略。

由于邊緣網(wǎng)絡(luò)環(huán)境下各個(gè)副本位置的不可控，傳統(tǒng)的Paxos 等一致性算法難以直接應(yīng)用，本文通過鎖定服務(wù)和傳播更新信息的方式實(shí)現(xiàn)一致性共識(shí)，從而保證用戶的讀寫一致性。

在節(jié)點(diǎn)發(fā)生寫操作時(shí)，系統(tǒng)會(huì)迅速地對存儲(chǔ)資源進(jìn)行加鎖操作以鎖定服務(wù)，并將相應(yīng)的更新信息沿著VST 的路徑向父節(jié)點(diǎn)和子節(jié)點(diǎn)進(jìn)行傳播，由于VST 樹深不超過D，則傳播完整棵樹的時(shí)長不超過2D，平均時(shí)長為1.5D，從鎖定服務(wù)到最終傳播更新的時(shí)間是可控的。此外，可以通過邊傳播邊解鎖服務(wù)的方式，使得節(jié)點(diǎn)完成更新時(shí)就可以接收資源請求。

上述過程是在傳統(tǒng)IP 網(wǎng)絡(luò)尋址方式的基礎(chǔ)上進(jìn)行的，但是邊緣存儲(chǔ)中可能存在信息中心網(wǎng)絡(luò)（ICN）［19］等特殊命名方式的網(wǎng)絡(luò)部署，因此，在這種場景下需要對算法進(jìn)行一定的改進(jìn)。本文針對擁有層次解析的ICN 網(wǎng)絡(luò)場景，對所提基于VST 的去中心化邊緣存儲(chǔ)算法進(jìn)行改進(jìn)，如圖4 所示。

圖4 ICN 網(wǎng)絡(luò)場景中的改進(jìn)VST 結(jié)構(gòu)示意圖Fig.4 Schematic diagram of improved VST structure in ICN network scenario

解析節(jié)點(diǎn)可以解析當(dāng)前容器內(nèi)所有點(diǎn)的位置，但副本資源存儲(chǔ)節(jié)點(diǎn)可以跨容器，本文所提基于VST 的去中心化邊緣存儲(chǔ)算法建立在最底層的解析容器中，針對ICN 場景的改進(jìn)算法包括以下3 個(gè)步驟：

1）節(jié)點(diǎn)A發(fā)起副本一致性請求，A向其所在的解析容器中的解析節(jié)點(diǎn)B以及A的VST 父、子節(jié)點(diǎn)發(fā)送信息。

2）B解析出當(dāng)前容器內(nèi)的副本位置，下發(fā)一致性信息。

3）所有收到一致性信息的節(jié)點(diǎn)將自己視作A，重復(fù)上述2 個(gè)步驟，直至所有副本節(jié)點(diǎn)收到一致性信息。

通過容器內(nèi)的解析擴(kuò)散和容器間的VST 擴(kuò)散，系統(tǒng)延遲時(shí)間將進(jìn)一步降低。

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

為驗(yàn)證VST 的有效性，本文搭建相應(yīng)的仿真系統(tǒng)，模擬基站和用戶間的資源訪問關(guān)系。如圖5 所示，按照熱點(diǎn)資源在時(shí)間上遵循Zipf［20］分布的特征搭建多副本場景。為了驗(yàn)證本文算法的普適性，在一致性場景和非一致性場景下分別進(jìn)行相應(yīng)的實(shí)驗(yàn)，并重點(diǎn)分析請求延遲和存儲(chǔ)開銷等性能。實(shí)驗(yàn)過程中VST 算法的參數(shù)設(shè)置如表1 所示。

圖5 VST 熱點(diǎn)資源所遵循的Zipf 分布Fig.5 Zipf distribution for VST hotspot resources

表1 VST 算法參數(shù)設(shè)置Table 1 VST algorithm parameters setting

3.1 不考慮一致性的仿真實(shí)驗(yàn)

在不考慮一致性的前提下，對比協(xié)同式（CV）和非協(xié)同式（NCV）的基站存儲(chǔ)算法以及本文算法（VST）在時(shí)延、存儲(chǔ)空間等方面的性能，結(jié)果如圖6所示。

圖6 非一致性場景下3 種算法的性能對比結(jié)果Fig.6 Performance comparison results of three algorithms in inconsistency scenarios

從圖6 可以看出：隨著副本數(shù)量的增加，在平均時(shí)延方面，VST 算法和CV 算法表現(xiàn)基本一致，優(yōu)于NCV 算法；在存儲(chǔ)開銷方面，VST 算法的存儲(chǔ)開銷遠(yuǎn)小于CV 算法。綜上，在不考慮一致性的場景中，VST 算法穩(wěn)定且性能良好。

3.2 考慮一致性的仿真實(shí)驗(yàn)

為了考慮一致性問題，實(shí)驗(yàn)過程中需要添加部分對副本的寫操作，并且直至所有副本都更新寫操作后才可以響應(yīng)用戶請求，因此，需要觀察副本數(shù)量和寫操作頻率對用戶請求時(shí)延的影響。圖7 所示為副本數(shù)量分別為20、50 和150 情況下，在不同寫操作頻率時(shí)用戶獲取準(zhǔn)確內(nèi)容的時(shí)延情況。

圖7 一致性場景下3 種算法的性能對比結(jié)果Fig.7 Performance comparison results of three algorithms in consistency scenarios

從圖7 可以看出，在副本數(shù)量固定時(shí)，隨著寫操作的頻繁發(fā)生，CV 算法與NCV 算法的時(shí)延逐漸升高，最終會(huì)出現(xiàn)時(shí)延過高而無法響應(yīng)用戶請求的情況，尤其在副本數(shù)量為150 時(shí)情況尤為嚴(yán)重。而本文VST 算法的時(shí)延雖然也會(huì)隨著寫操作頻率的升高而升高，但由于其樹深穩(wěn)定，延遲時(shí)間將逐漸趨于平穩(wěn)，在副本數(shù)量很大時(shí)，VST 算法仍然可以響應(yīng)高頻寫場景的用戶請求，保證用戶獲取資源的一致性。

4 結(jié)束語

本文提出一種基于VST 的邊緣協(xié)同式基站存儲(chǔ)算法，以解決邊緣網(wǎng)絡(luò)熱點(diǎn)資源請求所帶來的多副本不一致性問題，優(yōu)化用戶響應(yīng)延遲。實(shí)驗(yàn)結(jié)果表明，在不考慮一致性的仿真場景中，與主流的協(xié)同式算法及非協(xié)同式算法相比，該算法在時(shí)延與存儲(chǔ)開銷上性能表現(xiàn)更優(yōu)，在考慮一致性的仿真場景中，該算法的存儲(chǔ)性能明顯優(yōu)于其他2 種算法，在多副本高頻寫場景中，本文算法仍然可以提供良好的一致性服務(wù)。下一步考慮將本文算法與邊緣存儲(chǔ)策略相結(jié)合，從而為用戶提供更好的邊緣存儲(chǔ)服務(wù)。