朱亞東,郭嘉豐,蘭艷艷,程學(xué)旗

(1. 中國科學(xué)院 計算技術(shù)研究所 中國科學(xué)院網(wǎng)絡(luò)數(shù)據(jù)科學(xué)與技術(shù)重點實驗室，北京 100190; 2. 中國科學(xué)院大學(xué)，北京 100049)

基于時空局部性的層次化查詢結(jié)果緩存機(jī)制

朱亞東1, 2,郭嘉豐1,蘭艷艷1,程學(xué)旗1

(1. 中國科學(xué)院 計算技術(shù)研究所 中國科學(xué)院網(wǎng)絡(luò)數(shù)據(jù)科學(xué)與技術(shù)重點實驗室，北京 100190; 2. 中國科學(xué)院大學(xué)，北京 100049)

查詢結(jié)果緩存可以對查詢結(jié)果的文檔標(biāo)識符集合或者實際的返回頁面進(jìn)行緩存，以提高用戶查詢的響應(yīng)速度，相應(yīng)的緩存形式可以分別稱之為標(biāo)識符緩存或頁面緩存。對于固定大小的內(nèi)存，標(biāo)識符緩存可以獲得更高的命中率，而頁面緩存可以達(dá)到更高的響應(yīng)速度。該文根據(jù)用戶查詢訪問的時間局部性和空間局部性，提出了一種新穎的基于時空局部性的層次化結(jié)果緩存機(jī)制。首先，該機(jī)制將固定大小的結(jié)果緩存劃分為兩層：頁面緩存和標(biāo)識符緩存。對于用戶提交的查詢，該機(jī)制會首先使用第一層的頁面緩存進(jìn)行應(yīng)答，如果未能命中，則繼續(xù)嘗試使用第二層的標(biāo)識符緩存。實驗顯示這種層次化的緩存機(jī)制較傳統(tǒng)的僅依賴于單一緩存形式的機(jī)制，在平均查詢響應(yīng)時間上，取得了可觀的性能提升：例如，相對單純的頁面緩存，平均達(dá)到9%，最好情況下達(dá)到11%。其次，該機(jī)制在標(biāo)識符緩存的基礎(chǔ)上，設(shè)計了一種啟發(fā)式的預(yù)取策略，對用戶查詢檢索的空間局部性進(jìn)行挖掘。實驗顯示，這種預(yù)取策略的融合，能進(jìn)一步促進(jìn)檢索系統(tǒng)性能的有效提升，從而最終建立起一套時空完備的、有效的結(jié)果緩存機(jī)制。

頁面緩存;標(biāo)識符緩存;啟發(fā)式預(yù)取

1 引言

為了應(yīng)對繁重和高度動態(tài)變化的用戶查詢流量，各種優(yōu)化技術(shù)已被現(xiàn)代搜索引擎采用。緩存技術(shù)是其中一種重要的優(yōu)化手段，在搜索引擎系統(tǒng)的多個層面上進(jìn)行了部署和利用，以降低系統(tǒng)負(fù)載。在系統(tǒng)的底層，有針對索引結(jié)構(gòu)的倒排鏈緩存，用以減少與磁盤的I/O通信[1-3]；在搜索引擎的上層，有針對重復(fù)查詢的結(jié)果緩存，以避免查詢的重復(fù)執(zhí)行，從而提高查詢處理的能力[2-9]；此外，還可能有其他中間層次的緩存，如針對多個term倒排鏈交集的緩存[10]，定位緩存和top-k緩存等[11]。

本文主要針對查詢結(jié)果的緩存展開研究。文獻(xiàn)[7]第一個公開提出，將結(jié)果緩存作為降低查詢響應(yīng)時間的一種手段。文章中，作者研究了查詢?nèi)罩镜姆植迹⒈容^了幾種時下的緩存策略。作者表明，靜態(tài)緩存的性能普遍較差，而基于LRU或LFU的動態(tài)緩存可以獲得較好的性能。文獻(xiàn)[8]學(xué)習(xí)了查詢?nèi)罩揪植啃缘膸追N形式，提出除了在服務(wù)器端進(jìn)行結(jié)果的緩存外，還可以在用戶端對查詢的結(jié)果進(jìn)行緩存。Lempel和Moran的工作中[6]，提出了一種新的結(jié)果緩存策略，稱之為PDC(概率驅(qū)動緩存)策略。它是一種改進(jìn)的預(yù)取緩存機(jī)制，用于處理其他結(jié)果頁(第一頁之后的結(jié)果頁)的查詢請求。Fagni等人提出了一種混合結(jié)果緩存策略，稱之為SDC[1](靜態(tài)-動態(tài)緩存)。該策略維持了一個靜態(tài)緩存和動態(tài)緩存。靜態(tài)緩存存入了在過去較長時期內(nèi)頻繁出現(xiàn)的一些查詢，動態(tài)緩存則通過一定的緩存策略如LRU等進(jìn)行管理，存入的是近期頻繁訪問的查詢結(jié)果。Baeza-Yates等人也提出了一種與SDC較為類似的混合策略，其采用了雙動態(tài)緩存的結(jié)構(gòu)[9]。Gan和Suel研究了基于權(quán)重的結(jié)果緩存，將查詢的處理代價也作為緩存管理策略考慮的要素之一。此外，作者還提出了一種新的基于特征的緩存策略，文中的實驗結(jié)果顯示該策略取得了較大的性能提升[5]。

