通用緩存替換策略下的緩存強一致性研究

楊濤，鄭烇，，徐正歡，3，施錢寶，彭思偉

（1.中國科學技術大學自動化系未來網絡實驗室，合肥 230026；2.合肥綜合性國家科學中心人工智能研究院，合肥 230088；3.中國科學技術大學 先進技術研究院，合肥 230031）

0 概述

在傳統TCP/IP 網絡架構中，用戶提出服務請求，網絡將用戶請求傳送到服務器，服務器執行用戶請求，并在完成所要求的操作后將結果返回用戶。當用戶請求在網絡緩存區中找到對應內容時，即發生緩存命中，節點會將對應內容封裝后發送給請求者。信息中心網絡（Information-Centric Networking，ICN）是一種以內容為中心的新型網絡架構，特點是網絡拓撲中的所有節點都有緩存區。在ICN 中用戶僅關心內容本身，網絡對內容進行統一標識并基于內容進行定位、路由和傳輸［1］。緩存的存在使得熱門的內容更接近于用戶，選取合適的緩存策略能夠有效減小用戶訪問延遲和服務器負載，并緩解網絡鏈路負擔［2-3］。目前，ICN 主要包括命名數據網絡（Named Data Networking，NDN）、內容中心網絡（Content Centric Networking，CCN）和發布/訂閱互聯網路由范式（Publish/Subscribe Internet Routing Paradigm，PSIRP）等［1，4］典型架構。

隨著社會信息量的日益增加，網絡內容更新速率越來越快。如果緩存存儲過期內容，請求到達時則不會發生緩存命中，因此緩存一致性維護受到研究人員的廣泛關注［5-7］。目前，緩存一致性維護研究主要分為驗證和失效［6-7］兩類策略。驗證策略即緩存定期向服務器詢問內容是否過期，是一類實現緩存弱一致性的策略，原因在于源服務器的內容可能在兩次驗證之間發生更新，但是一些實時性要求較高的應用期望獲得最新的內容。失效策略是一類實現緩存強一致性的策略，主要分為被動查詢、主動移除、主動更新和主動選擇更新4種［7］。在被動查詢策略中，當緩存中發現請求對應副本時，緩存會首先詢問服務器，若服務器告知這是最新的內容，則會發生緩存命中。在主動移除策略中，當服務器更新某個內容時，會推送消息到所有的緩存節點，過期的內容將被移除。在主動更新策略中，在服務器更新內容后，不但會將緩存中過期的內容移除，還會推送最新的副本到緩存中。主動選擇更新策略是對主動更新策略的改進，通過只推送一些較為熱門內容的副本而減輕服務器的負擔。

目前，針對緩存強一致性研究的數學模型普遍基于最近最少使用（Least Recent Used，LRU）替換策略［6-7］，但在實際環境中，根據應用場景和緩存節點能力的不同，需要采取q-LRU、先進先出（First In First Out，FIFO）、隨機替換（Random Replacement，RANDOM）等不同的緩存替換策略。同時，建立準確的緩存分析模型對于構建資源消耗較小且性能更高的網絡結構具有重要作用。本文提出一種緩存強一致性策略下的通用建模方法，在內容失效的時間間隔分布不同時，模型計算可達到較高的精確度。通過實驗以驗證模型精確度并探究不同緩存參數和應用場景下的緩存性能變化。

1 相關研究

針對緩存到達最大容量后在新的內容到達時的內容替換問題，研究人員提出了LRU、FIFO、RANDOM、LFU、q-LRU、gLRU［8］、TinyLFU［9］等一系列緩存替換算法。

1.1 緩存分析模型

建立準確的緩存分析模型有助于更好地分析緩存行為。因此，在進行緩存部署前，需要進行資源估算，選擇合適的緩存替換策略，從而有效減少資源消耗。文獻［10］證明了RANDOM 和FIFO 在獨立引用模型（Independent Reference Model，IRM）下具有相同的分析效果。文獻［11］給出LRU 和FIFO 緩存命中率的近似解法，提高了計算效率。文獻［12］將極限定理應用于平均場相互作用模型，推導出RANDOM 策略的緩存命中率公式。文獻［13］使用連續時間Markov 鏈對LRU 和FIFO 的瞬時命中率進行研究。文獻［14］提出一種基于列表的緩存替換策略的緩存分析模型，具有很高的精確度。

