房耘耘（同濟(jì)大學(xué)電子與信息工程學(xué)院，上?！?01804）

基于多查詢特性的搜索引擎緩存替換策略研究

房耘耘
（同濟(jì)大學(xué)電子與信息工程學(xué)院，上海201804）

0　引言

互聯(lián)網(wǎng)飛速發(fā)展，對(duì)人們工作和生活影響日益加深。搜索引擎作為從互聯(lián)網(wǎng)海量信息獲取有效信息最快捷的方式，獲得廣泛使用且重要性日益提升。面對(duì)互聯(lián)網(wǎng)上存在高速膨脹的海量信息，為了返回用戶準(zhǔn)確全面的查詢結(jié)果，搜索引擎需要爬取和處理較以往更大數(shù)據(jù)量的網(wǎng)頁。搜索引擎查詢計(jì)算過程中讀取磁盤上的查詢?cè)~的索引文件涉及大量I/O操作，合并查詢?cè)~索引、查詢?cè)~與網(wǎng)頁相關(guān)性計(jì)算以及查詢結(jié)果排序等涉及大量計(jì)算。為了保證用戶的搜索體驗(yàn)，搜索引擎需要求實(shí)時(shí)返回查詢結(jié)果，高并發(fā)用戶請(qǐng)求帶來的大量計(jì)算給搜索引擎系統(tǒng)帶來了巨大的挑戰(zhàn)。伴隨搜索引擎發(fā)展不斷出現(xiàn)新的技術(shù)以解決挑戰(zhàn)，其中包括大規(guī)模并行處理、提前停止、索引壓縮和緩存技術(shù)等。

緩存作為一種高效的技術(shù)廣泛應(yīng)用在計(jì)算機(jī)各領(lǐng)域中，如CPU Cache、操作系統(tǒng)內(nèi)存頁緩存、Web緩存和數(shù)據(jù)庫緩存等，同樣緩存作為增強(qiáng)搜索引擎性能的高效方式得到業(yè)界廣泛應(yīng)用和學(xué)術(shù)界關(guān)注。搜索引擎緩存通過把一些查詢結(jié)果保存在速度較快的內(nèi)存，許多查詢可以從緩存直接返回結(jié)果，避免了查詢處理過程中的大量計(jì)算和I/O操作，顯著節(jié)省計(jì)算量，減輕搜索引擎后臺(tái)查詢處理壓力，增強(qiáng)搜索引擎的響應(yīng)性，節(jié)省硬件資源并提升系統(tǒng)效能。

緩存隨著命中率提高優(yōu)勢(shì)愈加顯著，緩存命中率為：Hit=Requestcache/Request，即被緩存滿足的查詢請(qǐng)求次數(shù)除以總查詢請(qǐng)求次數(shù)。帶緩存的搜索引擎系統(tǒng)的平均響應(yīng)時(shí)間定義為：Taverage=T1×Hit+T2×（1-Hit），其中T1表示緩存服務(wù)器查詢請(qǐng)求響應(yīng)時(shí)間，T2表示搜索引擎查詢處理服務(wù)器響應(yīng)時(shí)間，由于T2遠(yuǎn)大于T1，因此提高緩存系統(tǒng)命中率可以大幅減少搜索引擎系統(tǒng)查詢結(jié)果返回時(shí)間。隨著緩存滿足查詢請(qǐng)求次數(shù)的增多發(fā)送到搜索引擎后臺(tái)的查詢請(qǐng)求比例會(huì)降低，搜索引擎查詢服務(wù)器的工作負(fù)載會(huì)降低，搜索引擎系統(tǒng)在單位時(shí)間內(nèi)可以響應(yīng)更多的查詢請(qǐng)求，因此可以提高搜索引擎查詢請(qǐng)求吞吐量。因此本文采用緩存命中率作為衡量緩存替換策略優(yōu)劣的指標(biāo)。

由于緩存空間有限，當(dāng)緩存中存儲(chǔ)的查詢結(jié)果占滿緩存空間后，需要從緩存中替換出一部分?jǐn)?shù)據(jù)為新的數(shù)據(jù)留出空間。為了緩存有較高的命中率，需要替換未來訪問次數(shù)最低或未來較長(zhǎng)時(shí)間不會(huì)出現(xiàn)的查詢結(jié)果。緩存替換策略的工作是確定要替換掉的查詢結(jié)果數(shù)據(jù)，以最大化緩存命中率。

2　相關(guān)工作

2.1當(dāng)前搜索引擎緩存替換策略分析

緩存管理策略主要分為靜態(tài)策略和動(dòng)態(tài)策略。靜態(tài)策略通過統(tǒng)計(jì)分析搜索引擎查詢?nèi)罩?，將?dāng)前一段時(shí)間內(nèi)訪問頻率最高的查詢?cè)~對(duì)應(yīng)的返回結(jié)果放到緩存中，這是一種離線方法，緩存內(nèi)容在一定時(shí)間內(nèi)不會(huì)發(fā)生變化。周期性地對(duì)最近歷史訪問記錄進(jìn)行統(tǒng)計(jì)分析，獲取最近的高頻訪問查詢更新緩存數(shù)據(jù)。因?yàn)榫彺嬷屑虞d的是流行的查詢，熱點(diǎn)查詢的請(qǐng)求次數(shù)占了總查詢量的很大一部分，命中率在較小緩存空間下較動(dòng)態(tài)緩存有優(yōu)勢(shì)。一段時(shí)間內(nèi)不發(fā)生緩存替換，并發(fā)訪問模式效率高。緩存中是過期的數(shù)據(jù)，昨天流行的數(shù)據(jù)在今天不一定流行，不利于捕獲大量時(shí)效性高的隨機(jī)查詢數(shù)據(jù)。文獻(xiàn)［2］基于用戶查詢?nèi)罩颈容^了動(dòng)態(tài)緩存替換策略LRU，LRU策略的變種：FBR、LRU/2以及SLRU和靜態(tài)緩存策略的命中率，得出靜態(tài)緩存對(duì)較小容量緩存效率更高，相對(duì)動(dòng)態(tài)緩存策略在較小緩存空間下命中率更高，隨著緩存容量增大帶來的有效性增益不如動(dòng)態(tài)緩存增長(zhǎng)快。