比較有意思的是，最近Altingovde等人討論了一種混合結(jié)果緩存的使用[13]，與本文的思想較為類似，但在很多方面又有著巨大的差異。首先，二者依賴的模型架構(gòu)基礎(chǔ)完全不一樣，本文是建立在一種典型的商業(yè)分布式架構(gòu)基礎(chǔ)上(具體見第二章節(jié)的分析)，并認(rèn)為這種三層的層次性架構(gòu)(memory-doc server-disk)是層次性緩存機(jī)制有效性的理論基礎(chǔ)；其次，作者沒有從理論上對自己文中的思想進(jìn)行分析論證，只是簡單的實驗評估。而本文則從理論建模的角度，對本文提出的層次化緩存機(jī)制進(jìn)行了充分有效的分析；最后，本文還在此基礎(chǔ)上提出了一種基于標(biāo)識符緩存的啟發(fā)式預(yù)取策略，用以挖掘用戶查詢的空間局部性。這種預(yù)取策略的融合，很好地挖掘和拓展了層次化緩存機(jī)制的效用，從而進(jìn)一步促進(jìn)整個系統(tǒng)性能的有效提升，最終建立起一套對時間局部性和空間局部性都能有效捕捉的，完備的查詢結(jié)果緩存機(jī)制。

結(jié)果緩存主要有兩種形式：頁面緩存和標(biāo)識符緩存。給定一個固定大小的內(nèi)存，標(biāo)識符緩存可以存儲大量的緩存條目，這一數(shù)目遠(yuǎn)大于頁面緩存[1]。標(biāo)識符緩存中的緩存條目是一個有序的 (根據(jù)相關(guān)度排序) 整數(shù)標(biāo)識符集合，通常只有幾十字節(jié)大小 (在每頁10個結(jié)果的標(biāo)準(zhǔn)形式下，如10*8Byte)，而頁面緩存條目是可以直接返回給用戶的HTML頁面，一般為幾KB大小 (如10*512Byte)。在頁面緩存上的命中可以立即返回查詢結(jié)果，而在標(biāo)識符緩存上命中后，仍需要讀取文檔服務(wù)器以生成相應(yīng)的HTML頁面。所以，對于給定的內(nèi)存資源，頁面緩存機(jī)制可以達(dá)到較高的響應(yīng)速度，而標(biāo)識符緩存可以獲取較高的命中率。以往的大多數(shù)工作都集中于頁面緩存的應(yīng)用或某一種單獨形式的應(yīng)用。

本文基于用戶查詢訪問的時間局部性和空間局部性，提出了一種新穎的層次化緩存機(jī)制，這種緩存機(jī)制對頁面緩存的高響應(yīng)速度和標(biāo)識符緩存的高命中率，進(jìn)行了總體的均衡。對于有限的內(nèi)存資源，我們對每一層應(yīng)占用的內(nèi)存大小進(jìn)行了充分的討論，以獲得最優(yōu)化的性能提升。然后，我們在不同緩存大小的情形下，對本文提出的結(jié)果緩存機(jī)制進(jìn)行了討論和評估。相對于單獨的頁面緩存和標(biāo)識符緩存，我們的層次化緩存機(jī)制帶來了更好的性能提升。同時本文還提出了一種基于標(biāo)識符緩存的啟發(fā)式預(yù)取機(jī)制，挖掘用戶查詢的空間局部性。實驗顯示這種預(yù)取機(jī)制的融合，能進(jìn)一步地發(fā)掘?qū)哟位彺鏅C(jī)制的效用，帶來更大的性能提升。