文獻［15］提出使用特征時間近似的方法描述緩存在LRU 中的生存行為，稱為Che 近似。文獻［16］證明了Che 近似在計算緩存命中率時具有極高的準確度。至此基于特征時間近似的緩存分析方法受到研究人員的廣泛關注［17-18］并取得了一系列研究成果［19-21］。文獻［22］在Che 近似的基礎上，提出一類可以用特征時間近似的緩存替換策略的緩存命中率計算公式。

上述研究推進了緩存替換策略的數學分析模型向更簡單精確的方向發展，但考慮的都是理想模型，并未考慮存在緩存一致性等問題的實際應用場景。

1.2 緩存一致性分析模型

緩存一致性維護對一些實時性要求較高的應用而言非常重要。緩存一致性策略主要分為驗證和失效。基于生存時間（即特征時間）的緩存替換策略是一種較為常見的驗證策略［23］。內容在緩存中存活規定的時間，超時即被驅逐出緩存，在緩存時被認為是最新的內容，如果有對該內容的請求到來即發生緩存命中。驗證策略是一種弱一致性策略，如果內容在緩存中存在的這段時間內服務器發生內容失效事件，用戶請求到的即是過期的內容。時間戳也是一個維護緩存弱一致性的驗證策略，通過在數據包前加上時間戳的字段。文獻［24］設計了一種分布式緩存策略，根據內容剩余生存時間、流行度和對鄰居節點相同內容的感知性，使緩存自主決定存儲哪些內容。文獻［25］采用時間戳匹配方式滿足用戶對請求響應時間的要求，有效提高了信息準確率。失效策略主要分為被動策略和主動策略［6-7］，其中主動策略相較于被動策略會降低用戶的請求響應時間，但是會帶來服務器負載的增加。

文獻［6-7］針對失效策略建立Detti 模型和Zheng 模型。在Detti 模型中，對被動查詢策略和主動移除策略進行建模，將失效事件定義為獨立的更新過程。在Zheng 模型中，將失效事件和存在事件相關聯，使用條件概率的方法對于被動查詢策略和3 種主動策略建模，其中主動選擇更新策略能夠在有效降低服務器負載的同時使緩存取得相較于其他3 種策略更高的命中率，模型具有很高的精確度。在被動查詢策略下，Detti 模型實際計算的是不考慮一致性的情況，此時Zheng 模型具有更高的精確度。在主動移除策略下，兩種模型均能很好地擬合仿真結果。但是這兩種模型均僅對LRU 緩存替換策略進行研究，并未對更多的緩存替換策略進行研究。

為擴展緩存強一致性分析模型的適用范圍，使其適用于可以使用特征時間近似的緩存替換策略，并在不同失效策略下均具有很高的計算精確度，本文基于緩存建模基本假設，對q-LRU、FIFO和RANDOM這3 種緩存替換策略進行緩存強一致性模型分析。

2 緩存強一致性通用分析模型

2.1 模型假設

在建立緩存強一致性通用分析模型前進行如下假設：

1）假設有M個不同的內容，為了簡化計算，這些內容塊的大小均為1。在實際環境中的內容大小并不為1，但由于內容一般是可分塊的［16］，假設同一個內容分塊后流行度均相同，且在本文模型中僅考慮特征時間，因此設置相同大小的內容不會影響建模分析結果［15］。

2）假設每個內容的流行度分布滿足Zipf 分布［26］。內容的流行度等級為im，其中im=1，2，…，M，流行度等級越小，流行度越高。內容m的請求概率計算公式如下：

其中：A=為Zipf 歸一化因子，α是Zipf參數，Zipf 參數越大，流行內容越集中。本文假設內容流行度是固定不變的，但在實際環境中并非如此，因此針對內容流行度變化的情況，本文僅考慮一小段時間內的流行度，假設在這個時間片內的內容流行度是固定的。

