基于固態(tài)硬盤(pán)的在線(xiàn)全文索引管理策略研究

聶玉峰，陳雪帆

(1.武漢科技大學(xué)城市學(xué)院信息工程學(xué)部，湖北武漢430083;2.華中科技大學(xué)計(jì)算機(jī)學(xué)院，湖北武漢430074)

0 引言

全文檢索是指以文本為檢索對(duì)象，允許用戶(hù)以自然語(yǔ)言根據(jù)資料內(nèi)容而不僅是外在特征來(lái)實(shí)現(xiàn)信息檢索的技術(shù)。進(jìn)行全文檢索首先需要構(gòu)建索引，目前最常用的索引結(jié)構(gòu)是倒排索引，它由一列術(shù)語(yǔ)及其記錄列表組成，記錄列表中的每一項(xiàng)記錄了該術(shù)語(yǔ)在某篇文檔中的一次出現(xiàn)信息，主要包括文檔編號(hào)、位置等。在檢索時(shí)，如果命中了某術(shù)語(yǔ)，便可以通過(guò)其記錄列表快速地定位包含了該術(shù)語(yǔ)的文檔并進(jìn)行結(jié)果排序和生成摘要等操作。文獻(xiàn)［1］詳細(xì)介紹了基于倒排索引的全文檢索模型。

倒排索引數(shù)據(jù)量巨大，通常存儲(chǔ)在磁盤(pán)中。但磁盤(pán)的讀寫(xiě)性能與CPU和內(nèi)存之間的差距較大，使全文檢索系統(tǒng)存在磁盤(pán)瓶頸。幸運(yùn)的是基于閃存的固態(tài)硬盤(pán) (solid state drivers，SSD)作為一種純電子設(shè)備，讀寫(xiě)速度遠(yuǎn)勝于磁盤(pán)。容量也在不斷增大，OCZ已經(jīng)推出了1TB的SSD產(chǎn)品［2］。當(dāng)前SSD已被視為取代磁盤(pán)的理想選擇，全文檢索系統(tǒng)也不可避免地需要移植到SSD上。然而現(xiàn)有的索引管理方法都是基于磁盤(pán)的，直接應(yīng)用在物理特性與磁盤(pán)完全不同的SSD上不僅無(wú)法充分利用SSD優(yōu)異的讀寫(xiě)性能，而且會(huì)縮短SSD的使用壽命。因此，設(shè)計(jì)針對(duì)SSD的索引管理策略對(duì)于在SSD上部署全文檢索系統(tǒng)來(lái)說(shuō)是十分關(guān)鍵的。為此，本文首先分析了傳統(tǒng)的在線(xiàn)索引管理策略在SSD上的應(yīng)用情況并指出了其缺陷。然后提出了一種完全針對(duì)SSD的在線(xiàn)索引管理方法:基于分塊的部分合并策略。該方法避免了索引構(gòu)建過(guò)程中對(duì)SSD有害的隨機(jī)寫(xiě)操作，并利用SSD的高速隨機(jī)讀特性極大地減少了對(duì)SSD的寫(xiě)操作。最后對(duì)本文所提出的在線(xiàn)索引管理策略進(jìn)行了實(shí)驗(yàn)評(píng)估，結(jié)果表明該策略能夠更好地適應(yīng)SSD環(huán)境。

1 在線(xiàn)索引管理與固態(tài)硬盤(pán)技術(shù)

1.1 在線(xiàn)全文索引管理

