聊聊 Elasticsearch 的倒排索引

本文公眾號(hào)來(lái)源：柳樹(shù)的絮叨叨作者：靠發(fā)型吃飯的柳樹(shù)本文已收錄至我的GitHub為什么需要倒排索引 ?

倒排索引，也是索引。

索引，初衷都是為了快速檢索到你要的數(shù)據(jù)。?

每種數(shù)據(jù)庫(kù)都有自己要解決的問(wèn)題（或者說(shuō)擅長(zhǎng)的領(lǐng)域），對(duì)應(yīng)的就有自己的數(shù)據(jù)結(jié)構(gòu)，而不同的使用場(chǎng)景和數(shù)據(jù)結(jié)構(gòu)，需要用不同的索引，才能起到最大化加快查詢的目的。 ?

對(duì) Mysql 來(lái)說(shuō)，是 B+ 樹(shù)，對(duì) Elasticsearch/Lucene 來(lái)說(shuō)，是倒排索引。?

Elasticsearch 是建立在全文搜索引擎庫(kù) Lucene 基礎(chǔ)上的搜索引擎，它隱藏了 Lucene 的復(fù)雜性，取而代之的提供一套簡(jiǎn)單一致的 RESTful API，不過(guò)掩蓋不了它底層也是 Lucene 的事實(shí)。

Elasticsearch 的倒排索引，其實(shí)就是 Lucene 的倒排索引。

在沒(méi)有搜索引擎時(shí)，我們是直接輸入一個(gè)網(wǎng)址，然后獲取網(wǎng)站內(nèi)容，這時(shí)我們的行為是：?

document -> to -> words ?

通過(guò)文章，獲取里面的單詞，此謂「正向索引」，forward index. ?

后來(lái)，我們希望能夠輸入一個(gè)單詞，找到含有這個(gè)單詞，或者和這個(gè)單詞有關(guān)系的文章：

word -> to -> documents

于是我們把這種索引，成為inverted index，直譯過(guò)來(lái)，應(yīng)該叫「反向索引」，國(guó)內(nèi)翻譯成「倒排索引」，有點(diǎn)委婉了。

現(xiàn)在思考一下，如果讓你來(lái)設(shè)計(jì)這個(gè)可以通過(guò)單詞，反向找到文章的索引，你會(huì)怎么實(shí)現(xiàn)？?

關(guān)于 Elasticsearch 這類「搜索引擎」要解決的問(wèn)題、它和傳統(tǒng)關(guān)系型數(shù)據(jù)庫(kù)的區(qū)別等等，可以看我之前寫的文章：為什么需要 Elasticsearch（文末有鏈接）

首先，在數(shù)據(jù)生成的時(shí)候，比如爬蟲(chóng)爬到一篇文章，這時(shí)我們需要對(duì)這篇文章進(jìn)行分析，將文本拆解成一個(gè)個(gè)單詞。

這個(gè)過(guò)程很復(fù)雜，比如“生存還是死亡”，你要如何讓分詞器自動(dòng)將它分解為“生存”、“還是”、“死亡”三個(gè)詞語(yǔ)，然后把“還是”這個(gè)無(wú)意義的詞語(yǔ)干掉。這里不展開(kāi)，感興趣的同學(xué)可以查看文末關(guān)于「分析器」的鏈接。

接著，把這兩個(gè)詞語(yǔ)以及它對(duì)應(yīng)的文檔id存下來(lái)：?

word documentId ?

生存 ?1

死亡 ?1

接著爬蟲(chóng)繼續(xù)爬，又爬到一個(gè)含有“生存”的文檔，于是索引變成：

word documentId ?

生存 ?1,2

死亡 ?1

下次搜索“生存”，就會(huì)返回文檔ID是 1、2兩份文檔。

然而上面這套索引的實(shí)現(xiàn)，給小孩子當(dāng)玩具玩還行，要上生產(chǎn)環(huán)境，那還遠(yuǎn)著。

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

于是有了排序，我們需要對(duì)單詞進(jìn)行排序，像 B+ 樹(shù)一樣，可以在頁(yè)里實(shí)現(xiàn)二分查找。

光排序還不行，你單詞都放在磁盤呢，磁盤 IO 慢的不得了，所以 Mysql 特意把索引緩存到了內(nèi)存。

你說(shuō)好，我也學(xué) Mysql 的，放內(nèi)存，3，2，1，放，哐當(dāng)，內(nèi)存爆了。

哪本字典，會(huì)把所有單詞都貼在目錄里的？

所以，上圖：?

Lucene 的倒排索，增加了最左邊的一層「字典樹(shù)」term index，它不存儲(chǔ)所有的單詞，只存儲(chǔ)單詞前綴，通過(guò)字典樹(shù)找到單詞所在的塊，也就是單詞的大概位置，再在塊里二分查找，找到對(duì)應(yīng)的單詞，再找到單詞對(duì)應(yīng)的文檔列表。

當(dāng)然，內(nèi)存寸土寸金，能省則省，所以 Lucene 還用了 FST（Finite State Transducers）對(duì)它進(jìn)一步壓縮。