3）假設每個到達過程滿足泊松分布及IRM 模型，即所有內容之間的到達過程是相互獨立的且流行度分布不發生變化。假設所有內容的總到達速率為λ，則內容m的到達速率為λm=·λ。

4）假設內容在緩存節點間的傳輸時延為0。服務器和緩存間用于通信的包的大小相較于攜帶數據的包要小得多，因此不考慮這部分信息對服務器負載的影響。

2.2 特征時間近似

2.2.1 緩存替換策略

一般緩存大小設定為內容總數的0.5%～1.5%。當緩存存滿后，如果有新的內容到達，可能會觸發緩存替換事件，則需要選擇一個內容驅逐以存儲最新的內容。

LRU 策略內部相當于一個棧，棧頂為最新的內容，當棧滿后會驅逐棧底的內容。若請求內容已存在棧中，則會將該內容移動至棧頂，并且LRU 具有良好的時間相關性，若同一段時間內請求相同的內容較為密集時，則LRU 會體現出其優越性。q-LRU是LRU 的改進策略，內容訪問策略和驅逐策略與LRU 相同，但在內容緩存時會以q的概率緩存。

FIFO 策略會維護一個定長的隊列，先進來的內容在驅逐時會被最先驅逐。RANDOM 策略在發生緩存替換時，會在緩存中隨機選擇一個內容驅逐。RANDOM 和FIFO 非常相似，從替換角度看它們的處理方式對于每個內容都是平等的，適用于請求流量較為均勻的場景。

2.2.2 分析模型

Che 近似中用特征時間來描述內容從進入LRU 到被驅逐的過程，這里的特征時間Tc也可以稱為生存時間，即內容在緩存中存在的時間［15］。如果在某個時刻t到達一個對內容m的請求，此時發生緩存命中，則說明緩存中已存在該內容。按照特征時間的概念，即在(t-Tc，t]時間內至少需要有一次相同的請求到達。由于內容的到達滿足泊松過程，且到達速率為λm，因此得到內容m在緩存中存在的概率如式（2）所示。當緩存趨于穩態時，緩存穩定地進行內容替換，即緩存總是滿的。由于內容大小單位為1，緩存的大小即可以用所有內容存在概率的期望表示，如式（3）所示，其中C為緩存大小。這里Tc是一個常數，LRU 認為對于所有內容的特征時間是相同的［6-7，15］。根據PASTA 屬性得到內容m的平均緩存命中率如式（4）所示。對于所有內容的平均緩存命中率如式（5）所示。對q-LRU 而言，若緩存中存在內容m則要求上一次請求以q的概率存儲在緩存中或已經存在緩存中［22］，如式（6）所示。根據式（3）、式（4）可求得內容m的平均緩存命中率如式（7）所示，當q=1 時，與LRU 的緩存命中率公式相同。FIFO 的緩存命中率推導可以使用排隊論的方法，對于每個內容而言，計算如式（8）所示。在使用式（3）計算時，可將特征時間取均值。在IRM 流量下，認為RANDOM 的推導公式等同于FIFO［10］。

2.3 強一致性分析模型

維護緩存強一致性的策略即失效策略，包含被動查詢、主動移除、主動更新和主動選擇更新4 種，其中主動選擇更新實際是主動更新策略的一種變體，因此只考慮前3 種情況，即被動查詢、主動移除和主動更新。在此失效事件的到達采用通用分布，當存在失效事件時內容存在概率和命中率不同。

設(t)為內容m在t時間段內到達且緩存因此至少發生一次替換行為的概率。由于內容m到達過程滿足泊松過程，即要求在t時間段內至少有一次相同的請求到達過，因此對于LRU、FIFO、RANDOM：

由于q-LRU 緩存中均以q的概率進行首次插入，因此緩存替換行為至少發生一次的概率如下：

根據Zheng 模型的計算公式，可推算出內容有效概率的期望值如下：

2.3.1 被動查詢

