[[382143]]

本文轉(zhuǎn)載自微信公眾號(hào)「程序員歷小冰」，作者歷小冰。轉(zhuǎn)載本文請(qǐng)聯(lián)系程序員歷小冰公眾號(hào)。

熟悉 MySQL 的同學(xué)一定都知道，MySQL 對(duì)于復(fù)雜條件查詢(xún)的支持并不好。MySQL 最多使用一個(gè)條件涉及的索引來(lái)過(guò)濾，然后剩余的條件只能在遍歷行過(guò)程中進(jìn)行內(nèi)存過(guò)濾，對(duì)這個(gè)過(guò)程不了解的同學(xué)可以先行閱讀一下《MySQL復(fù)雜where條件分析》。

上述這種處理復(fù)雜條件查詢(xún)的方式因?yàn)橹荒芡ㄟ^(guò)一個(gè)索引進(jìn)行過(guò)濾，所以需要進(jìn)行大量的 I/O 操作來(lái)讀取行數(shù)據(jù)，并消耗 CPU 進(jìn)行內(nèi)存過(guò)濾，導(dǎo)致查詢(xún)性能的下降。

而 ElasticSearch 因其特性，十分適合進(jìn)行復(fù)雜條件查詢(xún)，是業(yè)界主流的復(fù)雜條件查詢(xún)場(chǎng)景解決方案，廣泛應(yīng)用于訂單和日志查詢(xún)等場(chǎng)景。

下面我們就一起來(lái)看一下，為什么 ElasticSearch 適合進(jìn)行復(fù)雜條件查詢(xún)。

ElasticSearch 簡(jiǎn)介

Elasticsearch 是開(kāi)源的實(shí)時(shí)分布式搜索分析引擎，內(nèi)部使用 Lucene 做索引與搜索。它提供"準(zhǔn)實(shí)時(shí)搜索"能力，并且能動(dòng)態(tài)集群規(guī)模，彈性擴(kuò)容。

Elasticsearch 使用 Lucene 作為其全文搜索引擎，用于處理純文本的數(shù)據(jù)，但 Lucene 只是一個(gè)庫(kù)，提供建立索引、執(zhí)行搜索等接口，但不包含分布式服務(wù)，這些正是 Elasticsearch 做的。

下面，我們來(lái)介紹一下 ElasticSearch 的相關(guān)概念。為了便于初學(xué)者理解，我們先將 ElasticSearch 中的概念和 MySQL 中的概念大致地進(jìn)行對(duì)應(yīng)。但是二者在具體細(xì)節(jié)上還是有很多差異的，大家深入了解 ElasticSearch 就會(huì)將二者區(qū)分清楚，不能強(qiáng)行對(duì)比等同。

• ElasticSearch 中的索引 Index 類(lèi)似于 MySQL 中的數(shù)據(jù)庫(kù) Database;
• ElasticSearch 中的類(lèi)型 Type 類(lèi)似于 MySQL 中的表 Table;需要注意，這個(gè)概念在 7.x 版本中被完全刪除，而且概念上和 Table 也有較大差異;
• ElasticSearch 中的文檔 Document 類(lèi)似于 MySQL 中的數(shù)據(jù)行 Row，每個(gè)文檔由多個(gè)字段 Filed 組成，這個(gè)Filed 就類(lèi)似于 MySQL 的 Column;
• ElasticSearch 中的映射 Mapping 是對(duì)索引庫(kù)中的索引字段及其數(shù)據(jù)類(lèi)型進(jìn)行定義，類(lèi)似于關(guān)系型數(shù)據(jù)庫(kù)中的表結(jié)構(gòu) Schema;
• ElasticSearch 使用自己的領(lǐng)域語(yǔ)言 Query DSL 來(lái)進(jìn)行增刪改查，而 MySQL 使用 SQL 語(yǔ)言進(jìn)行上訴操作。
• ElasticSearch 還有一系列有關(guān)其分布式特性的概念，我們這里就暫不介紹了，等后續(xù)學(xué)習(xí)到其分布式特性時(shí)在進(jìn)行介紹。

