Lucene倒排索引簡述 細說倒排索引構建

文章目錄

一、數據結構

1. ByteBlockPool

1.1 Buffer結構

1.2 Slice鏈表

2. BytesRefHash

3. PostingsArrays

二、構建索引過程

在《Lucene倒排索引簡述 之索引表》和《Lucene倒排索引簡述 之倒排表》兩篇文章中介紹了Lucene如何將倒排索引結構寫入索引文件，如何為實現高效搜索過程奠定了基礎。

Lucene需要收集每個Term在整個Segment的所有信息（DocID/TermFreq/Position/Offset/Payload），從而實現下圖所示倒排索引結構構建且存儲。所以問題的關鍵在於Lucene採用了些數據結構和手段實現高效的收集任務，完成索引時性能要求的呢？

前面的文章中介紹過Lucene的倒排索引有兩種格式，一種是用於搜索的Postings，在源碼中由FreqProxTermsWriterPerField負責；另一種是TermsVectors，由TermsVectorsWriterPerField實現。這兩種索引的收集過程基本相同，只是寫文件時有各自的編排方式上有所差異。更多的內容請閱讀《Lucene倒排索引簡述 番外篇》。這裡我們以第一種方式為例，來探索Lucene索引的高效之道。

假設直接利用文件系統來完成這種任務，那麼就是每個Term都有一個獨立的文件，文件名就是TermID，用一個List來存儲文件句柄。這種做法也是可以的完成我們的需求，但這種方式存在非常大的問題。因為它會帶大量的磁碟的隨機寫，磁碟本身的性能比較差，所以它可能還會加劇系統的IO問題。

Lucene利用這種思想在內存上設計一系列的結構以實現高性能，能夠避免大量對象的頻繁創建與銷毀帶來的性能開銷和可能引發GC問題的實現方案。本文將從這個角度開始來探究倒排索引構建過程中使用的各個數據結構。

一、數據結構

設計合適的數據結構對影響提升至關，在特定的場景使用的合適的結構是成功的基石，進而考慮演算法問題。演算法通常是特定結構下討論的話題，Lucene採用哪些數據結構奠定了構建索引的性能呢？

1. ByteBlockPool

ByteBlockPool是Lucene實現高效的可變長的基本類型數組，但實際上數組一旦初始化之後是長度是固定的，因為數組申請的內存必須是連續分配的，以致能夠提供隨機訪問的能力。那麼ByteBlockPool採用什麼手段來解決這樣的問題？

1.1 Buffer結構

在所有JDK中以數組為底層存儲的數據結構，如ArrayList/HashMap，實現可增長時都需要花一定代價的。數組增長的過程分兩步，首先申請更大數組，然後將原數組複製到新數組上。即使JVM已經對數組拷貝做了很多優化，如今拷貝的性能開銷已經很小了。但是在大量的索引時使得存儲在數組上的數據不斷增長，拷貝的性能開銷會慢慢突顯出現，同時數組頻繁創建也都會帶來JVM的GC問題。

ByteBlockPool是一個增長的數據結構，它實現可增長的秘密是利用二維數據的特性，二維數組是在一維數組上引用另一維數組，即是數組中的數組。 如果把它看成是List<byte[]>的形式，在List中每個元素存儲放的是int[]的引用，將它可視化之後如下圖：

當在我們聲明二維數組的時候，如果只指定第一維組的長度時，這方式申請的二維數組，兩維數組在Heap上不會連續分配。

如此說來，我們將的二維數組的每一行稱為Buffer，列叫為Buffer索引。放回到List<byte[]>理解這個結構，List存儲的是byte[]引用，那相當於是byte[]的索引。這裡我們稱byte[]為Buffer，List即是Buffer的索引。Buffer的長度是固定，當Buffer被寫滿了之後，需要僅繼續申請一個Buffer，省去常規的數組增長之後數據拷貝的過程。

1.2 Slice鏈表

到這裡Lucene僅僅完成了存儲大量數據的問題，索引構建過程還需要為每個Term都需要一塊相對獨立的空間來存儲Posting信息。但在收集過程，Term會出現在幾個文檔中，每個文檔出現次數和位置都無法確定，所以Lucene無法預Term需要多大的數組來存儲Posting信息。

為此Lucene在ByteBlockPool之上設計了可變長的邏輯結構，這結構就是Slice鏈表。它是由Slice為節點的鏈表，Lucene將Slice分成十級別，逐層遞增，十層之後長度恆定。Slice的最後一個位置用於存儲下個節點Offset，當最後一個Slice時存儲下個Slice的層級數。

Slice節點可以跨越多Buffer，Slice鏈表為我們提供了一個邏輯上連續的內存塊（byte[]）。它就是類似於文件系統上文件，每個Slice即是文件的數據塊，不過文件系統的數據塊的大小是固定的，而Slice的長度是分層級的。

這種設計方案好處是，Buffer會是相對比較緊湊的結構，能夠更充分利用的Buffer內存。按Zipf定律可知一個單詞出現的次數與它在頻率表裡的排名成反比，也就說可能會很多Term的頻率是很小的，同樣也有小部分Term的頻率非常大，Slice的設計也是考慮這一特點。

Slice鏈接初始化時在Buffer上分配一個比較小的Slice節點，可以看得出來Buffer上的Slice非常緊湊的數據結構，屬於ByteBlockPool的Buffer內部結構，Slice的鏈表相當於是一個文件，是一個連續且統一的結構。

ByteBlockPool與IntBlockPool設計思想完全一樣，IntBlockPool只能存儲int，ByteBlockPool存儲byte，這裡我們不再複述。Lucene僅實現這兩種數據類型，其它的類型可以通過編碼之後用ByteBlockPool存儲。

