基于固態硬盤的在線全文索引管理策略研究

聶玉峰，陳雪帆

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

0 引言

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

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

1 在線索引管理與固態硬盤技術

1.1 在線全文索引管理

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

圖1 索引構建過程

現有研究表明，基于合并更新的方法在索引構建速度上要優于基于原地更新的方法［3］。這是因為合并更新雖然理論上需要更多寫磁盤操作，但這些寫操作完全是順序的。相反原地更新方法卻會產生大量隨機寫磁盤操作，在實踐中索引性能反倒不如合并更新。因此現有的全文檢索工具如Lucene［4］，一般都采用基于合并的索引管理策略。

1.2 固態硬盤技術

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

由于擦除次數的限制，SSD的使用壽命需要密切關注，它主要受制于兩個方面:首先是寫操作的量，擦除是由寫入觸發的，減少寫操作自然能夠延長使用壽命。SSD廠商通常建議用戶使用高檔SSD來應對寫密集型的應用［7］。其次是FTL，高效的FTL算法能夠減輕隨機寫操作對閃存的影響。眾所周知，隨機寫是不利于閃存的，不僅速度較順序寫要慢得多，而且會觸發更多擦除，在使用SSD的過程中要盡量避免。

2 現有索引管理方法存在的問題與分析

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

2.1 原地更新

在磁盤上原地更新方法的整體性能不如合并更新，而在SSD上原地更新的總體效率依然要低于合并更新。表1給出了在SSD上對兩種策略的索引和檢索性能進行測試的結果，其中原地更新方法來自文獻 ［9］，合并更新方法則是常用的幾何分區合并策略［10］，從中可以發現兩種方法的檢索性能基本相同，但原地更新的索引構建耗時大約是合并更新的3.5倍。這是因為原地更新方法在索引過程中產生了大量的隨機寫，SSD的隨機寫性能雖然較磁盤有了較大提升，但還是不如順序寫。而且這些隨機寫顯然會對SSD造成比較嚴重的損耗。上述問題是由原地更新方法的設計思想造成的，難以進行改進。

表1 原地更新與合并更新的性能對比

2.2 合并更新

合并更新方法效率高，寫操作也是順序的，但這類方法的缺點是寫入數據量過大。表2給出了幾何分區合并策略在索引管理時寫入的數據量與有效索引數據量的對比，索引到50萬篇文檔時，幾何分區合并算法實際寫入SSD的數據量大約是有效數據的3.2倍，而到100萬篇時已經達到了4.8倍。而過多的寫入會引發大量擦除操作，影響SSD的使用壽命。

表2 寫入數據量統計結果

這些額外的寫入是由索引的合并產生的，目的是為了避免隨機寫，同時讓索引在磁盤上連續存儲，提高讀取索引的速度。磁盤具有很長的使用壽命，因此用額外的寫入來換取更高的性能是完全值得的。然而由于擦除次數的限制，現階段SSD的使用壽命遠不如磁盤，如果把合并更新方法不加改進地直接應用于SSD，大量寫操作會直接造成SSD的過分損耗。

另一方面，SSD的隨機讀性能相對于磁盤有了極大提升，表3給出了幾何分區合并策略與不合并策略分別在磁盤和SSD上的檢索性能對比結果。從中可以發現在磁盤上幾何分區策略的檢索速度大約是不合并策略的16.5倍，但在SSD上卻只有約3.3倍。這說明通過頻繁合并保持索引連續存儲的必要性已經大為降低了。

表3 不同設備上的檢索性能對比

通過上一小節以及本小節的分析，我們發現基于原地更新的索引管理策略存在著性能低下和隨機寫的問題，而基于合并更新的管理策略的問題在于會產生大量額外寫入。總之，傳統的在線索引管理方法都不宜在SSD上直接使用。

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

3.1 設計思想

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

上述思想是考慮到兩個方面的因素:首先，文檔集內不同的術語被檢索到的頻率有著極大的差別，高頻詞記錄列表數據量較大，被檢索到的頻率遠遠大于記錄列表數據量較小的低頻詞。其次，即使減少了低頻詞索引的合并操作使其存儲的連續性降低，但因為低頻詞的索引量小，SSD遠勝于磁盤的隨機讀性能完全可以保證讀取性能，這一點我們在第2.2小節中已經有過分析。因此，低頻詞索引的合并開銷完全可以適當節省。但由于SSD隨機讀的速度還是不如順序讀，因此對于索引數據量大的高頻詞索引還是應當積極地合并，保持其連續性。

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

圖2 不同情況下讀取某術語完整記錄列表的過程

3.2 內存索引按術語分塊

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

圖3 內存索引分塊寫入

有的術語可能在上一次內存索引寫SSD時占據了一個完整的索引塊，而在這一次內存索引寫SSD時其記錄列表信息量達不到Bp，那么在這一次寫SSD時該術語便不能占據整個索引塊。相反，若上一次某術語只能與別的術語共享索引塊，而這一次可以獨占一個索引塊，那么在這一次寫SSD時便可以獨占索引塊。總之，能否獨占索引塊只與這一次的內存索引中的記錄列表數據量相關。

