一致性場景下的邊緣網絡低時延存儲算法

李昊天，盛益強

（1.中國科學院聲學研究所國家網絡新媒體工程技術研究中心，北京 100190；2.中國科學院大學電子電氣與通信工程學院，北京 100049）

0 概述

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

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

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

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

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

1 相關知識

1.1 基站存儲模型與本文假設

基站存儲模型可以通過如下數學模型進行描述：圖G=(V，U，E)表示邊緣存儲網絡，其中，V={v1，v2，…，vn}表示基站存儲節點，U={u1，u2，…，um}表示用戶節點，E={(x，y)|x∈V，y∈V∪U}表示基站和基站之間以及基站與用戶節點之間的距離，資源內容用I={i1，i2，…，ik}表示，每個基站vj存儲的資源Ij(t)?I隨時間發生變化，所有的Ij(t)構成資源存儲策略?；敬鎯δＰ徒Y構如圖1 所示。

圖1 基站存儲模型結構Fig.1 Base station storage model structure

本文進行如下假設：

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

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

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

1.2 分布式存儲一致性

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

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

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

2.1 虛擬傳播樹結構

VST 從全局來看是一棵K叉樹，點集VT?V，邊集ET?E，對于任意的資源內容i，有且只有一棵VSTi與之對應，VSTi的節點表示當前時刻K所有擁有資源i的基站存儲節點。VST 本身是抽象的，任何節點都不存儲完整的VST 數據結構，每個VST 節點只保存其父節點和子節點信息以及一些與資源i相關的訪問次數、最近訪問時間等少量統計數據信息，額外的存儲開銷遠小于存儲整棵VST 的開銷。VST 結構以及VST 節點的元數據結構偽代碼如圖2 所示。

圖2 VST 結構示意圖Fig.2 Schematic diagram of VST structure

2.2 VST 生成算法

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

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

2.3 VST 節點淘汰算法

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

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

算法1VST 節點淘汰算法

2.4 一致性邊緣存儲策略

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

由于邊緣網絡環境下各個副本位置的不可控，傳統的Paxos 等一致性算法難以直接應用，本文通過鎖定服務和傳播更新信息的方式實現一致性共識，從而保證用戶的讀寫一致性。

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

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

圖4 ICN 網絡場景中的改進VST 結構示意圖Fig.4 Schematic diagram of improved VST structure in ICN network scenario

解析節點可以解析當前容器內所有點的位置，但副本資源存儲節點可以跨容器，本文所提基于VST 的去中心化邊緣存儲算法建立在最底層的解析容器中，針對ICN 場景的改進算法包括以下3 個步驟：

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

2）B解析出當前容器內的副本位置，下發一致性信息。

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

通過容器內的解析擴散和容器間的VST 擴散，系統延遲時間將進一步降低。

3 實驗結果與分析

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

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

表1 VST 算法參數設置Table 1 VST algorithm parameters setting

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

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

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

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

3.2 考慮一致性的仿真實驗

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

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

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

4 結束語

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