動(dòng)態(tài)策略中隨著數(shù)據(jù)項(xiàng)被訪問，在緩存數(shù)據(jù)缺失和緩存空間飽和時(shí)會(huì)分別導(dǎo)致數(shù)據(jù)項(xiàng)加載和替換，引起緩存內(nèi)容不斷發(fā)生變化。由于緩存具有容量限制，當(dāng)緩存空間滿時(shí)要加載新的數(shù)據(jù)項(xiàng)需要首先采用某種替換算法將部分緩存的內(nèi)容替換出以留出空間容納新的緩存數(shù)據(jù)項(xiàng)。著名的替換算法有LRU，LFU，LRU/2，SLRU等，這些算法分別依據(jù)緩存數(shù)據(jù)項(xiàng)的訪問時(shí)間信息，頻次信息等作為替換依據(jù)。

靜態(tài)和動(dòng)態(tài)混合的緩存策略［5］，充分利用查詢的時(shí)間局部性和空間局部性。通過歷史查詢記錄分析將訪問請(qǐng)求頻次最高的流行查詢及對(duì)應(yīng)結(jié)果放入靜態(tài)緩存，靜態(tài)緩存中的數(shù)據(jù)在一段時(shí)間內(nèi)只讀不發(fā)生數(shù)據(jù)替換。其余緩存空間通過指定的替換算法動(dòng)態(tài)管理，用來服務(wù)不在靜態(tài)緩存中的查詢。動(dòng)態(tài)和靜態(tài)相結(jié)合的替換策略獲得超過單純動(dòng)態(tài)和靜態(tài)替換策略的緩存命中率。但也存在動(dòng)態(tài)空間被壓縮，捕獲隨機(jī)查詢能力下降；數(shù)據(jù)過時(shí)問題，浪費(fèi)緩存空間；沒有統(tǒng)一的數(shù)據(jù)管理策略，緩存數(shù)據(jù)查詢存在重復(fù)請(qǐng)求問題。

文獻(xiàn)［8］提出基于查詢?cè)~歷史訪問記錄特征信息和代表查詢?cè)~自身特性的指標(biāo)。證明了緩存命中率隨著替換算法涉及特性的增加而提升，充分利用查詢的訪問特征信息是提高緩存命中率的關(guān)鍵。利用數(shù)據(jù)統(tǒng)計(jì)和機(jī)器學(xué)習(xí)的方法相比直接設(shè)計(jì)特定的緩存替換算法更為準(zhǔn)確，取得較高的緩存命中率。但緩存管理方式復(fù)雜，成本高昂，可用性低。

概率驅(qū)動(dòng)的緩存策略［3］，通過統(tǒng)計(jì)計(jì)算之前提交的每個(gè)查詢的概率分布，概率模型用來標(biāo)識(shí)特定查詢結(jié)果頁未來訪問概率的大小，并基于概率模型來預(yù)測(cè)用戶請(qǐng)求的查詢結(jié)果頁并將對(duì)應(yīng)的查詢結(jié)果提前放入緩存來提高緩存命中率。文獻(xiàn)［6］通過鑒別不常見查詢?cè)~，在緩存管理策略中引入了緩存進(jìn)入控制策略阻止用戶查詢中不活躍的查詢?cè)~對(duì)應(yīng)的查詢結(jié)果進(jìn)入到緩存，避免了不常見查詢進(jìn)入緩存占用常見查詢?cè)~的空間引起緩存命中率下降。緩存進(jìn)入控制策略用查詢?cè)~的過去訪問頻率預(yù)測(cè)其未來的訪問頻率，通過一個(gè)初始化訓(xùn)練階段可以計(jì)算得到查詢?cè)~的過去訪問頻率。文獻(xiàn)［17］給出了確定相關(guān)查詢和預(yù)取的方法。文獻(xiàn)［18］提出了預(yù)取特定的查詢結(jié)果頁面的方法。文獻(xiàn)［7］和［10］研究了不同數(shù)據(jù)類型的緩存和空間分配比。文獻(xiàn)［9］提出在大規(guī)模矩陣式搜索結(jié)點(diǎn)陣列存在的情況下，通過數(shù)據(jù)副本和數(shù)據(jù)聚集，增加位置緩存把搜索請(qǐng)求路由到特定查詢結(jié)點(diǎn)來優(yōu)化緩存系統(tǒng)和提升搜索引擎的資源利用率，提升搜索引擎的吞吐量并減少用戶延遲。文獻(xiàn)［19-20］研究了搜索引擎緩存數(shù)據(jù)的時(shí)效性問題。文獻(xiàn)［20-21］研究了搜索引擎緩存對(duì)查詢計(jì)算節(jié)省量的問題，引入了查詢?cè)~索引長(zhǎng)度并結(jié)合緩存替換算法來量化查詢計(jì)算節(jié)省量。

