Lucene之倒排索引簡述(1)
前言
在全文檢索領域, Lucene可謂是獨領風騷數十年。倒排索引構成全文檢索的根基,只有深入理解了倒排索引的實現原理,才能算是入門了全文檢索領域。本文將對Lucene的倒排索引的實現原理和技術細節進行詳細的剖析,這些內容適用於Lucene 5.x至7.x系列版本。文章整體內容組織如下:
- 倒排索引理論
- Lucene倒排索引實現
- Lucene索引檔案構成
- 什麼是Terms Index?
- 什麼是Terms Dictionary?
- 結束語
理論
在學術上,倒排索引結構非常簡明易懂,如下:
也許你已接觸過倒排索引,下面這張圖你或許已經看過很多次了。本文將從你熟悉的部分開始,一步步深入去挖掘這張圖的一個個細節。這裡先介紹兩個重要概念:
-
索引,索引詞表。倒排索引並不需要掃描整個文件集,而是對文件進行預處理,識別出文檔集中每個詞。
-
倒排表,倒排表中的每一個條目也可以包含詞在文件中的位置資訊(如詞位置、句子、段落),這樣的結構有利於實現鄰近搜尋。詞頻和權重資訊,用於文件的相關性計算。
倒排索引由兩部分組成,所有獨立的詞列表稱為索引,詞對應的一系列表統稱為倒排表。 —— 來自《資訊檢索》
如圖,整個倒排索引分兩部分,左邊是Term Dictionary(索引表,可簡稱為Dictionary),是由一系列的Terms組成的;右邊為Postings List(倒排表),由所有的Term對應的Postings組成。
實際上Lucene所用的資訊資訊檢索方面的術語基本跟 Information Retrieval (《資訊檢索》原版)保持一致。比如Term、Dictionary、Postings等。
首先,有必要解釋一下,每個Segment中的每個欄位(Field)都有這麼一個獨立的結構。其次,它是不可改寫的,即不能新增或更改。至於為何選擇不可改寫的設計,簡單說有兩個方面:一是更新對磁碟來說不夠友好;另一方面是寫效能的影響,可能會引發各種併發問題。
我們可以用一個HashMap來簡單描述這個結構: Map<String, List<Integer>>,
這個Map的Key的即是 Term ,那它的Value即是 Postings 。所以它的Key的集合即是 Dictionary 了,這與上圖的描述太貼切了。由於HashMap的Key查詢還是用了HashTable,所以它還解決Dictionary的快速查詢的問題,一切顯得太美好了。這可以說是一個 hello world
版 的倒排索引實現了。
Lucene的實現
全文搜尋引擎通常是需要儲存大量的文字,Postings可能會佔據大量的儲存空間,同樣Dictionary也可能是非常大的,因此上面說的基於HashMap的實現方式幾乎是不可行的。在海量資料背景下,倒排索引的實現都極其複雜,因為它直接關係到儲存成本以及搜尋效能。為此,Lucene引入了多種巧妙的資料結構和演算法。
Lucene索引檔案構成
我們知道Lucene將索引檔案拆分為了多個檔案,這裡我們僅討論倒排索引部分。Lucene把用於儲存Term的索引檔案叫Terms Index,它的字尾是 .tip
;把Postings資訊分別儲存在 .doc
、 .pay
、 .pox
,分別記錄Postings的DocId資訊和Term的詞頻、Payload資訊、pox是記錄位置資訊。Terms Dictionary的檔案字尾稱為 .tim
,它是Term與Postings的關係紐帶,儲存了Term和其對應的Postings檔案指標。
總體來說,通過Terms Index(.tip)能夠快速地在Terms Dictionary(.tim)中找到你的想要的Term,以及它對應的Postings檔案指標與Term在Segment作用域上的統計資訊。
postings: 實際上Postings包含的東西並不僅僅是DocIDs(我們通常把這一個有序文件編號系列叫DocIDs),它還包括文件編號、以及詞頻、Term在文件中的位置資訊、還有Payload資料。
所以關於倒排索引至少涉及5類檔案,本文不會全面展開。
什麼是Terms Index
下面引用了一張來自網路上的圖,非常直觀:
Terms Index即為上圖中.tip部分,它實際上是由一個或多個 FST
組成的,Segment上每個欄位都有自己的一個FST(FSTIndex)記錄在 .tip
上,所以圖中FSTIndex的個數即是Segment擁有欄位的個數。另外圖中為了方便我們理解把FST畫成Trie結構,然後其葉子節點又指向了tim的Block的,這實際上是用了一種叫Burst-Trie的資料結構。
Burst-Trie
.tip
看起來是像一棵Trie,所以整張圖表現出來就是論文上的Burst-Trie結構了。上面一棵Trie,Trie的葉子節點是Container(即是Lucene中的Block)。下圖就是Paper上描述的Burst-Trie的結構:
來自Burst-Trie論文上的一張圖
Burst-Trie
,關於Burst-Trie,網上有很多專業資料,這裡只做簡單介紹。Burst-Trie可以認為是Trie的一種變種,它主要是將字尾進行了壓縮,降低了Trie的高度,從而獲取更好查詢效能。
Lucene工程上的實現方式
Burst-Trie在Lucene是如何應用的?
前面提到了Lucene是採用 Burst-Trie
的思想,但在實現上存在一定的出入,Lucene的Burst-Trie被拆成兩部分。如果一定把它們對應起來的話,我認為Burst-Trie的AccessTree的實現是FST,存在.tip檔案中;Container的實現是Block,存在.tim檔案裡。Burst-Trie的Container內部是開放性結構,可能是Binary-Tree,可以也List。Lucene的block是陣列,準確的說,就是把一系列的Block系列化寫到檔案上,這裡好像並沒有做特殊的處理。
FST
在Lucene, Terms Dictionary
被儲存在.tim檔案上。當一個Segment的文件數量越來越多的時候Dictionary的詞彙也會越來越多,那查詢效率必然也會逐漸變低。因此需要一個很好的資料結構為Dictionary建構一個索引,將Dictionary的索引進一步壓縮,這就是後來的Terms Index(.tii)。這是在早期的版本中使用的,到Lucene 4.0之後做一次重構和升級,同時改名為.tip。
FST:Finite-State-Transducer,結構上是 圖 。我們知道把一堆字串放一堆,把它們的同共字首進行壓縮就會變成Burst-Trie。如果把字尾變成一個一個節點,那麼它就是Trie結構了。如果將字尾也進行壓縮的話,那你就能發現他更變成一張圖結構了。 那麼我們易知FST是壓縮字典樹字尾的圖結構,她擁有Trie高效搜尋能力,同時還非常小。這樣的話我們的搜尋時,能把整個FST載入到記憶體。
實際上, FST的結構非常複雜,我們可以簡單的將其理解為一個高效的K-V結構,而且空間佔用率更高 。這裡想簡單強調一下: Lucene到底在FST裡存了什麼資料? 如果你已經瞭解FST在Lucene中充當的角色和作用的話,我想你可能會誤認為FST中存了Dictionary中所有的Terms資料,這樣可以通過FST是找到具體的Term的位置,或者通過FST可以切實獲知一個Term是否存在。
然而,事實並非如此。 FST即不能知道某個Term在Dictionary(.tim)檔案上具體的位置,也不能僅通過FST就能確切的知道Term是否真實存在。它只能告訴你,查詢的Term可能在這些Blocks上,到底存不存在FST並不能給出確切的答案, 因為FST是通過Dictionary的每個Block的字首構成,所以通過FST只可以直接找到這個Block在.tim檔案上具體的File Pointer ,並無法直接找到Terms。關於FST的詳細細節,後面將以一篇獨立的文章來講解,這裡暫時不展開過多細節。
下面會詳細的介紹Dictionary的檔案結構,這裡先提一下。每個Block都有字首的,Block的每個Term實際不記錄共同字首的。只有通過Block的共同的字首,這是整個Block的每個Term共同的,所以每個Term僅需要記錄字尾可以通過計算得到,這可以減少在Block內查詢Term時的字串比較的長度。
簡單理解的話,你可以把它當成一個高階的BloomFilter,我們BloomFilter是有一定的錯誤率的;同時BloomFilter是通過HashCode實現的,只能用它來測試是否存在,並無法快速定位。在FST中,並無錯誤率且能快速定位。但是BloomFilter有更高的效能。
說了這麼一大半天, Terms Index到底帶來哪些實質性的功能呢? Terms Index是Dictionary的索引,它採用 了FST結構。上面已經提及了,FST提供兩個基本功能分別是:
-
快速試錯,即是在FST上找不到可以直接跳出不需要遍歷整個Dictionary。類似於BloomFilter的作用。
-
快速定位Block的位置,通過FST是可以直接計算出Block的在檔案中位置(offset,FP)。
上面已經介紹了FST的一種功能,此外,FST還有別的功能,因為FST也是一個Automation(自動狀態機)。這是正則表示式的一種實現方式,所以FST能提供正則表示式的能力。 通過FST能夠極大的提高近似查詢的效能 ,包括萬用字元查詢、SpanQuery、PrefixQuery等,甚至包括近期社群正在做的基於正則表示式的查詢。
什麼是Terms Dictionary?
前面我們已經介紹了 Terms Dictionary
的索引, Terms Index
。已經頻頻提到的Terms Dictionary到底是什麼東東?Terms Dictionary是Segment的字典, 索引表
。它能夠讓你知道你的查詢的這個Term的統計資訊,如 tf-idf
中 df(doc_freq)
和 Total Term Frequence
(Term在整個Segment出現頻率);還能讓你知道Postings的元資料,這裡是指Term的docids、tf以及offset等資訊在Postings各個檔案的檔案指標FP。
Block並不記錄這個Block的起始和結束的範圍,所以當FST最終指向多個Block時,就會退化為線性搜尋。那什麼時候會出現FST最終指向多個Block呢?最簡單的一種情況是,超過48個的Term,且出現首字母相同的term的個數不超過25個。這種情況下由於沒有每個Block都沒有共同字首,所以構建出來的FST只有一個結束節點記錄每個Block的檔案定址的偏移增量。
Lucene規定, 每個Block的大小在25-48範圍內 。
說這麼多,還是覺得太抽象了,我們來看一下 .tim
檔案結構示意圖:
主要是大兩部分資訊,1. Block資訊,包含所有Term的詳情;2. Field的自有屬性和統計資訊。接下來我們將展開來介紹這兩部分內容。
Block資訊 — NodeBlock
在整個.tim檔案上,我覺得比較複雜且值得拎出來講的只有NodeBlock。那麼,Block又是什麼東東?它是如何被構建的?這部分程式碼,還是比較晦澀難懂得,我每次讀時也都會產生一些新的疑問。
我們前面所有說的Block即是NodeBlock的一個Entry 。 由上圖可以知道,Block中有兩種OuterNode和InnerNode。這裡我想引用程式碼上兩個類名來輔助我們接下來的剖析:PendingTerm/PendingBlock,我們暫且把它們叫作 待寫的Term
和 子Block的指標
吧。
NodeBlock從構建邏輯上來講是它是樹型結構,所以它由葉子節點和非葉子節點兩種節點組成。葉子節點就叫OutterNode,非葉子節點就叫InnerNode。一個Block可能含有一堆的Term(PendingTerm)和PendingBlock(當它是非葉子節點時),實際上PendingBlock也是不可能出現在葉子節點上的。如果是PendingBlock,那麼這個Entry只記錄兩個資訊:字尾(這個Block的共同字尾)以及子Block的檔案指標,此時就不必再記上所說的統計資訊和postings資訊了。
如圖所示,一個Block記錄的資訊非常多,首先是Block的型別和Entry的條數等元資料資訊,而後是該Block擁有的所有Entry。
這裡每個Entry含有後綴、統計資訊(對應為前面據說的權重,它含有ttf和df)、Postings的位置資訊(這就是反覆提及postings相關的檔案指標,postings是拆分多檔案儲存的)。 關於Postings更多細節,放到下個章節來討論。
Field資訊 — FieldMetadata
相對來說 FieldMetadata
組織結構就簡單多了,純粹的線性寫入即可。但Field資訊記錄的內容還是挺多的,包括欄位本身的屬性,如欄位編號、Terms的個數、最大和最小的Terms;此外還記錄了Segment級別的一些統計資訊,包括tdf、擁有該欄位的文件總數(如果文件沒有該欄位,或者該欄位為空就不計了)。
-
RootCode實際上指向該欄位第一個Block的檔案指標。
-
LongsSize這個名字有點隱晦,它是說該欄位的欄位儲存哪些Postings資訊。因為我們是可以指定Postings儲存或者不儲存諸如位置資訊和Payload資訊的,存與不存將被表現在這裡了。
從搜尋流程來看,Lucene先讀到FieldMetadata的資訊,然後判斷Query上Terms是否落在這裡欄位的MinTerm和MaxTerm之間。如果不在的話,完全不需要去讀NodeBlock的。MinTerm和MaxTerm可以有效的避免讀取不必要的.tip檔案。
結束語
到這裡,關於倒排索引結構中第一部分內容已經介紹完了,限於篇幅的原因,還有更多有趣的小細節沒有呈現出來。簡單總結一下:我們先從 Information Retrieve 開始瞭解學術上倒排索引結構,接著我們又對Luecne的實現做了深入剖析。Lucene對索引詞表也做了索引(叫Terms Index,檔案字尾是.tip),索引詞表的索引採用Finite-State Transducer這種資料結構。由於這種結構佔用空間極小,所以它完成可以被載入到記憶體加速Terms Dictionary的查詢過程。而後又介紹了Terms Dictionary,Terms Dictionary以Terms Index共同構成與Burst-Trie類似的資料結構,Terms Dictionary含兩部分資訊:1. NodeBlock記錄Dictionary的所有Terms;2. FieldMetadata儲存了FieldInfos資訊和Segment的統計資訊。
關於倒排索引還有Postings List,這部分內容將在下篇文章中介紹。