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

房耘耘（同濟大學電子與信息工程學院，上海　201804）

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

房耘耘
（同濟大學電子與信息工程學院，上海201804）

0　引言

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

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

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

由于緩存空間有限，當緩存中存儲的查詢結果占滿緩存空間后，需要從緩存中替換出一部分數據為新的數據留出空間。為了緩存有較高的命中率，需要替換未來訪問次數最低或未來較長時間不會出現的查詢結果。緩存替換策略的工作是確定要替換掉的查詢結果數據，以最大化緩存命中率。

2　相關工作

2.1當前搜索引擎緩存替換策略分析

緩存管理策略主要分為靜態策略和動態策略。靜態策略通過統計分析搜索引擎查詢日志，將當前一段時間內訪問頻率最高的查詢詞對應的返回結果放到緩存中，這是一種離線方法，緩存內容在一定時間內不會發生變化。周期性地對最近歷史訪問記錄進行統計分析，獲取最近的高頻訪問查詢更新緩存數據。因為緩存中加載的是流行的查詢，熱點查詢的請求次數占了總查詢量的很大一部分，命中率在較小緩存空間下較動態緩存有優勢。一段時間內不發生緩存替換，并發訪問模式效率高。緩存中是過期的數據，昨天流行的數據在今天不一定流行，不利于捕獲大量時效性高的隨機查詢數據。文獻［2］基于用戶查詢日志比較了動態緩存替換策略LRU，LRU策略的變種：FBR、LRU/2以及SLRU和靜態緩存策略的命中率，得出靜態緩存對較小容量緩存效率更高，相對動態緩存策略在較小緩存空間下命中率更高，隨著緩存容量增大帶來的有效性增益不如動態緩存增長快。

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

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

文獻［8］提出基于查詢詞歷史訪問記錄特征信息和代表查詢詞自身特性的指標。證明了緩存命中率隨著替換算法涉及特性的增加而提升，充分利用查詢的訪問特征信息是提高緩存命中率的關鍵。利用數據統計和機器學習的方法相比直接設計特定的緩存替換算法更為準確，取得較高的緩存命中率。但緩存管理方式復雜，成本高昂，可用性低。

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

當前搜索引擎緩存研究啟示：要重合運用查詢特性信息，從數據中學習，設計符合查詢分布規律的替換策略，實現高效的替換算法。

2.2搜索引擎查詢分布研究

本文試驗所用數據來自搜狗搜索實驗室提供的用戶查詢日志，數據文件為搜狗搜索引擎2008年6月份的用戶查詢點擊日志，日志文件按天劃分，每天約170萬條記錄。每條記錄的格式為：訪問時間、用戶ID、查詢請求、該URL在返回結果中的排名、用戶點擊順序號和用戶點擊的URL。緩存策略命中率測試中，采取以第21-27日查詢預熱，測試第28日命中率的方式，因此在研究查詢整體分布時，本文對21-28日查詢日志進行整體分析。

大量搜索引擎日志分析顯示出搜索引擎訪問記錄數字統計特性符合一定全局性的規律。用戶的查詢、點擊URL、查看結果頁面的頻次具有Power-law分布特征［15］；并且不同查詢、不同用戶和不同點擊URL的數量滿足Heaps定律［11-12］。Heaps［16］定律折射出：盡管搜索引擎總查詢量巨大，但不同查詢串的數量不會急劇增長，會保持相對穩定。因此空間適當的搜索引擎緩存不會出現大比例的緩存數據項替換，從理論上保證了搜索引擎的效能。

局部性是緩存能夠起作用的理論基礎，在計算機領域中指程序在一個段時間內執行期間訪問地址在一定范圍。本文通過對查詢日志統計分析驗證了查詢請求的局部性，少數高頻查詢占據了總查詢請求次數的大多數。通過搜索日志分析發現：頻次最高的20%查詢占據了約80%的查詢請求量（圖2）。占不同查詢數較少的搜索頻次排名靠前的高頻查詢占到總查詢次數的很大一部分，表明緩存高頻查詢是提升命中率的關鍵。

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

以查詢熱度代表了當前該查詢的訪問情況，日志分析發現：一段時間內查詢訪問次數較高、用戶數越多，查詢結果點擊次數較高查詢熱度越高。捕獲熱點查詢是保證高緩存命中率的關鍵。查詢間隔時間越長、最近未訪問時間越久，預示著查詢詞冷卻，未來一定時間內被訪問概率變小。

圖1　查詢復用距離（log-log）

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

3　基于多查詢特性的未來價值函數

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

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