當(dāng)前搜索引擎緩存研究啟示：要重合運(yùn)用查詢特性信息，從數(shù)據(jù)中學(xué)習(xí)，設(shè)計(jì)符合查詢分布規(guī)律的替換策略，實(shí)現(xiàn)高效的替換算法。

2.2搜索引擎查詢分布研究

本文試驗(yàn)所用數(shù)據(jù)來自搜狗搜索實(shí)驗(yàn)室提供的用戶查詢?nèi)罩荆瑪?shù)據(jù)文件為搜狗搜索引擎2008年6月份的用戶查詢點(diǎn)擊日志，日志文件按天劃分，每天約170萬條記錄。每條記錄的格式為：訪問時(shí)間、用戶ID、查詢請(qǐng)求、該URL在返回結(jié)果中的排名、用戶點(diǎn)擊順序號(hào)和用戶點(diǎn)擊的URL。緩存策略命中率測(cè)試中，采取以第21-27日查詢預(yù)熱，測(cè)試第28日命中率的方式，因此在研究查詢整體分布時(shí)，本文對(duì)21-28日查詢?nèi)罩具M(jìn)行整體分析。

大量搜索引擎日志分析顯示出搜索引擎訪問記錄數(shù)字統(tǒng)計(jì)特性符合一定全局性的規(guī)律。用戶的查詢、點(diǎn)擊URL、查看結(jié)果頁面的頻次具有Power-law分布特征［15］；并且不同查詢、不同用戶和不同點(diǎn)擊URL的數(shù)量滿足Heaps定律［11-12］。Heaps［16］定律折射出：盡管搜索引擎總查詢量巨大，但不同查詢串的數(shù)量不會(huì)急劇增長(zhǎng)，會(huì)保持相對(duì)穩(wěn)定。因此空間適當(dāng)?shù)乃阉饕婢彺娌粫?huì)出現(xiàn)大比例的緩存數(shù)據(jù)項(xiàng)替換，從理論上保證了搜索引擎的效能。

局部性是緩存能夠起作用的理論基礎(chǔ)，在計(jì)算機(jī)領(lǐng)域中指程序在一個(gè)段時(shí)間內(nèi)執(zhí)行期間訪問地址在一定范圍。本文通過對(duì)查詢?nèi)罩窘y(tǒng)計(jì)分析驗(yàn)證了查詢請(qǐng)求的局部性，少數(shù)高頻查詢占據(jù)了總查詢請(qǐng)求次數(shù)的大多數(shù)。通過搜索日志分析發(fā)現(xiàn)：頻次最高的20%查詢占據(jù)了約80%的查詢請(qǐng)求量（圖2）。占不同查詢數(shù)較少的搜索頻次排名靠前的高頻查詢占到總查詢次數(shù)的很大一部分，表明緩存高頻查詢是提升命中率的關(guān)鍵。

搜索引擎查詢時(shí)間局部性表現(xiàn)為：對(duì)于查詢請(qǐng)求序列（Q1，Q2，Q3，…，Qn），Qi（1≤i≤n）表示第i次查詢請(qǐng)求，當(dāng)i＜j時(shí)，若Qi=Qj則稱Qi在間隔d=|i-j|距離產(chǎn)生重復(fù)查詢，d被稱為查詢復(fù)用距離。查詢復(fù)用距離如圖1所示，可以看到多數(shù)查詢的復(fù)用距離集中在間隔相對(duì)較小的范圍內(nèi)，但是進(jìn)一步通過統(tǒng)計(jì)分析查詢?cè)~的查詢間隔距離可以發(fā)現(xiàn)，有相當(dāng)一部分查詢的間隔跨度較大，LRU等動(dòng)態(tài)替換算法管理緩存時(shí)會(huì)造成后續(xù)相同查詢緩存缺失，不能復(fù)用查詢結(jié)果產(chǎn)生緩存增益。一部分常見查詢間隔較大，捕獲這部分查詢有利于提升緩存命中率。

以查詢熱度代表了當(dāng)前該查詢的訪問情況，日志分析發(fā)現(xiàn)：一段時(shí)間內(nèi)查詢?cè)L問次數(shù)較高、用戶數(shù)越多，查詢結(jié)果點(diǎn)擊次數(shù)較高查詢熱度越高。捕獲熱點(diǎn)查詢是保證高緩存命中率的關(guān)鍵。查詢間隔時(shí)間越長(zhǎng)、最近未訪問時(shí)間越久，預(yù)示著查詢?cè)~冷卻，未來一定時(shí)間內(nèi)被訪問概率變小。

圖1　查詢復(fù)用距離（log-log）

圖2　查詢頻率排名（log-log）

3　基于多查詢特性的未來價(jià)值函數(shù)

傳統(tǒng)緩存替換算法如LRU，LFU及其變種以時(shí)間和頻率作為緩存替換依據(jù)，通過多級(jí)隊(duì)列區(qū)分單次查詢和多次查詢等，無法細(xì)粒度區(qū)分?jǐn)?shù)據(jù)項(xiàng)的緩存價(jià)值，不能準(zhǔn)確的緩存高緩存價(jià)值的數(shù)據(jù)。沒有根本解決LRU對(duì)大間隔查詢捕獲不足和LFU的數(shù)據(jù)污染問題?；趯?duì)象大小的替換算法Size和GDSF等主要考慮數(shù)據(jù)項(xiàng)大小等特性，基于目標(biāo)函數(shù)的替換算法LUV和Mix等復(fù)雜替換策略考慮了眾多參數(shù)但不一定準(zhǔn)確符合實(shí)際需要。搜索日志分析可以發(fā)現(xiàn)：用戶查詢?cè)~分布范圍較廣，查詢?cè)~之間沒有直接聯(lián)系和規(guī)律，查詢請(qǐng)求量有階段性變化，查詢的時(shí)效性和頻繁性也有較大不同。廣泛的查詢?cè)~范圍和不穩(wěn)定的搜索請(qǐng)求量使得傳統(tǒng)緩存替換算法的有效性降低。用在搜索引擎緩存替換策略中，上述緩存替換策略不能充分合理的利用查詢請(qǐng)求歷史記錄中眾多統(tǒng)計(jì)指標(biāo)，替換函數(shù)不一定符合實(shí)際查詢分布規(guī)律，不能準(zhǔn)確確定數(shù)據(jù)項(xiàng)的緩存價(jià)值以提高命中率。

