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