來(lái)源：https://ricstudio.top/archives/es-lucene-reverted-index

"All problems in computer science can be solved by another level of indirection.”

– David J. Wheeler

“計(jì)算機(jī)世界就是 trade-off 的藝術(shù)”

| 前言

最近接觸的幾個(gè)項(xiàng)目都使用到了 Elasticsearch (以下簡(jiǎn)稱 ES ) 來(lái)存儲(chǔ)數(shù)據(jù)和對(duì)數(shù)據(jù)進(jìn)行搜索分析，就對(duì) ES 進(jìn)行了一些學(xué)習(xí)。本文整理自我自己的一次技術(shù)分享。本文不會(huì)關(guān)注 ES 里面的分布式技術(shù)、相關(guān) API 的使用，而是專注分享下?”ES 如何快速檢索“?這個(gè)主題上面。這個(gè)也是我在學(xué)習(xí)之前對(duì) ES 最感興趣的部分。本文大致包括以下內(nèi)容：1) 關(guān)于搜索? ? ???

• 傳統(tǒng)關(guān)系型數(shù)據(jù)庫(kù)和 ES 的差別

• 搜索引擎原理

2) 細(xì)究倒排索引? ???

• 倒排索引具體是個(gè)什么樣子的（posting list -> term dic -> term index）

• 關(guān)于 postings list 的一些巧技 （FOR、Roaring Bitmaps）

• 如何快速做聯(lián)合查詢？

二、關(guān)于搜索

先設(shè)想一個(gè)關(guān)于搜索的場(chǎng)景，假設(shè)我們要搜索一首詩(shī)句內(nèi)容中帶“前”字的古詩(shī)，

用傳統(tǒng)關(guān)系型數(shù)據(jù)庫(kù)和 ES 實(shí)現(xiàn)會(huì)有什么差別？
如果用像 MySQL 這樣的 RDBMS 來(lái)存儲(chǔ)古詩(shī)的話，我們應(yīng)該會(huì)去使用這樣的 SQL 去查詢。select?name?from?poems?where?content?like?"%前%";
這種我們稱為順序掃描法，需要遍歷所有的記錄進(jìn)行匹配。不但效率低，而且不符合我們搜索時(shí)的期望，比如我們?cè)谒阉鳌癆BCD"這樣的關(guān)鍵詞時(shí)，通常還希望看到"A","AB","CD",“ABC”的搜索結(jié)果。于是乎就有了專業(yè)的搜索引擎，比如我們今天的主角 -- ES。

搜索引擎原理

搜索引擎的搜索原理簡(jiǎn)單概括的話可以分為這么幾步，

• 內(nèi)容爬取，停頓詞過(guò)濾比如一些無(wú)用的像"的"，“了”之類的語(yǔ)氣詞/連接詞
• 內(nèi)容分詞，提取關(guān)鍵詞
• 根據(jù)關(guān)鍵詞建立倒排索引
• 用戶輸入關(guān)鍵詞進(jìn)行搜索

這里我們就引出了一個(gè)概念，也是我們今天的要剖析的重點(diǎn) -?倒排索引。也是 ES 的核心知識(shí)點(diǎn)。

如果你了解 ES 應(yīng)該知道，ES 可以說(shuō)是對(duì) Lucene 的一個(gè)封裝，里面關(guān)于倒排索引的實(shí)現(xiàn)就是通過(guò) lucene 這個(gè) jar 包提供的 API 實(shí)現(xiàn)的，所以下面講的關(guān)于倒排索引的內(nèi)容實(shí)際上都是 lucene 里面的內(nèi)容。

三、倒排索引

首先我們還不能忘了我們之前提的搜索需求，先看下建立倒排索引之后，我們上述的查詢需求會(huì)變成什么樣子。

這樣我們一輸入“前”，借助倒排索引就可以直接定位到符合查詢條件的古詩(shī)。
當(dāng)然這只是一個(gè)很大白話的形式來(lái)描述倒排索引的簡(jiǎn)要工作原理。在 ES 中，這個(gè)倒排索引是具體是個(gè)什么樣的，怎么存儲(chǔ)的等等，這些才是倒排索引的精華內(nèi)容。

1. 幾個(gè)概念

在進(jìn)入下文之前，先描述幾個(gè)前置概念。