由于被動查詢是緩存在接收到用戶對內容的請求后向服務器發出詢問，因此內容在緩存中的生存時間仍按無一致性策略進行計算。將計算結果與失效時間間隔相比較，按照有效且存在或存在且有效的計算方法可以得到內容的平均命中率［7］。內容m的平均命中率如下：

2.3.2 主動移除

在主動移除策略中，由于服務器會主動移除已經失效的內容，因此緩存并不總是滿的，緩存到達最大容量和內容過期均會將內容刪除，且特征時間的計算不能直接使用非一致性公式。此時緩存中存在的內容總量可以表示為緩存大小和緩存中有效內容的最小值：

聯立式（12）、式（13）、式（14）可以求得特征時間，繼而可以求出平均緩存命中率。

2.3.3 主動更新

當服務器發生更新事件，即緩存中的內容失效時，服務器會主動推送最新的內容到緩存節點，此時所有請求只要在緩存中發現內容，即是有效的，會發生緩存命中，實際的計算公式與非一致性公式相同。

上述q-LRU、FIFO 和RANDOM 緩存替換策略均可用特征時間來近似，對于其他策略，只要能給出特征時間近似的解法，本文緩存分析模型同樣適用。

2.3.4 服務器負載

對于被動查詢和主動移除策略而言，服務器負載僅和未命中的緩存內容相關，計算公式如下：

對于主動策略而言，除了處理未命中內容，在失效事件發生時會主動推送新的內容，服務器負載計算如下：

由于服務器只會對緩存中存在的內容進行主動推送，因此式（16）等式右邊的后半部分可以理解為需要更新內容大小的均值。

3 實驗結果與分析

通過仿真實驗驗證緩存強一致性分析模型的準確性，同時探究選取不同緩存場景或緩存參數時緩存命中率和服務器負載的變化規律。

使用基于Python 開發的實驗環境進行仿真實驗。實驗環境設置為：操作系統為Windows10，CPU 為Intel Core i7-8750H，內存為16 GB，Python 版本為3.6。仿真拓撲中包括：1 個用戶模擬器，用于發出請求；1 個緩存節點，用于放置不同的緩存替換策略，同時監測并統計緩存性能的變化；1 個服務器，用于響應緩存的請求。

在實驗中，設定內容總數為6 000，不失一般性，將這些內容編號，內容塊的編號越大，流行度越低。內容流行度分布滿足Zipf 分布，Zipf 參數在實驗中設定為0.8。設定緩存默認大小為60，內容總的請求速率為80 req/s，失效時間間隔的期望值默認設定為20 s。對于失效事件的到達間隔，可以是常數及均勻分布、指數分布等分布描述，由于文章篇幅的限制，下文僅給出常數時間間隔和滿足指數分布時間間隔的情況。

為驗證模型的準確性，采用式（17）計算誤差：

其中：(Ph)model為緩存分析模型計算得到的命中率；(Ph)sim為實際仿真實驗得到的緩存命中率。

在所有實驗中利用緩存分析模型計算出對應的數值結果，用線的形式進行表示，同時用點的形式表示仿真器在對應條件下生成的結果。首先進行模型的準確性驗證，分別在q-LRU、FIFO 和RANDOM 策略下，依次使用3 種不同的緩存強一致性策略進行實驗。然后在緩存參數變化時，探究q-LRU 中緩存概率q的大小、Zipf 參數、平均失效時間間隔和緩存大小變化對緩存性能的影響。最后在緩存參數不同時，對不同緩存替換策略進行性能比較。通過緩存分析模型計算結果和仿真結果的比較，以驗證模型準確性。

3.1 不同緩存替換策略的緩存強一致性實驗

圖1～圖3 驗證了在內容m發生失效事件的時間間隔為常數（=20）和其時間間隔分布滿足指數分布（～E(0.05)，請求速率為20 req/s）時，不同失效策略下模型內容平均命中率計算結果與仿真結果的吻合程度。由于篇幅限制，所有實驗在圖片中僅展示內容編號前500 的比較結果。由圖1～圖3 可以看出，在不同緩存替換策略、不同失效策略下緩存強一致性分析模型均取得了較高的準確度，最大誤差為2.18%。模型與仿真的誤差來源既與模型有關，又與仿真器設計本身有關，若仿真時間足夠大，事件產生足夠準確，則仿真器的誤差可忽略不計。另外，無一致性策略的模型本身可能也存在誤差。由于主動更新模型計算公式等同于無一致性策略的模型，因此其誤差即是無一致性策略的模型誤差的計算公式。