這樣，在一次內存索引寫SSD結束后，記錄列表數據量較大的高頻詞在SSD上獨占了一個或多個索引塊。而余下記錄列表數據量較小的低頻詞則共享了一個索引塊。因此在經過了內存索引按術語分塊后，高頻詞的索引信息基本上都位于被獨占的索引塊中。在需要合并某高頻詞的索引時，就可以直接對其獨占的索引塊進行操作，使得合并的開銷與整體的索引規模無關而只于該術語的索引量有關。

3.3 索引塊部分合并

在內存索引分塊寫入SSD的過程中，如果某個高頻詞獨占的索引塊達到了一定數量，便會觸發索引合并，這里我們采用了二路對數合并策略［11］對其進行管理。而對于共享索引塊則不會進行任何合并操作。這一點與傳統的基于合并更新的索引策略不同，在傳統策略中，索引合并是針對全體索引文件的，所有的術語都有可能參加索引合并。而在本文的索引管理策略中，只有被高頻詞獨占的索引塊才能參與合并。以下是基于分塊的部分合并策略的完整步驟:

輸入:已達到容量上限待寫入SSD的內存索引

輸出:經過更新的SSD索引

begin

創建列表termList

將內存索引中的術語按記錄列表的數據量從大到小的順序寫入termList

T=termList中第一個術語

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

為T創建一個索引塊Bt并將其全部記錄列表寫入

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

其中值得強調的就是限額采伐以及科學經營，這是國內相關法律規定的重要制度，同時也是對森林資源進行控制的關鍵性措施。在以往的多年以來國內的森林資源已經是得到了嚴格的控制，整體上呈現出非常好的態勢，但是國內依舊是在林木資源上比較缺乏的，這方面的管理還是需要進一步強化。

對T獨占的索引塊進行二路對數合并

}

T=termList中下一個術語

}

創建一個索引塊Bshare

寫入T的記錄列表

while(true){

T=termList中下一個術語

向Bshare寫入T的記錄列表

break

}

end

需要強調的是，某個術語能否獨占一個索引塊來存儲其記錄列表在每次內存索引寫SSD時都要進行判斷。這是考慮到術語在文檔集中可能并不是均勻分布的，很可能只是在某一部分頻繁出現。就像某個熱點問題只會在某一段時間被集中關注。因此，只需要合并其頻繁出現的部分的索引，保證檢索效率。

4 實驗結果與分析

本節對我們提出的基于分塊的部分合并索引策略進行了實驗評測，指標包括索引與檢索性能以及寫入SSD的數據量，并引入了幾何分區合并策略以及不合并策略作為參照。幾何分區合并是一種常用的具有較高性能的在線索引管理方法，不合并策略不進行任何合并，因此具有最快的索引構建速度，寫操作數據量也與有效索引數據量相同。實驗的硬件環境與第2節中所介紹的相同，但增加了文檔數量，達到了400萬篇。內存索引的大小為100MB左右，參數Bp的值為1MB。

每一次SSD索引更新結束后，便對上述指標進行一次統計，其中一次檢索操作由讀取10000個檢索詞的全部記錄列表信息組成，這些檢索詞來自AOL從真實環境中收集的檢索記錄［12］。圖4、圖5分別給出了索引與檢索性能的實驗結果。其中橫坐標表示內存索引寫SSD的次數。縱坐標表示的分別是這次內存索引寫SSD結束后索引構建操作的總用時以及此時進行一次檢索所耗費的時間。在索引構建性能方面，如圖4所示，基于分塊的部分合并策略索引構建的用時與不合并策略相比僅僅是其1.6倍，而常用的幾何分區合并策略的用間達到了不合并策略的4.3倍。這主要是因為我們大幅減少了索引合并的數量，避免了頻繁進行合并更新的巨大開銷。在檢索性能方面，從圖5中可以看到完成一次檢索新方法的用時大概只有幾何分區策略的60.4%，其原因在于我們對訪問頻繁的高頻詞采用了更積極的合并策略，因而增強了其存儲的連續性。雖然對于低頻詞索引存儲的連續性減弱了，但由于單個低頻詞索引數據量較小，SSD優異的隨機讀性能依然保證了其讀取效率。而且低頻詞由于被命中次數少，因此總的來說對檢索速度的影響也很小。

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

圖7 參數Bp的取值對檢索性能的影響

5 結束語

本文首先通過實驗分析了現有在線索全文引管理策略在SSD環境下的不足之處，并以此為基礎提出了一種針對SSD的全文索引管理策略:基于分塊的部分合并策略。該方法沿用了通過合并操作更新SSD索引的思想，在索引構建過程中對內存索引按術語分塊并對劃分的索引塊進行部分合并，充分利用了SSD高效隨機讀的特性減少了意義不大的合并操作。實驗結果表明，新策略不僅具有優越的索引構建與檢索性能，而且顯著降低了對SSD的損耗，與傳統策略相比能夠更好地適應SSD的環境。下一步的工作是嘗試引入參數Bp的動態適應機制，提高該策略對不同硬件環境和數據集的適應性。

［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全文檢索引擎的應用研究與實現［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).［鄭文靜，李明強，舒繼武.Flash存儲技術 ［J］.計算機研究與發展，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.