朱亞?wèn)|,郭嘉豐,蘭艷艷,程學(xué)旗

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

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

朱亞?wèn)|1, 2,郭嘉豐1,蘭艷艷1,程學(xué)旗1

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

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

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

1 引言

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

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

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

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

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

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

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

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

2.1 系統(tǒng)概述

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

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

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

(1)

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

(2)

2.2 頁(yè)面緩存機(jī)制

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

(3)

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

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

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

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

(4)

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

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

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

(5)

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

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

2.5 時(shí)間代價(jià)分析

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

(6)

(7)

(8)

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

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

(9)

(10)

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

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

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

(11)

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

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

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

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

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

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

圖5 用戶請(qǐng)求下一頁(yè)的概率

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

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

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

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

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

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

4 實(shí)驗(yàn)評(píng)估

4.1 數(shù)據(jù)和實(shí)驗(yàn)設(shè)置

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

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

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

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

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

圖6 平均響應(yīng)時(shí)間對(duì)比

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

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

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

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

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

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

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

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

朱亞?wèn)|(1985—)，博士，主要研究領(lǐng)域?yàn)樾畔z索，機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘。E?mail：zhuyadong1985@126．com郭嘉豐(1980—)，博士，副研究員，主要研究領(lǐng)域?yàn)樾畔z索，機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘等。E?mail：guojiafeng@ict．a(chǎn)c．cn蘭艷艷(1982—)，博士，副研究員，主要研究領(lǐng)域?yàn)榻y(tǒng)計(jì)機(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

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

TP391

A