圖1 單個內容的緩存命中率（q-LRU，q=0.6）Fig.1 Cache hit ratio for a single content（q-LRU，q=0.6）

圖2 單個內容的緩存命中率（FIFO）Fig.2 Cache hit ratio for a single content（FIFO）

圖3 單個內容的緩存命中率（RANDOM）Fig.3 Cache hit ratio for a single content（RANDOM）

3.2 參數變化對緩存性能的影響

由于指數分布的失效間隔在實際環境中更為常見，考慮篇幅限制，因此分析參數變化對緩存性能的影響時，僅考慮指數分布。圖4 給出了在不同Zipf參數下，當q=0.6且～E(0.05)時q-LRU 隨著q的變化緩存命中率的變化曲線，計算結果與仿真結果相比最大誤差為2.81%。

圖4 Zipf 參數不同時緩存命中率隨q 的變化Fig.4 Cache hit ratio variations with different q under different Zipf parameters

不同的失效策略帶來的趨勢是相同的，因此此處僅研究被動查詢情況下緩存性能的變化。不同的Zipf 參數代表著不同的流量環境：當Zipf 參數較大時（α=1.5），流行內容非常集中，當q變大時緩存性能趨近于LRU，由于LRU 具有良好的時間相關性，流行的內容在緩存中生存的時間會更久，因此會取得更大的命中率；當Zipf 參數稍小一些時（α=1.0），流行內容集中度降低，編號靠后的內容出現的概率增加，頻繁進行內容替換容易產生緩存污染，q取值較小時緩存命中率會大一些，但是當q取值很小時，緩存的替換變得困難，緩存命中率反而會變得很小；當Zipf 參數較小時（α=0.5），流量相對均勻，在q大于0.1 時，q的變化基本不會影響緩存命中率。

在圖5 中，改變發生失效事件的速率，即失效平均時間間隔，在q-LRU 策略處于被動查詢策略下最大誤差為6.92%，在FIFO 策略處于被動查詢策略下最大誤差為3.73%，在其他策略下最大誤差為2.17%，計算模型仍可以很好地擬合仿真結果。隨著失效平均時間間隔的增加，失效行為發生的越來越少，存儲在緩存中的內容更可能是最新的內容，因此緩存命中率增加。主動更新策略使緩存一直是最新的，具有最高的命中率，且與失效事件無關。對于q-LRU而言，主動移除策略會使緩存有更多空間存儲新的內容，因此緩存命中率比被動查詢策略稍大一些。對于FIFO 和RANDOM 而言，它們驅逐內容的方式對每個內容均是平等的，因此主動更新策略和主動移除策略的性能相似。

圖5 緩存命中率隨平均失效時間間隔的變化Fig.5 Cache hit ratio variations with mean expiration time intervals

在圖6 中，隨著緩存大小的增加，緩存能夠存儲更多的內容，緩存命中率得到提高。在圖6（a）中最大誤差為4.68%，在圖6（b）中最大誤差為2.06%，在圖6（c）中最大誤差為1.79%，本文模型依然具有較高的計算精確度。

圖6 緩存命中率隨著緩存大小的變化（～E（0.05））Fig.6 Cache hit ratio variations with different cache sizes（T sm～E（0.05））

3.3 緩存替換策略比較

在Zipf 參數、平均失效時間間隔、緩存大小等影響緩存性能的變量已知的情況下，選擇合適的緩存替換策略能有效提升緩存命中率，減小服務器負載。

