現在的位置: 首頁 > 演算法 > 正文

Elasticsearch 的倒排索引是什麼

2020年02月21日 演算法 ⁄ 共 3749字 ⁄ 字型大小 評論關閉

  為什麼需要倒排索引

  倒排索引,也是索引。

  索引,初衷都是為了快速檢索到你要的數據。

  每種資料庫都有自己要解決的問題(或者說擅長的領域),對應的就有自己的數據結構,而不同的使用場景和數據結構,需要用不同的索引,才能起到最大化加快查詢的目的。

  對 Mysql 來說,是 B+ 樹,對 Elasticsearch/Lucene 來說,是倒排索引。

  Elasticsearch 是建立在全文搜索引擎庫 Lucene 基礎上的搜索引擎,它隱藏了 Lucene 的複雜性,取而代之的提供一套簡單一致的 RESTful API,不過掩蓋不了它底層也是 Lucene 的事實。

  Elasticsearch 的倒排索引,其實就是 Lucene 的倒排索引。

  為什麼叫倒排索引

  在沒有搜索引擎時,我們是直接輸入一個網址,然後獲取網站內容,這時我們的行為是:

  document -> to -> words

  通過文章,獲取裡面的單詞,此謂「正向索引」,forward index.

  後來,我們希望能夠輸入一個單詞,找到含有這個單詞,或者和這個單詞有關係的文章:

  word -> to -> documents

  於是我們把這種索引,成為inverted index,直譯過來,應該叫「反向索引」,國內翻譯成「倒排索引」,有點委婉了。

  現在思考一下,如果讓你來設計這個可以通過單詞,反向找到文章的索引,你會怎麼實現?

  倒排索引的內部結構

  首先,在數據生成的時候,比如爬蟲爬到一篇文章,這時我們需要對這篇文章進行分析,將文本拆解成一個個單詞。

  這個過程很複雜,比如「生存還是死亡」,你要如何讓分詞器自動將它分解為「生存」、「還是」、「死亡」三個詞語,然後把「還是」這個無意義的詞語幹掉。這裡不展開,感興趣的同學可以查看文末關於「分析器」的鏈接。

  下次搜索「生存」,就會返迴文檔ID是 1、2兩份文檔。

  然而上面這套索引的實現,給小孩子當玩具玩還行,要上生產環境,那還遠著。

  想想看,這個世界上那麼多單詞,中文、英文、日文、韓文 … 你每次搜索一個單詞,我都要全局遍歷一遍,很明顯不行。

  於是有了排序,我們需要對單詞進行排序,像 B+ 樹一樣,可以在頁里實現二分查找。

  光排序還不行,你單詞都放在磁碟呢,磁碟 IO 慢的不得了,所以 Mysql 特意把索引緩存到了內存。

  你說好,我也學 Mysql 的,放內存,3,2,1,放,哐當,內存爆了。

  Lucene 的倒排索,增加了最左邊的一層「字典樹」term index,它不存儲所有的單詞,只存儲單詞前綴,通過字典樹找到單詞所在的塊,也就是單詞的大概位置,再在塊里二分查找,找到對應的單詞,再找到單詞對應的文檔列表。

  當然,內存寸土寸金,能省則省,所以 Lucene 還用了 FST(Finite State Transducers)對它進一步壓縮。

  FST 是什麼?這裡就不展開了,這次重點想聊的,是最右邊的 Posting List 的,別看它只是存一個文檔 ID 數組,但是它在設計時,遇到的問題可不少。

  Frame Of Reference

  我們來簡化下 Lucene 要面對的問題,假設有這樣一個數組:

  [73, 300, 302, 332, 343, 372]

  如何把它進行儘可能的壓縮?

  Lucene 里,數據是按 Segment 存儲的,每個 Segment 最多存 65536 個文檔 ID, 所以文檔 ID 的範圍,從 0 到 2^32-1,所以如果不進行任何處理,那麼每個元素都會佔用 2 bytes ,對應上面的數組,就是 6 * 2 = 12 bytes.

  怎麼壓縮呢?

  壓縮,就是儘可能降低每個數據佔用的空間,同時又能讓信息不失真,能夠還原回來。

  Step 1:Delta-encode —— 增量編碼

  我們只記錄元素與元素之間的增量,於是數組變成了:

  [73, 227, 2, 30, 11, 29]

  Step 2:Split into blocks —— 分割成塊

  Lucene里每個塊是 256 個文檔 ID,這樣可以保證每個塊,增量編碼後,每個元素都不會超過 256(1 byte)。

  為了方便演示,我們假設每個塊是 3 個文檔 ID:

  [73, 227, 2], [30, 11, 29]

  Step 3:Bit packing —— 按需分配空間

  對於第一個塊,[73, 227, 2],最大元素是227,需要 8 bits,好,那我給你這個塊的每個元素,都分配 8 bits的空間。

  但是對於第二個塊,[30, 11, 29],最大的元素才30,只需要 5 bits,那我就給你每個元素,只分配 5 bits 的空間,足矣。

  這一步,可以說是把吝嗇發揮到極致,精打細算,按需分配。

  以上三個步驟,共同組成了一項編碼技術,Frame Of Reference(FOR):

  Roaring bitmaps

  接著來聊聊 Posting List 的第二個痛點 —— 如何快速求交並集(intersections and unions)。

  這樣就需要根據三個欄位,去三棵倒排索引里去查,當然,磁碟里的數據,上一節提到過,用了 FOR 進行壓縮,所以我們要把數據進行反向處理,即解壓,才能還原成原始的文檔 ID,然後把這三個文檔 ID 數組在內存中做一個交集。

  即使沒有多條件查詢, Lucene 也需要頻繁求並集,因為 Lucene 是分片存儲的。

  同樣,我們把 Lucene 遇到的問題,簡化成一道演算法題。

  假設有下面三個數組:

  [64, 300, 303, 343]

  [73, 300, 302, 303, 343, 372]

  [303, 311, 333, 343]

  求它們的交集。

  Option 1: Integer 數組

  直接用原始的文檔 ID ,可能你會說,那就逐個數組遍歷一遍吧,遍歷完就知道交集是什麼了。

  其實對於有序的數組,用跳錶(skip table)可以更高效,這裡就不展開了,因為不管是從性能,還是空間上考慮,Integer 數組都不靠譜,假設有100M 個文檔 ID,每個文檔 ID 占 2 bytes,那已經是 200 MB,而這些數據是要放到內存中進行處理的,把這麼大量的數據,從磁碟解壓後丟到內存,內存肯定撐不住。

  Option 2: Bitmap

  假設有這樣一個數組:

  [3,6,7,10]

  那麼我們可以這樣來表示:

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

  看出來了么,對,我們用 0 表示角標對應的數字不存在,用 1 表示存在。

  這樣帶來了兩個好處:

  節省空間:既然我們只需要0和1,那每個文檔 ID 就只需要 1 bit,還是假設有 100M 個文檔,那隻需要 100M bits = 100M * 1/8 bytes = 12.5 MB,比之前用 Integer 數組 的 200 MB,優秀太多。

  運算更快:0 和 1,天然就適合進行位運算,求交集,「與」一下,求並集,「或」一下,一切都回歸到計算機的起點。

  Option 3: Roaring Bitmaps

  細心的你可能發現了,bitmap 有個硬傷,就是不管你有多少個文檔,你佔用的空間都是一樣的,之前說過,Lucene Posting List 的每個 Segement 最多放 65536 個文檔ID,舉一個極端的例子,有一個數組,裡面只有兩個文檔 ID:

  [0, 65535]

  用 Bitmap,要怎麼表示?

  [1,0,0,0,….(超級多個0),…,0,0,1]

  你需要 65536 個 bit,也就是 65536/8 = 8192 bytes,而用 Integer 數組,你只需要 2 * 2 bytes = 4 bytes

  呵呵,死板的 bitmap。可見在文檔數量不多的時候,使用 Integer 數組更加節省內存。

  我們來算一下臨界值,很簡單,無論文檔數量多少,bitmap都需要 8192 bytes,而 Integer 數組則和文檔數量成線性相關,每個文檔 ID 占 2 bytes,所以:

  8192 / 2 = 4096

  當文檔數量少於 4096 時,用 Integer 數組,否則,用 bitmap。

  這裡補充一下 Roaring bitmaps 和 之前講的 Frame Of Reference 的關係。

  Frame Of Reference 是壓縮數據,減少磁碟佔用空間,所以當我們從磁碟取數據時,也需要一個反向的過程,即解壓,解壓後才有我們上面看到的這樣子的文檔ID數組:[73, 300, 302, 303, 343, 372] ,接著我們需要對數據進行處理,求交集或者並集,這時候數據是需要放到內存進行處理的,我們有三個這樣的數組,這些數組可能很大,而內存空間比磁碟還寶貴,於是需要更強有力的壓縮演算法,同時還要有利於快速的求交並集,於是有了Roaring Bitmaps 演算法。

  另外,Lucene 還會把從磁碟取出來的數據,通過 Roaring bitmaps 處理後,緩存到內存中,Lucene 稱之為 filter cache。

  總結

  每種資料庫都有自己要解決的問題(或者說擅長的領域),對應的就有自己的數據結構,而不同的使用場景和數據結構,需要用不同的索引,才能起到最大化加快查詢的目的。

  這篇文章講的雖是 Lucene 如何實現倒排索引,如何精打細算每一塊內存、磁碟空間、如何用詭譎的位運算加快處理速度,但往高處思考,再類比一下 Mysql,你就會發現,雖然都是索引,但是實現起來,截然不同。

抱歉!評論已關閉.