term

關(guān)鍵詞這個(gè)東西是我自己的講法，在 ES 中，關(guān)鍵詞被稱為?term。

postings list

還是用上面的例子，{靜夜思, 望廬山瀑布}是 "前" 這個(gè) term 所對(duì)應(yīng)列表。在 ES 中，這些被描述為所有包含特定 term 文檔的 id 的集合。由于整型數(shù)字 integer 可以被高效壓縮的特質(zhì)，integer 是最適合放在 postings list 作為文檔的唯一標(biāo)識(shí)的，ES 會(huì)對(duì)這些存入的文檔進(jìn)行處理，轉(zhuǎn)化成一個(gè)唯一的整型 id。

再說(shuō)下這個(gè) id 的范圍，在存儲(chǔ)數(shù)據(jù)的時(shí)候，在每一個(gè) shard 里面，ES 會(huì)將數(shù)據(jù)存入不同的 segment，這是一個(gè)比 shard 更小的分片單位，這些 segment 會(huì)定期合并。在每一個(gè) segment 里面都會(huì)保存最多 2^31 個(gè)文檔，每個(gè)文檔被分配一個(gè)唯一的 id，從0到(2^31)-1。

相關(guān)的名詞都是 ES 官方文檔給的描述，后面參考材料中都可以找到出處。

2. 索引內(nèi)部結(jié)構(gòu)

上面所描述的倒排索引，僅僅是一個(gè)很粗糙的模型。真的要在實(shí)際生產(chǎn)中使用，當(dāng)然還差的很遠(yuǎn)。在實(shí)際生產(chǎn)場(chǎng)景中，比如 ES 最常用的日志分析，日志內(nèi)容進(jìn)行分詞之后，可以得到多少的 term？那么如何快速的在海量 term 中查詢到對(duì)應(yīng)的 term 呢？遍歷一遍顯然是不現(xiàn)實(shí)的。

term dictionary

于是乎就有了?term dictionary，ES 為了能快速查找到 term，將所有的 term 排了一個(gè)序，二分法查找。是不是感覺有點(diǎn)眼熟，這不就是 MySQL 的索引方式的，直接用 B 樹建立索引詞典指向被索引的數(shù)據(jù)。

term index

但是問題又來(lái)了，你覺得 Term Dictionary 應(yīng)該放在哪里？肯定是放在內(nèi)存里面吧？磁盤 io 那么慢。就像 MySQL 索引就是存在內(nèi)存里面了。但是如果把整個(gè) term dictionary 放在內(nèi)存里面會(huì)有什么后果呢？?jī)?nèi)存爆了...別忘了，ES 默認(rèn)可是會(huì)對(duì)全部 text 字段進(jìn)行索引，必然會(huì)消耗巨大的內(nèi)存，為此 ES 針對(duì)索引進(jìn)行了深度的優(yōu)化。在保證執(zhí)行效率的同時(shí)，盡量縮減內(nèi)存空間的占用。于是乎就有了?term index。Term index 從數(shù)據(jù)結(jié)構(gòu)上分類算是一個(gè)“Trie 樹”，也就是我們常說(shuō)的字典樹。這是一種專門處理字符串匹配的數(shù)據(jù)結(jié)構(gòu)，用來(lái)解決在一組字符串集合中快速查找某個(gè)字符串的問題。這棵樹不會(huì)包含所有的 term，它包含的是 term 的一些前綴（這也是字典樹的使用場(chǎng)景，公共前綴）。通過(guò) term index 可以快速地定位到 term dictionary 的某個(gè) offset，然后從這個(gè)位置再往后順序查找。就像右邊這個(gè)圖所表示的。（怎么樣，像不像我們查英文字典，我們定位 S 開頭的第一個(gè)單詞，或者定位到 Sh 開頭的第一個(gè)單詞，然后再往后順序查詢）lucene 在這里還做了兩點(diǎn)優(yōu)化，一是 term dictionary 在磁盤上面是分 block 保存的，一個(gè) block 內(nèi)部利用公共前綴壓縮，比如都是 Ab 開頭的單詞就可以把 Ab 省去。二是 term index 在內(nèi)存中是以 FST（finite state transducers）的數(shù)據(jù)結(jié)構(gòu)保存的。FST 有兩個(gè)優(yōu)點(diǎn)：