本文致力于充分利用查詢詞的歷史統計信息作為緩存替換的依據以提高緩存命中率，設計新型緩存替換策略，彌補LRU替換策略對常見大間隔查詢緩存命中不足的劣勢。設計符合查詢時效性的模型，基于數據分析中的多元回歸方法確定模型參數值，做到模型參數隨查詢訪問記錄可調整，利用歷史信息預測未來查詢請求的可能性作為緩存替換依據，緩存替換算法采用替換掉未來最低訪問可能的數據項，保留未來訪問可能性高的數據項的方式來提高命中率。

搜索日志相關研究表明：一個查詢的熱度代表當前該查詢訪問請求情況，當前的熱點查詢和常見查詢訪問次數較高、訪問請求的用戶數多，查詢結果的鏈接點擊次數較高。另一方面：查詢詞請求出現的間隔時間越長以及該查詢詞最近未被訪問的時間越長預示著該查詢詞的冷卻。當前一段時間查詢請求頻次越高、請求訪問的用戶數越多以及查詢結果的鏈接點擊次數越多該查詢詞在未來傾向于被查詢的次數越多；當前一段時間內某查詢請求間隔時間越長以及該查詢最近未被訪問的時間越長表示該查詢詞訪問熱度較低，預示著未來一段時間內被用戶請求查詢的可能性越低。

依據以上分析，可以以查詢詞相關的各種歷史統計特征作為參數建模，來標示查詢詞未來被訪問的可能大小，繼而作為緩存替換的依據。經過綜合分析，提出以下六個查詢詞特性作為緩存替換的依據：

F1：查詢頻次，LFU算法的基礎，代表了查詢詞的歷史訪問熱度。

F2：獨立用戶數，代表了查詢的廣泛度和流行度。

F3：查詢結果平均點擊數，代表了用戶對查詢信息本身的興趣和了解廣度。

F4：最近未訪問時長，代表了查詢的最近訪問時間特性，LRU的基礎。

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

F6：平均訪問時間間隔，查詢跨度內的平均查詢間隔時長是綜合的時間局部性度量特征，整體反映了查詢的時間局部性強度和緩存效能。

經過全面分析，以：

作為查詢熱度值函數，其中F1-F6分別為：查詢詞的查詢頻次、查詢詞返回結果的平均點擊鏈接數、該查詢對應的獨立用戶數、查詢最近未被訪問時長（當前時間減去該查詢最近一次的訪問時間）、查詢平均訪問時間間隔以及最后兩次查詢的訪問時間間隔，r1-r6為查詢詞特征值的指數系數，r0為比例系數，Y代表查詢詞的熱度值。上式中特征值的指數和比例系數的引入使模型更符合實際情況，當前r0-r6的值未知，F1-F6可以通過查詢日志統計分析得到，確定未知參數r0-r6的值是問題的關鍵。

本文所用搜索日志數據為按天劃分的搜索日志，某一查詢詞當日出現次數和間隔時長往往和該查詢詞上次出現當日的查詢詞訪問記錄有聯系。基于以上分析，在中，令Y值為某查詢詞在一天中的出現次數（Y≥1），F1-F6分別為該查詢詞上一次出現當天搜索日志中該查詢詞出現的次數、返回結果平均點擊次數、獨立用戶數、平均訪問時間間隔、最后兩次出現時間間隔以及上次該查詢出現時刻距離本日該查詢出現時刻的間隔時長。每個查詢通過一個月中多日搜索日志構造出多條包含未知參數r0-r6的1.1型等式，兩邊同時取對數得到：

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

多元線性回歸定義為：設隨機變量y與x1，x2，…，xp滿足關系式：

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

一般要求觀測次數n大于待估計參數的個數，即n＞p+1。本文實驗數據中p=6，查詢詞在一天中的查詢請求次數和該查詢詞上一次出現當日查詢詞的相關統計信息及時間間隔等組成為一組觀測數據，因此可通過以上多元回歸模型計算未知參數r0-r6的查詢詞在一個月的日志文件中需要至少在九天的搜索日志記錄中出現（一個查詢在前后兩日出現的形成一條記錄）。

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

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

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

4　基于綜合價值的緩存替換策略

緩存替換策略的設計目標是達到較高的緩存命中率以及較低的計算復雜度，這就要求緩存替換策略能夠準確評估緩存數據項的價值，找出緩存價值相對低的數據項替換出緩存。緩存數據項的價值依賴于該數據在未來一段時間內被訪問的情況：數據項未來被訪問的時間距離現在越近、未來一段時間內被請求的次數越多該數據項的緩存價值越高。因此緩存替換時如果能較準確地預測數據項未來被訪問的情況，替換出低緩存價值的數據項，保留高緩存價值的數據項，可以達到較高的緩存命中率并充分發揮緩存的效能。