2. BytesRefHash

Lucene在構建Postings的時候，採用一種類似HashMap結構，這個類HashMap的結構便是BytesRefHash,它是BytesRefHash是一個非通用的Map實現。 它的非通用性表現在BytesRefHash存儲的鍵值對分別是Term和TermID，其次它並沒有實現Map介面，也沒有實現Map的相關操作。

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

BytesRefHash是為Postings構建過程生成並存儲Term和TermID之間的而設計的結構，如果Term已經存在，返回對應TermID；否則將Term存儲，同時生成TermID並返回。Term在存儲過程BytesRefHash將BytesRef的有效數據拷貝在ByteBlockPool上，從而實現緊湊的key的存儲。TermID是從0開始自增長的連續數值，存儲在int[]上。BytesRefHash非散列哈希表，從而TermID的存儲也是緊湊的。

因為BytesRefHash為了儘可能避免用到對象類型，所以直接採用int[]存儲TermID，實際上也就很難直接採用散列表的數據結構來解決HashCode衝突的問題。

Lucene構建倒排索引的過程分了兩步操作，構建Postings和TermVectors。它們倆過程共享一個ByteBlookPool，也就是在每個DocumentsWriter共用同一個ByteRefHash（因為BytesRefHash以ByteBlockPool都不是線程安全的，因此它們都是線程級別）。它為Postings收集過程提供去重和Term與TermID對應關係的存儲及檢索。

3. PostingsArrays

從PostingsArrays的名字上容易被誤以為是就Postings收集的存儲結構，實則並不是。在Postings構建過程中，Lucene是將各項信息寫到ByteBlockPool的Slice鏈表上。鏈表是單向鏈表，它的表頭和表尾存儲到PostingsArrays，從而快速寫入和從開頭開始遍歷。這個結構曾在《Lucene倒排索引簡述 番外篇》介紹過，可以配合起來讀。

PostingsArrays除了記錄了Slice鏈表的索引之外，它還存儲上個文檔的DocID和TermFreq，還有Term上次出現的位置和位移的情況。即是PostingsArrays由幾個int[]組成，其下標都是TermID（TermID是連續分配的整型數，所以PostingsArrays是能被緊湊的存儲的），對應的值便是記錄TermID上一次出現的各種信息了。就是說Lucene用多個int[]存儲Term的各種信息，一個int[]僅存TermID的一種信息中的一個數據。

Lucene為了能夠直接使用基本類型數據，才有PostingsArrays結構的。方便理解你可以理解成是Postings[]，每個Postings對象含有DocId,TermFreq,intStarts,lastPosition等屬性。

二、構建索引過程

在索引構過程中，Term由TextField經過TokenStream之後產生，它由一個可復用對象BytesRef表示。但在建構索引的鏈路上，Lucene更多的是用TermID來表示Term，因為TermID是連續分配的數值，也是為了適用PostingsArrays的結構特點。這是PostingsArrays工作原理的第一前提，可以用數組來存儲Term對的信息。

當Term第一次出現時，Lucene嘗試在BytesRefHash取到TermID失敗，此時Lucene將它的狀態標記新人。新出現的Term作為新生嬰兒，需要在BytesRefHash上為它分配一個身份證號（TermID）。然後在PostingsArrays登記戶籍信息了，它記錄了它的名字（BytesRef的byte[]）在哪個位置（前面提過，BytesRefHash直接把Term存儲在ByteBlockPool的，所以需要位置記下來）；然後為建立一個履歷檔案（第一Slice鏈表），記錄它將來在每個年級（DocID）的考試次數（TermFreq）。

如果地區比較有心，還會另一份為Term建那個一檔案（第二Slice鏈表）用於記錄，每個次考試的情況，如果班級（Position），座位號（Offset），以及成績（Payload）。這些數據是Term成長過程的產生的，經歷一次記一次。關於每次考試的情況，第一次考試Lucene直接把它寫入ByteBlockPool的Slice鏈表上，同時會記一會在PostingsArrays用於下次記錄計算增量。為了節省內存空間，Position/Offset第二次及以後都用VInt來記錄它的增量。

這就是為什麼PostingsArrays需要記錄lastPosition/lastOffset的原因，關於lastDocID和lastTermFreq除了因為需要算增量之外，還因為Term每次出現都累加，所以先在PostingsArrays記錄。此外則是每個信息在Slice中是沒有索引，不方便回溯和修改。

構建索引的過程，實際上就是ByteBlockPool(IntBlockPool)、BytesRefHash和PostingsArrays三者之間的協作。當它們同框之後，結構的美感體驗淋漓盡致。

這裡為了簡化流程，圖中將IntBlockPool簡化成為int[]，也就是說它也是Slice的方式實現連續的鏈表。

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

為什麼byteStart和intStart需要先指向IntBlockPool呢？ 主要是因為TermID對應可能會有兩條Slice鏈表，以TermID為索引的數組不方便存儲。通過IntBlockPool可以方便處理，僅需要IntBlockPool連續兩個位置，下一個位置用於存儲第兩個Slice鏈表。當然IntBlockPool的引入讓這個過程變得更複雜了，也體現Lucene的設計之精湛和巧妙。

將表尾是為了方便寫入數據，表頭將是了方便遍歷了。在索引提交的時候，Lucene將這兩個Slice鏈表的數據通過PostingsEnum遍歷出來，交由BlockTreeTermsWriter完成索引文件的產出。構建索引過程也就走向終點，同時新一輪的索引構建開始。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！