FST 是什么？這里就不展開(kāi)了，這次重點(diǎn)想聊的，是最右邊的 Posting List 的，別看它只是存一個(gè)文檔 ID 數(shù)組，但是它在設(shè)計(jì)時(shí)，遇到的問(wèn)題可不少。

原生的 Posting List 有兩個(gè)痛點(diǎn)：

• 如何壓縮以節(jié)省磁盤空間

• 如何快速求交并集（intersections and unions）

先來(lái)聊聊壓縮。

我們來(lái)簡(jiǎn)化下 Lucene 要面對(duì)的問(wèn)題，假設(shè)有這樣一個(gè)數(shù)組：

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

如何把它進(jìn)行盡可能的壓縮？

Lucene 里，數(shù)據(jù)是按 Segment 存儲(chǔ)的，每個(gè) Segment 最多存 65536 個(gè)文檔 ID， 所以文檔 ID 的范圍，從 0 到 2^32-1，所以如果不進(jìn)行任何處理，那么每個(gè)元素都會(huì)占用 2 bytes ，對(duì)應(yīng)上面的數(shù)組，就是 6 * 2 = 12 bytes. ?

怎么壓縮呢？

壓縮，就是盡可能降低每個(gè)數(shù)據(jù)占用的空間，同時(shí)又能讓信息不失真，能夠還原回來(lái)。

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

我們只記錄元素與元素之間的增量，于是數(shù)組變成了：

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

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

Lucene里每個(gè)塊是 256 個(gè)文檔 ID，這樣可以保證每個(gè)塊，增量編碼后，每個(gè)元素都不會(huì)超過(guò) 256（1 byte）.

為了方便演示，我們假設(shè)每個(gè)塊是 3 個(gè)文檔 ID：

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

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

對(duì)于第一個(gè)塊，[73, 227, 2]，最大元素是227，需要 8 bits，好，那我給你這個(gè)塊的每個(gè)元素，都分配 8 bits的空間。

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

這一步，可以說(shuō)是把吝嗇發(fā)揮到極致，精打細(xì)算，按需分配。

以上三個(gè)步驟，共同組成了一項(xiàng)編碼技術(shù)，F(xiàn)rame Of Reference（FOR）：

接著來(lái)聊聊 Posting List 的第二個(gè)痛點(diǎn) —— 如何快速求交并集（intersections and unions）。

在 Lucene 中查詢，通常不只有一個(gè)查詢條件，比如我們想搜索：

• 含有“生存”相關(guān)詞語(yǔ)的文檔

• 文檔發(fā)布時(shí)間在最近一個(gè)月

• 文檔發(fā)布者是平臺(tái)的特約作者

這樣就需要根據(jù)三個(gè)字段，去三棵倒排索引里去查，當(dāng)然，磁盤里的數(shù)據(jù)，上一節(jié)提到過(guò)，用了 FOR 進(jìn)行壓縮，所以我們要把數(shù)據(jù)進(jìn)行反向處理，即解壓，才能還原成原始的文檔 ID，然后把這三個(gè)文檔 ID 數(shù)組在內(nèi)存中做一個(gè)交集。

即使沒(méi)有多條件查詢， Lucene 也需要頻繁求并集，因?yàn)?Lucene 是分片存儲(chǔ)的。

同樣，我們把 Lucene 遇到的問(wèn)題，簡(jiǎn)化成一道算法題。

假設(shè)有下面三個(gè)數(shù)組：

[64, 300, 303, 343] ?

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

[303, 311, 333, 343] ?

求它們的交集。

Option 1: Integer 數(shù)組

直接用原始的文檔 ID ，可能你會(huì)說(shuō)，那就逐個(gè)數(shù)組遍歷一遍吧，遍歷完就知道交集是什么了。

其實(shí)對(duì)于有序的數(shù)組，用跳表（skip table）可以更高效，這里就不展開(kāi)了，因?yàn)椴还苁菑男阅?，還是空間上考慮，Integer 數(shù)組都不靠譜，假設(shè)有100M 個(gè)文檔 ID，每個(gè)文檔 ID 占 2 bytes，那已經(jīng)是 200 MB，而這些數(shù)據(jù)是要放到內(nèi)存中進(jìn)行處理的，把這么大量的數(shù)據(jù)，從磁盤解壓后丟到內(nèi)存，內(nèi)存肯定撐不住。

Option 2: Bitmap

假設(shè)有這樣一個(gè)數(shù)組：

[3,6,7,10]

那么我們可以這樣來(lái)表示：

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

看出來(lái)了么，對(duì)，我們用 0 表示角標(biāo)對(duì)應(yīng)的數(shù)字不存在，用 1 表示存在。

這樣帶來(lái)了兩個(gè)好處：

• 節(jié)省空間：既然我們只需要0和1，那每個(gè)文檔 ID 就只需要 1 bit，還是假設(shè)有 100M 個(gè)文檔，那只需要 100M bits = 100M * 1/8 bytes = 12.5 MB，比之前用 Integer 數(shù)組 的 200 MB，優(yōu)秀太多

• 運(yùn)算更快：0 和 1，天然就適合進(jìn)行位運(yùn)算，求交集，「與」一下，求并集，「或」一下，一切都回歸到計(jì)算機(jī)的起點(diǎn)

