通用緩存替換策略下的緩存強(qiáng)一致性研究

楊濤，鄭烇，，徐正歡，3，施錢(qián)寶，彭思偉

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

0 概述

在傳統(tǒng)TCP/IP 網(wǎng)絡(luò)架構(gòu)中，用戶提出服務(wù)請(qǐng)求，網(wǎng)絡(luò)將用戶請(qǐng)求傳送到服務(wù)器，服務(wù)器執(zhí)行用戶請(qǐng)求，并在完成所要求的操作后將結(jié)果返回用戶。當(dāng)用戶請(qǐng)求在網(wǎng)絡(luò)緩存區(qū)中找到對(duì)應(yīng)內(nèi)容時(shí)，即發(fā)生緩存命中，節(jié)點(diǎn)會(huì)將對(duì)應(yīng)內(nèi)容封裝后發(fā)送給請(qǐng)求者。信息中心網(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ò)對(duì)內(nèi)容進(jìn)行統(tǒng)一標(biāo)識(shí)并基于內(nèi)容進(jìn)行定位、路由和傳輸［1］。緩存的存在使得熱門(mén)的內(nèi)容更接近于用戶，選取合適的緩存策略能夠有效減小用戶訪問(wèn)延遲和服務(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)。

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

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

1 相關(guān)研究

針對(duì)緩存到達(dá)最大容量后在新的內(nèi)容到達(dá)時(shí)的內(nèi)容替換問(wèn)題，研究人員提出了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 緩存命中率的近似解法，提高了計(jì)算效率。文獻(xiàn)［12］將極限定理應(yīng)用于平均場(chǎng)相互作用模型，推導(dǎo)出RANDOM 策略的緩存命中率公式。文獻(xiàn)［13］使用連續(xù)時(shí)間Markov 鏈對(duì)LRU 和FIFO 的瞬時(shí)命中率進(jìn)行研究。文獻(xiàn)［14］提出一種基于列表的緩存替換策略的緩存分析模型，具有很高的精確度。

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

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

1.2 緩存一致性分析模型

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

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

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

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

2.1 模型假設(shè)

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

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

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

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

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

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

2.2 特征時(shí)間近似

2.2.1 緩存替換策略

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

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

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

2.2.2 分析模型

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

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

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

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

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

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

2.3.1 被動(dòng)查詢

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

2.3.2 主動(dòng)移除

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

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

2.3.3 主動(dòng)更新

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 緩存替換策略比較

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

基于式（15）和式（16）可知，在被動(dòng)查詢策略和主動(dòng)移除策略下，服務(wù)器負(fù)載取決于緩存的未命中率，即當(dāng)服務(wù)器負(fù)載較小的時(shí)候，也是緩存命中率最高的時(shí)候，所選的策略也是最優(yōu)的。在同樣場(chǎng)景下，應(yīng)用主動(dò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ù)變大時(shí)，選擇FIFO或RANDOM 策略的服務(wù)器負(fù)載要更大，緩存命中率更低，此時(shí)選擇LRU 或q-LRU 更優(yōu)。在Zipf 參數(shù)較大時(shí)，LRU 與q-LRU 的選擇可以參考圖4 及其解析。從圖7 可以看出：當(dāng)Zipf 參數(shù)較大時(shí)q-LRU 對(duì)應(yīng)的服務(wù)器負(fù)載略低于LRU，此時(shí)緩存替換策略選取q-LRU 最優(yōu)；當(dāng)Zipf 參數(shù)較小時(shí)，這些策略都可以選擇，從實(shí)現(xiàn)難度來(lái)看，F(xiàn)IFO 和RANDOM 要更為簡(jiǎn)單。從這些緩存替換策略的本身分析也可以看出，F(xiàn)IFO 和RANDOM 策略適合流行度比較均勻的內(nèi)容，而LRU 具有良好的時(shí)間相關(guān)性，在熱門(mén)內(nèi)容更多時(shí)具有更好的性能。

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

圖8 4 種緩存替換策略下服務(wù)器負(fù)載隨平均失效時(shí)間間隔的變化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%。在緩存較大時(shí)，F(xiàn)IFO 和RANDOM 具有相同的性能，但服務(wù)器負(fù)載總是高于LRU 或q-LRU。從服務(wù)器負(fù)載的角度來(lái)看，在緩存較大時(shí)，q-LRU 策略下服務(wù)器負(fù)載最低，此時(shí)q-LRU 是最優(yōu)策略。在緩存較小時(shí)，很多流行的內(nèi)容沒(méi)有被緩存下來(lái)，因此服務(wù)器負(fù)載較大，此時(shí)4 種緩存替換策略均會(huì)產(chǎn)生較高的服務(wù)器負(fù)載，可以選用實(shí)現(xiàn)更為簡(jiǎn)單的FIFO 或RANDOM策略。

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

4 結(jié)束語(yǔ)

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