前端實時記錄查詢特征信息并存儲，查詢特征記錄可以快捷的轉化為的訪問統計信息F并代入未來價值函數，可以得到該查詢詞對應的緩存價值。即用查詢詞當前的訪問信息預測評估了未來該查詢被請求訪問情況。鑒于只有占不同查詢中小部分的常見查詢才具有未來價值函數值，以及低緩存替換策略計算復雜度的需求，本系統不采用對緩存中所有關鍵詞計算價值函數值并排序然后替換掉價值函數值最低的關鍵詞對應數據項這種緩存替換策略。

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

圖1　不同替換區大小下的緩存命中率對比

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

5　實驗結果

曲線開始階段因為能利用未來價值函數作為替換的依據隨著替換區的增大緩存命中率逐漸遞增，替換區達到一定大小后命中率趨于平緩穩定，這是因為替換區已經保留了足夠多的常見查詢，在一定緩存空間下當替換區大小相對緩存空間大小過高時，替換區內常見查詢保留過高，不利于對隨機查詢的再次捕獲，導致命中率下降。小緩存空間下（1萬）替換區完全覆蓋后，緩存保留最常見的查詢導致緩存命中率持續提升。

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

6　結語

本文通過對搜索引擎查詢分布特性的分析研究，提出了基于多查詢特性的未來價值函數，通過周期性日志分析統計計算查詢相關特征值并利用多元回歸函數計算得到查詢詞的r參數值，緩存替換時將查詢詞的未來價值函數值融入到綜合替換策略中。首先，通過大規模細粒度的搜索日志分析將每一個查詢詞過去一個月內的訪問歷史特征信息按天統計出來，然后基于查詢請求分布規律為查詢詞建立價值函數并利用歷史訪問統計信息計算出價值函數中的未知參數，最后在緩存替換時充分利用了查詢詞當下的動態特性和歷史訪問特征信息預示的緩存價值，本緩存替換策略傾向于保留當下活躍查詢詞和常見查詢詞在緩存中，顯然這是保證較高緩存命中率的關鍵。總體上充分利用LRU替換策略的動態特性對時效性查詢的捕獲，替換時不直接替換掉最久未訪問的查詢而是從一定量 （替換區大小）最久未訪問查詢中比較綜合價值函數值大小，將綜合價值最小的查詢替換掉，這樣可以保留高緩存價值查詢數據以獲得較高緩存命中率。本緩存策略彌補了LRU對大查詢間隔常見查詢緩存缺失的劣勢，通過調整替換區大小可以動態改變緩存對常見查詢和時效性查詢的捕獲能力，對查詢負載類型的變化具有良好適應性。通過對每日更新的查詢日志分析，可以動態調整查詢相關特征的參數值，使綜合價值函數準確，時效性高，充分利用查詢當前的歷史訪問信息對未來訪問情況的預測作用。最后通過對比測試證明了本緩存替換策略相較傳統緩存替換策略的優勢。

［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.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.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.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，Flavio 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］李亞楠，王斌.一個中文搜索引擎的查詢日志分析.數字圖書館論壇.1673-2286.2008.07.002.

［14］馬宏遠，王斌.基于日志分析的搜索引擎查詢結果緩存研究.計算機研究與發展.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-），男，山東濟寧人，碩士，研究方向為分布式計算、大數據分析

2015-08-01

2015-08-10

緩存是搜索引擎中的重要技術，能顯著節省查詢處理計算量，縮短查詢請求響應時間和提高系統吞吐量，得到學術界的關注和業界的廣泛應用。當前搜索引擎緩存替換策略沒有充分利用查詢的多種訪問特征信息，沒有充分利用查詢分布特性，傳統替換策略用在搜索引擎中存在各種不足。針對以上問題研究查詢請求的分布特征，分析現有緩存替換策略的不足，然后基于查詢詞訪問特征提出代表查詢詞未來熱度值的綜合價值函數模型，然后通過對搜索引擎查詢日志進行細粒度的統計分析，得到每個查詢詞每日各訪問特性的詳細記錄，并基于多元回歸分析方法計算得到查詢詞價值函數模型的未知參數，設計結合查詢詞當前動態訪問特性和未來訪問熱度值的查詢結果緩存管理策略，并通過真實查詢記錄測試不同替換區大小下本緩存系統的命中率，對比證明所提出的緩存替換策略相對于傳統替換策略在命中率方面的顯著提升。

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.