番外篇：Lucene索引流程與倒排索引實現

前兩篇文章主要圍繞Lucene的底層索引文件結構方面介紹了倒排索引原理：

Lucene倒排索引原理探秘(1)

Lucene倒排索引原理探秘(2)

在Lucene中，寫數據的基本單元稱之為Document，本文將介紹一個Document寫入Lucene后的索引全流程。

基礎概念

如下幾個概念，Lucene的Document中給出了明確的定義，在這里先強調一下：

1. Document(文檔)由Field(字段)構成。

2. Field是Term的集合。

3. Segment是最小的獨立索引單元，由多個Documents構成。

在每一個Segment范疇內，每一個Document都被分配了一個唯一的數字ID，稱之為DocID，同時根據每個Field的名字定一個唯一的FieldNaming，對于索引字段進到Postings之前也會被分配一個唯一的TermID。Field除了FieldNaming之外也有一個FieldNumber，與DocID和TermID一樣都是一個自增的數值。

整體流程

一個Document寫到Lucene中，大致涉及如下六大處理過程：

1. 處理需要存儲的Fields

2. 構建正向索引

3. 對Field進行分詞，構建倒排索引和TermVectors

4. 處理Points類型字段(6.0以后的版本)

5. 保存分詞字段的Norms信息

6. Flush生成Segment，完成數據持久化存儲

這并不是意味著每一個Document必然會經歷這六大過程，有一些過程是互斥的，如步驟2與3、3與4、4與5都只能二選其一，同時，每一個步驟也都可以通過配置跳過。

下面將詳細展開每一個處理所關聯的細節。

Field存儲

Field數據的存儲與否，是可選的。Lucene關于Field存儲的文件格式，與MySQL的frm文件格式類似。關于Field的處理，主要是由StoredFieldsConsumer完成。

Lucene為了保證寫入的性能，文檔一旦提交后便不可改寫，這點跟MySQL的frm文件是不一樣的。字段存儲是唯一一個按文檔存儲的文件，此外都是打破文檔的邊界按字段存儲的。

另外，因為Lucene作為搜索引擎，它讀取文檔的操作往往是以隨機訪問的方式。為此Lucene將文檔數據寫到.fdt文件的同時，還需要為DocID對應的文檔所在.tdt文件上位置構建索引，并將索引存儲到.fdx文件中，以提供快速隨機訪問的能力。

DocID是Lucene的內部ID，它被用來快速獲取Document，但使用者并不能直接獲取。需要注意區分DocID與用戶定義的有業務意義的文檔ID，它們并不是一回事。

索引構建及存儲

在Lucene中，索引可以分成兩類，正向索引和倒排索引。在索引過程中，通常需要指定在哪個Field中進行檢索的，也就是TermID在所有具有相同FieldName的Field中是唯一的。

Lucene通常為所有相同FieldName的字段分配一個PerField對象，由PerField實現所有字段級別所有操作。相同FieldName的所有Field在處理邏輯是可以認為是連續的，在這個過程中，DocID僅作為Term的屬性存在。Field是Terms的集合，因此可以認為索引階段Field就是所有同名Field的所有Terms的集合。

正向索引

正向索引記錄了DocId到FieldValue的映射關系，提供了通過DocID就能直接獲取字段值的能力。DocValuesWriter將DocIdSet與FieldValue分別存儲在類似數組的結構中，他們的存儲順序的是一致的。然后，DocValuesConsumer將FieldValues和DocIdSet一并寫到.dvd文件中。每個需要存儲DocValues的Field都有一對這樣的結構，且DocValues是按字段連續存儲在.dvd文件中。每個Field的DocIdSet和FieldValues在dvd文件中的索引信息(起始位置)，被存儲在.dvm文件中。

這實現上是一種列式存儲的結構。這種列式存儲結構，給Lucene帶來很多二次計算的可能，比如Hive On Solr/ElasticSearch，Solr的高級特性Streaming Expression等。Streaming Expression是Solr提供基于Lucene索引實現的計算框架，以及在Streaming Expression上實現SQL的能力。

存儲DocID的內存是用DocsWithFieldSet（底層實際上是BitSet），在磁盤上的組織則要復雜一些。在Lucene7.0之后，Lucene針對BitSet的稠稀性，采用不同的存儲方式：當BitSet比較稀疏時，直接存儲DocID；當BitSet稠密時，則直接存儲BitSet的Bits數據。根據數據的分布情況不同，采用適當的結構不僅可以提高空間的利用率，還能提高遍歷的效率。唯一的缺點估計就是實現起來比較復雜。當前版本DocValues還不支持分詞。

Lucene定義多種DocValues類型，每種類型的存儲方式有區別，但有一點是相同的：DocIDSet和DocValues均為分開存儲的。關于DocValues部分其實是一個大話題，這里不再過多展開。