文章的其余部分組織如下：第二節(jié)描述了幾種基本的緩存機(jī)制以及本文提出的層次化的結(jié)果緩存機(jī)制，并對每一種策略下的平均查詢響應(yīng)時間進(jìn)行數(shù)學(xué)建模，然后比較分析；第三節(jié)根據(jù)用戶查詢的空間局部性，結(jié)合標(biāo)識符緩存的優(yōu)勢，提出了一種啟發(fā)式預(yù)取的策略；第四節(jié)對文章提出的緩存機(jī)制和預(yù)取策略進(jìn)行了實驗評估；第五節(jié)對文章進(jìn)行了總結(jié)并簡單闡述了將來的工作。

2 層次化的結(jié)果緩存機(jī)制

我們將詳細(xì)論述本文提出的層次化的結(jié)果緩存機(jī)制。首先我們介紹了兩種傳統(tǒng)的結(jié)果緩存機(jī)制，然后對每一種策略下的查詢的平均響應(yīng)時間進(jìn)行了分析和對比評估。

2.1 系統(tǒng)概述

一個典型的大規(guī)模網(wǎng)絡(luò)搜索引擎系統(tǒng)如圖1所示，它是由一定數(shù)目的檢索節(jié)點組成的分布式架構(gòu)。在這些檢索節(jié)點之上，有一個額外的代理節(jié)點。它負(fù)責(zé)將接受到的用戶查詢轉(zhuǎn)發(fā)到相應(yīng)的檢索節(jié)點，同時收集返回的檢索結(jié)果。然后代理節(jié)點根據(jù)他們的相關(guān)度得分，對這些結(jié)果進(jìn)行合并排序，從而產(chǎn)生一個有序的文檔標(biāo)識符集合。最后根據(jù)這些文檔標(biāo)識符，從文檔服務(wù)器中獲取URL和相關(guān)的文檔摘要信息等，然后生成相應(yīng)的HTML頁面返回給用戶[1]。檢索結(jié)果的緩存通常部署在代理節(jié)點上面。

圖1 帶有結(jié)果緩存的大規(guī)模分布式網(wǎng)絡(luò)搜索引擎構(gòu)架

根據(jù)上面的處理流程，在沒有結(jié)果緩存的情況下，查詢的平均處理時間t1可表述為式(1)。

(1)

其中trank指查詢的排序處理時間，這一過程包括索引倒排鏈的讀取，計算排序等，最終提供了一個有序的文檔標(biāo)識符集合；tsummay表示根據(jù)這些文檔標(biāo)識符從文檔服務(wù)器中讀取相關(guān)摘要內(nèi)容花費的時間；tgenerate表示根據(jù)摘要內(nèi)容生成HTML頁面耗費的時間。事實上，相對于trank和tsummay，將摘要內(nèi)容生成HTML頁面耗費的時間非常少，tgenerate可忽略不計。所以此時t1可表示為式(2)。

(2)

2.2 頁面緩存機(jī)制

以往的工作大多集中在頁面緩存的應(yīng)用上，這里我們也采用該機(jī)制作為我們的評估基準(zhǔn)(baseline)。這種機(jī)制下，查詢的基本處理流程如圖2(a)所示。t2表示在頁面緩存機(jī)制下，查詢的平均處理時間，如式(3)所示。

(3)

這里，a表示頁面緩存的命中率；tinsert1表示插入一個條目到頁面緩存耗費的時間；tread1表示從頁面緩存讀取一個緩存條目耗費的時間；trank和tsummay含義與公式(1)中的相同。

2.3 標(biāo)識符緩存機(jī)制

結(jié)果緩存還可以采用標(biāo)識符緩存的形式，這種機(jī)制下， 基本的查詢處理流程如圖2(b)所示。t3表示在標(biāo)識符緩存機(jī)制下，查詢的平均處理時間，并表示為式(4)。

圖2 傳統(tǒng)的結(jié)果緩存機(jī)制: (a)頁面緩存處理機(jī)制, (b)標(biāo)識符緩存處理機(jī)制

(4)

其中，b表示標(biāo)識符緩存的命中率；tinsert2表示插入一個條目到標(biāo)識符緩存耗費的時間；tread2表示從標(biāo)識符緩存中讀取一個條目耗費的時間；trank和tsummay含義與公式(1)中的相同。

2.4 層次化的結(jié)果緩存機(jī)制

這種機(jī)制同時融合了頁面緩存和標(biāo)識符緩存，并以一個合適的比例對二者在結(jié)果緩存中的大小進(jìn)行了劃分。這種機(jī)制下，查詢的處理流程如圖3所示。t4表示在該機(jī)制下查詢的平均響應(yīng)時間，并表示為式(5)。