Option 3: Roaring Bitmaps

細(xì)心的你可能發(fā)現(xiàn)了，bitmap 有個(gè)硬傷，就是不管你有多少個(gè)文檔，你占用的空間都是一樣的，之前說(shuō)過(guò)，Lucene ?Posting List 的每個(gè) Segement 最多放 65536 個(gè)文檔ID，舉一個(gè)極端的例子，有一個(gè)數(shù)組，里面只有兩個(gè)文檔 ID：

[0, 65535]

用 Bitmap，要怎么表示？

[1,0,0,0,….(超級(jí)多個(gè)0),…,0,0,1]

你需要 65536 個(gè) bit，也就是 65536/8 = 8192 bytes，而用 Integer 數(shù)組，你只需要 2 * 2 bytes = 4 bytes

呵呵，死板的 bitmap?？梢?jiàn)在文檔數(shù)量不多的時(shí)候，使用 Integer 數(shù)組更加節(jié)省內(nèi)存。

我們來(lái)算一下臨界值，很簡(jiǎn)單，無(wú)論文檔數(shù)量多少，bitmap都需要 8192 bytes，而 Integer 數(shù)組則和文檔數(shù)量成線性相關(guān)，每個(gè)文檔 ID 占 2 bytes，所以：

8192 / 2 = 4096

當(dāng)文檔數(shù)量少于 4096 時(shí)，用 Integer 數(shù)組，否則，用 bitmap.

這里補(bǔ)充一下 Roaring bitmaps 和 之前講的 Frame Of Reference 的關(guān)系。

Frame Of Reference 是壓縮數(shù)據(jù)，減少磁盤占用空間，所以當(dāng)我們從磁盤取數(shù)據(jù)時(shí)，也需要一個(gè)反向的過(guò)程，即解壓，解壓后才有我們上面看到的這樣子的文檔ID數(shù)組：[73, 300, 302, 303, 343, 372] ?，接著我們需要對(duì)數(shù)據(jù)進(jìn)行處理，求交集或者并集，這時(shí)候數(shù)據(jù)是需要放到內(nèi)存進(jìn)行處理的，我們有三個(gè)這樣的數(shù)組，這些數(shù)組可能很大，而內(nèi)存空間比磁盤還寶貴，于是需要更強(qiáng)有力的壓縮算法，同時(shí)還要有利于快速的求交并集，于是有了Roaring Bitmaps 算法。

另外，Lucene 還會(huì)把從磁盤取出來(lái)的數(shù)據(jù)，通過(guò) Roaring bitmaps 處理后，緩存到內(nèi)存中，Lucene 稱之為 filter cache. ?

文章的最后，如果來(lái)一段話總結(jié)（zhuang）升華（bi）一下，這篇文章就會(huì)得高分。

有什么總結(jié)，可以拔高這篇文章的高度呢？

首先，你會(huì)發(fā)現(xiàn)，很多業(yè)務(wù)上、技術(shù)上要解決的問(wèn)題，最后都可以抽象為一道算法題，復(fù)雜問(wèn)題簡(jiǎn)單化。

呃，這個(gè)“華”，升的還不夠。

另一個(gè)具有高度的“華”，其實(shí)在開(kāi)頭已經(jīng)講出來(lái)了：

每種數(shù)據(jù)庫(kù)都有自己要解決的問(wèn)題（或者說(shuō)擅長(zhǎng)的領(lǐng)域），對(duì)應(yīng)的就有自己的數(shù)據(jù)結(jié)構(gòu)，而不同的使用場(chǎng)景和數(shù)據(jù)結(jié)構(gòu)，需要用不同的索引，才能起到最大化加快查詢的目的。

這篇文章講的雖是 Lucene 如何實(shí)現(xiàn)倒排索引，如何精打細(xì)算每一塊內(nèi)存、磁盤空間、如何用詭譎的位運(yùn)算加快處理速度，但往高處思考，再類比一下 Mysql，你就會(huì)發(fā)現(xiàn)，雖然都是索引，但是實(shí)現(xiàn)起來(lái)，截然不同。

這個(gè)往細(xì)講，又是一篇文章：如此不同，如此成功 —— B+ 樹(shù)索引 vs 倒排索引

知識(shí)要融合起來(lái)看才有意思。

來(lái)，放大招了，兩個(gè)問(wèn)題：

• Lucene 為什么不用 b+ 樹(shù)來(lái)搜索數(shù)據(jù)？

• Mysql 為什么不用 倒排索引來(lái)檢索數(shù)據(jù)？

附上兩張圖：

Mysql 的 B+樹(shù)索引

推薦阿里云推廣服務(wù)器89/年，229/3年，買來(lái)送自己，送女朋友馬上過(guò)年再合適不過(guò)了，買了搭建個(gè)項(xiàng)目給面試官看也香，還可以熟悉技術(shù)棧，(老用戶用家人賬號(hào)買就好了，我用我女朋友的?）。掃碼購(gòu)買

我這里還有一個(gè)：搭建教程，從0開(kāi)始一步一步帶你搭建?