全文索引管理技術(shù)分為離線(xiàn)管理和在線(xiàn)管理兩類(lèi)。前者用于靜態(tài)文檔集。而后者則用于處理動(dòng)態(tài)增長(zhǎng)的文檔集，不僅要隨時(shí)更新現(xiàn)有索引信息，還要響應(yīng)檢索請(qǐng)求，較離線(xiàn)管理要復(fù)雜許多。在索引構(gòu)建過(guò)程中，完整的索引信息由兩部分組成，一部分在內(nèi)存中，稱(chēng)為內(nèi)存索引。另一部分則在磁盤(pán)上，稱(chēng)為磁盤(pán)索引。新文檔產(chǎn)生的索引會(huì)首先被寫(xiě)入內(nèi)存，內(nèi)存索引膨脹至一定程度時(shí)，便將內(nèi)存索引更新至磁盤(pán)索引中，整個(gè)過(guò)程如圖1所示。目前有兩種常用的更新磁盤(pán)索引的思想:原地更新以及合并更新，它們區(qū)別了兩類(lèi)在線(xiàn)索引管理策略。原地更新方法通過(guò)將術(shù)語(yǔ)的新的記錄列表直接追加寫(xiě)入到磁盤(pán)中該術(shù)語(yǔ)已有的記錄列表的后面來(lái)更新磁盤(pán)索引。合并更新方法則通過(guò)將內(nèi)存索引與磁盤(pán)索引進(jìn)行合并來(lái)更新磁盤(pán)索引，在合并過(guò)程中，術(shù)語(yǔ)已有的記錄列表會(huì)被讀出然后與新的記錄列表一起被連續(xù)地寫(xiě)回磁盤(pán)上。由于磁盤(pán)的物理特性，這兩種方法都盡量讓同一個(gè)術(shù)語(yǔ)的記錄列表信息在磁盤(pán)上能夠連續(xù)存儲(chǔ)，從而保證了讀取索引信息的速度。

圖1 索引構(gòu)建過(guò)程

現(xiàn)有研究表明，基于合并更新的方法在索引構(gòu)建速度上要優(yōu)于基于原地更新的方法［3］。這是因?yàn)楹喜⒏码m然理論上需要更多寫(xiě)磁盤(pán)操作，但這些寫(xiě)操作完全是順序的。相反原地更新方法卻會(huì)產(chǎn)生大量隨機(jī)寫(xiě)磁盤(pán)操作，在實(shí)踐中索引性能反倒不如合并更新。因此現(xiàn)有的全文檢索工具如Lucene［4］，一般都采用基于合并的索引管理策略。

1.2 固態(tài)硬盤(pán)技術(shù)

SSD的存儲(chǔ)介質(zhì)閃存具有完全不同于磁盤(pán)的物理特性:首先，閃存由許多塊組成，每個(gè)塊包含一定數(shù)目的頁(yè)，讀寫(xiě)操作以頁(yè)為單位。其次，閃存不支持覆蓋寫(xiě)，在對(duì)頁(yè)進(jìn)行復(fù)寫(xiě)時(shí)需要先擦除包含該頁(yè)的整個(gè)塊。擦除所需的時(shí)間比寫(xiě)入多一個(gè)數(shù)量級(jí)，而且每個(gè)塊允許的擦除次數(shù)是有限的，一般為一萬(wàn)至十萬(wàn)次［5］，超過(guò)這個(gè)次數(shù)后該塊便被認(rèn)為是壞塊。因此，SSD專(zhuān)門(mén)引入了FTL技術(shù)［6］來(lái)管理閃存，它的塊映射機(jī)制屏蔽了閃存特殊的存取方式，將其模擬為磁盤(pán)。此外FTL還具有損耗均衡和垃圾回收等功能。

由于擦除次數(shù)的限制，SSD的使用壽命需要密切關(guān)注，它主要受制于兩個(gè)方面:首先是寫(xiě)操作的量，擦除是由寫(xiě)入觸發(fā)的，減少寫(xiě)操作自然能夠延長(zhǎng)使用壽命。SSD廠(chǎng)商通常建議用戶(hù)使用高檔SSD來(lái)應(yīng)對(duì)寫(xiě)密集型的應(yīng)用［7］。其次是FTL，高效的FTL算法能夠減輕隨機(jī)寫(xiě)操作對(duì)閃存的影響。眾所周知，隨機(jī)寫(xiě)是不利于閃存的，不僅速度較順序?qū)懸枚?，而且?huì)觸發(fā)更多擦除，在使用SSD的過(guò)程中要盡量避免。

2 現(xiàn)有索引管理方法存在的問(wèn)題與分析

本節(jié)中我們通過(guò)實(shí)驗(yàn)分別考察了兩類(lèi)索引管理策略在SSD上的運(yùn)行情況，并根據(jù)實(shí)驗(yàn)結(jié)果指出了現(xiàn)有策略的不足之處。實(shí)驗(yàn)的硬件環(huán)境為2.0GHz處理器 (Intel Dual E2180)，2GB內(nèi)存，320GB的磁盤(pán)以及40GB的SSD(Intel X25-M)。數(shù)據(jù)集收集自維基百科網(wǎng)站［8］，其中包含大約100萬(wàn)篇網(wǎng)頁(yè)文檔。