(5)

圖3 層次化的結(jié)果緩存處理機(jī)制

其中，a表示頁面緩存的命中率；b表示標(biāo)識符緩存的命中率；其他參數(shù)的含義與公式(2)～(4)中相同。

2.5 時間代價分析

顯然，t1，t2，t3和t4分別表示在沒有結(jié)果緩存、頁面結(jié)果緩存、標(biāo)識符結(jié)果緩存、層次化結(jié)果緩存四種情況下的平均響應(yīng)時間。對于一個特定的網(wǎng)絡(luò)搜索引擎系統(tǒng)，一些參數(shù)的值如：trank，tsummay，tinsert1，tread1，tinsert2和tread2都可以直接測試出來，是一個較為穩(wěn)定的常數(shù)值。在本文后續(xù)實驗章節(jié)中，我們提供了這些參數(shù)的估值(參見表2)。這里我們以本文的實驗環(huán)境為例，將這些參數(shù)的估值代入公式(3)～(5)得到公式(6)～(8)。

(6)

(7)

(8)

頁面緩存VS標(biāo)識符緩存：我們首先對t2和t3進(jìn)行對比分析，如式(9)～(10)所示。

t2-t3=30.91(1-a)-(30.91-30.5b)

(9)

(10)

在本文的實驗環(huán)境中，每一個頁面緩存條目的大小是5KB(10*512Byte)左右，每一個標(biāo)識符緩存條目大小是80B(10*8Byte)。對于固定大小的內(nèi)存，標(biāo)識符緩存提供的緩存條目數(shù)是頁面緩存的64倍。所以在相同的緩存管理策略下，標(biāo)識符緩存的命中率始終大于等于頁面緩存的命中率，即a≤b總是成立的。

當(dāng)a>0.9867b時，也即b≥a>0.9867b，有t2

頁面緩存VS層次化緩存： 對于t2和t4，直接的理論上的比較是困難的。因為兩個表達(dá)式中的參數(shù)a的值并不相同。由于頁面緩存單個條目的大小是標(biāo)識符緩存條目的64倍，因此，如果我們拿出頁面緩存中的很小一部分用于標(biāo)識符緩存，一方面對頁面緩存的命中率幾乎沒有影響，另一方面由標(biāo)識符緩存帶來的性能增益卻是非?？捎^的。例如，對于有300K個緩存條目的頁面緩存，如果我們拿出5K個條目用于標(biāo)識符緩存，帶來的頁面緩存命中率上的變化可忽略不計，即參數(shù)a沒有變化 (實驗顯示，在相同緩存策略如LRU的情況下，頁面緩存在300K個緩存條目和295K個緩存條目下的命中率幾乎不變)，而對應(yīng)的標(biāo)識符緩存卻能額外的提供320K(5K*64)個緩存條目，顯然，這極大提高了結(jié)果緩存的命中率。在這種情況下，層次化緩存機(jī)制較頁面緩存帶來的性能提升，可表示為式(11)。

(11)

例如，b=10%，那么相應(yīng)的性能提升可達(dá)9.86%。

事實上，我們可以從局部性原理的角度對層次化緩存機(jī)制進(jìn)行評估。如圖4中所示，這種層次化緩存機(jī)制類似于計算機(jī)系統(tǒng)中的存儲層次模型。最上面的一層擁有最快的速度和最高的成本，最下面的一層擁有最慢的速度和最低的價格。相對于頁面緩存機(jī)制，層次化緩存機(jī)制增加了一個中間層次，這個層次擁有相對高的速度(文檔服務(wù)器的讀速率tsummary)，但相對低廉的價格。這樣，每一層都作為下面一層的高速緩存，充分利用了局部性原理，很好地融合了速度與成本的目標(biāo)。

圖4 層次化結(jié)果緩存與存儲層次架構(gòu)對比

最優(yōu)劃分：對于層次化結(jié)果緩存機(jī)制，在結(jié)果緩存中，對頁面緩存和標(biāo)識符緩存各自層次大小的劃分，存在一個均衡。找到一個最優(yōu)劃分使性能最大化是非常重要的。由上面t4的表達(dá)式可以發(fā)現(xiàn)，t4的大小取決于a和b(頁面緩存和標(biāo)識符緩存的命中率)，而a和b除了跟每部分的緩存大小相關(guān)外，還跟緩存策略以及實際中具體的用戶查詢行為有關(guān)。所以，我們不能從理論上直接指出使t4最小化的精確劃分。然而，基于上面章節(jié)的分析，我們可以獲得一些有意義的建議：