傳統(tǒng)替換算法對(duì)查詢請(qǐng)求的規(guī)律參考不足，對(duì)查詢的時(shí)效性，突發(fā)性和常見查詢等查詢分布沒有針對(duì)性設(shè)計(jì)，所使用的目標(biāo)函數(shù)不一定符合真實(shí)查詢請(qǐng)求規(guī)律，不能充分利用查詢請(qǐng)求歷史對(duì)未來查詢的預(yù)測(cè)作用。現(xiàn)有緩存替換算法采用一個(gè)訪問信息指標(biāo)或幾個(gè)指標(biāo)的簡(jiǎn)單組合作為查詢?cè)~對(duì)應(yīng)查詢結(jié)果數(shù)據(jù)項(xiàng)的替換依據(jù)，用在搜索引擎緩存替換策略中，不能充分利用查詢請(qǐng)求歷史記錄中眾多統(tǒng)計(jì)指標(biāo)。研究表明基于多特性的緩存替換算法在命中率方面高于現(xiàn)在通用算法，且隨著算法涉及特性的增加緩存命中率也提升，這說明充分利用查詢中呈現(xiàn)的特性是提高緩存命中率的關(guān)鍵。經(jīng)典方法沒有以最佳的方式利用查詢特性，從數(shù)據(jù)中學(xué)習(xí)比直接設(shè)計(jì)替換算法有更好的優(yōu)勢(shì)。與直接設(shè)計(jì)特定的緩存替換算法相比，利用數(shù)據(jù)統(tǒng)計(jì)和機(jī)器學(xué)習(xí)的方法更為準(zhǔn)確，特別是在搜索引擎有大量搜索日志可以利用和復(fù)雜替換算法的開銷與查詢處理開銷相比較小的現(xiàn)實(shí)情況下。

本文致力于充分利用查詢?cè)~的歷史統(tǒng)計(jì)信息作為緩存替換的依據(jù)以提高緩存命中率，設(shè)計(jì)新型緩存替換策略，彌補(bǔ)LRU替換策略對(duì)常見大間隔查詢緩存命中不足的劣勢(shì)。設(shè)計(jì)符合查詢時(shí)效性的模型，基于數(shù)據(jù)分析中的多元回歸方法確定模型參數(shù)值，做到模型參數(shù)隨查詢?cè)L問記錄可調(diào)整，利用歷史信息預(yù)測(cè)未來查詢請(qǐng)求的可能性作為緩存替換依據(jù)，緩存替換算法采用替換掉未來最低訪問可能的數(shù)據(jù)項(xiàng)，保留未來訪問可能性高的數(shù)據(jù)項(xiàng)的方式來提高命中率。

搜索日志相關(guān)研究表明：一個(gè)查詢的熱度代表當(dāng)前該查詢?cè)L問請(qǐng)求情況，當(dāng)前的熱點(diǎn)查詢和常見查詢?cè)L問次數(shù)較高、訪問請(qǐng)求的用戶數(shù)多，查詢結(jié)果的鏈接點(diǎn)擊次數(shù)較高。另一方面：查詢?cè)~請(qǐng)求出現(xiàn)的間隔時(shí)間越長(zhǎng)以及該查詢?cè)~最近未被訪問的時(shí)間越長(zhǎng)預(yù)示著該查詢?cè)~的冷卻。當(dāng)前一段時(shí)間查詢請(qǐng)求頻次越高、請(qǐng)求訪問的用戶數(shù)越多以及查詢結(jié)果的鏈接點(diǎn)擊次數(shù)越多該查詢?cè)~在未來傾向于被查詢的次數(shù)越多；當(dāng)前一段時(shí)間內(nèi)某查詢請(qǐng)求間隔時(shí)間越長(zhǎng)以及該查詢最近未被訪問的時(shí)間越長(zhǎng)表示該查詢?cè)~訪問熱度較低，預(yù)示著未來一段時(shí)間內(nèi)被用戶請(qǐng)求查詢的可能性越低。

依據(jù)以上分析，可以以查詢?cè)~相關(guān)的各種歷史統(tǒng)計(jì)特征作為參數(shù)建模，來標(biāo)示查詢?cè)~未來被訪問的可能大小，繼而作為緩存替換的依據(jù)。經(jīng)過綜合分析，提出以下六個(gè)查詢?cè)~特性作為緩存替換的依據(jù)：

F1：查詢頻次，LFU算法的基礎(chǔ)，代表了查詢?cè)~的歷史訪問熱度。

F2：獨(dú)立用戶數(shù)，代表了查詢的廣泛度和流行度。

F3：查詢結(jié)果平均點(diǎn)擊數(shù)，代表了用戶對(duì)查詢信息本身的興趣和了解廣度。