倒排索引

MySQL 有 B+ 樹(shù)索引，而 ElasticSearch 則是倒排索引 (Inverted Index)，它通過(guò)倒排索引來(lái)實(shí)現(xiàn)比 MySQL 更快的過(guò)濾和復(fù)雜條件的查詢(xún)，此外，全文搜索功能也是依賴(lài)倒排索引才能實(shí)現(xiàn)。下面，我們就具體來(lái)看一下何為倒排索引。

倒排索引按照維基百科的描述，是存儲(chǔ)文檔內(nèi)容到文檔位置映射關(guān)系的數(shù)據(jù)庫(kù)索引結(jié)構(gòu)。不過(guò)只看定義，我是有點(diǎn)迷惑，這不是和 MySQL 的非主鍵索引類(lèi)似嘛，為什么要叫它“倒排”呢?這個(gè)問(wèn)題我目前也為搞清楚，可能要等到后續(xù)了解了其具體實(shí)現(xiàn)才能理解。

我們還是以書(shū)籍檢索為例，假設(shè)有以下數(shù)據(jù)，每一行就是一個(gè) Document，每個(gè) Document 由 id，ISBN 號(hào)，作者名稱(chēng)和評(píng)分組成。

給上述數(shù)據(jù)按照 ISBN 和 Author 建立的倒排索引如下所示。倒排索引是每個(gè)字段分開(kāi)建立的，相互獨(dú)立。有兩個(gè)專(zhuān)門(mén)的術(shù)語(yǔ)，分別是索引 Term 和倒排表 Posting List。字段的值就是 Term，比如 N0007，而 Term 對(duì)應(yīng)的文檔 ID 的列表就是 Posting List，對(duì)應(yīng)圖中紅色的部分。

一般 Term 都是按照順序排序的，比如 Author 名稱(chēng)就是按照字母序進(jìn)行了排序，排序之后，當(dāng)我們搜索某一個(gè) Term 時(shí)，就不需要從頭遍歷，而是采用二分查找。一系列排序后的 Term 就組成了索引表 Term Dictionary。

但是 Term Dictionary 往往很大，無(wú)法完整放入內(nèi)存，這是為了更快的查詢(xún)，還需要再給它創(chuàng)建索引，也就是 Term Index 。

ElasticSearch 使用 Burst-Trie 結(jié)構(gòu)來(lái)實(shí)現(xiàn) Term Index，它是一種前綴樹(shù) Trie 的一種變種，它主要是將后綴進(jìn)行了壓縮，降低了Trie的高度，從而獲取更好查詢(xún)性能。

Term Index 并不需要像 MySQL 的索引一樣，包含所有的 Term，而是包含的是這些 Term 的前綴。它就類(lèi)似于字典的查詢(xún)目錄，可以進(jìn)行快速定位到 Term Dictionary 的某一位置，然后再?gòu)倪@個(gè)位置向后查詢(xún)。

綜上， Alice，Alf，Arlan，Bob，Tom 等詞的倒排索引如下所示。綠色部分是 Term Index，藍(lán)色部分是 Term Dictionary，紅色部分是 Posting List。

一般來(lái)說(shuō)，Term Index 都是全部緩存在內(nèi)存中，查詢(xún)時(shí)，先通過(guò)其快速定位到 Term Dictionary 對(duì)應(yīng)的大致范圍，然后再進(jìn)行磁盤(pán)讀取查找對(duì)應(yīng)的 Term，這樣就大大減少了磁盤(pán) I/O 的次數(shù)。

聯(lián)合索引查詢(xún)

了解了 ElasticSearch 的倒排索引后，我們?cè)賮?lái)看看其如何處理復(fù)雜的聯(lián)合索引查詢(xún)。比如上述書(shū)籍例子中，我們需要查詢(xún)?cè)u(píng)分等于2.2并且作者名稱(chēng)叫 Tom的書(shū)籍。

