分布式網絡內置緩存優化技術研究

周錦程, 王浩暢

(東北石油大學 計算機與信息技術學院， 大慶 163318)

0 引言

隨著云計算、大數據技術的不斷發展，以分布式網絡進行數據存儲和應用已經成為互聯網數據服務模式的主要形式之一。在分布式網絡中，內置緩存策略決定了網絡數據的傳輸性能，而目前分布式網絡各節點緩存相對獨立，無法充分的、高效的利用緩存資源。為此，對于分布式網絡內置緩存的全局優化非常具有研究的價值。

網絡內置緩存策略根據作用范圍可以分為單節點緩存數據和多節點緩存數據。單節點緩存數據是依據節點本地緩存數據進行決策的單節點緩存策略；多節點緩存數據是基于復雜算法的緩存資源協商決策多節點協調緩存策略[1]。單節點緩存策略算法主要有頁面置換算法LRU(Least Recently Used)、最不經常使用頁置換算法lFU(least Frequently Used)等，多節點緩存策略算法主要為CLS(Concept Learning System)[2]。單節點緩存策略算法簡單，但是不能反映全局網絡中的數據傳輸特性，存在緩存數據冗余和頻繁更替的問題；多節點緩存策略算法復雜，能夠提高全網的緩存利用率，但是多節點協同具有較高的復雜度，網絡服務器的壓力較大。同時，分布式網絡默認的緩存是網內節點獨立、基于應用層無數據區分的全局緩存策略，這樣會導致緩存中存在數據冗余和無法做到緩存資源高效利用的問題[3]。為此，研究如何降低緩存數據冗余度、提高有限緩存空間對數據頻率緩存的比例、注重邊緣化緩存、降低算法復雜度對于提高分布式網絡緩存利用效率具有非常重要的現實意義。

1 分布是網絡內置緩存數據放置分析

1.1 網絡環境模型構建

在進行分布式網絡分析時，由于網絡環境的復雜化需要對網絡環境進行簡化和限定。在已有的研究中，潘越偉通過分析分布是網絡數據傳輸模型，證實了無論是線性拓撲的網絡結構還是樹狀拓撲的網絡結構，其數據請求的命中率基本保持一致[4]。所以本文對網絡環境模型形式化直接采用線性拓撲結構進行分析，構建單鏈路緩存數據分配模型如圖1所示[5]：

圖1 單鏈路緩存數據分配模型

如圖1所示網絡數據請求滿足連續序列分布，隨著數據序列的增長，請求頻率逐漸降低，如果設分布網絡存在K條單鏈路緩存節點，則其中一個節點k的數據請求概率可以表示為[6]式(1)。

(1)

其中，α為數據序列指數特征參數，α>1，k∈{1,2,…,K}。根據式(1)，α值越大數據請求分布越集中在熱節點上；相反，α值越小則數據請求分布則數據請求分布越均勻。

在分布式網絡中，其不同于傳統網絡能夠建立完整的數據緩存，而是根據數據塊分別緩存，如果假設數據塊數量為δ，各路由節點具有相同大小的緩存空間n，節點k上的緩存數據集合為Ck，節點上的數據可以標記為Ck1，Ck2，…，Ckn。當網絡節點接收到網絡數據請求包后，查詢本地是否已經緩存了數據，如果緩存了則繼續接收請求，如果沒有緩存則跳到下一個路由節點[7]。

1.2 緩存數據放置模型

根據網絡環境模型分析，設Ckj為節點k上的某個數據，函數f(Ckj)為數據Ckj的數據序列，f(Ckj)分布滿足齊普夫定律條件，g(Ck)為數據分布函數，計算公式表示為式(2)。

(2)

其中，1≤k≤N，1≤j，α為數據分布指數特征參數。

在節點k緩存請求獲得數據，Pk為數據請求在k節點上的概率，如果在第一個節點，第一個節點上的概率為P1=g(C1)g(B)，如果第一個節點上未接收請求則轉向第二個節點，第二個節點上的概率為P2=g(C2-C1)/g(B)，以此類推得到數據存儲節點上的概率為式(3)。

(3)

其中，Rt為數據請求延時，如果經過n次跳轉后接收請求則Rt=nt,由此可推算出請求的平均延時為式(4)。

(4)