基于式（15）和式（16）可知，在被動查詢策略和主動移除策略下，服務器負載取決于緩存的未命中率，即當服務器負載較小的時候，也是緩存命中率最高的時候，所選的策略也是最優的。在同樣場景下，應用主動更新策略，雖然緩存命中率最高，但服務器負載也是最大的。在圖7 中，改變Zipf 參數，觀察4 種緩存替換策略隨著Zipf 參數變化服務器負載的變化情況。在圖7（a）中最大誤差為2.49%，在圖7（b）中最大誤差為0.88%，在圖7（c）中最大誤差為0.69%。可以看出，當Zipf 參數變大時，選擇FIFO或RANDOM 策略的服務器負載要更大，緩存命中率更低，此時選擇LRU 或q-LRU 更優。在Zipf 參數較大時，LRU 與q-LRU 的選擇可以參考圖4 及其解析。從圖7 可以看出：當Zipf 參數較大時q-LRU 對應的服務器負載略低于LRU，此時緩存替換策略選取q-LRU 最優；當Zipf 參數較小時，這些策略都可以選擇，從實現難度來看，FIFO 和RANDOM 要更為簡單。從這些緩存替換策略的本身分析也可以看出，FIFO 和RANDOM 策略適合流行度比較均勻的內容，而LRU 具有良好的時間相關性，在熱門內容更多時具有更好的性能。

圖7 4 種緩存替換策略下服務器負載隨Zipf 參數的變化（～E（0.05））Fig.7 Server load variations with different Zipf parameters under four cache replacement strategies（～E（0.05））

在圖8 中，通過改變平均失效時間間隔分析這4 種緩存替換策略下服務器負載的變化情況。在圖8（a）中最大誤差為1.01%，在圖8（b）中最大誤差為0.62%，在圖8（c）中最大誤差為0.39%。在3 種失效策略下，主動更新的服務器負載最大。在平均失效時間間隔比較小時，對主動更新策略下服務器負載影響很大，因為失效越頻繁，服務器越繁忙，其他兩種策略只和緩存未命中相關，在此場景下，平均失效時間間隔和服務器負載減小，但變化趨勢很小。在平均失效時間間隔大于2 s 時，LRU 或q-LRU 的性能總是優于FIFO 和RANDOM，且此時q-LRU 是最優策略。在平均失效時間間隔小于2 s 時，是一種快速更新的行為，在實際環境中并不常見，此時FIFO或RANDOM 更為合適，因為緩存替換的行為也需要時間，如果替換的時間相較于失效時間間隔不是足夠小，則用戶很難請求到最新的內容。

圖8 4 種緩存替換策略下服務器負載隨平均失效時間間隔的變化Fig.8 Server load variations with different mean expiration time intervals under four cache replacement strategies

圖9 給出了4 種緩存替換策略下服務器負載隨著緩存大小的變化情況。在圖9（a）中最大誤差為0.60%，在圖9（b）中最大誤差為0.69%，在圖9（c）中最大誤差為0.53%。在緩存較大時，FIFO 和RANDOM 具有相同的性能，但服務器負載總是高于LRU 或q-LRU。從服務器負載的角度來看，在緩存較大時，q-LRU 策略下服務器負載最低，此時q-LRU 是最優策略。在緩存較小時，很多流行的內容沒有被緩存下來，因此服務器負載較大，此時4 種緩存替換策略均會產生較高的服務器負載，可以選用實現更為簡單的FIFO 或RANDOM策略。

圖9 4 種緩存替換策略下服務器負載隨緩存大小的變化Fig.9 Server load variations for different cache sizes under four cache replacement strategies

4 結束語

本文構建緩存強一致性通用分析模型，并給出3 種緩存強一致性策略下緩存命中率和服務器負載的計算方法。通過選取不同的緩存參數進行仿真實驗，證明了通用分析模型具有較高的計算精確度，并且根據通用分析模型的計算方法，可在不同緩存參數或緩存場景下選取最優的緩存替換策略以取得最優的緩存性能。后續可將緩存強一致性通用分析模型拓展至更復雜的網絡拓撲結構，進一步提高計算結果的精確度，同時在真實網絡環境中部署緩存替換策略，基于通用分析模型選取合適的緩存參數，使緩存節點可在資源消耗較小時取得較優的緩存性能。