[發(fā)明專利]一種基于譜聚類的內(nèi)容分發(fā)網(wǎng)絡(luò)緩存方法及系統(tǒng)

有效

• 申請?zhí)枺?/td>: 202110359576.7
• 申請日: 2021-04-02
• 公開（公告）號: CN113225380B
• 公開（公告）日: 2022-06-28
• 發(fā)明（設(shè)計）人: 張昕怡;謝高崗;趙淮毅
• 申請（專利權(quán)）人: 中國科學(xué)院計算技術(shù)研究所
• 主分類號: H04L67/568
• 分類號: H04L67/568;H04L67/5682;H04L67/10;H04L67/63;G06K9/62
• 代理公司: 北京律誠同業(yè)知識產(chǎn)權(quán)代理有限公司 11006
• 代理人: 祁建國

本發(fā)明提出一種基于譜聚類的內(nèi)容分發(fā)網(wǎng)絡(luò)緩存方法及系統(tǒng)包括準入策略和替換策略兩部分。其中，準入策略基于譜聚類挖掘請求之間的關(guān)聯(lián)性，將具有關(guān)聯(lián)性的用戶請求預(yù)取到CDN的HOC中，從而盡可能減少在HOC中緩存未命中情況的發(fā)生。而替換策略則利用GDSF的替換策略，基于用戶請求的頻率、大小和最近訪問的時間來選擇緩存替換的對象。此外，SpeCache設(shè)置的緩存參數(shù)不是固定的，通過在請求記錄上滑動窗口來計算并按照一定的時間間隔更新相應(yīng)參數(shù)，這種數(shù)據(jù)驅(qū)動的方法可以使得緩存策略隨著CDN流量模式的變化而動態(tài)更新，同時也避免了歷史信息的過擬合，最終提升CDN緩存的命中率。

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

本發(fā)明涉及分發(fā)網(wǎng)絡(luò)中的緩存替換技術(shù)領(lǐng)域，并特別涉及一種基于譜聚類的內(nèi)容分發(fā)網(wǎng)絡(luò)緩存方法及系統(tǒng)。

背景技術(shù)

內(nèi)容分發(fā)網(wǎng)絡(luò)(Content Delivery Network,CDN)是構(gòu)建在現(xiàn)有網(wǎng)絡(luò)基礎(chǔ)之上的智能虛擬網(wǎng)絡(luò)，依靠部署在各地的邊緣服務(wù)器(Edge Server)，通過中心平臺的負載均衡、內(nèi)容分發(fā)、調(diào)度等功能模塊，使用戶就近獲取所需內(nèi)容，降低網(wǎng)絡(luò)擁塞，提高用戶訪問響應(yīng)速度和命中率。

CDN的核心是使用邊緣服務(wù)器來加快用戶請求內(nèi)容的響應(yīng)速度。當用戶請求到達邊緣服務(wù)器時，如果該服務(wù)器存儲了用戶請求的內(nèi)容，則該邊緣服務(wù)器可以直接將該內(nèi)容返回給用戶。但是，如果用戶請求的內(nèi)容不在邊緣服務(wù)器中，則邊緣服務(wù)器需要向源服務(wù)器(Origin Server)發(fā)送內(nèi)容請求，并獲取內(nèi)容，上述過程增大了用戶獲取內(nèi)容的時延，同時降低了服務(wù)質(zhì)量。CDN通過將內(nèi)容存儲在地理位置上接近用戶的邊緣服務(wù)器中，提高用戶請求內(nèi)容的響應(yīng)速率。但是，邊緣服務(wù)器上的存儲資源有限，并不能緩存所有用戶請求內(nèi)容。而從源服務(wù)器獲取請求的內(nèi)容，會增加用戶請求的響應(yīng)時延，同時帶來從邊緣服務(wù)器到源服務(wù)器的網(wǎng)絡(luò)帶寬開銷。因此，保障用戶請求盡可能多的在邊緣服務(wù)器中命中是提高CDN服務(wù)質(zhì)量的第一要義。

CDN服務(wù)器采用層次化的存儲架構(gòu)。第一層通常是一個容量小但速度快的內(nèi)存緩存(In memory Cache)，在CDN中稱之為“流行對象緩存”(Hot Object Cache,HOC)。第二層則為容量大但速度相對較慢的磁盤緩存(Disk Cache,DC)。從源服務(wù)器獲取請求內(nèi)容后，邊緣服務(wù)器將其交付給用戶，同時，邊緣服務(wù)器將該內(nèi)容存儲在DC中，HOC根據(jù)其準入策略(Admission Policy)，決定是否將該內(nèi)容存儲到HOC中。當用戶請求的內(nèi)容在HOC中不存在，需要從DC或源服務(wù)器獲取該內(nèi)容并存儲到HOC中，但HOC的剩余容量不足以存儲它時，HOC要根據(jù)其替換策略(Eviction Policy)，替換出一個或多個已經(jīng)存儲的內(nèi)容，為新的內(nèi)容騰出空間。由于用戶從HOC中獲取內(nèi)容的速度比從DC中獲取的速度快，因此，設(shè)計恰當?shù)臏嗜氩呗院吞鎿Q策略，讓用戶請求的內(nèi)容盡可能多的在HOC中命中，是提高CDN的性能和服務(wù)質(zhì)量的第二要義。

“請求命中率”(Object Hit Ratio,OHR)表示在HOC中命中的用戶請求數(shù)與請求總數(shù)之比。而OHR的值是衡量緩存方案的性能的重要指標之一，也是本發(fā)明重點關(guān)注的指標。

緩存策略包括準入策略和替換策略。在設(shè)計緩存策略時，用戶請求內(nèi)容的最近請求時間(Recency)，頻率(Frequency)和請求內(nèi)容的大小(Size)是需要需要考慮的主要因素。學(xué)術(shù)界對于CDN中HOC緩存策略的研究，大多只關(guān)注緩存替換策略。所有請求的對象都可以被緩存，且上述因素中的一個或多個作為策略設(shè)計的基礎(chǔ)。最近最少使用策略(LeastRecently Used,LRU)是一種非常流行的緩存替換策略。該策略認為最近使用過的數(shù)據(jù)在未來訪問的可能性較大，而很久都沒請求過的數(shù)據(jù)再次被請求的概率較小，因此優(yōu)先替換最近最少被請求的內(nèi)容來為新的請求內(nèi)容騰出空間。根據(jù)中的統(tǒng)計數(shù)據(jù)，包括Varnish和Nginx在內(nèi)的大多數(shù)流行的開源Web緩存系統(tǒng)都使用LRU作為替換算法。其他替換策略，例如LRFU，LFU-DA，GDS，GDSF，ARC和Cliffhanger基于更復(fù)雜的訪問特征來選擇替換的內(nèi)容。