[發(fā)明專利]緩存替換策略的選擇方法、裝置、代理服務(wù)器和系統(tǒng)

在審

• 申請(qǐng)?zhí)枺?/td>: 201010295033.5
• 申請(qǐng)日: 2010-09-26
• 公開(kāi)（公告）號(hào): CN102137139A
• 公開(kāi)（公告）日: 2011-07-27
• 發(fā)明（設(shè)計(jì)）人: 趙宇萍;魏含宇;王浩;陳建
• 申請(qǐng)（專利權(quán)）人: 華為技術(shù)有限公司
• 主分類號(hào): H04L29/08
• 分類號(hào): H04L29/08;H04L12/56
• 代理公司: 深圳市深佳知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 44285
• 代理人: 彭愿潔;李文紅

技術(shù)領(lǐng)域

本發(fā)明涉及通信領(lǐng)域，尤其涉及緩存替換策略的選擇方法、裝置、代理服務(wù)器和系統(tǒng)。

背景技術(shù)

隨著因特網(wǎng)(Internet)的飛速發(fā)展，越來(lái)越多的人通過(guò)因特網(wǎng)來(lái)獲取豐富的信息資源。然而，用戶數(shù)量的劇增不可避免地帶來(lái)網(wǎng)絡(luò)服務(wù)器負(fù)載加重、客戶端響應(yīng)延遲變大以及主干網(wǎng)絡(luò)擁塞等問(wèn)題。尤其是近年來(lái)視頻點(diǎn)播、遠(yuǎn)程教育和電子商務(wù)等因特網(wǎng)流媒體應(yīng)用的日益廣泛，使得這些問(wèn)題變得更加嚴(yán)重。

解決這些問(wèn)題的傳統(tǒng)方法是不斷升級(jí)網(wǎng)絡(luò)服務(wù)器和提高網(wǎng)絡(luò)接入帶寬。然而，這種傳統(tǒng)方法并不能從根本上解決問(wèn)題，這是因?yàn)椋ǔＧ闆r下，服務(wù)器的升級(jí)速度要低于用戶數(shù)量的增長(zhǎng)速度；僅僅提高網(wǎng)絡(luò)接入帶寬也并不能緩解主干網(wǎng)絡(luò)的擁塞問(wèn)題，而對(duì)主干網(wǎng)絡(luò)進(jìn)行升級(jí)則耗資巨大。

代理緩存技術(shù)能夠有效解決上述傳統(tǒng)方法遇到的問(wèn)題。代理緩存又稱代理服務(wù)器，是位于瀏覽器與服務(wù)器或客戶端與服務(wù)器之間的一臺(tái)服務(wù)器，能夠提供較大的存儲(chǔ)空間。當(dāng)用戶訪問(wèn)數(shù)據(jù)時(shí)，首先檢查代理緩存中有沒(méi)有用戶需要訪問(wèn)的數(shù)據(jù)，若有，則直接發(fā)送給用戶，否則，從服務(wù)器中獲取相應(yīng)的數(shù)據(jù)發(fā)送給客戶。

代理緩存的這種訪問(wèn)機(jī)制可以減少用戶訪問(wèn)遠(yuǎn)程服務(wù)器的次數(shù)，在直接提高客戶端響應(yīng)速度的同時(shí)，間接地減輕遠(yuǎn)程服務(wù)器負(fù)載和主干網(wǎng)絡(luò)擁塞。此外，由于在代理緩存中保存了數(shù)據(jù)拷貝，即使遠(yuǎn)程服務(wù)器在一段時(shí)間內(nèi)暫時(shí)無(wú)法提供服務(wù)，也不會(huì)影響用戶從代理緩存獲取信息資源，這些能夠明顯提高客戶端服務(wù)質(zhì)量。

然而，代理緩存的存儲(chǔ)容量有限；一旦存儲(chǔ)區(qū)滿，則必須按照事先約定的某種策略，將一部分當(dāng)前不再具有存儲(chǔ)價(jià)值的數(shù)據(jù)替換出去，從而為后續(xù)客戶服務(wù)。替換策略的好壞直接影響代理緩存的性能，因此，緩存替換策略是影響代理緩存性能的一個(gè)重要因素。

通常，衡量一個(gè)緩存替換策略優(yōu)劣的性能指標(biāo)主要有緩存命中率(CacheHit?Rate，CHR)，也簡(jiǎn)稱為命中率、字節(jié)命中率(Byte?Hit?Rate，BHR)和延時(shí)時(shí)間(Latency?Time，LT)。所謂緩存命中率，是指緩存頁(yè)數(shù)命中的次數(shù)與用戶總的請(qǐng)求數(shù)之比；字節(jié)命中率，是指緩存中命中的字節(jié)數(shù)與用戶總請(qǐng)求的字節(jié)數(shù)之比；延時(shí)時(shí)間(Latency?Time)是指從用戶提出一個(gè)訪問(wèn)請(qǐng)求開(kāi)始，到用戶接收到該請(qǐng)求的響應(yīng)為止所經(jīng)歷的時(shí)間為延時(shí)時(shí)間。

目前，通常的緩存替換策略包括最不經(jīng)常使用(Least?Frequently?Used，LFU)算法、基于大小的貪婪(Greedy?Dual?Size，GDS)算法、最近最不經(jīng)常使用(Least?Frequency?and?Recently?Used，LFRU)算法、某周期內(nèi)最不經(jīng)常使用(Period?Least?Frequency?Used，PLFU)算法和最少服務(wù)字節(jié)(Lease?ServedBytes，LSB)算法等。緩存替換策略的性能取決于諸多因素，例如，用戶訪問(wèn)模型、用戶訪問(wèn)的應(yīng)用特性和緩存的大小等等。目前，尚無(wú)一種緩存替換策略能夠針對(duì)所有因素而優(yōu)于其它算法，并且，這些算法不具有針對(duì)應(yīng)用變化的自適應(yīng)調(diào)節(jié)能力，例如，針對(duì)于傳統(tǒng)的Web訪問(wèn)，GDS算法具有較好的性能；而在視頻點(diǎn)播(Video?On?Demand，VOD)應(yīng)用中使用LFRU算法和PLFU算法，它們比傳統(tǒng)的LFU算法效率高，更適合大規(guī)模的VOD系統(tǒng)，但對(duì)于P2P下載應(yīng)用，LSB算法則更合適。

隨著現(xiàn)在網(wǎng)絡(luò)中應(yīng)用的不斷變化，對(duì)緩存替換策略的適應(yīng)性提出了新的要求。以Squid?Cache為例，說(shuō)明現(xiàn)有技術(shù)使用的典型方案。Squid?Cache(簡(jiǎn)稱為Squid)是一個(gè)流行的開(kāi)源代理服務(wù)器和Web緩存服務(wù)器，通過(guò)配置文件工作。以下是Squid?Cache的一部分配置文件的文本，其中包括了緩存替換策略的配置；

……

cache_mem?1228MB

maximum_object_size?5096KB

maximum_object_size_in_memory?5096KB

cache_replacement_policy?heap?LFUDA

memory_replacement_policy?heap?LRU

cache_dir?aufs/cache?2797016256

cache_access_log/log/access.log

cache_log/log/cache.log

……

其中，關(guān)于緩存替換策略的配置是下面兩行：

cache_replacement_policy?heap?LFUDA