2.1 原地更新

在磁盤(pán)上原地更新方法的整體性能不如合并更新，而在SSD上原地更新的總體效率依然要低于合并更新。表1給出了在SSD上對(duì)兩種策略的索引和檢索性能進(jìn)行測(cè)試的結(jié)果，其中原地更新方法來(lái)自文獻(xiàn) ［9］，合并更新方法則是常用的幾何分區(qū)合并策略［10］，從中可以發(fā)現(xiàn)兩種方法的檢索性能基本相同，但原地更新的索引構(gòu)建耗時(shí)大約是合并更新的3.5倍。這是因?yàn)樵馗路椒ㄔ谒饕^(guò)程中產(chǎn)生了大量的隨機(jī)寫(xiě)，SSD的隨機(jī)寫(xiě)性能雖然較磁盤(pán)有了較大提升，但還是不如順序?qū)?。而且這些隨機(jī)寫(xiě)顯然會(huì)對(duì)SSD造成比較嚴(yán)重的損耗。上述問(wèn)題是由原地更新方法的設(shè)計(jì)思想造成的，難以進(jìn)行改進(jìn)。

表1 原地更新與合并更新的性能對(duì)比

2.2 合并更新

合并更新方法效率高，寫(xiě)操作也是順序的，但這類(lèi)方法的缺點(diǎn)是寫(xiě)入數(shù)據(jù)量過(guò)大。表2給出了幾何分區(qū)合并策略在索引管理時(shí)寫(xiě)入的數(shù)據(jù)量與有效索引數(shù)據(jù)量的對(duì)比，索引到50萬(wàn)篇文檔時(shí)，幾何分區(qū)合并算法實(shí)際寫(xiě)入SSD的數(shù)據(jù)量大約是有效數(shù)據(jù)的3.2倍，而到100萬(wàn)篇時(shí)已經(jīng)達(dá)到了4.8倍。而過(guò)多的寫(xiě)入會(huì)引發(fā)大量擦除操作，影響SSD的使用壽命。

表2 寫(xiě)入數(shù)據(jù)量統(tǒng)計(jì)結(jié)果

這些額外的寫(xiě)入是由索引的合并產(chǎn)生的，目的是為了避免隨機(jī)寫(xiě)，同時(shí)讓索引在磁盤(pán)上連續(xù)存儲(chǔ)，提高讀取索引的速度。磁盤(pán)具有很長(zhǎng)的使用壽命，因此用額外的寫(xiě)入來(lái)?yè)Q取更高的性能是完全值得的。然而由于擦除次數(shù)的限制，現(xiàn)階段SSD的使用壽命遠(yuǎn)不如磁盤(pán)，如果把合并更新方法不加改進(jìn)地直接應(yīng)用于SSD，大量寫(xiě)操作會(huì)直接造成SSD的過(guò)分損耗。

另一方面，SSD的隨機(jī)讀性能相對(duì)于磁盤(pán)有了極大提升，表3給出了幾何分區(qū)合并策略與不合并策略分別在磁盤(pán)和SSD上的檢索性能對(duì)比結(jié)果。從中可以發(fā)現(xiàn)在磁盤(pán)上幾何分區(qū)策略的檢索速度大約是不合并策略的16.5倍，但在SSD上卻只有約3.3倍。這說(shuō)明通過(guò)頻繁合并保持索引連續(xù)存儲(chǔ)的必要性已經(jīng)大為降低了。

表3 不同設(shè)備上的檢索性能對(duì)比

通過(guò)上一小節(jié)以及本小節(jié)的分析，我們發(fā)現(xiàn)基于原地更新的索引管理策略存在著性能低下和隨機(jī)寫(xiě)的問(wèn)題，而基于合并更新的管理策略的問(wèn)題在于會(huì)產(chǎn)生大量額外寫(xiě)入。總之，傳統(tǒng)的在線(xiàn)索引管理方法都不宜在SSD上直接使用。

3 基于分塊的部分合并策略

3.1 設(shè)計(jì)思想