• 空間占用小。通過(guò)對(duì)詞典中單詞前綴和后綴的重復(fù)利用，壓縮了存儲(chǔ)空間
• 查詢速度快。O(len(str)) 的查詢時(shí)間復(fù)雜度。

OK，現(xiàn)在我們能得到 lucene 倒排索引大致是個(gè)什么樣子的了。

四、關(guān)于 postings list 的一些巧技

在實(shí)際使用中，postings list 還需要解決幾個(gè)痛點(diǎn)，

• postings list 如果不進(jìn)行壓縮，會(huì)非常占用磁盤空間，
• 聯(lián)合查詢下，如何快速求交并集（intersections and unions）

對(duì)于如何壓縮，可能會(huì)有人覺得沒有必要，”posting list 不是已經(jīng)只存儲(chǔ)文檔 id 了嗎？還需要壓縮？”，但是如果在 posting list 有百萬(wàn)個(gè) doc id 的情況，壓縮就顯得很有必要了。（比如按照朝代查詢古詩(shī)？），至于為啥需要求交并集，ES 是專門用來(lái)搜索的，肯定會(huì)有很多聯(lián)合查詢的需求吧 （AND、OR）。按照上面的思路，我們先將如何壓縮。

1. 壓縮

Frame of Reference

在 lucene 中，要求 postings lists 都要是有序的整形數(shù)組。這樣就帶來(lái)了一個(gè)很好的好處，可以通過(guò) 增量編碼（delta-encode）這種方式進(jìn)行壓縮。比如現(xiàn)在有 id 列表?[73, 300, 302, 332, 343, 372]，轉(zhuǎn)化成每一個(gè) id 相對(duì)于前一個(gè) id 的增量值（第一個(gè) id 的前一個(gè) id 默認(rèn)是 0，增量就是它自己）列表是[73, 227, 2, 30, 11, 29]。在這個(gè)新的列表里面，所有的 id 都是小于 255 的，所以每個(gè) id 只需要一個(gè)字節(jié)存儲(chǔ)。實(shí)際上 ES 會(huì)做的更加精細(xì)，

它會(huì)把所有的文檔分成很多個(gè) block，每個(gè) block 正好包含 256 個(gè)文檔，然后單獨(dú)對(duì)每個(gè)文檔進(jìn)行增量編碼，計(jì)算出存儲(chǔ)這個(gè) block 里面所有文檔最多需要多少位來(lái)保存每個(gè) id，并且把這個(gè)位數(shù)作為頭信息（header）放在每個(gè) block 的前面。這個(gè)技術(shù)叫?Frame of Reference。
上圖也是來(lái)自于 ES 官方博客中的一個(gè)示例（假設(shè)每個(gè) block 只有 3 個(gè)文件而不是 256）。FOR 的步驟可以總結(jié)為：

經(jīng)過(guò)最后的位壓縮之后，整型數(shù)組的類型從固定大小 (8,16,32,64 位)4 種類型,擴(kuò)展到了[1-64] 位共 64 種類型。

通過(guò)以上的方式可以極大的節(jié)省 posting list 的空間消耗，提高查詢性能。不過(guò) ES 為了提高 filter 過(guò)濾器查詢的性能，還做了更多的工作，那就是緩存。

Roaring Bitmaps (for filter cache)

在 ES 中，可以使用 filters 來(lái)優(yōu)化查詢，filter 查詢只處理文檔是否匹配與否，不涉及文檔評(píng)分操作，查詢的結(jié)果可以被緩存。對(duì)于 filter 查詢，es 提供了 filter cache 這種特殊的緩存，filter cache 用來(lái)存儲(chǔ) filters 得到的結(jié)果集。緩存 filters 不需要太多的內(nèi)存，它只保留一種信息，即哪些文檔與 filter 相匹配。同時(shí)它可以由其它的查詢復(fù)用，極大地提升了查詢的性能。我們上面提到的 Frame Of Reference 壓縮算法對(duì)于 postings list 來(lái)說(shuō)效果很好，但對(duì)于需要存儲(chǔ)在內(nèi)存中的 filter cache 等不太合適。filter cache 會(huì)存儲(chǔ)那些經(jīng)常使用的數(shù)據(jù)，針對(duì) filter 的緩存就是為了加速處理效率，對(duì)壓縮算法要求更高。對(duì)于這類 postings list，ES 采用不一樣的壓縮方式。那么讓我們一步步來(lái)。首先我們知道 postings list 是 Integer 數(shù)組，具有壓縮空間。假設(shè)有這么一個(gè)數(shù)組，我們第一個(gè)壓縮的思路是什么？用位的方式來(lái)表示，每個(gè)文檔對(duì)應(yīng)其中的一位，也就是我們常說(shuō)的位圖，bitmap。它經(jīng)常被作為索引用在數(shù)據(jù)庫(kù)、查詢引擎和搜索引擎中，并且位操作（如 and 求交集、or 求并集）之間可以并行，效率更好。