根據式(3)可知，節點緩存數據冗余度較低時，則數據源服務器壓力小，再結合式(4)可知，數據平均請求延時與緩存節點接收數據有直接的關系，數據緩存離請求節點越近，則請求延時越小。但是，由于受到緩存空間大小的限制，如果距離近的節點無法有足夠的容量完全接收數據，那么則根據網絡節點的熱度逐漸接收，最大限度的降低數據的請求時間和網絡的消耗。

2 基于數據頻率的緩存優化策略

2.1 基于數據頻率緩存策略

在發出數據請求時，數據源響應會經過路由節點傳送給用戶。如果數據請求的容量小于節點緩存容量，則不影響網絡的響應效率，如果用戶的請求數據不斷的增加，分布式網絡會將請求頻率高的數據優先存儲在離用戶近的網絡節點上。根據緩存數據分配模型(圖1)保證網絡運行穩定的前提下，Nod1節點緩存用戶請求頻率最高的n個數據f(C1)，當用戶請求數據在數據集f(C1)中可直接得到Nod1節點緩存相應。Nod2緩存接收其他用戶請求數據f(C2)。由此，數據頻率策略將用戶請求頻率高的數據緩存到本地，但是并不會依據請求頻率來替換原有緩存的內容，而是在統計最近時間段數據請求頻率，考慮到數據頻率衰減過程，數據頻率策略在原有數據結構基礎上增加請求記錄表如圖2所示。

圖2 請求記錄表

請求記錄表記錄節點接收到最近的N次請求。當數據請求CX在請求過程中，請求記錄表數量達到了上限，則統計出CX在請求記錄表中被請求的次數，并與其他數據被請求的次數做比較，當CX頻率在請求記錄表中的次數排在請求數據簽名，則將CX緩存到節點中。

根據請求記錄表，計算當前及誒單中數據頻率高低，以數據請求次數作為衡量標準，最近N此請求中數據ci被請求的次數所占比例Ch(i)計算表達式為式(5)。

(5)

其中，δcout(i,j)為數據ci與請求記錄表中的第j條數據ci相同時計數加1。

數據頻率策略由數據頻率計算、緩存數據替換和請求記錄表三部分構成，數據頻率計算根據公式(5)計算出數據的頻率。當新數據到來時首先檢查節點緩存是否已滿，如果未滿直接存儲在緩存中，如果已滿則計算數據的頻率Ch(i)，判斷數據ci的頻率是否處于所有請求前列，如果是則將數據存儲到該節點，如果不是則跳轉下一個節點，維護當前節點請求記錄表。

2.2 基于數據頻率緩存優化

根據基于數據頻率的緩存策略所采用的算法分為計算數據數據頻率的算法，緩存數據替換算法和請求記錄表維護算法構成，優化流程如下：

(1) 接收新緩存數據時檢查CS表是否已滿，若未滿則將緩存數據添加到CS表中，若CS表已滿則計算將要緩存數據的流行度Ch(i)；

(2) 判斷新緩存數據流行度是否處于前m個受歡迎的內容，如果是則進行第(3)步，如果不會則跳到第(4)步；

(3) 按照LRU方案將新緩存數據存儲到節點CS上；

(4) 根據新緩存數據更新RRT表，并采用FIFO原則對RRT表進行維護。

3 實驗仿真

3.1 實驗環境介紹

為了檢驗本文提出的基于數據頻率的緩存優化策略具有一定的可行性，構建基于NS-3的ndnSIM仿真平臺環境，ndnSIM是離散事件驅動網絡模擬器。環境搭建要先安裝boost-lib 1.55和python bindings 2.7，再安裝NS-3 v0.4.3，設置路徑后檢查關鍵模塊是否安裝成功，安裝R語言3.02并給R環境安裝模塊，最后進行運行測試，測試搭建成功后進行仿真。

實驗采用了單鏈路拓撲(Single Path Network,SPN)結構和模擬真實網絡的無標度網絡拓撲結構(Scale-Free Network,SFN)[8]。SPN鏈路包括一個請求節點、一個數據源節點、10個網絡節點，SPN鏈路網絡結構如圖3所示。

圖3 SPN鏈路網絡結構

SFN結構利用NetworkX工具生成50個節點的拓撲結構，將節點1和8作為資源點，葉子節點作為用戶節點，其他節點為網絡節點，SFN網絡結構如圖4所示。

圖4 SFN網絡結構

數據包路由采用ndnSIM的BestRoute路由策略[9]，用戶數據請求滿足Zipf-like分布[10]。在分布式網絡中網絡節點具有相同緩存空間大小，實驗參數設置如表1所示。