理論上，我們只需要分別按照 Score 和 Author 字段的倒排索引進(jìn)行查詢(xún)，獲取響應(yīng)的 Posting List，再將其做交集合并即可。

這里又要吐槽一下 MySQL，它是不支持這個(gè)合并操作的，它只能按照一個(gè)字段的索引進(jìn)行查詢(xún)，然后根據(jù)另外一個(gè)字段的條件做內(nèi)存過(guò)濾。順便說(shuō)一下，MySQL 的 join 功能也弱爆了，感興趣的同學(xué)可以了解一下這篇文章

而 ElasticSearch 則支持使用跳表 Skip List和 Bitset 的方式將數(shù)據(jù)集進(jìn)行合并。

• 使用 Skip List 結(jié)構(gòu)，同時(shí)遍歷 Score 和 Author 查詢(xún)出來(lái)的 Posting List，利用其 Skip List 結(jié)構(gòu)，相互跳躍對(duì)比，得出合集。
• 使用 Bitset 結(jié)構(gòu)，對(duì) Score 和 Author 查詢(xún)出來(lái)的 Posting List 的值計(jì)算出各自的 Bitset，然后進(jìn)行 AND 操作。

跳表合并策略

ElasticSearch 在存儲(chǔ) Posting List 數(shù)據(jù)時(shí)，就保存了對(duì)應(yīng)的多級(jí)跳表結(jié)構(gòu)響應(yīng)的數(shù)據(jù)，這也體現(xiàn)了其空間換時(shí)間的基本思想。

這里先介紹一下跳表的基本概念，它其實(shí)是一種可以進(jìn)行二分查找的有序鏈表。跳表在原有的有序鏈表上面增加了多級(jí)索引，通過(guò)索引來(lái)實(shí)現(xiàn)快速查找。首先在最高級(jí)索引上查找最后一個(gè)小于當(dāng)前查找元素的位置，然后再跳到次高級(jí)索引繼續(xù)查找，直到跳到最底層為止，通過(guò)這種方式，加快了查詢(xún)的速度。

比如，按照 Score 查出來(lái)的 Posting List 為[2,3,4,5,7,9,10,11]，按照 Author 查出來(lái)的結(jié)果為 [3,8,9,12,13]，則二者的跳表結(jié)構(gòu)如下圖所示。

具體合并過(guò)程則是先選最短的 posting list，也就是 Author 的結(jié)果集，從其最小的一個(gè) id 開(kāi)始，將其作為當(dāng)前最大值。然后依次剩余 posting list 中查找大于或等于該值的位置。

比如上述結(jié)果集中，先去 Score 結(jié)果集中查找 3，找到后，就表明 3是二者的合集元素之一;然后再重新開(kāi)啟一輪，選取 Author 結(jié)果集中 3 的下一個(gè)值 8 ，去 Score 結(jié)果集查詢(xún) 8，發(fā)現(xiàn)了大于等于 8 的最小的值是 9 ，所以不可能有共同的值 8，然后再去 Author 結(jié)果集查找 9 ，發(fā)現(xiàn)其大于等于 9 的最小值是 12，所以再去 Score 結(jié)果集中查找大于等于 12的值，發(fā)現(xiàn)并不存在;最終得出二者的合集就只有[3]。

在查詢(xún)過(guò)程中，每個(gè) posting list 都可以根據(jù)當(dāng)前 id 通過(guò) skip list 快速跳過(guò)不符合的 id 值，加速整個(gè)合并取交集的過(guò)程。

ElasticSearch 對(duì)于較長(zhǎng)的 posting list 也會(huì)使用 Frame Of Reference 進(jìn)行壓縮編碼，減少了磁盤(pán)占用，減少了索引尺寸。有關(guān)具體存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)我們后續(xù)再進(jìn)行細(xì)聊。

Bitset 合并策略