F4：最近未訪問時(shí)長(zhǎng)，代表了查詢的最近訪問時(shí)間特性，LRU的基礎(chǔ)。

F5：最后兩次訪問時(shí)間間隔，重要的時(shí)間局部性特征信息，LIRS算法的基礎(chǔ)。

F6：平均訪問時(shí)間間隔，查詢跨度內(nèi)的平均查詢間隔時(shí)長(zhǎng)是綜合的時(shí)間局部性度量特征，整體反映了查詢的時(shí)間局部性強(qiáng)度和緩存效能。

經(jīng)過全面分析，以：

作為查詢熱度值函數(shù)，其中F1-F6分別為：查詢?cè)~的查詢頻次、查詢?cè)~返回結(jié)果的平均點(diǎn)擊鏈接數(shù)、該查詢對(duì)應(yīng)的獨(dú)立用戶數(shù)、查詢最近未被訪問時(shí)長(zhǎng)（當(dāng)前時(shí)間減去該查詢最近一次的訪問時(shí)間）、查詢平均訪問時(shí)間間隔以及最后兩次查詢的訪問時(shí)間間隔，r1-r6為查詢?cè)~特征值的指數(shù)系數(shù)，r0為比例系數(shù)，Y代表查詢?cè)~的熱度值。上式中特征值的指數(shù)和比例系數(shù)的引入使模型更符合實(shí)際情況，當(dāng)前r0-r6的值未知，F(xiàn)1-F6可以通過查詢?nèi)罩窘y(tǒng)計(jì)分析得到，確定未知參數(shù)r0-r6的值是問題的關(guān)鍵。

本文所用搜索日志數(shù)據(jù)為按天劃分的搜索日志，某一查詢?cè)~當(dāng)日出現(xiàn)次數(shù)和間隔時(shí)長(zhǎng)往往和該查詢?cè)~上次出現(xiàn)當(dāng)日的查詢?cè)~訪問記錄有聯(lián)系?；谝陨戏治觯谥?，令Y值為某查詢?cè)~在一天中的出現(xiàn)次數(shù)（Y≥1），F(xiàn)1-F6分別為該查詢?cè)~上一次出現(xiàn)當(dāng)天搜索日志中該查詢?cè)~出現(xiàn)的次數(shù)、返回結(jié)果平均點(diǎn)擊次數(shù)、獨(dú)立用戶數(shù)、平均訪問時(shí)間間隔、最后兩次出現(xiàn)時(shí)間間隔以及上次該查詢出現(xiàn)時(shí)刻距離本日該查詢出現(xiàn)時(shí)刻的間隔時(shí)長(zhǎng)。每個(gè)查詢通過一個(gè)月中多日搜索日志構(gòu)造出多條包含未知參數(shù)r0-r6的1.1型等式，兩邊同時(shí)取對(duì)數(shù)得到：

的形式（其中Y'=lg（Y），β0=lg（r0），β1=r1，X1=lg（F1），……），該等式符合多元線性回歸模型，通過多組實(shí)際觀測(cè)數(shù)據(jù)構(gòu)造多元線性回歸方程組，可以通過最小二乘法計(jì)算得到未知參數(shù)β0-β6。

多元線性回歸定義為：設(shè)隨機(jī)變量y與x1，x2，…，xp滿足關(guān)系式：

其中β0，β1，…，βp，σ2均為未知參數(shù)，p≥2，稱式（3）為多元線性回歸模型。在實(shí)際問題中，通過獲得n組觀測(cè)數(shù)據(jù)（xi1，xi2，…，xip，yi），i=1，2，…，n，線性回歸模型（3）可以表示為：

一般要求觀測(cè)次數(shù)n大于待估計(jì)參數(shù)的個(gè)數(shù)，即n＞p+1。本文實(shí)驗(yàn)數(shù)據(jù)中p=6，查詢?cè)~在一天中的查詢請(qǐng)求次數(shù)和該查詢?cè)~上一次出現(xiàn)當(dāng)日查詢?cè)~的相關(guān)統(tǒng)計(jì)信息及時(shí)間間隔等組成為一組觀測(cè)數(shù)據(jù)，因此可通過以上多元回歸模型計(jì)算未知參數(shù)r0-r6的查詢?cè)~在一個(gè)月的日志文件中需要至少在九天的搜索日志記錄中出現(xiàn)（一個(gè)查詢?cè)谇昂髢扇粘霈F(xiàn)的形成一條記錄）。

模型（4）的矩陣形式為：

在滿足式（3）的多元回歸模型中，使用最小二乘估計(jì)法根據(jù)n組樣本觀測(cè)值（xi1，xi2，…，xip，yi），i=1，2，…，n，參數(shù)β0，β1，…，βp的估計(jì)值β0'，β1'，…，βp'，使平方和達(dá)到最小，對(duì)每一個(gè)未知數(shù)求偏導(dǎo)，并整理得到等式XTXβ= XTY，其中，

可求得β0，β1，…，βp的解為β→=（XTX）-1XTY。然后通過（1.2）式轉(zhuǎn)化就得到了未知參數(shù)值r0-r6。

4　基于綜合價(jià)值的緩存替換策略