表1 實驗參數設置

3.2 性能評估標準

根據數據頻率策略的組成本文選擇定義數據請求延時、緩存接收率、緩存數據置換率作為性能指標。

內容請求延時可以反映出網絡的訪問效率，設請求的總次數為M，請求的時刻為Dreq，數據響應的時刻為Decho,則網絡所有節點數據請求的平均延時為式(6)。

(6)

緩存接收率是指請求發出后到達數據源之前得到的數據響應，緩存接收率越高，則說明請求到達的越快，數據源的壓力越小。記錄節點i在時間段t內的數據請求緩存接收率總次數為NHit(i)，接收總次數為NMis(i)，網絡中所有節點平均接收率為式(7)。

(7)

緩存數據置換率是指節點新舊數據替換出來的緩存比例，置換率越高則對服務器的壓力越大。設節點i替換出的數次數為rmDate(i)，節點i接收到的數據請求次數為onDate(i)，緩存數據置換率為式(8)。

(8)

3.3 實驗分析

此次試驗劃分為緩存數據分布試驗、網絡緩存接收率實驗、數據請求延時實驗和緩存數據置換率實驗四組，基于數據頻率緩存算法用OCPPC表示，最不經常使用頁置換算法用LFU表示，頁面置換算法用LRU表示,比較三種緩存策略。

(1) 緩存數據分布試驗

此次試驗α值1.9，仿真時間200 s，實驗參數如表1所示，緩存算法運行平穩后，統計每個節點緩存數據序列平均值，觀察緩存算法優化前后對比結果如圖5所示。

圖5 緩存數據分布對比

通過圖5可以看出，節點2上的理論值為150.5，OCPPC緩存內容平均值為184，LFU緩存內容平均值為289，LRU緩存內容平均值為319。基于數據頻率緩存算法OCPPC能夠使鏈路節點上的緩存數據更接近理論最優數據分配結果，α越大數據請求越集中，數據頻率大對數據分布的影響大。

(2) 網絡緩存接收率實驗

統計接收率與總請求次數的比值，得網絡平均緩存接收率，α=1.9，網絡結構選擇單鏈路拓撲結構和無標度網絡拓撲結構。單鏈路拓撲網絡緩存接收率對比如圖6所示。

圖6 單鏈路拓撲緩存接收率對比

無標度拓撲網絡緩存接收率對比如圖7所示。

圖7 無標度拓撲緩存接收率對比

通過圖6和圖7可以看出，運行到100 s時，0CPPC算法命中率72%，LFU算法命中率57%，LRU命中率43%，并且隨著時間的增加命中率越來越高。由此可見，基于數據頻率緩存算法具有較高的網絡緩存接收率，相比單鏈路拓撲緩存無標度拓撲緩存所需的穩定時間較長。

(3) 數據請求延時實驗

數據請求延時實驗基于數據頻率緩存算法序列小于100的數據延時約為30 s，可以在較近節點上請求到數據，基于數據頻率緩存算法可以將訪問頻繁的數據緩存到距離請求者較近的節點上。在較大序列中，雖然請求延時頁面置換算法優于基于數據頻率緩存算法，但是基于數據頻率緩存算法在大量請求記錄統計中更加全面。平均數據請求延時對比如圖8所示。

圖8 平均數據請求延時對比

(4) 緩存數據置換率實驗

用較低的緩存數據置換頻率置換數據可以減少緩存的維護，α=1.9，緩存數據置換率對比如圖9所示。

由圖9可以見，算法置換率由高到低分別為頁面置換算法、最不經常使用頁置換算法、基于數據頻率緩存優化算法。在前30 s，OCPPC緩存頻率也是快速升高，但是OCPPC進行了自主學習，搜集內容請求逐漸減少，在100 s后換出率逐漸穩定。

圖9 緩存數據置換率對比

4 總結

本文針對目前分布式網絡采用單節點緩存存在的局限性問題和資源利用率不足的問題進行分析，探討了數據放置的分析模型，并提出根據數據頻率高低來進行緩存放置，數據頻率策略根據請求記錄構建數據的頻率統計模型，依據數據頻率在整個鏈路放置緩存數據，最后通過仿真實驗證實了該策略的有效性，能夠提高資源的請求效率、降低數據的請求延時和減少服務器的負載，在分布式網絡緩存管理中具有較好的優化效果。