但是，位圖有個(gè)很明顯的缺點(diǎn)，不管業(yè)務(wù)中實(shí)際的元素基數(shù)有多少，它占用的內(nèi)存空間都恒定不變。也就是說(shuō)不適用于稀疏存儲(chǔ)。業(yè)內(nèi)對(duì)于稀疏位圖也有很多成熟的壓縮方案，lucene 采用的就是roaring bitmaps。
我這里用簡(jiǎn)單的方式描述一下這個(gè)壓縮過(guò)程是怎么樣，

將 doc id 拆成高 16 位，低 16 位。對(duì)高位進(jìn)行聚合 (以高位做 key，value 為有相同高位的所有低位數(shù)組)，根據(jù)低位的數(shù)據(jù)量 (不同高位聚合出的低位數(shù)組長(zhǎng)度不相同)，使用不同的 container(數(shù)據(jù)結(jié)構(gòu)) 存儲(chǔ)。

• len<4096 ArrayContainer 直接存值
• len>=4096 BitmapContainer 使用 bitmap 存儲(chǔ)

分界線的來(lái)源：value 的最大總數(shù)是為2^16=65536. 假設(shè)以 bitmap 方式存儲(chǔ)需要?65536bit=8kb,而直接存值的方式，一個(gè)值 2 byte，4K 個(gè)總共需要2byte*4K=8kb。所以當(dāng) value 總量 <4k 時(shí),使用直接存值的方式更節(jié)省空間。

空間壓縮主要體現(xiàn)在:

• 高位聚合 (假設(shè)數(shù)據(jù)中有 100w 個(gè)高位相同的值,原先需要?100w*2byte,現(xiàn)在只要?1*2byte)
• 低位壓縮

缺點(diǎn)就在于位操作的速度相對(duì)于原生的 bitmap 會(huì)有影響。

這就是 trade-off 呀。平衡的藝術(shù)。

2. 聯(lián)合查詢

講完了壓縮，我們?cè)賮?lái)講講聯(lián)合查詢。先講簡(jiǎn)單的，如果查詢有 filter cache，那就是直接拿 filter cache 來(lái)做計(jì)算，也就是說(shuō)位圖來(lái)做 AND 或者 OR 的計(jì)算。如果查詢的 filter 沒有緩存，那么就用 skip list 的方式去遍歷磁盤上的 postings list。

以上是三個(gè) posting list。我們現(xiàn)在需要把它們用 AND 的關(guān)系合并，得出 posting list 的交集。首先選擇最短的 posting list，逐個(gè)在另外兩個(gè) posting list 中查找看是否存在，最后得到交集的結(jié)果。遍歷的過(guò)程可以跳過(guò)一些元素，比如我們遍歷到綠色的 13 的時(shí)候，就可以跳過(guò)藍(lán)色的 3 了，因?yàn)?3 比 13 要小。
用 skip list 還會(huì)帶來(lái)一個(gè)好處，還記得前面說(shuō)的嗎，postings list 在磁盤里面是采用 FOR 的編碼方式存儲(chǔ)的

會(huì)把所有的文檔分成很多個(gè) block，每個(gè) block 正好包含 256 個(gè)文檔，然后單獨(dú)對(duì)每個(gè)文檔進(jìn)行增量編碼，計(jì)算出存儲(chǔ)這個(gè) block 里面所有文檔最多需要多少位來(lái)保存每個(gè) id，并且把這個(gè)位數(shù)作為頭信息（header）放在每個(gè) block 的前面。