? 對于一個有限的相對較小的結(jié)果緩存，我們傾向于將絕大部分的結(jié)果緩存空間劃分給標(biāo)識符緩存；

? 對于一個相對較大的結(jié)果緩存，我們傾向于拿出一個較小比例的緩存空間用作標(biāo)識符緩存，而將大部分的檢索結(jié)果緩存到頁面緩存中；

圖5 用戶請求下一頁的概率

3 基于標(biāo)識符緩存的啟發(fā)式預(yù)取策略

事實上，用戶的查詢行為除了具有時間局部性，還具有空間局部性。本章節(jié)在層次化緩存機(jī)制的基礎(chǔ)上，進(jìn)一步挖掘用戶查詢的空間局部性，提出了一種基于標(biāo)識符緩存的啟發(fā)式預(yù)取策略。

我們以部分AOL檢索服務(wù)的查詢?nèi)罩緸槔?2006年3月1日到31日)，對查詢?nèi)罩局杏脩舴摰目赡苄赃M(jìn)行統(tǒng)計，結(jié)果如圖5所示。它表示的含義為，當(dāng)給定同一個話題的第(i-1)個頁面的請求后，用戶點擊第i個頁面的概率。由圖中可知，當(dāng)用戶點擊了第一頁后，其點擊第二頁的概率只有0.2左右，而當(dāng)用戶請求了第二個頁面后，其則有很大的可能性(概率大于0.5)繼續(xù)請求第三個頁面，其他以此類推。事實上，通常絕大數(shù)的用戶查詢請求都不會超過前三個頁面[15]。根據(jù)這一系列查詢?nèi)罩镜慕y(tǒng)計特征，同時結(jié)合標(biāo)識符緩存自身的優(yōu)勢：即能用較小的緩存空間提供大量的緩存條目，我們提出了一種基于標(biāo)識符緩存的啟發(fā)式預(yù)取策略，如表1表示。其中query (keywords, m, n)是一個向后端檢索平臺提交的用戶查詢形式，查詢內(nèi)容為keywords，m為用戶請求的結(jié)果頁面號，n表示需要在標(biāo)識符緩存中緩存的，從m開始的連續(xù)n個結(jié)果頁面。

表1 一種基于標(biāo)識符緩存的啟發(fā)式預(yù)取策略

整個預(yù)取策略是非常簡單的：當(dāng)?shù)谝粋€結(jié)果頁面被請求并且不在任一層次的結(jié)果緩存中(首先在頁面緩存中查找，其次是標(biāo)識符緩存)，我們會對查詢進(jìn)行擴(kuò)展，然后向后端的檢索平臺請求第一和第二兩個結(jié)果頁面，并插入到標(biāo)識符緩存中；當(dāng)?shù)诙€結(jié)果頁面被請求，它通常會立即返回給用戶，然后向后端檢索平臺繼續(xù)請求后續(xù)的三個頁面，并插入到標(biāo)識符緩存中。通過這種方式，我們僅對那些具有很大訪問可能性的有限結(jié)果頁面進(jìn)行預(yù)取。這樣我們在限制由預(yù)取帶來的額外后端負(fù)載的同時，最大化了系統(tǒng)的響應(yīng)速度。

總體上，我們對那些有較大訪問可能性的、有限的結(jié)果頁面進(jìn)行了預(yù)取，同時利用了標(biāo)識符緩存的空間優(yōu)勢，有效地壓縮了由預(yù)取帶來的額外空間開銷，相對于傳統(tǒng)的依賴于頁面緩存的方法，顯然具有更大的優(yōu)勢。這樣在層次化緩存機(jī)制的基礎(chǔ)上，融合啟發(fā)式的預(yù)取策略，建立了一套完備有效的結(jié)果緩存機(jī)制，很好地促進(jìn)了Web檢索性能的提升。

4 實驗評估

4.1 數(shù)據(jù)和實驗設(shè)置

