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

（1.中國科學(xué)技術(shù)大學(xué)自動化系未來網(wǎng)絡(luò)實驗室，合肥 230026；2.合肥綜合性國家科學(xué)中心人工智能研究院，合肥 230088；3.中國科學(xué)技術(shù)大學(xué) 先進(jìn)技術(shù)研究院，合肥 230031）

0 概述

在傳統(tǒng)TCP/IP 網(wǎng)絡(luò)架構(gòu)中，用戶提出服務(wù)請求，網(wǎng)絡(luò)將用戶請求傳送到服務(wù)器，服務(wù)器執(zhí)行用戶請求，并在完成所要求的操作后將結(jié)果返回用戶。當(dāng)用戶請求在網(wǎng)絡(luò)緩存區(qū)中找到對應(yīng)內(nèi)容時，即發(fā)生緩存命中，節(jié)點(diǎn)會將對應(yīng)內(nèi)容封裝后發(fā)送給請求者。信息中心網(wǎng)絡(luò)（Information-Centric Networking，ICN）是一種以內(nèi)容為中心的新型網(wǎng)絡(luò)架構(gòu)，特點(diǎn)是網(wǎng)絡(luò)拓?fù)渲械乃泄?jié)點(diǎn)都有緩存區(qū)。在ICN 中用戶僅關(guān)心內(nèi)容本身，網(wǎng)絡(luò)對內(nèi)容進(jìn)行統(tǒng)一標(biāo)識并基于內(nèi)容進(jìn)行定位、路由和傳輸［1］。緩存的存在使得熱門的內(nèi)容更接近于用戶，選取合適的緩存策略能夠有效減小用戶訪問延遲和服務(wù)器負(fù)載，并緩解網(wǎng)絡(luò)鏈路負(fù)擔(dān)［2-3］。目前，ICN 主要包括命名數(shù)據(jù)網(wǎng)絡(luò)（Named Data Networking，NDN）、內(nèi)容中心網(wǎng)絡(luò)（Content Centric Networking，CCN）和發(fā)布/訂閱互聯(lián)網(wǎng)路由范式（Publish/Subscribe Internet Routing Paradigm，PSIRP）等［1，4］典型架構(gòu)。

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

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

1 相關(guān)研究

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

1.1 緩存分析模型

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

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

上述研究推進(jìn)了緩存替換策略的數(shù)學(xué)分析模型向更簡單精確的方向發(fā)展，但考慮的都是理想模型，并未考慮存在緩存一致性等問題的實際應(yīng)用場景。

1.2 緩存一致性分析模型

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

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

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

2 緩存強(qiáng)一致性通用分析模型

2.1 模型假設(shè)

在建立緩存強(qiáng)一致性通用分析模型前進(jìn)行如下假設(shè)：

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

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

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

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

4）假設(shè)內(nèi)容在緩存節(jié)點(diǎn)間的傳輸時延為0。服務(wù)器和緩存間用于通信的包的大小相較于攜帶數(shù)據(jù)的包要小得多，因此不考慮這部分信息對服務(wù)器負(fù)載的影響。

2.2 特征時間近似

2.2.1 緩存替換策略

一般緩存大小設(shè)定為內(nèi)容總數(shù)的0.5%～1.5%。當(dāng)緩存存滿后，如果有新的內(nèi)容到達(dá)，可能會觸發(fā)緩存替換事件，則需要選擇一個內(nèi)容驅(qū)逐以存儲最新的內(nèi)容。

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

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

2.2.2 分析模型

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

2.3 強(qiáng)一致性分析模型

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

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

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

根據(jù)Zheng 模型的計算公式，可推算出內(nèi)容有效概率的期望值如下：

2.3.1 被動查詢

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

2.3.2 主動移除

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

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

2.3.3 主動更新

當(dāng)服務(wù)器發(fā)生更新事件，即緩存中的內(nèi)容失效時，服務(wù)器會主動推送最新的內(nèi)容到緩存節(jié)點(diǎn)，此時所有請求只要在緩存中發(fā)現(xiàn)內(nèi)容，即是有效的，會發(fā)生緩存命中，實際的計算公式與非一致性公式相同。

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

2.3.4 服務(wù)器負(fù)載

對于被動查詢和主動移除策略而言，服務(wù)器負(fù)載僅和未命中的緩存內(nèi)容相關(guān)，計算公式如下：

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

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

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

通過仿真實驗驗證緩存強(qiáng)一致性分析模型的準(zhǔn)確性，同時探究選取不同緩存場景或緩存參數(shù)時緩存命中率和服務(wù)器負(fù)載的變化規(guī)律。

使用基于Python 開發(fā)的實驗環(huán)境進(jìn)行仿真實驗。實驗環(huán)境設(shè)置為：操作系統(tǒng)為Windows10，CPU 為Intel Core i7-8750H，內(nèi)存為16 GB，Python 版本為3.6。仿真拓?fù)渲邪ǎ? 個用戶模擬器，用于發(fā)出請求；1 個緩存節(jié)點(diǎn)，用于放置不同的緩存替換策略，同時監(jiān)測并統(tǒng)計緩存性能的變化；1 個服務(wù)器，用于響應(yīng)緩存的請求。

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

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

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

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

3.1 不同緩存替換策略的緩存強(qiáng)一致性實驗

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

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

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

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

3.2 參數(shù)變化對緩存性能的影響

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

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

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

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

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

在圖6 中，隨著緩存大小的增加，緩存能夠存儲更多的內(nèi)容，緩存命中率得到提高。在圖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 參數(shù)、平均失效時間間隔、緩存大小等影響緩存性能的變量已知的情況下，選擇合適的緩存替換策略能有效提升緩存命中率，減小服務(wù)器負(fù)載。

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

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

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

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

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

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

4 結(jié)束語

本文構(gòu)建緩存強(qiáng)一致性通用分析模型，并給出3 種緩存強(qiáng)一致性策略下緩存命中率和服務(wù)器負(fù)載的計算方法。通過選取不同的緩存參數(shù)進(jìn)行仿真實驗，證明了通用分析模型具有較高的計算精確度，并且根據(jù)通用分析模型的計算方法，可在不同緩存參數(shù)或緩存場景下選取最優(yōu)的緩存替換策略以取得最優(yōu)的緩存性能。后續(xù)可將緩存強(qiáng)一致性通用分析模型拓展至更復(fù)雜的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，進(jìn)一步提高計算結(jié)果的精確度，同時在真實網(wǎng)絡(luò)環(huán)境中部署緩存替換策略，基于通用分析模型選取合適的緩存參數(shù)，使緩存節(jié)點(diǎn)可在資源消耗較小時取得較優(yōu)的緩存性能。