ElasticSearch除了使用 skipList 來(lái)進(jìn)行數(shù)據(jù)磁盤(pán)讀取時(shí)的合并操作外，還會(huì)將一些查詢(xún)條件對(duì)應(yīng)的結(jié)果集 posting list 進(jìn)行內(nèi)存緩存，也就是所謂的 Filter Cache，為了后續(xù)再次復(fù)用。

為了減少內(nèi)存緩存所消耗的內(nèi)存空間大小，ElasticSearch 沒(méi)有使用單純的數(shù)組和 bitset 來(lái)存儲(chǔ) posting list，而是使用要壓縮效率更高的 Roaring Bitmap。

我們可以先來(lái)講一下單純數(shù)組或 bitset 數(shù)據(jù)結(jié)構(gòu)為什么并不使用。比如如下一道較為常見(jiàn)的面試題目：

給定含有40億個(gè)不重復(fù)的位于[0, 2^32 - 1]區(qū)間內(nèi)的整數(shù)的集合，如何快速判定某個(gè)數(shù)是否在該集合內(nèi)?

如果我們要使用 unsigned long 數(shù)組來(lái)存儲(chǔ)它的話(huà)，也就需要消耗 40億 * 32 位 = 160 Byte，大致是 16000 MB。

如果要使用位圖 Bitset 來(lái)存儲(chǔ)的話(huà)，即某個(gè)數(shù)位于原集合內(nèi)，就將它對(duì)應(yīng)的位圖內(nèi)的比特置為1，否則保持為0。這樣只需要消耗 2 ^ 32 位 = 512 MB，這可只有原來(lái)的 3.2 % 左右。

但是，Bitset 也有其缺陷，也就是稀疏存儲(chǔ)的問(wèn)題，比如上述集合并不是 40億，而是只有2，3個(gè)，那么 Bitset 中只有少數(shù)幾位是1，其他位都是 0，但是它仍然占用了 512 MB。

而 RoaringBitmap 就是為了解決稀疏存儲(chǔ)的問(wèn)題。下圖就是 RoaringBitmap 的基本原理示意圖。

首先，如上圖所示，計(jì)算出32位無(wú)符號(hào)整數(shù)和 65536 的除數(shù)和余數(shù)。其含義表示，將32位無(wú)符號(hào)整數(shù)按照高16位分桶，即最多可能有2^16=65536個(gè)桶，術(shù)語(yǔ)懲治為 container。存儲(chǔ)數(shù)據(jù)時(shí)，按照數(shù)據(jù)的高16位找到 container(找不到就會(huì)新建一個(gè))，再將低16位放入container中。也就是說(shuō)，一個(gè) RoaringBitmap 就是很多container的集合。

然后 container 內(nèi)具體的存儲(chǔ)結(jié)構(gòu)要根據(jù)存入其內(nèi)數(shù)據(jù)的基數(shù)來(lái)決定。

• 基數(shù)小于 2 ^ 12 次方即 4096時(shí)，使用unsigned short類(lèi)型的有序數(shù)組來(lái)存儲(chǔ)，最大消耗空間就是 8 KB。
• 基數(shù)大于 4096 時(shí)，則使用大小為 2 ^ 16 次方的普通 bitset 來(lái)存儲(chǔ)，固定消耗 8 KB。當(dāng)然，有些時(shí)候也會(huì)對(duì) bitset 進(jìn)行行程長(zhǎng)度編碼(RLE)壓縮，進(jìn)一步減少空間占用。

ElasticSearch 就是使用 Roaring Bitmap 來(lái)緩存不同條件查詢(xún)出來(lái)的 posting list，然后再進(jìn)行與操作計(jì)算出最終結(jié)果集。

后記

至此，我們也算了解了 ElasticSearch 為什么比 MySQL 更適合復(fù)雜條件查詢(xún)，但是有好就有弊，因?yàn)闉榱瞬樵?xún)做了這么多的準(zhǔn)備工作，ElasticSearch 的插入速度就會(huì)慢于 MySQL，而且數(shù)據(jù)存入ES后并不是立馬就能檢索到。