實驗中，我們采用了AOL檢索服務(wù)2006年3月1日到31日之間的查詢?nèi)罩?。并從中隨機(jī)選取了一部分的查詢子集，包含了7 172 919條查詢。我們采用了文獻(xiàn)[5,11]應(yīng)用的規(guī)則，對查詢?nèi)罩具M(jìn)行預(yù)處理，這其中包括去除停用詞，移除只包含停用詞的查詢。在4.2節(jié)實驗中，我們對那些對后續(xù)結(jié)果頁面訪問的查詢請求(ItemRank>10)也予以移除 。處理后的日志集合包含6 587 522條查詢，這里面包含2 326 676條不同的查詢，其中1 417 612條查詢僅僅出現(xiàn)過一次，399 657條查詢出現(xiàn)過兩次。統(tǒng)計顯示這些查詢的頻率服從Zipf分布[12,14-16]。實驗中，這些查詢?nèi)罩景磿r間順序執(zhí)行，前60%(3 952 513)用于緩存系統(tǒng)的預(yù)熱，剩下的40%(2 635 009)用于測量性能參數(shù)。我們在一個單獨的機(jī)器上，采用一個優(yōu)化版本的Lucene進(jìn)行索引的建立和查詢的處理。該機(jī)器采用8 Intel(R) Xeon(R) CPU E5410@2.33GHz以及16GB的RAM。真實的應(yīng)用場景中，一般會存在一個檢索節(jié)點集群，例如，Katta* http://katta.sourceforge.net/部署的分布式檢索框架。這里我們采用的是單個檢索節(jié)點的實驗場景，一方面是出于簡單高效的考慮；另一方面是因為，本文關(guān)注的是前端代理節(jié)點上的查詢結(jié)果緩存的策略機(jī)制，對于后端檢索節(jié)點，可以看成一個黑盒，而不關(guān)心具體的部署細(xì)節(jié)。另外，我們采用相同的兩臺機(jī)器搭建一個文檔服務(wù)器，在上面部署一套voldemort* http://project-voldemort.com/，其中配置的bdb緩存是4GB。我們索引了近700萬文檔，其中包含大約150萬的Wikipedia網(wǎng)頁。

表2展示了在第二節(jié)中提到的相關(guān)參數(shù)的估值。由于頁面緩存和標(biāo)識符緩存都在一個內(nèi)存中，所以tinsert1和tread1，與tinsert2和tread2有相同的值，我們統(tǒng)一用tinsert和tread代替。這些參數(shù)的估值可以作為參考，代入到第二節(jié)中的時間代價公式中，以簡化相關(guān)的理論分析。

表2 實驗中的參數(shù)估值/毫秒

4.2 層次化緩存機(jī)制評估

圖6展示了在三種緩存機(jī)制下的平均響應(yīng)時間，其中橫軸表示頁面緩存條目數(shù)(每一個頁面緩存條目粒度大小是5KB)，縱軸表示查詢的響應(yīng)時間(response time)，單位毫秒(ms)。對于層次化的結(jié)果緩存機(jī)制，我們采用了固定的50K頁面緩存條目用于標(biāo)識符緩存。結(jié)果顯示，較傳統(tǒng)的頁面緩存機(jī)制，層次化的緩存機(jī)制獲得了平均9%的性能提升。最好的地方甚至超過11%，如在300K條目數(shù)的情形。在我們的實驗中，每一個頁面緩存條目的大小是5KB(10*512B)，每一個標(biāo)識符緩存條目的大小是80B(10*8B)，一個頁面緩存條目能提供64倍的標(biāo)識符緩存條目。因此，對于標(biāo)識符緩存機(jī)制，即便僅占據(jù)20K頁面緩存條目數(shù)，其依然能提供高達(dá)1280K(20K*64)個標(biāo)識符緩存條目。顯然，當(dāng)標(biāo)識符緩存的大小超過30K頁面緩存條目，所有測試集中的查詢都將被緩存，因此，之后的標(biāo)識符緩存曲線呈水平不變的趨勢。另外，我們發(fā)現(xiàn)當(dāng)緩存大小小于400K條目時，相對于頁面緩存，標(biāo)識符緩存具有更好的性能。隨著緩存大小的增加，由標(biāo)識符緩存帶來的性能增益逐漸減少，頁面緩存和層次化緩存之間的間隔也逐漸減小。

圖6 平均響應(yīng)時間對比

圖7 200K緩存條目數(shù)下的最優(yōu)劃分

圖8 800K緩存條目數(shù)下的最優(yōu)劃分

圖9 是否融合預(yù)取機(jī)制下的性能對比