所有的在線(xiàn)索引策略第一步都是更新內(nèi)存索引，區(qū)別只在于如何更新輔存索引。在上一節(jié)中，我們發(fā)現(xiàn)基于合并的方法雖然會(huì)產(chǎn)生額外的寫(xiě)入，但完全可以通過(guò)適當(dāng)減少索引合并來(lái)加以改進(jìn)。由此我們總結(jié)了針對(duì)SSD的索引管理策略的核心思想:利用SSD較高的隨機(jī)讀速度改進(jìn)合并更新策略，對(duì)高頻詞索引要積極合并，保證其檢索效率，同時(shí)減少意義不大的低頻詞索引的合并，從而在不影響性能的前提下，減少對(duì)SSD的寫(xiě)操作。

上述思想是考慮到兩個(gè)方面的因素:首先，文檔集內(nèi)不同的術(shù)語(yǔ)被檢索到的頻率有著極大的差別，高頻詞記錄列表數(shù)據(jù)量較大，被檢索到的頻率遠(yuǎn)遠(yuǎn)大于記錄列表數(shù)據(jù)量較小的低頻詞。其次，即使減少了低頻詞索引的合并操作使其存儲(chǔ)的連續(xù)性降低，但因?yàn)榈皖l詞的索引量小，SSD遠(yuǎn)勝于磁盤(pán)的隨機(jī)讀性能完全可以保證讀取性能，這一點(diǎn)我們?cè)诘?.2小節(jié)中已經(jīng)有過(guò)分析。因此，低頻詞索引的合并開(kāi)銷(xiāo)完全可以適當(dāng)節(jié)省。但由于SSD隨機(jī)讀的速度還是不如順序讀，因此對(duì)于索引數(shù)據(jù)量大的高頻詞索引還是應(yīng)當(dāng)積極地合并，保持其連續(xù)性。

據(jù)此我們提出了基于分塊的部分合并策略，在該策略中只有記錄列表數(shù)據(jù)量積累到一定程度的高頻詞的索引才會(huì)進(jìn)行合并更新，這一過(guò)程我們稱(chēng)之為部分合并。但是如果僅僅只是在現(xiàn)有策略的基礎(chǔ)上進(jìn)行部分合并是不合適的。因?yàn)樵诂F(xiàn)有策略中高頻詞的記錄列表會(huì)分布在全體索引文件中，要得到其完整的索引信息就必須掃描所有的索引文件，如圖2(a)所示，造成部分合并的效率不可避免地受到整體索引規(guī)模的影響。因此，本策略對(duì)內(nèi)存索引按術(shù)語(yǔ)分塊寫(xiě)入，將高頻詞的記錄列表信息抽取出來(lái)，使得部分合并的效率只與術(shù)語(yǔ)的索引規(guī)模相關(guān)，如圖2(b)所示。以下小節(jié)將詳細(xì)介紹上述過(guò)程。

圖2 不同情況下讀取某術(shù)語(yǔ)完整記錄列表的過(guò)程

3.2 內(nèi)存索引按術(shù)語(yǔ)分塊

在基于分塊的部分合并策略進(jìn)行內(nèi)存索引寫(xiě)SSD的過(guò)程中，會(huì)對(duì)內(nèi)存索引進(jìn)行分塊寫(xiě)入，使內(nèi)存索引在SSD上形成按術(shù)語(yǔ)劃分成的索引塊文件。每一個(gè)索引塊中至少包含一定數(shù)量的記錄列表數(shù)據(jù)，我們?cè)O(shè)置了一個(gè)參數(shù)Bp來(lái)表示這個(gè)設(shè)定的數(shù)據(jù)量。內(nèi)存索引中記錄列表數(shù)據(jù)量超過(guò)Bp的術(shù)語(yǔ)將占據(jù)一個(gè)完整的索引塊，即該索引塊保存的全部是屬于該術(shù)語(yǔ)的記錄列表信息。而索引數(shù)據(jù)量沒(méi)有達(dá)到Bp的術(shù)語(yǔ)則要與其他情況相同的術(shù)語(yǔ)共享一個(gè)索引塊，它們的記錄列表信息會(huì)被保存在同一個(gè)索引文件中。上述過(guò)程如圖3所示，其中free，www等高頻詞各占用一個(gè)索引塊保存記錄列表信息。而pass等低頻詞的記錄列表則被寫(xiě)入同一個(gè)索引塊。

圖3 內(nèi)存索引分塊寫(xiě)入

