elasticsearch 倒排索引原理

網上看到的一篇文章，對Lucene的倒排索引是如何執行的，說的比較易懂，就轉過來分享下。

Elasticsearch是通過Lucene的倒排索引技術實現比關係型資料庫更快的過濾。特別是它對多條件的過濾支持非常好，比如年齡在18和30之間，性別為女性這樣的組合查詢。倒排索引很多地方都有介紹，但是其比關係型資料庫的b-tree索引快在哪裡？到底為什麼快呢？

籠統的來說，b-tree索引是為寫入優化的索引結構。當我們不需要支持快速的更新的時候，可以用預先排序等方式換取更小的存儲空間，更快的檢索速度等好處，其代價就是更新慢。要進一步深入的化，還是要看一下Lucene的倒排索引是怎麼構成的。

這裡有好幾個概念。我們來看一個實際的例子，假設有如下的數據：

這裡每一行是一個document。每個document都有一個docid。那麼給這些document建立的倒排索引就是：

可以看到，倒排索引是per field的，一個欄位由一個自己的倒排索引。18,20這些叫做 term，而[1,3]就是posting list。Posting list就是一個int的數組，存儲了所有符合某個term的文檔id。那麼什麼是term dictionary 和 term index？

假設我們有很多個term，比如：

Carla,Sara,Elin,Ada,Patty,Kate,Selena

如果按照這樣的順序排列，找出某個特定的term一定很慢，因為term沒有排序，需要全部過濾一遍才能找出特定的term。排序之後就變成了：

Ada,Carla,Elin,Kate,Patty,Sara,Selena

這樣我們可以用二分查找的方式，比全遍歷更快地找出目標的term。這個就是 term dictionary。有了term dictionary之後，可以用 logN 次磁碟查找得到目標。但是磁碟的隨機讀操作仍然是非常昂貴的（一次random access大概需要10ms的時間）。所以盡量少的讀磁碟，有必要把一些數據緩存到內存里。但是整個term dictionary本身又太大了，無法完整地放到內存里。於是就有了term index。term index有點像一本字典的大的章節表。比如：

A開頭的term ……………. Xxx頁

C開頭的term ……………. Xxx頁

E開頭的term ……………. Xxx頁

如果所有的term都是英文字元的話，可能這個term index就真的是26個英文字元表構成的了。但是實際的情況是，term未必都是英文字元，term可以是任意的byte數組。而且26個英文字元也未必是每一個字元都有均等的term，比如x字元開頭的term可能一個都沒有，而s開頭的term又特別多。實際的term index是一棵trie 樹：

例子是一個包含 "A", "to", "tea", "ted", "ten", "i", "in", 和 "inn" 的 trie 樹。這棵樹不會包含所有的term，它包含的是term的一些前綴。通過term index可以快速地定位到term dictionary的某個offset，然後從這個位置再往後順序查找。再加上一些壓縮技術（搜索 Lucene Finite State Transducers） term index 的尺寸可以只有所有term的尺寸的幾十分之一，使得用內存緩存整個term index變成可能。整體上來說就是這樣的效果。

現在我們可以回答「為什麼Elasticsearch/Lucene檢索可以比mysql快了。Mysql只有term dictionary這一層，是以b-tree排序的方式存儲在磁碟上的。檢索一個term需要若干次的random access的磁碟操作。而Lucene在term dictionary的基礎上添加了term index來加速檢索，term index以樹的形式緩存在內存中。從term index查到對應的term dictionary的block位置之後，再去磁碟上找term，大大減少了磁碟的random access次數。

額外值得一提的兩點是：term index在內存中是以FST（finite state transducers）的形式保存的，其特點是非常節省內存。Term dictionary在磁碟上是以分block的方式保存的，一個block內部利用公共前綴壓縮，比如都是Ab開頭的單詞就可以把Ab省去。這樣term dictionary可以比b-tree更節約磁碟空間。

如何聯合索引查詢？

所以給定查詢過濾條件 age=18 的過程就是先從term index找到18在term dictionary的大概位置，然後再從term dictionary里精確地找到18這個term，然後得到一個posting list或者一個指向posting list位置的指針。然後再查詢 gender=女 的過程也是類似的。最後得出 age=18 AND gender=女 就是把兩個 posting list 做一個「與」的合併。

這個理論上的「與」合併的操作可不容易。對於mysql來說，如果你給age和gender兩個欄位都建立了索引，查詢的時候只會選擇其中最selective的來用，然後另外一個條件是在遍歷行的過程中在內存中計算之後過濾掉。那麼要如何才能聯合使用兩個索引呢？有兩種辦法：

• 使用skip list數據結構。同時遍歷gender和age的posting list，互相skip；
• 使用bitset數據結構，對gender和age兩個filter分別求出bitset，對兩個bitset做AN操作。

PostgreSQL 從 8.4 版本開始支持通過bitmap聯合使用兩個索引，就是利用了bitset數據結構來做到的。當然一些商業的關係型資料庫也支持類似的聯合索引的功能。Elasticsearch支持以上兩種的聯合索引方式，如果查詢的filter緩存到了內存中（以bitset的形式），那麼合併就是兩個bitset的AND。如果查詢的filter沒有緩存，那麼就用skip list的方式去遍歷兩個on disk的posting list。

利用 Skip List 合併

以上是三個posting list。我們現在需要把它們用AND的關係合併，得出posting list的交集。首先選擇最短的posting list，然後從小到大遍歷。遍歷的過程可以跳過一些元素，比如我們遍歷到綠色的13的時候，就可以跳過藍色的3了，因為3比13要小。

