一致性場景下的邊緣網(wǎng)絡(luò)低時延存儲算法

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

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

0 概述

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

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

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

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

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

1 相關(guān)知識

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

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

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

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

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

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

3）各個基站的存儲空間足夠大，除非主動刪除，否則資源i在存儲到某個基站vj后將會一直保留。

1.2 分布式存儲一致性

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

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

2 基于虛擬傳播樹的邊緣存儲算法

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

VST 從全局來看是一棵K叉樹，點集VT?V，邊集ET?E，對于任意的資源內(nèi)容i，有且只有一棵VSTi與之對應(yīng)，VSTi的節(jié)點表示當(dāng)前時刻K所有擁有資源i的基站存儲節(jié)點。VST 本身是抽象的，任何節(jié)點都不存儲完整的VST 數(shù)據(jù)結(jié)構(gòu)，每個VST 節(jié)點只保存其父節(jié)點和子節(jié)點信息以及一些與資源i相關(guān)的訪問次數(shù)、最近訪問時間等少量統(tǒng)計數(shù)據(jù)信息，額外的存儲開銷遠(yuǎn)小于存儲整棵VST 的開銷。VST 結(jié)構(gòu)以及VST 節(jié)點的元數(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)基站vi收到一個資源is的請求時，若當(dāng)前節(jié)點沒有存儲資源is，則會向周圍基站節(jié)點擴(kuò)散尋找（若超過一定時間沒有找到，會向云存儲中心直接請求），直至找到最近的存儲該資源的基站節(jié)點vj，此時vi和vj建立父子關(guān)系，vj是vi的父節(jié)點，同時保存兩者之間的傳輸距離（延遲），并且vi從vj處復(fù)制資源is。以此類推，建立一棵傳播樹，同時，為了避免節(jié)點擁有的子節(jié)點個數(shù)過多，從而產(chǎn)生額外的查詢和存儲開銷，當(dāng)父節(jié)點的子節(jié)點數(shù)目達(dá)到閾值K時，會隱藏自己擁有資源is的特征，從而保證VST 是一棵K叉樹。VST 生成算法流程如圖3 所示。

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

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

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

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

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

2.4 一致性邊緣存儲策略

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

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

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

上述過程是在傳統(tǒng)IP 網(wǎng)絡(luò)尋址方式的基礎(chǔ)上進(jìn)行的，但是邊緣存儲中可能存在信息中心網(wǎng)絡(luò)（ICN）［19］等特殊命名方式的網(wǎng)絡(luò)部署，因此，在這種場景下需要對算法進(jìn)行一定的改進(jìn)。本文針對擁有層次解析的ICN 網(wǎng)絡(luò)場景，對所提基于VST 的去中心化邊緣存儲算法進(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é)點可以解析當(dāng)前容器內(nèi)所有點的位置，但副本資源存儲節(jié)點可以跨容器，本文所提基于VST 的去中心化邊緣存儲算法建立在最底層的解析容器中，針對ICN 場景的改進(jìn)算法包括以下3 個步驟：

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

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

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

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

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

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

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

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

3.1 不考慮一致性的仿真實驗

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

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

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

3.2 考慮一致性的仿真實驗

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

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

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

4 結(jié)束語

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