從lucene的文件結構看它的性能
作者：沖出宇宙（lotusroots）
時(shí)間：
注：轉載請注明作者。
Lucene是一個(gè)apache項目，完全使用java語(yǔ)言編寫(xiě)（廢話(huà)，誰(shuí)都知道apache主要是做java項目的，不過(guò)，已經(jīng)有人對Lucene進(jìn)行了遷移，比如CLucene），它提供了一個(gè)基本的索引文檔后進(jìn)行搜索的功能。目前版本是2.0，具體信息可以直接看http://lucene.apache.org/官方網(wǎng)站。同時(shí)，http://www.lucene.com.cn/about.htm提供了一個(gè)很不錯的介紹（同時(shí)介紹了CLucene項目）。
本文不打算介紹它的使用，因為它的使用實(shí)在是過(guò)于簡(jiǎn)單，而且，太多的人寫(xiě)了關(guān)于它的使用方法。本文試圖從一個(gè)更高的層次來(lái)分析一下lucene的文件結構及其性能，所以，需要讀者已經(jīng)對搜索引擎的工作原理有較深入的了解（推薦學(xué)習MIT的開(kāi)放課程中的Information Extraction）。
本文的內容主要參考了http://lucene.apache.org/java/docs/fileformats.html，這是lucene的文件結構頁(yè)面。
一 lucene文件的基本構架
lucene文件結構的最大特點(diǎn)是其結構十分緊湊。從文件開(kāi)始的第一個(gè)字節直到最后一個(gè)字節都是有效數據，中間沒(méi)有任何空閑的字節。這樣有優(yōu)點(diǎn)也有缺點(diǎn)，優(yōu)點(diǎn)是讀取迅速，缺點(diǎn)是修改復雜。因為lucene的作者說(shuō)lucene并不是為修改頻繁的應用設計的，所以，文件結構這么做是無(wú)可厚非的。在修改頻繁的環(huán)境下，lucene的性能注定會(huì )很差。如果是那樣的話(huà)，您或許需要考慮使用更好的技術(shù)，因為增加一個(gè)文檔到索引其實(shí)可以做到十分迅速。
在壓縮方面，lucene也采用了一些基本的方法。比如，它對int類(lèi)型就進(jìn)行了所謂的byte壓縮方法（最初級的方法）。不過(guò)，它在String上面采用的utf-8的編碼顯然會(huì )比utf-16編碼占用更多的空間。其它地方還能夠看到壓縮的是Field Data（域值，.fdt）文件，這個(gè)文件保存的是文檔包含的域的具體文本（一個(gè)文檔可以劃分為多個(gè)域，每個(gè)域都是一個(gè)字符串），顯然這是很大的數據（zlib好像在這里比較常用，google據說(shuō)也這樣壓縮，不過(guò)，文本壓縮的最好辦法顯然不是zip，更好的辦法還有ppmd）。
二 lucene構建索引的性能
索引，專(zhuān)業(yè)點(diǎn)說(shuō)，包含2種：前向索引和反向索引（倒排索引，inverted index）。前者表示的是某個(gè)文檔里面的所有詞語(yǔ)，后者表示的是包含某個(gè)詞語(yǔ)的所有文檔。對應到Lucene上面，它的前向索引可以認為是Term Vectors（詞語(yǔ)向量）相關(guān)文件，包含.tvx、.tvd和.tvf這3種文件。前向索引沒(méi)有什么好評論的，它一般只是做為重組原始數據時(shí)候的依據，其構建十分簡(jiǎn)單明了。反向索引對應到Lucene上就是index（索引）。Lucene把索引劃分成一個(gè)一個(gè)的segment（塊，其實(shí)是一個(gè)小索引），直觀(guān)的說(shuō)，當有一批新數據到達的時(shí)候，我們一般給其構建成一個(gè)新的segment，這是因為修改原來(lái)的segment的代價(jià)很高（并不是說(shuō)一定很高，只是lucene采用的文件結構無(wú)法簡(jiǎn)單的加入新的文檔）。當一個(gè)index包含的segment太多的時(shí)候，查找性能就很差了（因為一次查詢(xún)需要查詢(xún)多個(gè)segment），需要進(jìn)行segment的合并。
下面是index和segment的基本結構：
1. index:
index包含4類(lèi)文件：1）記錄segment信息的文件；2）指示索引是否正在更改的標記文件；3）簡(jiǎn)單組合了若干個(gè)文件的復雜文件；4）segment文件及其附屬文件。
2. segment:
segment其實(shí)是一個(gè)小型index，它包含了詞匯表、域表、反向索引表、域權重表、詞語(yǔ)向量（即前向索引）和已經(jīng)刪除文檔表。詞匯表包括了本segment里面出現的所有詞匯（記得詞匯不見(jiàn)得是真的詞語(yǔ)，它其實(shí)就是索引的字符串）。
三 lucene修改和刪除索引的性能
嚴格的說(shuō)，lucene底層并不支持對某個(gè)文檔的修改。因為它的緊密結構抗拒了對文檔的直接修改。當需要修改某些文檔的時(shí)候，可以是這樣的：
1. 刪除這些文檔。這樣會(huì )使得這些文檔ID加入到已經(jīng)刪除的文檔表里面。
2. 構建新的索引。這樣會(huì )生成一個(gè)新的segment。
3. 合并索引的所有segment。這樣會(huì )把所有的segment都合并到一起，構成唯一的一個(gè)segment。
大家可以看到，如果僅僅從以上3步來(lái)看，lucene的修改索引的性能極差。好在可以利用緩沖，分批的懶惰的進(jìn)行上面的第2步和第3步。
四 lucene的查詢(xún)性能
我們從幾個(gè)方面來(lái)分析它的查詢(xún)性能：
1. 文件個(gè)數。文件個(gè)數越多，查詢(xún)的時(shí)候需要訪(fǎng)問(wèn)的文件就越多，從而開(kāi)銷(xiāo)也會(huì )越大。這是因為要讀取的類(lèi)似數據處在不連續的位置。當你把所有segment都合并成一個(gè)之后，這種問(wèn)題就不存在了?？墒?，合并segment的花銷(xiāo)很大，需要謹慎考慮。
2. 索引詞匯。lucene的詞匯其實(shí)并不是簡(jiǎn)單的詞匯，而是“域+詞匯”的保存形式。當域比較多的時(shí)候，這種方式的索引詞匯構建方式顯然會(huì )大大降低查找的效率。不過(guò)，值得一提的是，為了降低空間占用，lucene在排序詞匯之后，按照如下的形式進(jìn)行保存： <PrefixLength, Suffix, FieldNum>，這里，PrefixLength表示本詞匯借用了前面一個(gè)詞匯的前面PrefixLength個(gè)字符，Suffix表示本詞匯余下的字符串，FieldNum表示本字符串屬于的域。
3. 布爾表達式計算。布爾表達式查找的時(shí)候，涉及到幾條詞匯倒排索引的合并的問(wèn)題。未壓縮的索引合并是一個(gè)十分容易（不過(guò)，算法需要很精細才能優(yōu)化各種情況）的事情，可是，lucene的索引經(jīng)過(guò)壓縮了（包括前面提到的和相鄰數據相減的壓縮方法）以及String長(cháng)度的不確定性，所以，我們無(wú)法根據詞匯直接定位到它對應的TermInfo（做為一個(gè)變型，你可以在內存中為它做個(gè)索引）。于是lucene就使用了SkipInterval/SkipData（樁，即定位標記）這類(lèi)結構來(lái)加快比較速度，通過(guò)和它們的比較，可以簡(jiǎn)單的跳過(guò)多個(gè)字節，從而加快了查找速度。當然了，這種策略比起直接的排序后2分查找顯然是慢了許多。
4. 權重計算。權重的計算顯然和文件結構沒(méi)有太大關(guān)系。但是，已知的是，lucene保存了每個(gè)詞匯的出現頻率和每個(gè)域的權重值，這樣就可以通過(guò)一些簡(jiǎn)單的公式計算滿(mǎn)足要求的文檔對本次查詢(xún)的匹配度了。
五 Nutch對lucene的改進(jìn)
Nutch據說(shuō)還是lucene的作者寫(xiě)的，不過(guò)，這次這個(gè)高手打算直接和商業(yè)搜索引擎進(jìn)行抗衡，他引入了分布式的構架。Nutch一開(kāi)始就是分布式的，它本來(lái)就是定位在百以上量級的集群系統（或者網(wǎng)格）上的。對于搜索引擎來(lái)說(shuō)，除了抓?。ɑ蛘哌€包含一些前期的數據處理）外，其余的工作都是信息保存、索引構建和索引查找。Nutch使用的分布式構架，它利用了多臺機器的性能來(lái)同時(shí)構建索引（這一點(diǎn)的可行性在講MapReduce的google論文里面已經(jīng)做了詳細的描述），這顯然能夠提高做索引的速度。在索引查找上面，因為索引查找顯然不同于做索引，它要求極高的速度和不高的精度。簡(jiǎn)單的基于MapReduce的方法的最大缺點(diǎn)就是速度慢（因為它簡(jiǎn)單嘛），所以，這位高手強烈建議不要使用分布式的查找方法，因為速度比單機查找還要慢很多（考慮一下，對于google來(lái)說(shuō)，它的數據量據說(shuō)達到上百個(gè)T，即10萬(wàn)G，沒(méi)有機器可以?huà)焐线@么大的硬盤(pán)吧？所以，他們肯定是分布式查詢(xún)的）?？梢钥隙ǖ氖?，Nutch在搜索方面對lucene的改進(jìn)就是分布式的做索引。當然了，Nutch比lucene好的地方在于它有了抓取程序（雖然十分的原始）。
后記
大家都在熱捧這些開(kāi)源軟件，但是，我提醒大家一下：它們距離真正的商業(yè)應用還是有一定差距的?；蛟S你會(huì )說(shuō)Nutch不是很好么？它的作者都加入yahoo了?？墒?，你想過(guò)沒(méi)有？yahoo本來(lái)就是做搜索的，它根本就不需要那么簡(jiǎn)單的技術(shù)，它可能基于其它方面的考慮，比如影響度或者創(chuàng )新度。雖然開(kāi)源軟件速度比較慢，但是，你可以通過(guò)十分優(yōu)秀的緩沖算法來(lái)彌補它的不足。簡(jiǎn)單的說(shuō)，緩沖才是一個(gè)追求速度的搜索引擎最需要關(guān)心的地方。作者在有空的時(shí)候將專(zhuān)門(mén)撰文討論搜索引擎的緩沖處理。
這么多年以來(lái)，搜索引擎的構架幾乎沒(méi)有發(fā)生任何改變（google使用的構架可以在15年前看到同樣的），所以，想在這個(gè)方面有所突破幾乎不可能了?，F在人們的研究熱點(diǎn)都集中在信息抓?。ǔ槿?，獲?。┖托畔⑻幚砩?。這些方面的技術(shù)還很不成熟，也是能夠出現突破的地方。
聯(lián)系客服