倒排索引

與Field存儲相較而言，倒排索引的構建則要復雜很多，因為涉及到整個Segment級別的信息處理，比如Term在哪些文檔出現了，在每個文檔分別出現幾次，每次出現在什么位置等等，這些信息都是需要站到Segment這個視角上才能夠收集。

Lucene中的倒排索引實現分成兩類：一種是傳統的，按Segment構建的Postings，這是我們通常理解的倒排索引結構；另一種方式是在每個上文檔構建的TermVectors，又叫詞向量或者文檔向量。

Postings

Posting是大家所熟悉的結構：左邊是Terms列表，記錄Field中出現的所有的Terms，也是叫TermsDictionary；右邊是Postings，記錄Term所對應的所出現哪些文檔的文檔號，出現次數，位置信息等。示意圖如下：

在構建Posting過程中需要考慮如何收集Terms的位置信息和統計信息，還要考慮在大規模的數據量級下如何去重和排序。這些都是實現倒排索引需要考慮的關鍵問題，一些不合理的細節所導致的額外性能開銷，就會直接影響全局索引性能。

現在我們來看一下Lucene構建Posting的過程：在實時索引時，Postings先在內存中臨時構建。Field被分詞后變成一系列Terms的集合，而后遍歷這個Terms的集合，為每個Term分配一個ID，叫TermID。Lucene用一個類HashMap的數據結構來存儲Term與TermID的映射關系，同時實現去重的目的。分配完TermID之后，后續就可以使用TermID來表示Term。

在Postings構建過程中，會在PostingsArrays存儲上個文檔的DocID和TermFreq，還有Term上次出現的位置和位移信息。PostingsArrays由幾個int[]組成，其下標即為TermID(TermID是連續分配的整型數，所以PostingsArrays是緊湊的)，對應的值便是記錄TermID上一次出現的相關信息。就是說，Lucene用多個int[]存儲Term的各種信息，一個int[]存放TermID的一種信息。

Lucene為了能夠直接使用基本數據類型（基本類型有兩大好處：減少內存開銷和提升性能），所以才有了PostingsArrays結構。為了便于理解，PostingsArrays可以表示為Postings[]，每個Postings對象含有docFreq,intStart,lastPos等屬性。

PostingsArrays這個結構只保留每個TermID最后出現的情況，對于TermID每次出現的具體信息則需要存在其它的結構之中。它們就是IntBlockPool&ByteBlockPool，它能有效的避免Java堆中由于分配小對象而引發內存碎片化從而導致Full GC的問題，同時還解決數組長度增長所需要的數據拷貝問題，最后是不再需要申請超大且連續的內存。

限于篇幅，關于這兩個結構的細節設計將在下一篇文章中分享。這里我們暫且將其看成兩個連續的int[]和byte[]，Postings的數據實際只存儲在BytesBlockPool(byte[])一個地方，IntBlockPool(int[])中存儲的是索引。

需要注意的是，Postings是在byte[]存儲的結構是一個表尾增加的鏈表結構，在構建索引的時候用IntBlockPool來記錄Term下一次要寫的位置。也就是說，PostingsArrays的intStarts[]是Term的byte[]的表尾，而表頭是記錄在PostingsArrays的byteStart上，這也是一個int數組，記錄每個Term的在BytesBlockPool的起始位置。有了表頭和表尾之后，我們就可以ByteBlockPool里拿到整個鏈表了。

為什么不能直接寫磁盤？?這是因為在構建過程中無法知道Postings有多長，不能確定要預留多少空間；另外構建過程中Term是隨機出現的而非有序的；最后是Term難以再排序，只能按TermID的順序處理。

為什么需要postingsArrays？?因為寫到byte[]的只是增量，那么就需要找到上次的Term出現情況才能計算。如果總是在byte[]上查找則顯得過重，因為Postings存儲在byte[]時，它的結構是一個單向鏈表。有了PostingsArrays中記錄的上條信息，則便于計算增量。

這里多提一點，Lucene在Segment提交之前，實現上不是在寫Buffer，而是先在內存上構建了。當Segment提交之后，將內存上的索引重新編碼之后再刷磁盤。 也就是說，索引在構建時寫在內存的數據結構和編碼與最終寫在磁盤上的結構完全不一樣。 基于以上，且不僅限以上原因，需要先收集posting的信息。知道這點之后，至于它叫什么，是緩沖，預構建，還是收集都是一樣的。

收集完，也就是已經把整個Segment的文檔全部遍歷了，此時觸發Flush的操作。然后，將Term排序之后編排成TermEnum格式，此處進入索引寫磁盤的步驟了。

關于倒排索引更多信息，在前兩篇文章中已經詳細披露了。

TermVectors