緩存替換策略的設(shè)計(jì)目標(biāo)是達(dá)到較高的緩存命中率以及較低的計(jì)算復(fù)雜度，這就要求緩存替換策略能夠準(zhǔn)確評(píng)估緩存數(shù)據(jù)項(xiàng)的價(jià)值，找出緩存價(jià)值相對(duì)低的數(shù)據(jù)項(xiàng)替換出緩存。緩存數(shù)據(jù)項(xiàng)的價(jià)值依賴于該數(shù)據(jù)在未來一段時(shí)間內(nèi)被訪問的情況：數(shù)據(jù)項(xiàng)未來被訪問的時(shí)間距離現(xiàn)在越近、未來一段時(shí)間內(nèi)被請(qǐng)求的次數(shù)越多該數(shù)據(jù)項(xiàng)的緩存價(jià)值越高。因此緩存替換時(shí)如果能較準(zhǔn)確地預(yù)測(cè)數(shù)據(jù)項(xiàng)未來被訪問的情況，替換出低緩存價(jià)值的數(shù)據(jù)項(xiàng)，保留高緩存價(jià)值的數(shù)據(jù)項(xiàng)，可以達(dá)到較高的緩存命中率并充分發(fā)揮緩存的效能。

前端實(shí)時(shí)記錄查詢特征信息并存儲(chǔ)，查詢特征記錄可以快捷的轉(zhuǎn)化為的訪問統(tǒng)計(jì)信息F并代入未來價(jià)值函數(shù)，可以得到該查詢?cè)~對(duì)應(yīng)的緩存價(jià)值。即用查詢?cè)~當(dāng)前的訪問信息預(yù)測(cè)評(píng)估了未來該查詢被請(qǐng)求訪問情況。鑒于只有占不同查詢中小部分的常見查詢才具有未來價(jià)值函數(shù)值，以及低緩存替換策略計(jì)算復(fù)雜度的需求，本系統(tǒng)不采用對(duì)緩存中所有關(guān)鍵詞計(jì)算價(jià)值函數(shù)值并排序然后替換掉價(jià)值函數(shù)值最低的關(guān)鍵詞對(duì)應(yīng)數(shù)據(jù)項(xiàng)這種緩存替換策略。

本文提出綜合了LRU算法和未來價(jià)值函數(shù)的緩存替換策略，充分發(fā)揮LRU策略對(duì)查詢最近訪問時(shí)間特性的利用以捕獲熱點(diǎn)查詢且計(jì)算復(fù)雜度低的優(yōu)勢(shì)，以及未來價(jià)值函數(shù)中利用查詢?cè)~當(dāng)前訪問統(tǒng)計(jì)信息所標(biāo)識(shí)的查詢?cè)~緩存價(jià)值。緩存替換策略為：維護(hù)一個(gè)以查詢?cè)~最近一次訪問時(shí)間為標(biāo)準(zhǔn)的LRU隊(duì)列，替換時(shí)從LRU隊(duì)列末尾選擇N個(gè)最久未訪問的查詢?cè)~（N稱為替換區(qū)大小）做比較。通過以下策略找出要換出的查詢?cè)~數(shù)據(jù)項(xiàng)：定義未經(jīng)過搜索日志分析計(jì)算出r0-r6值的查詢?cè)~的權(quán)值為其被請(qǐng)求訪問的次數(shù)，定義經(jīng)過搜索日志分析并計(jì)算出 r0-r6值的查詢?cè)~權(quán)值為Y=由于經(jīng)過搜索日志分析并計(jì)算出r0-r6的查詢?cè)~是一個(gè)月內(nèi)至少有九天中被請(qǐng)求訪問的常見查詢，未經(jīng)過搜索日志分析計(jì)算出r0-r6的查詢?cè)~往往是生僻查詢?cè)~或新出現(xiàn)查詢?cè)~，這種查詢?cè)~往往只出現(xiàn)一次或少數(shù)幾次，可重現(xiàn)性差，間隔時(shí)間較長(zhǎng)，緩存價(jià)值低。因此設(shè)定經(jīng)過搜索日志分析計(jì)算出r0-r6的查詢?cè)~的權(quán)值大于未經(jīng)過搜索日志分析計(jì)算出r0-r6的查詢?cè)~的權(quán)值，有優(yōu)先替換掉費(fèi)常見查詢而保留常見查詢。遍歷替換區(qū)中的查詢?cè)~得到權(quán)值最小的查詢?cè)~作為犧牲者，從緩存中刪除該查詢和對(duì)應(yīng)的查詢結(jié)果數(shù)據(jù)，為未來進(jìn)入緩存的查詢?cè)~對(duì)應(yīng)的查詢結(jié)果數(shù)據(jù)留出空間。在遍歷的過程中，考慮到占查詢總量中約20%的查詢?cè)~只會(huì)出現(xiàn)一次沒有緩存價(jià)值，設(shè)定若某個(gè)查詢?cè)~未經(jīng)過搜索日志分析計(jì)算出r0-r6并且其被訪問次數(shù)為1則直接刪除緩存中這條查詢?cè)~對(duì)應(yīng)數(shù)據(jù)項(xiàng)，而無需繼續(xù)遍歷比較剩下的查詢?cè)~。這樣大大的提高了緩存替換的效率并且不降低緩存命中率。N作為緩存替換區(qū)大小值可以調(diào)節(jié)，N值越大查詢?cè)~對(duì)應(yīng)的歷史訪問統(tǒng)計(jì)信息對(duì)替換策略的影響越大，同時(shí)更傾向于保留常見查詢，替換算法的計(jì)算復(fù)雜度越高；N值越小查詢?cè)~的動(dòng)態(tài)特性即該查詢?cè)~的最久未訪問時(shí)間在替換策略中的影響越高，同時(shí)緩存替換計(jì)算復(fù)雜度越低。

圖1　不同替換區(qū)大小下的緩存命中率對(duì)比

圖2　不同緩存大小下本替換策略與LRU替換策略的緩存命中率對(duì)比

5　實(shí)驗(yàn)結(jié)果