圖7、圖8對頁面緩存和標(biāo)識符緩存的最優(yōu)劃分進(jìn)行了研究分析。我們分別采用了200K和800K兩種大小的緩存資源，用以模擬有限的小緩存資源和較大的緩存資源兩種情形。其中x軸表示用于標(biāo)識符緩存的空間比例大小，y軸是響應(yīng)時間，單位毫秒(ms)。在圖9中，當(dāng)全部的緩存大小用于標(biāo)識符緩存時，獲得了最低的響應(yīng)時間。這種情形下(即一個有限的較小的緩存空間)，相對于頁面緩存，標(biāo)識符緩存具有更好的查詢性能，所以我們傾向于保留絕大多數(shù)的緩存空間用于標(biāo)識符緩存，這也與2.5節(jié)中的分析一致。在圖7中， 當(dāng)10%的緩存空間用于標(biāo)識符緩存時，獲得了最佳的性能。事實上，隨著可用的緩存空間的增大，由標(biāo)識符緩存帶來的性能增益逐步減小。進(jìn)一步說，只有當(dāng)標(biāo)識符緩存占據(jù)較小的空間比例的時候，才能一方面將大部分的查詢結(jié)果緩存在頁面緩存中，很好地發(fā)揮頁面緩存的性能優(yōu)勢；另一方面也可以很好地利用標(biāo)識符緩存的優(yōu)勢，即用較小的緩存空間提供大量的緩存條目，對二者的優(yōu)勢進(jìn)行有效的均衡。

4.3 基于標(biāo)識符緩存的啟發(fā)式預(yù)取策略的評估

大量的日志統(tǒng)計顯示，通常的用戶查詢請求僅僅訪問了結(jié)果頁面的第一頁[15]。在4.1和4.2節(jié)的工作中，我們依照文獻(xiàn)[5]的方法，將查詢?nèi)罩局袑罄m(xù)結(jié)果頁面(ItemRank>10)的查詢請求去除。這樣，我們在不考慮查詢預(yù)取的情況下，對本文提出的層次化緩存機(jī)制進(jìn)行了有效的評估。事實上，用戶的查詢除了具有時間局部性，還具有空間局部性。我們對實驗的日志數(shù)據(jù)進(jìn)行了重新處理，將那些對后續(xù)結(jié)果頁面的查詢請求進(jìn)行了保留。然后我們對融合了預(yù)取策略的層次化緩存機(jī)制進(jìn)行實驗評估，實驗結(jié)果如圖9所示。顯然融合了預(yù)取策略的層次化緩存機(jī)制，在查詢響應(yīng)時間上，能帶來進(jìn)一步的性能提升，并且隨著緩存大小的增大，提升進(jìn)一步增強(qiáng)并趨于穩(wěn)定?？傮w上，我們對那些有較大訪問可能性的，有限的結(jié)果頁面進(jìn)行了預(yù)取，同時利用了標(biāo)識符緩存的空間優(yōu)勢，有效地壓縮了由預(yù)取帶來的額外空間開銷，相對于傳統(tǒng)的依賴于頁面緩存的方法，顯然具有更大的優(yōu)勢。

5 總結(jié)和將來的工作

結(jié)果緩存是搜索引擎中一種有效的優(yōu)化手段，用于降低查詢響應(yīng)時間，提高系統(tǒng)吞吐率。對于有限的內(nèi)存資源，本文提出的層次化緩存機(jī)制能獲得很好的性能提升。同時在此基礎(chǔ)上，我們還提出了一種基于標(biāo)識符緩存的啟發(fā)式預(yù)取策略，用以挖掘用戶查詢行為的空間局部性。實驗顯示，這種預(yù)取策略的融合，能進(jìn)一步促進(jìn)整個系統(tǒng)的性能提升。至此，我們建立起了一套完備有效的結(jié)果緩存機(jī)制，很好地促進(jìn)了Web檢索系統(tǒng)的性能提升。在將來的工作中，我們會針對實時搜索引擎中(如新聞搜索，微博搜索)的緩存一致性問題進(jìn)行進(jìn)一步的研究[17-20]，使本文提出的層次化緩存機(jī)制具有更廣泛的應(yīng)用場景。

[1] P Saraiva, E de Moura, N Ziviani，et al. Rank-preserving two-level caching for scalable search engines [C]//Proceedings of the SIGIR, 2001:51-58.

[2] R Baeza-Yates, F Saint-Jean. A three-level search-engine index based in query log distribution [J].SPIRE,2003.

[3] R Baeza-Yates, A Gionis, F Junqueira, et al. The impact of caching on search engines [C]//Proceedings of the SIGIR, 2007.

[4] T Fagni, R Perego, F Silvestri, et al. Boosting the performance of Web search engines: Caching and prefetching query results by exploiting historical usage data [J]. ACM TOIS, 2006:24(1):51-78.

[5] Q Gan, T Suel. Improved techniques for result caching in Web search engines [C]//Proceedings of the WWW,2009:431-440.