有的術(shù)語(yǔ)可能在上一次內(nèi)存索引寫(xiě)SSD時(shí)占據(jù)了一個(gè)完整的索引塊，而在這一次內(nèi)存索引寫(xiě)SSD時(shí)其記錄列表信息量達(dá)不到Bp，那么在這一次寫(xiě)SSD時(shí)該術(shù)語(yǔ)便不能占據(jù)整個(gè)索引塊。相反，若上一次某術(shù)語(yǔ)只能與別的術(shù)語(yǔ)共享索引塊，而這一次可以獨(dú)占一個(gè)索引塊，那么在這一次寫(xiě)SSD時(shí)便可以獨(dú)占索引塊?？傊?，能否獨(dú)占索引塊只與這一次的內(nèi)存索引中的記錄列表數(shù)據(jù)量相關(guān)。

這樣，在一次內(nèi)存索引寫(xiě)SSD結(jié)束后，記錄列表數(shù)據(jù)量較大的高頻詞在SSD上獨(dú)占了一個(gè)或多個(gè)索引塊。而余下記錄列表數(shù)據(jù)量較小的低頻詞則共享了一個(gè)索引塊。因此在經(jīng)過(guò)了內(nèi)存索引按術(shù)語(yǔ)分塊后，高頻詞的索引信息基本上都位于被獨(dú)占的索引塊中。在需要合并某高頻詞的索引時(shí)，就可以直接對(duì)其獨(dú)占的索引塊進(jìn)行操作，使得合并的開(kāi)銷(xiāo)與整體的索引規(guī)模無(wú)關(guān)而只于該術(shù)語(yǔ)的索引量有關(guān)。

3.3 索引塊部分合并

在內(nèi)存索引分塊寫(xiě)入SSD的過(guò)程中，如果某個(gè)高頻詞獨(dú)占的索引塊達(dá)到了一定數(shù)量，便會(huì)觸發(fā)索引合并，這里我們采用了二路對(duì)數(shù)合并策略［11］對(duì)其進(jìn)行管理。而對(duì)于共享索引塊則不會(huì)進(jìn)行任何合并操作。這一點(diǎn)與傳統(tǒng)的基于合并更新的索引策略不同，在傳統(tǒng)策略中，索引合并是針對(duì)全體索引文件的，所有的術(shù)語(yǔ)都有可能參加索引合并。而在本文的索引管理策略中，只有被高頻詞獨(dú)占的索引塊才能參與合并。以下是基于分塊的部分合并策略的完整步驟:

輸入:已達(dá)到容量上限待寫(xiě)入SSD的內(nèi)存索引

輸出:經(jīng)過(guò)更新的SSD索引

begin

創(chuàng)建列表termList

將內(nèi)存索引中的術(shù)語(yǔ)按記錄列表的數(shù)據(jù)量從大到小的順序?qū)懭雝ermList

T=termList中第一個(gè)術(shù)語(yǔ)

while(T的記錄列表數(shù)據(jù)量≥Bp){

為T(mén)創(chuàng)建一個(gè)索引塊Bt并將其全部記錄列表寫(xiě)入

if(T觸發(fā)了索引塊合并條件){

其中值得強(qiáng)調(diào)的就是限額采伐以及科學(xué)經(jīng)營(yíng)，這是國(guó)內(nèi)相關(guān)法律規(guī)定的重要制度，同時(shí)也是對(duì)森林資源進(jìn)行控制的關(guān)鍵性措施。在以往的多年以來(lái)國(guó)內(nèi)的森林資源已經(jīng)是得到了嚴(yán)格的控制，整體上呈現(xiàn)出非常好的態(tài)勢(shì)，但是國(guó)內(nèi)依舊是在林木資源上比較缺乏的，這方面的管理還是需要進(jìn)一步強(qiáng)化。

對(duì)T獨(dú)占的索引塊進(jìn)行二路對(duì)數(shù)合并

}

T=termList中下一個(gè)術(shù)語(yǔ)

}

創(chuàng)建一個(gè)索引塊Bshare

寫(xiě)入T的記錄列表

while(true){

T=termList中下一個(gè)術(shù)語(yǔ)

向Bshare寫(xiě)入T的記錄列表

break

}

end