因?yàn)檫@個(gè) FOR 的編碼是有解壓縮成本的。利用 skip list，除了跳過(guò)了遍歷的成本，也跳過(guò)了解壓縮這些壓縮過(guò)的 block 的過(guò)程，從而節(jié)省了 cpu。

五、總結(jié)

下面我們來(lái)做一個(gè)技術(shù)總結(jié)（感覺有點(diǎn)王剛老師的味道）

• 為了能夠快速定位到目標(biāo)文檔，ES 使用倒排索引技術(shù)來(lái)優(yōu)化搜索速度，雖然空間消耗比較大，但是搜索性能提高十分顯著。
• 為了能夠在數(shù)量巨大的 terms 中快速定位到某一個(gè) term，同時(shí)節(jié)約對(duì)內(nèi)存的使用和減少磁盤 io 的讀取，lucene 使用 "term index -> term dictionary -> postings list" 的倒排索引結(jié)構(gòu)，通過(guò)?FST?壓縮放入內(nèi)存，進(jìn)一步提高搜索效率。
• 為了減少 postings list 的磁盤消耗，lucene 使用了?FOR（Frame of Reference）技術(shù)壓縮，帶來(lái)的壓縮效果十分明顯。
• ES 的 filter 語(yǔ)句采用了?Roaring Bitmap?技術(shù)來(lái)緩存搜索結(jié)果，保證高頻 filter 查詢速度的同時(shí)降低存儲(chǔ)空間消耗。
• 在聯(lián)合查詢時(shí)，在有 filter cache 的情況下，會(huì)直接利用位圖的原生特性快速求交并集得到聯(lián)合查詢結(jié)果，否則使用?skip list?對(duì)多個(gè) postings list 求交并集，跳過(guò)遍歷成本并且節(jié)省部分?jǐn)?shù)據(jù)的解壓縮 cpu 成本

Elasticsearch 的索引思路

將磁盤里的東西盡量搬進(jìn)內(nèi)存，減少磁盤隨機(jī)讀取次數(shù) (同時(shí)也利用磁盤順序讀特性)，結(jié)合各種壓縮算法，用及其苛刻的態(tài)度使用內(nèi)存。

所以，對(duì)于使用 Elasticsearch 進(jìn)行索引時(shí)需要注意:

• 不需要索引的字段，一定要明確定義出來(lái)，因?yàn)槟J(rèn)是自動(dòng)建索引的
• 同樣的道理，對(duì)于 String 類型的字段，不需要 analysis 的也需要明確定義出來(lái)，因?yàn)槟J(rèn)也是會(huì) analysis 的
• 選擇有規(guī)律的 ID 很重要，隨機(jī)性太大的 ID(比如 Java 的 UUID) 不利于查詢

最后說(shuō)一下，技術(shù)選型永遠(yuǎn)伴隨著業(yè)務(wù)場(chǎng)景的考量，每種數(shù)據(jù)庫(kù)都有自己要解決的問題（或者說(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)，截然不同?；\統(tǒng)的來(lái)說(shuō)，b-tree 索引是為寫入優(yōu)化的索引結(jié)構(gòu)。當(dāng)我們不需要支持快速的更新的時(shí)候，可以用預(yù)先排序等方式換取更小的存儲(chǔ)空間，更快的檢索速度等好處，其代價(jià)就是更新慢，就像 ES。

希望本篇文章能給你帶來(lái)一些收獲~

參考文檔：

• https://www.elastic.co/cn/blog/frame-of-reference-and-roaring-bitmaps
• https://www.elastic.co/cn/blog/found-elasticsearch-from-the-bottom-up
• http://blog.mikemccandless.com/2014/05/choosing-fast-unique-identifier-uuid.html
• https://www.infoq.cn/article/database-timestamp-02
• https://zhuanlan.zhihu.com/p/137574234
• ickname="架構(gòu)師社區(qū)" data-alias="devabc" data-signature="架構(gòu)師社區(qū)，專注分享架構(gòu)師技術(shù)干貨，架構(gòu)師行業(yè)秘聞，匯集各類奇妙好玩的架構(gòu)師話題和流行的架構(gòu)師動(dòng)向！" data-from="0">