[6] R Lempel, S Moran. Predictive caching and prefetching of query results in search engines [C]//Proceedings of the WWW, 2003:19-28.

[7] E Markatos. On caching search engine query results [J]. Computer Communications, 2000,24(7):137-143.

[8] Y Xie, D O’Hallaron. Locality in search engine queries and its implications for caching [C]//Proceedings of the IEEE Infocom, 2002.

[9] R Baeza-Yates, F Junqueira, V Plachouras, et al. Admission policies for caches of search engine results [J]. SPIRE,2007.

[10] X Long, T Suel. Three-level caching for efficient query processing in large Web search engines [C]//Proceedings of the WWW,2005:257-266.

[11] Mauricio Marin, Veronica Gil-Costa, Carlos Gomez-Pantoja. New Caching Techniques for Web Search Engines [C]//HPDC’10,2010:20-25.

[12] D Puppin, F Silvestri, R Perego, et al. Load-balancing and caching for collection selection architectures [C]//Proceedings of the INFOSCALE, 2007.

[13] Altingovde I, Ozcan R. Second Chance: A Hybrid Approach for Dynamic Result Caching in Search Engines [C]//Proceedings of the ECIR’11, 2011:510-516.

[14] J Wang, S Shan, M Lei, et al. Web search engine: characteristics of user behaviors and their implication [J].Science in China, 2001,44(F): 351-365.

[15] David J Brenes, Daniel Gayo-Avello. Stratified analysis of AOL query log [J]. Information Sciences. 2009,179:1844-1858.

[16] C Silverstein, M Henzinger, H Marais,et al. Analysis of a Very Large AltaVista Query Log [J]. Technical Report 014, SRC (Digital, Palo Alto), 1998.

[17] Sadiye Alici, Altingovde I, Ozcan R. Time-based Result Cache Invalidation for Web Search Engines [C]//Proceedings of the SIGIR’11, 2011.

[18] B B Cambazoglu, F P Junqueira, V Plachouras, et al. A refreshing perspective of search engine caching [C]//Proceedings of the WWW,2010:181-190.

[19] R Blanco, E Bortnikov, F Junqueira, et al. Caching search engine results over incremental indices [C]//Proceedings of the SIGIR, 2010:82-89.

[20] S Alici, I S Altingovde, R Ozcan, et al. Timestamp-based cache invalidation for search engines [C]//Proceedings of the WWW,2011:3-4.

A Hierarchical Search Result Caching Based on Temporal and Spatial Locality

ZHU Yadong1, 2, GUO Jiafeng1, LAN Yanyan1, CHENG Xueqi1

(1. CAS Key Lab of Network Data Science and Technology, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China; 2. University of Chinese Academy of Sciences, Beijing 100049, China)

In a result cache, either document identifiers (docID cache) or the actual HTML pages (page cache) can be stored to accelerate the response speed. For a fixed memory size, the docID cache can achieve a higher hit ratio while the page cache can obtain higher response speed. This paper proposes a novel hierarchical result caching scheme based on temporal and spatial locality, in which the result cache is firstly split into two layers: a page cache and a docID cache. In our scheme, page cache will be the first choice for answering some queries, and then the docID cache. In terms of average query response time, the results show that the proposed approach achieves a substantial performance improvement than baseline method by 9% on average, and up to 11% in the best situation. Secondly, the scheme also designs an adaptive prefetching strategy based on docID cache. The experiments show that the proposed scheme combined with the prefetching strategy can lead to an additional performance improvement. And we finally build a complete and effective result caching scheme by capturing the temporal and spatial locality of user search behaviours.

page cache; DocID cache; query response time

朱亞東(1985—)，博士，主要研究領(lǐng)域為信息檢索，機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘。E?mail：zhuyadong1985@126．com郭嘉豐(1980—)，博士，副研究員，主要研究領(lǐng)域為信息檢索，機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘等。E?mail：guojiafeng@ict．a(chǎn)c．cn蘭艷艷(1982—)，博士，副研究員，主要研究領(lǐng)域為統(tǒng)計機(jī)器學(xué)習(xí)，信息檢索和數(shù)據(jù)挖掘等。E?mail：lanyanyan@ict．a(chǎn)c．cn

1003-0077(2016)01-0063-08

2013-10-12 定稿日期： 2014-05-15

國家973計劃(2014CB340401,2012CB316303);國家863計劃(2014AA015204)；國家自然科學(xué)基金(61472401，61433014，61425016，61203298，61572473)

TP391

A