需要強(qiáng)調(diào)的是，某個(gè)術(shù)語(yǔ)能否獨(dú)占一個(gè)索引塊來(lái)存儲(chǔ)其記錄列表在每次內(nèi)存索引寫(xiě)SSD時(shí)都要進(jìn)行判斷。這是考慮到術(shù)語(yǔ)在文檔集中可能并不是均勻分布的，很可能只是在某一部分頻繁出現(xiàn)。就像某個(gè)熱點(diǎn)問(wèn)題只會(huì)在某一段時(shí)間被集中關(guān)注。因此，只需要合并其頻繁出現(xiàn)的部分的索引，保證檢索效率。

4 實(shí)驗(yàn)結(jié)果與分析

本節(jié)對(duì)我們提出的基于分塊的部分合并索引策略進(jìn)行了實(shí)驗(yàn)評(píng)測(cè)，指標(biāo)包括索引與檢索性能以及寫(xiě)入SSD的數(shù)據(jù)量，并引入了幾何分區(qū)合并策略以及不合并策略作為參照。幾何分區(qū)合并是一種常用的具有較高性能的在線(xiàn)索引管理方法，不合并策略不進(jìn)行任何合并，因此具有最快的索引構(gòu)建速度，寫(xiě)操作數(shù)據(jù)量也與有效索引數(shù)據(jù)量相同。實(shí)驗(yàn)的硬件環(huán)境與第2節(jié)中所介紹的相同，但增加了文檔數(shù)量，達(dá)到了400萬(wàn)篇。內(nèi)存索引的大小為100MB左右，參數(shù)Bp的值為1MB。

每一次SSD索引更新結(jié)束后，便對(duì)上述指標(biāo)進(jìn)行一次統(tǒng)計(jì)，其中一次檢索操作由讀取10000個(gè)檢索詞的全部記錄列表信息組成，這些檢索詞來(lái)自AOL從真實(shí)環(huán)境中收集的檢索記錄［12］。圖4、圖5分別給出了索引與檢索性能的實(shí)驗(yàn)結(jié)果。其中橫坐標(biāo)表示內(nèi)存索引寫(xiě)SSD的次數(shù)?？v坐標(biāo)表示的分別是這次內(nèi)存索引寫(xiě)SSD結(jié)束后索引構(gòu)建操作的總用時(shí)以及此時(shí)進(jìn)行一次檢索所耗費(fèi)的時(shí)間。在索引構(gòu)建性能方面，如圖4所示，基于分塊的部分合并策略索引構(gòu)建的用時(shí)與不合并策略相比僅僅是其1.6倍，而常用的幾何分區(qū)合并策略的用間達(dá)到了不合并策略的4.3倍。這主要是因?yàn)槲覀兇蠓鶞p少了索引合并的數(shù)量，避免了頻繁進(jìn)行合并更新的巨大開(kāi)銷(xiāo)。在檢索性能方面，從圖5中可以看到完成一次檢索新方法的用時(shí)大概只有幾何分區(qū)策略的60.4%，其原因在于我們對(duì)訪(fǎng)問(wèn)頻繁的高頻詞采用了更積極的合并策略，因而增強(qiáng)了其存儲(chǔ)的連續(xù)性。雖然對(duì)于低頻詞索引存儲(chǔ)的連續(xù)性減弱了，但由于單個(gè)低頻詞索引數(shù)據(jù)量較小，SSD優(yōu)異的隨機(jī)讀性能依然保證了其讀取效率。而且低頻詞由于被命中次數(shù)少，因此總的來(lái)說(shuō)對(duì)檢索速度的影響也很小。

另一方面，基于分塊的部分合并策略顯著減少了對(duì)SSD的寫(xiě)操作。圖6給出了實(shí)驗(yàn)結(jié)果，其中橫坐標(biāo)表示的是當(dāng)前內(nèi)存索引寫(xiě)SSD的次數(shù)，縱坐標(biāo)則表示此時(shí)對(duì)SSD的寫(xiě)操作總的數(shù)據(jù)量。從中可以看到本文所提出的策略產(chǎn)生的寫(xiě)操作的數(shù)據(jù)量大概是不合并策略的2.1倍，但相對(duì)于幾何分區(qū)合并策略，本策略寫(xiě)入的數(shù)據(jù)大概只是其37.4%。這還是由于我們大量減少了會(huì)產(chǎn)生額外寫(xiě)操作的索引合并的緣故。最后圖7給出了參數(shù)Bp的不同取值對(duì)本策略的檢索性能的影響。Bp取值越大，能夠參與索引合并的術(shù)語(yǔ)減少，會(huì)降低檢索速度:Bp取值為4MB時(shí)完成一次檢索的用時(shí)比Bp取值0.5MB時(shí)多了1.4秒左右，比Bp取值1MB時(shí)多了大約0.6秒。但相應(yīng)的索引合并操作也會(huì)減少。為了平衡檢索性能與寫(xiě)入的數(shù)據(jù)量，我們?cè)O(shè)Bp的值為1MB。