曲線開始階段因?yàn)槟芾梦磥韮r(jià)值函數(shù)作為替換的依據(jù)隨著替換區(qū)的增大緩存命中率逐漸遞增，替換區(qū)達(dá)到一定大小后命中率趨于平緩穩(wěn)定，這是因?yàn)樘鎿Q區(qū)已經(jīng)保留了足夠多的常見查詢，在一定緩存空間下當(dāng)替換區(qū)大小相對(duì)緩存空間大小過高時(shí)，替換區(qū)內(nèi)常見查詢保留過高，不利于對(duì)隨機(jī)查詢的再次捕獲，導(dǎo)致命中率下降。小緩存空間下（1萬）替換區(qū)完全覆蓋后，緩存保留最常見的查詢導(dǎo)致緩存命中率持續(xù)提升。

從本圖可以看出：本文提出的替換策略相比LRU策略在緩存較小區(qū)間隨著緩存空間的增加緩存命中率提升的更迅速，可以充分利用緩存空間帶來較高的緩存命中率。由圖可知，本文提出的緩存替換算法相比LRU算法在最優(yōu)緩存空間（每日總查詢量的20%）下命中率有顯著提升，命中率提高7%左右，考慮到查詢量巨大，這是非?？捎^的提升。

6　結(jié)語

本文通過對(duì)搜索引擎查詢分布特性的分析研究，提出了基于多查詢特性的未來價(jià)值函數(shù)，通過周期性日志分析統(tǒng)計(jì)計(jì)算查詢相關(guān)特征值并利用多元回歸函數(shù)計(jì)算得到查詢?cè)~的r參數(shù)值，緩存替換時(shí)將查詢?cè)~的未來價(jià)值函數(shù)值融入到綜合替換策略中。首先，通過大規(guī)模細(xì)粒度的搜索日志分析將每一個(gè)查詢?cè)~過去一個(gè)月內(nèi)的訪問歷史特征信息按天統(tǒng)計(jì)出來，然后基于查詢請(qǐng)求分布規(guī)律為查詢?cè)~建立價(jià)值函數(shù)并利用歷史訪問統(tǒng)計(jì)信息計(jì)算出價(jià)值函數(shù)中的未知參數(shù)，最后在緩存替換時(shí)充分利用了查詢?cè)~當(dāng)下的動(dòng)態(tài)特性和歷史訪問特征信息預(yù)示的緩存價(jià)值，本緩存替換策略傾向于保留當(dāng)下活躍查詢?cè)~和常見查詢?cè)~在緩存中，顯然這是保證較高緩存命中率的關(guān)鍵?？傮w上充分利用LRU替換策略的動(dòng)態(tài)特性對(duì)時(shí)效性查詢的捕獲，替換時(shí)不直接替換掉最久未訪問的查詢而是從一定量 （替換區(qū)大?。┳罹梦丛L問查詢中比較綜合價(jià)值函數(shù)值大小，將綜合價(jià)值最小的查詢替換掉，這樣可以保留高緩存價(jià)值查詢數(shù)據(jù)以獲得較高緩存命中率。本緩存策略彌補(bǔ)了LRU對(duì)大查詢間隔常見查詢緩存缺失的劣勢(shì)，通過調(diào)整替換區(qū)大小可以動(dòng)態(tài)改變緩存對(duì)常見查詢和時(shí)效性查詢的捕獲能力，對(duì)查詢負(fù)載類型的變化具有良好適應(yīng)性。通過對(duì)每日更新的查詢?nèi)罩痉治觯梢詣?dòng)態(tài)調(diào)整查詢相關(guān)特征的參數(shù)值，使綜合價(jià)值函數(shù)準(zhǔn)確，時(shí)效性高，充分利用查詢當(dāng)前的歷史訪問信息對(duì)未來訪問情況的預(yù)測(cè)作用。最后通過對(duì)比測(cè)試證明了本緩存替換策略相較傳統(tǒng)緩存替換策略的優(yōu)勢(shì)。

［1］Deitel H M，Deitel P J，Choffnes D R.Operating systems，3rd edition，Prentice Hall，2004

［2］E.Markatos.On caching search engine query results.In 5th International Web Caching and Content Delivery Workshop，May 2000.

［3］R.Lempel and S.Moran.Predictive caching and prefetching of query results in search engines.In Proc of the 12th World Wide Web Conference，19-28，2003

［4］X.Long，T.Suel.Three-level caching for efficient query processing in large web search engines.In Proc of the 14th World Wide Web Conference，May 2005.

［5］T.Fagni，R.Perego，F(xiàn).Silvestri，S.Orlando.Boosting the performance of web search engines：Caching and prefetching query results by exploiting historical usage data.ACM Trans on Information Systems，24，2006.

［6］R.Baeza-Yates，F(xiàn).Junqueira，V.Plachouras，H.Witschel.Admission policies for caches of search engine results.InProc.of the 14th String Processing and Information Retrieval Symposium，Sept.2007.

［7］R.Baeze-Yates，A.Gionis，F(xiàn).Junquerira，et al.Design tradeoffs for search engine caching.ACM Trans on Web，2008，2（4）：1-28.

［8］Q.Gran，T.Suel.Improved techniques for result caching in web search engines.Proceedings of WWW 09，ACM，2009：431-440.

［9］Marin，M.，Gil-Costa，V.，&Gomez-Pantoja，C.，New caching techniques for web search engines.In Proceedings of the 19th ACM international symposium.On high performance distributed computing（pp.215-226），2010.