整個過程如下

Next -> 2Advance(2) -> 13Advance(13) -> 13Already on 13Advance(13) -> 13 MATCH!!!Next -> 17Advance(17) -> 22Advance(22) -> 98Advance(98) -> 98Advance(98) -> 98 MATCH!!!

最後得出的交集是[13,98]，所需的時間比完整遍歷三個posting list要快得多。但是前提是每個list需要指出Advance這個操作，快速移動指向的位置。什麼樣的list可以這樣Advance往前做蛙跳？skip list：

從概念上來說，對於一個很長的posting list，比如：

[1,3,13,101,105,108,255,256,257]

我們可以把這個list分成三個block：

[1,3,13] [101,105,108] [255,256,257]

然後可以構建出skip list的第二層：

[1,101,255]

1,101,255分別指向自己對應的block。這樣就可以很快地跨block的移動指向位置了。

Lucene自然會對這個block再次進行壓縮。其壓縮方式叫做Frame Of Reference編碼。示例如下：

考慮到頻繁出現的term（所謂low cardinality的值），比如gender里的男或者女。如果有1百萬個文檔，那麼性別為男的posting list里就會有50萬個int值。用Frame of Reference編碼進行壓縮可以極大減少磁碟佔用。這個優化對於減少索引尺寸有非常重要的意義。當然mysql b-tree里也有一個類似的posting list的東西，是未經過這樣壓縮的。

因為這個Frame of Reference的編碼是有解壓縮成本的。利用skip list，除了跳過了遍歷的成本，也跳過了解壓縮這些壓縮過的block的過程，從而節省了cpu。

利用bitset合併

Bitset是一種很直觀的數據結構，對應posting list如：

[1,3,4,7,10]

對應的bitset就是：

[1,0,1,1,0,0,1,0,0,1]

每個文檔按照文檔id排序對應其中的一個bit。Bitset自身就有壓縮的特點，其用一個byte就可以代表8個文檔。所以100萬個文檔只需要12.5萬個byte。但是考慮到文檔可能有數十億之多，在內存里保存bitset仍然是很奢侈的事情。而且對於個每一個filter都要消耗一個bitset，比如age=18緩存起來的話是一個bitset，18<=age<25是另外一個filter緩存起來也要一個bitset。

所以秘訣就在於需要有一個數據結構：

• 可以很壓縮地保存上億個bit代表對應的文檔是否匹配filter；
• 這個壓縮的bitset仍然可以很快地進行AND和 OR的邏輯操作。

Lucene使用的這個數據結構叫做 Roaring Bitmap。

其壓縮的思路其實很簡單。與其保存100個0，佔用100個bit。還不如保存0一次，然後聲明這個0重複了100遍。

這兩種合併使用索引的方式都有其用途。Elasticsearch對其性能有詳細的對比（https://www.elastic.co/blog/frame-of-reference-and-roaring-bitmaps）。簡單的結論是：因為Frame of Reference編碼是如此 高效，對於簡單的相等條件的過濾緩存成純內存的bitset還不如需要訪問磁碟的skip list的方式要快。

如何減少文檔數？

一種常見的壓縮存儲時間序列的方式是把多個數據點合併成一行。Opentsdb支持海量數據的一個絕招就是定期把很多行數據合併成一行，這個過程叫compaction。類似的vivdcortext使用mysql存儲的時候，也把一分鐘的很多數據點合併存儲到mysql的一行里以減少行數。

這個過程可以示例如下：

可以看到，行變成了列了。每一列可以代表這一分鐘內一秒的數據。

Elasticsearch有一個功能可以實現類似的優化效果，那就是Nested Document。我們可以把一段時間的很多個數據點打包存儲到一個父文檔里，變成其嵌套的子文檔。示例如下：

{timestamp:12:05:01, idc:sz, value1:10,value2:11}{timestamp:12:05:02, idc:sz, value1:9,value2:9}{timestamp:12:05:02, idc:sz, value1:18,value:17}

可以打包成：

{max_timestamp:12:05:02, min_timestamp: 1205:01, idc:sz,records: [ {timestamp:12:05:01, value1:10,value2:11}{timestamp:12:05:02, value1:9,value2:9}{timestamp:12:05:02, value1:18,value:17}]}

這樣可以把數據點公共的維度欄位上移到父文檔里，而不用在每個子文檔里重複存儲，從而減少索引的尺寸。

在存儲的時候，無論父文檔還是子文檔，對於Lucene來說都是文檔，都會有文檔Id。但是對於嵌套文檔來說，可以保存起子文檔和父文檔的文檔id是連續的，而且父文檔總是最後一個。有這樣一個排序性作為保障，那麼有一個所有父文檔的posting list就可以跟蹤所有的父子關係。也可以很容易地在父子文檔id之間做轉換。把父子關係也理解為一個filter，那麼查詢時檢索的時候不過是又AND了另外一個filter而已。前面我們已經看到了Elasticsearch可以非常高效地處理多filter的情況，充分利用底層的索引。

使用了嵌套文檔之後，對於term的posting list只需要保存父文檔的doc id就可以了，可以比保存所有的數據點的doc id要少很多。如果我們可以在一個父文檔里塞入50個嵌套文檔，那麼posting list可以變成之前的1/50。

原文出處：http://www.infoq.com/cn/articles/database-timestamp-02

推薦閱讀：