圖7 參數(shù)Bp的取值對(duì)檢索性能的影響

5 結(jié)束語(yǔ)

本文首先通過(guò)實(shí)驗(yàn)分析了現(xiàn)有在線(xiàn)索全文引管理策略在SSD環(huán)境下的不足之處，并以此為基礎(chǔ)提出了一種針對(duì)SSD的全文索引管理策略:基于分塊的部分合并策略。該方法沿用了通過(guò)合并操作更新SSD索引的思想，在索引構(gòu)建過(guò)程中對(duì)內(nèi)存索引按術(shù)語(yǔ)分塊并對(duì)劃分的索引塊進(jìn)行部分合并，充分利用了SSD高效隨機(jī)讀的特性減少了意義不大的合并操作。實(shí)驗(yàn)結(jié)果表明，新策略不僅具有優(yōu)越的索引構(gòu)建與檢索性能，而且顯著降低了對(duì)SSD的損耗，與傳統(tǒng)策略相比能夠更好地適應(yīng)SSD的環(huán)境。下一步的工作是嘗試引入?yún)?shù)Bp的動(dòng)態(tài)適應(yīng)機(jī)制，提高該策略對(duì)不同硬件環(huán)境和數(shù)據(jù)集的適應(yīng)性。

［1］Zobel J，Moffat A.Inverted files for text search engines［J］.ACM Computing Surveys，2006，38(2):1-55.

［2］OCZ Technology.RevoDrive X2(PCI-E solid state drives，220GB-960GB，MLC NAND)［EB/OL］.［2012-01-12］.http://www.ocztechnology.com/ocz-revodrive-x2-pci-express-ssd.html.

［3］Lester N，Zobel J，Williams H E.Efficient online index maintenance for contiguous inverted lists［J］.Information Processing and Management，2006，42(4):916-933.

［4］GUAN Jianhe，GAN Jianfeng.Design and implementation of web search engine based on Lucene［J］.Computer Engineering and Design，2007，28(2):489-491(in Chinese).［管建和，甘劍峰.基于Lucene全文檢索引擎的應(yīng)用研究與實(shí)現(xiàn)［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2007，28(2):489-491.］

［5］ZHENGWenjing，LIMingqiang，SHU Jiwu.Flash storage technology ［J］.Journal of Computer Research and Development，2010，47(4):716-726(in Chinese).［鄭文靜，李明強(qiáng)，舒繼武.Flash存儲(chǔ)技術(shù) ［J］.計(jì)算機(jī)研究與發(fā)展，2010，47(4):716-726.］

［6］Chung T S，Park DJ，Park SW，et al.A survey of flash translation layer［J］.Journal of Systems Architecture-Embedded Systems Design，2009，55(5-6):332-343.

［7］CHEN F，LUO T，ZHANG X D.CAFTL:A content-aware flash translation layer enhancing the lifespan of flash memory based solid state drives［C］//San Jose，U.S.A:USENIX Conference on File and Storage Technologies，2011:77-90.

［8］Wikipedia static HTML dumps ［EB/OL］.［2011-07-21］.http://static.wikipedia.org.

［9］Shieh W Y，Chung CP.A statistics-based approach to incrementally update inverted files［J］.Information Processing and Management，2005，41(2):275-288.

［10］Lester N，Moffat A，Zobel J.Efficient online index construction for text databases ［J］.ACM Transactions on Database Systems，2008，33(3):1-33.

［11］Büttcher S，Clarke CL A.Indexing time vs query time:Trade-offs in dynamic information retrieval systems［C］//Bremen，Germany:International Conference on Information and Knowledge Management，2005:317-318.

［12］Pass G，Chowdhury A，Torgeson C.A picture of search［C］//Hong Kong:International Conference on Scalable Information Systems，2006:1-7.