Lucene高性能索引之道

在Lucene倒排索引原理探秘(1)和Lucene倒排索引原理探秘(2)兩篇文章中詳細介紹了Lucene的倒排索引文件組織結(jié)構(gòu)，這為高效的搜索過程奠定了良好的基礎(chǔ)。

我們已經(jīng)知道，Lucene的倒排索引有兩種格式：一種是用于搜索的Postings；另一種是TermsVectors。這兩種索引的構(gòu)建過程基本相同，只是寫文件時在編排方式上有所差異，在《番外篇：Lucene索引流程與倒排索引實現(xiàn)》一文中已經(jīng)做了詳細介紹。

在構(gòu)建倒排索引的過程中，Lucene需要收集每個Term在整個Segment中的相關(guān)信息(DocID、TermFreq、Position、Offset、Payload），并且將這些信息存儲下來，如下圖所示。因此，在索引階段，如何高效的收集這些信息，顯得至關(guān)重要，本文將以Postings索引格式為例，詳細探討Lucene索引過程中所采用的數(shù)據(jù)結(jié)構(gòu)與技術(shù)手段。

數(shù)據(jù)結(jié)構(gòu)

Lucene設(shè)計了一系列內(nèi)存高效的數(shù)據(jù)結(jié)構(gòu)，通過對象復用和內(nèi)存分頁的思想，來優(yōu)化Java GC問題。這部分內(nèi)容將圍繞ByteBlockPool、ByteRefHash、PostingsArray三個結(jié)構(gòu)展開。

ByteBlockPool

ByteBlockPool是Lucene實現(xiàn)高效的可變長的基本類型數(shù)組，但實際上數(shù)組一旦初始化之后長度是固定的，因為數(shù)組申請的內(nèi)存必須是連續(xù)分配的，以致能夠提供快速隨機訪問的能力。那么ByteBlockPool是如何實現(xiàn)的？

Buffer結(jié)構(gòu)

在JDK中，以數(shù)組為底層存儲的數(shù)據(jù)結(jié)構(gòu)，如ArrayList/HashMap，實現(xiàn)可增長時都需要花費一定的代價。數(shù)組增長的過程分兩步，首先申請更大數(shù)組，然后將原數(shù)組復制到新數(shù)組中。即使JVM已經(jīng)對數(shù)組拷貝做了很多優(yōu)化，但隨著數(shù)據(jù)量的不斷增大，拷貝的性能開銷問題也會越來越凸顯，同時，數(shù)組的頻繁創(chuàng)建也都會加大JVM的GC負擔。

ByteBlockPool是一個可動態(tài)增長的結(jié)構(gòu)，如下圖所示：

ByteBlockPool是一個由多個Buffer構(gòu)成的數(shù)組，如上圖右側(cè)所示，左側(cè)的數(shù)字則代表了每一個Buffer在這個二維數(shù)組中的Index位置。Buffer的長度是固定的，當一個Buffer被寫滿以后，需要申請一個新的Buffer，如果這個Buffer數(shù)組要擴展，僅僅是將已有Buffer的引用拷貝了一次，而不需要拷貝數(shù)據(jù)本身。Buffer本質(zhì)上是一個byte[]，因此，ByteBlockPool其實是一個byte的二維數(shù)組，用Buffer數(shù)組來表達則更易理解。

Slice鏈表

索引構(gòu)建過程需要為每個Term分配一塊相對獨立的空間來存儲Posting信息。一個Term可能會出現(xiàn)在幾個文檔中，而且在每個文檔出現(xiàn)的次數(shù)和位置都無法確定，所以Lucene無法預知Term需要多大的數(shù)組來存儲Posting信息。

為此Lucene在ByteBlockPool之上設(shè)計了可變長的邏輯結(jié)構(gòu)，這結(jié)構(gòu)就是Slice鏈表。它的節(jié)點稱之為Slice，Lucene將Slice分成十個級別，逐層遞增，十層之后長度恒定。Slice的最后一個位置用于存儲下個節(jié)點Offset，對于最后一個Slice，則存儲了下個Slice的層級數(shù)。

Slice節(jié)點可以跨越多個Buffer，Slice鏈表為我們提供了一個邏輯上連續(xù)的內(nèi)存塊。如果將Slice鏈表理解成類分布式文件系統(tǒng)上的文件，每個Slice則是文件的數(shù)據(jù)塊，不過文件系統(tǒng)的數(shù)據(jù)塊的大小是固定的，而Slice的長度則是分層級的。

這種設(shè)計方案的一個好處：Buffer是相對比較緊湊的結(jié)構(gòu)，能夠更高效的利用Buffer內(nèi)存。按Zipf定律可知一個單詞出現(xiàn)的次數(shù)與它在頻率表里的排名成反比，也就是說可能會有很多Term的頻率是很低的，同樣也有小部分Term的頻率則非常高，Slice的設(shè)計正是考慮到了這一分布特點。

ByteBlockPool與IntBlockPool設(shè)計思想完全一樣，IntBlockPool只能存儲int，ByteBlockPool存儲byte，這里我們不再贅述。Lucene僅實現(xiàn)這兩種基礎(chǔ)的數(shù)據(jù)類型，其它的類型可以通過編碼之后用ByteBlockPool來存儲。

BytesRefHash

Lucene在構(gòu)建Postings的時候，采用一種類似HashMap結(jié)構(gòu)，這個類HashMap的結(jié)構(gòu)便是BytesRefHash,它是一個非通用的Map實現(xiàn)。?它的非通用性表現(xiàn)在BytesRefHash存儲的鍵值對分別是Term和TermID，其次它并沒有實現(xiàn)Map接口，也沒有實現(xiàn)Map的相關(guān)操作。

Term在Lucene中通常會被表示為BytesRef，而BytesRef的內(nèi)部是一個byte[]，這是一個可以復用的對象。當通過TermID在BytesRefHash獲取詞元的時候，便將ByteBlockPool的byte[]拷貝到BytesRef的byte[]，同時指定有效長度。整個BytesRefHash生存周期中僅持有一個BytsRef，所以該BytesRef的byte[]長度是詞元的長度。

BytesRefHash用來存儲Term和TermID之間的映射關(guān)系，如果Term已經(jīng)存在，返回對應(yīng)TermID；否則將Term存儲并且生成TermID后返回。Term在存儲過程BytesRefHash將BytesRef的有效數(shù)據(jù)拷貝在ByteBlockPool上，從而實現(xiàn)緊湊的key值存儲。TermID是從0開始自增長的連續(xù)數(shù)值，存儲在int[]上。BytesRefHash非散列哈希表，從而TermID的存儲也是緊湊的。

因為BytesRefHash為了盡可能避免用到對象類型，所以直接采用int[]存儲TermID，實際上也就很難直接采用散列表的數(shù)據(jù)結(jié)構(gòu)來解決HashCode沖突的問題。

Lucene構(gòu)建倒排索引的過程分了兩步操作，構(gòu)建Postings和TermVectors。它們倆過程共享一個ByteBlockPool，也就是在每個DocumentsWriter共用同一個ByteRefHash（因為BytesRefHash以ByteBlockPool都不是線程安全的）。它為Postings收集過程提供去重和Term與TermID對應(yīng)關(guān)系的存儲及檢索等功能。

PostingsArrays

從PostingsArrays名字上容易被誤以為是存儲Postings數(shù)據(jù)的結(jié)構(gòu)，實則不然。在Postings構(gòu)建過程中，Lucene將各項信息寫到ByteBlockPool的Slice鏈表上。鏈表是單向鏈表，它的表頭和表尾存儲到PostingsArrays，從而能夠快速寫入，并且可以從頭開始遍歷。這個結(jié)構(gòu)曾在《番外篇：Lucene索引流程與倒排索引實現(xiàn)》一文中介紹過。

PostingsArrays除了記錄了Slice鏈表的索引之外，它還存儲上個文檔的DocID和TermFreq，還有Term上次出現(xiàn)的位置和偏移信息。PostingsArrays由幾個int[]組成，其下標都是TermID（TermID是連續(xù)分配的整數(shù)），對應(yīng)的值便是記錄TermID上一次出現(xiàn)的各種信息。

Lucene為了能夠直接使用基本類型數(shù)據(jù)，所以才有了PostingsArrays結(jié)構(gòu)。方便理解你可以理解成是Postings[]，每個Postings對象含有DocId,TermFreq,intStarts,lastPosition等屬性。

索引構(gòu)建過程

在索引構(gòu)過程中，Term由TextField經(jīng)過TokenStream處理之后產(chǎn)生，它由一個可復用對象BytesRef表示。在建構(gòu)索引的鏈路上，Lucene更多是用TermID來表示Term。

當Term第一次出現(xiàn)時，Lucene嘗試在BytesRefHash取到TermID失敗，此時Lucene將它的狀態(tài)標記"新人"。新出現(xiàn)的Term作為"新人"，需要在BytesRefHash上為它分配一個"證件號碼"（TermID）。在PostingsArrays中會登記他的"戶籍信息"，包含他的名字（BytesRef的byte[]）在哪個位置（前面提過，BytesRefHash直接把Term存儲在ByteBlockPool上，所以需要把位置記下來）；還會為他建立一個履歷檔案（第一Slice鏈表），記錄他將來在每個年級（DocID）的考試次數(shù)（TermFreq）。

在每一個"地區(qū)"，還可以為Term建立另外一份檔案（第二Slice鏈表）用于記錄每次考試的情況，比如班級（Position），座位號（Offset），以及成績（Payload）。這些數(shù)據(jù)是Term成長過程的產(chǎn)生，經(jīng)歷一次記一次。關(guān)于每次考試的情況，第一次考試Lucene直接把它寫入ByteBlockPool的Slice鏈表上，同時會記錄增量信息，為了節(jié)省內(nèi)存空間，Position/Offset第二次及以后都用VInt來記錄這個增量值。

這就是PostingsArrays需要記錄lastPosition/lastOffset的原因，而lastDocID和lastTermFreq不僅可用計算增量，還可以用來計算Term每次出現(xiàn)后TermFreq的累加值。需要說明的一點：每個信息在Slice中沒有索引，不方便回溯和修改。

構(gòu)建索引的過程是ByteBlockPool(IntBlockPool)、BytesRefHash和PostingsArrays三者之間的協(xié)作，如下圖所示：

這里為了簡化流程，圖中將IntBlockPool簡化成為int[]，也就是說它也是Slice的方式實現(xiàn)連續(xù)的鏈表。

PostingsArrays的byteStarts[TermID]記錄Term的兩個鏈表的表頭在ByteBlockPool的絕對位置，intStarts[TermID]記錄下次要寫的位置，則textStarts[TermID]則記錄BytesRefHash把Term存儲在ByteBlockPool的哪個位置上。

為什么byteStart和intStart需要先指向IntBlockPool呢？?主要是因為TermID可能對應(yīng)了兩條Slice鏈表，以TermID為索引的數(shù)組不方便存儲。通過IntBlockPool可以方便處理，僅需要IntBlockPool連續(xù)兩個位置，下一個位置用于存儲第兩個Slice鏈表。IntBlockPool的引入雖然讓這個過程變得更復雜了，但也更體現(xiàn)了Lucene的設(shè)計之精湛和巧妙。

在索引提交的時候，Lucene將這兩個Slice鏈表的數(shù)據(jù)通過PostingsEnum遍歷出來，交由BlockTreeTermsWriter完成索引文件的輸出。至此，已經(jīng)完成了一輪構(gòu)建索引的流程。

本文轉(zhuǎn)載自微信公眾號【Nosql漫談】。

NoSQL數(shù)據(jù)庫

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔相應(yīng)法律責任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實后本網(wǎng)站將在24小時內(nèi)刪除侵權(quán)內(nèi)容。