［10］Rifat Ozcan，I.Sengor Altingovde，B.Barla Cambazoglu，F(xiàn)lavio P.Junqueira，？zgür Ulusoy.A five-level static cache architecture !for web search engines.Information Processing and Management，48（2012）：828-840.

［11］Silverstein C，Henzinger M，Marais H，et al.Analysis of a very large web search log.Proc of SIGIR 98.ACM，1998：6-12.

［12］Y.Li，S.Zhang，B.Wang，et al.Characteristics of Chinese Query Logs.Journal of Computational Information Systems，2008，4（3）：1127-1136.

［13］李亞楠，王斌.一個(gè)中文搜索引擎的查詢?nèi)罩痉治?數(shù)字圖書館論壇.1673-2286.2008.07.002.

［14］馬宏遠(yuǎn)，王斌.基于日志分析的搜索引擎查詢結(jié)果緩存研究.計(jì)算機(jī)研究與發(fā)展.49：224-228，2012.

［15］M.Faloutsos，P.Faloutsos，C.Faloutsos.On power-law relationships of the Internet topology.SIGCOMM'99：251-262.

［16］Linyuan Lü，Zi-Ke Zhang，Tao Zhou.Deviation of Zipf's and Heaps'Laws in Human Languages with Limited Dictionary Sizes.Scientific Reports 3，Article number：1082.Published 30 January 2013.

［17］Pragya Kaushik.Sreesh Gaur.Mayank Singh.Use of query logs for providing cache support to the search engine.978-93-80544-12-0/14/2014 IEEE.

［18］Hong-yuan Ma，Wei Liu，Bing-jie Wei，Liang Shi，Xiu-guo Bao，Li-hong Wang.PAAP：Prefetch-Aware Admission Policies for Query !Results Cache in Web Search Engines.SIGIR'14 July 06-11 2014.

［19］Edward Bortnikov.Ronny Lempel.and Kolman Vornovitsky.Caching for realtime Search.Springer-Verlag Berlin Heidelberg 2011.

［20］B.Barla Cambazoglu.Flavio P.Junqueira.Vassilis Plachouras.A refreshing perspective of search engine caching.WWW 2010，!April 26-30，2010.

［21］RIFAT OZCAN，ISMAIL SENGOR ALTINGOVDE，OZG¨UR ULUSOY.Cost-aware strategies for query result caching in web Search Engines.ACM 1559-1131/2011/05.

［22］Fethi Burak Sazoglu.B.Barla Cambazoglu.Rifat Ozcan.A financial cost metric for result caching.SIGIR'13，July 28-August.

Search Engine；Cache Replacement Strategy；Integrated Value；Multiple Query Attributes；Regression Analysis

Research on the Search Engine Cache Replacement Strategy Based on Multiple Query Attributes

FANG Yun-yun
（Department of Computer Science，School of Electronics and Information Engineering，Tongji University，Tongji 201804）

1007-1423（2015）23-0003-08

10.3969/j.issn.1007-1423.2015.23.001

房耘耘（1990-），男，山東濟(jì)寧人，碩士，研究方向?yàn)榉植际接?jì)算、大數(shù)據(jù)分析

2015-08-01

2015-08-10

緩存是搜索引擎中的重要技術(shù)，能顯著節(jié)省查詢處理計(jì)算量，縮短查詢請(qǐng)求響應(yīng)時(shí)間和提高系統(tǒng)吞吐量，得到學(xué)術(shù)界的關(guān)注和業(yè)界的廣泛應(yīng)用。當(dāng)前搜索引擎緩存替換策略沒有充分利用查詢的多種訪問特征信息，沒有充分利用查詢分布特性，傳統(tǒng)替換策略用在搜索引擎中存在各種不足。針對(duì)以上問題研究查詢請(qǐng)求的分布特征，分析現(xiàn)有緩存替換策略的不足，然后基于查詢?cè)~訪問特征提出代表查詢?cè)~未來熱度值的綜合價(jià)值函數(shù)模型，然后通過對(duì)搜索引擎查詢?nèi)罩具M(jìn)行細(xì)粒度的統(tǒng)計(jì)分析，得到每個(gè)查詢?cè)~每日各訪問特性的詳細(xì)記錄，并基于多元回歸分析方法計(jì)算得到查詢?cè)~價(jià)值函數(shù)模型的未知參數(shù)，設(shè)計(jì)結(jié)合查詢?cè)~當(dāng)前動(dòng)態(tài)訪問特性和未來訪問熱度值的查詢結(jié)果緩存管理策略，并通過真實(shí)查詢記錄測(cè)試不同替換區(qū)大小下本緩存系統(tǒng)的命中率，對(duì)比證明所提出的緩存替換策略相對(duì)于傳統(tǒng)替換策略在命中率方面的顯著提升。

Cache is a very important technology in search engine，which can significantly save query computation processing，improve query response and improve system throughput，which are widely applied by the academia and the industry.Current cache replacement policy does not take full advantage of search engine queries of multiple access feature information，does not take advantage of query distribution，also deficiencies exist in the traditional replacement policy when used in search engines.For the above problems，studies query distribution features，analyses the insufficient of existing cache replace strategies，then proposes integrated value function model represent query future heat value based on query access features，analyses search engine query log for fine grain degrees，gets each query's daily access characteristics of detailed records，and based on multiple return analysis in the minimum II multiplication calculation to get the unknown parameter in the function model，designs cache management policy integrate current dynamic access attributes with the heat value of the query in the future，hit ratio test of replace management strategy through real query shows that，in contrast with traditional cache replacement strategy，this replacement strategy significantly exceeds them in hit rate.