上面已經用了比較長的篇幅來介紹Posting。接下來簡單介紹第二種結構，需要存儲的數據跟第一種實際上一樣的，都是Term和Term的統計信息、位置信息。只不過，TermVectors在Postings的基礎又將Terms按文檔做了重新排序。同一個文檔中，如果一個Field中出現了一個同名的Term出現了兩次，則會被分開記錄兩次。

回顧一下Postings中記錄的幾種信息：

TermFreq：在一個文檔中出現的次數，通過與DocID成對出現。

Position：Term出現的位置，相當于DocID。

Offset：在文檔內的位移，與Position一起才能確定一個位置。

Payload：附加信息，如詞性等，可用于自定義評分等。

這些信息也是TermVectors需要記錄的。顯然這些信息實際上與是否在文檔內并無影響，所以TermVectors記錄信息實際上Postings并無太大差別。只不過對于TermVectors是已經知道DocID的，所以并不會在所有Term上記錄DocID。當然，Freq、Position和Offset也不會記錄在其它Documnet出現的情況了。 此外還有一點需要注意的，TermVectors把Term所有信息都記錄在同一個文件上（.tvd），這與Postings的記錄方式是一樣的。Postings將它們拆分成三個文件分別存儲DocID和TermFreq、Position和Offset、Payload。

Lucene在存儲TermVectors的時候，默認將4096個文檔打包成一個chunk來存儲。在一個chuck的結構如上圖，這里想強調的是，TermFreq/Position/Offset/Payload的存儲格式基本一樣，這里以TermFreq為例。

假設有個Term="Solr"出現這三個文檔的FieldA、FieldB和FieldC三個字段中，它們TermID不一定相同，只要這三文檔不是一樣，它們極可能是不同的。因為每個文檔的每個字段都有自己的Term和TermID的映射表，這就是跟Postings最大的差異。

為什么沒有DocFreq、TotalTermFreq呢？如果已經讀過《Lucene倒排索引原理探秘(1)》，應該知道這些字段級別的統計信息，它們會被存放在TermDictionary的FieldMetaData里。也就是說，Postings和TermVectors都不會記錄部分信息的。

TermVectors在Solr中有挺多應該場景的，比如Highlight，MoreLikeThis，分類聚類等NLP任務等。

默認TermVectors是開啟的，雖然在搜索時，只要不用它就不會去讀這部分信息。但是在索引時，還是會帶來性能開銷的。不僅如此Segment Flush之后還可能會出現多次Merge，也都會帶來一定的開銷。如果在搜索時，不需要用TermVectors的情況下，可以將其省略掉。

PointValues

PointValues原本用于地理位置信息的索引和查詢，但它在多維數值或者多維數值區間索引和搜索上的表現也都非常出色。因此，PointValues已成為數值字段的默認實現。原先的數值字段(IntField/FloatField/LongField/DoubleField)已被標記為廢棄接口(@Deprecated)，且加了Legacy前綴。

Solr在`Solr7.0`開始支持PointValues，并成為數值字段的推薦使用類型。同時BackPort到`Solr6.5`版本。

PointValues采用新存儲結構: BKD-Tree(KD-Tree的變種)。KD-Tree主要應用于多維空間，范圍搜索和最近鄰搜索。BKD-Tree是基于KD-Tree實現的數據結構，它有高效的IO性能、更高磁盤利用率等優點?；贐KD-Tree實現的IntPoint（含LongPoint，FloatPoint，DoublePoint）不管是索引的性能，還是在搜索的性能都比原先的TrieField的性能更加高，索引文件也更小，尤其是搜索時占用Heap內存要小很多。

PointValues是一個非常有價值的特性，它并不只是適用于多維的空間搜索，在一維的各個場景下的性能指標也都非常不錯，強烈推薦大家關注并且使用該特性。

Norms

Norms，Normalization Factors，存儲的是每個文檔中每個字段的歸一化因子和Boost（索引時的Boost已經被棄用了，交由Payload接管）。這兩個數值都會直接影響搜索時最終文檔評分。

在TFIDFSimailary模型下，歸一化因子的計算可以簡單理解為log2(1/numTerms)。

Norms是所有索引文件中最簡單的，所以它在我腦海中的存在感極弱。Norms可以通過配置FieldType.setOmitNorms(true)，表示不存儲norms，但默認是會存儲的。這個配置是字段級別的，也就是在一個多字段的文檔中，可以選擇部分字段存儲，部分不存儲。由上公式就可以知道，Norms的計算需要知道字段中去重后有多少個Terms，所以它跟Postings也算是有一點關系的，也是放在Postings之后處理的。

總結

這篇文章講解了Lucene為一個Document構建索引的處理流程，重點講解了兩種倒排索引結構，Posting與TermVectors，希望能夠結合前面的兩篇文章來加深大家關于Lucene倒排索引結構的理解。

本文轉載自微信公眾號【Nosql漫談】。

NoSQL數據庫

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