[[318129]]

 Elasticsearch 是通過 Lucene 的倒排索引技術(shù)實(shí)現(xiàn)比關(guān)系型數(shù)據(jù)庫更快的過濾。特別是它對(duì)多條件的過濾支持非常好，比如年齡在 18 和 30 之間，性別為女性這樣的組合查詢。倒排索引很多地方都有介紹，但是其比關(guān)系型數(shù)據(jù)庫的 b-tree 索引快在哪里?到底為什么快呢?

籠統(tǒng)的來說，b-tree 索引是為寫入優(yōu)化的索引結(jié)構(gòu)。當(dāng)我們不需要支持快速的更新的時(shí)候，可以用預(yù)先排序等方式換取更小的存儲(chǔ)空間，更快的檢索速度等好處，其代價(jià)就是更新慢。要進(jìn)一步深入的化，還是要看一下 Lucene 的倒排索引是怎么構(gòu)成的。

這里有好幾個(gè)概念。我們來看一個(gè)實(shí)際的例子，假設(shè)有如下的數(shù)據(jù)：

這里每一行是一個(gè) document。每個(gè) document 都有一個(gè) docid。那么給這些 document 建立的倒排索引就是：

年齡

性別

可以看到，倒排索引是 per field 的，一個(gè)字段有一個(gè)自己的倒排索引。18,20 這些叫做 term，而 [1,3] 就是 posting list。Posting list 就是一個(gè) int 的數(shù)組，存儲(chǔ)了所有符合某個(gè) term 的文檔 id。那么什么是 term dictionary 和 term index?

假設(shè)我們有很多個(gè) term，比如：

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

如果按照這樣的順序排列，找出某個(gè)特定的 term 一定很慢，因?yàn)?term 沒有排序，需要全部過濾一遍才能找出特定的 term。排序之后就變成了：

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

這樣我們可以用二分查找的方式，比全遍歷更快地找出目標(biāo)的 term。這個(gè)就是 term dictionary。有了 term dictionary 之后，可以用 logN 次磁盤查找得到目標(biāo)。但是磁盤的隨機(jī)讀操作仍然是非常昂貴的(一次 random access 大概需要 10ms 的時(shí)間)。所以盡量少的讀磁盤，有必要把一些數(shù)據(jù)緩存到內(nèi)存里。但是整個(gè) term dictionary 本身又太大了，無法完整地放到內(nèi)存里。于是就有了 term index。term index 有點(diǎn)像一本字典的大的章節(jié)表。比如：

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

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

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

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

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

現(xiàn)在我們可以回答“為什么 Elasticsearch/Lucene 檢索可以比 mysql 快了。Mysql 只有 term dictionary 這一層，是以 b-tree 排序的方式存儲(chǔ)在磁盤上的。檢索一個(gè) term 需要若干次的 random access 的磁盤操作。而 Lucene 在 term dictionary 的基礎(chǔ)上添加了 term index 來加速檢索，term index 以樹的形式緩存在內(nèi)存中。從 term index 查到對(duì)應(yīng)的 term dictionary 的 block 位置之后，再去磁盤上找 term，大大減少了磁盤的 random access 次數(shù)。

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

如何聯(lián)合索引查詢?

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

這個(gè)理論上的“與”合并的操作可不容易。對(duì)于 mysql 來說，如果你給 age 和 gender 兩個(gè)字段都建立了索引，查詢的時(shí)候只會(huì)選擇其中最 selective 的來用，然后另外一個(gè)條件是在遍歷行的過程中在內(nèi)存中計(jì)算之后過濾掉。那么要如何才能聯(lián)合使用兩個(gè)索引呢?有兩種辦法：

• 使用 skip list 數(shù)據(jù)結(jié)構(gòu)。同時(shí)遍歷 gender 和 age 的 posting list，互相 skip;
• 使用 bitset 數(shù)據(jù)結(jié)構(gòu)，對(duì) gender 和 age 兩個(gè) filter 分別求出 bitset，對(duì)兩個(gè) bitset 做 AN 操作。

PostgreSQL 從 8.4 版本開始支持通過 bitmap 聯(lián)合使用兩個(gè)索引，就是利用了 bitset 數(shù)據(jù)結(jié)構(gòu)來做到的。當(dāng)然一些商業(yè)的關(guān)系型數(shù)據(jù)庫也支持類似的聯(lián)合索引的功能。Elasticsearch 支持以上兩種的聯(lián)合索引方式，如果查詢的 filter 緩存到了內(nèi)存中(以 bitset 的形式)，那么合并就是兩個(gè) bitset 的 AND。如果查詢的 filter 沒有緩存，那么就用 skip list 的方式去遍歷兩個(gè) on disk 的 posting list。

利用 Skip List 合并

以上是三個(gè) posting list。我們現(xiàn)在需要把它們用 AND 的關(guān)系合并，得出 posting list 的交集。首先選擇最短的 posting list，然后從小到大遍歷。遍歷的過程可以跳過一些元素，比如我們遍歷到綠色的 13 的時(shí)候，就可以跳過藍(lán)色的 3 了，因?yàn)?3 比 13 要小。

整個(gè)過程如下

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

最后得出的交集是 [13,98]，所需的時(shí)間比完整遍歷三個(gè) posting list 要快得多。但是前提是每個(gè) list 需要指出 Advance 這個(gè)操作，快速移動(dòng)指向的位置。什么樣的 list 可以這樣 Advance 往前做蛙跳?skip list：

從概念上來說，對(duì)于一個(gè)很長的 posting list，比如：

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

我們可以把這個(gè) list 分成三個(gè) block：

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

然后可以構(gòu)建出 skip list 的第二層：

[1,101,255]

1,101,255 分別指向自己對(duì)應(yīng)的 block。這樣就可以很快地跨 block 的移動(dòng)指向位置了。

Lucene 自然會(huì)對(duì)這個(gè) block 再次進(jìn)行壓縮。其壓縮方式叫做 Frame Of Reference 編碼。

示例如下：考慮到頻繁出現(xiàn)的 term(所謂 low cardinality 的值)，比如 gender 里的男或者女。如果有 1 百萬個(gè)文檔，那么性別為男的 posting list 里就會(huì)有 50 萬個(gè) int 值。用 Frame of Reference 編碼進(jìn)行壓縮可以極大減少磁盤占用。這個(gè)優(yōu)化對(duì)于減少索引尺寸有非常重要的意義。當(dāng)然 mysql b-tree 里也有一個(gè)類似的 posting list 的東西，是未經(jīng)過這樣壓縮的。

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

利用 bitset 合并

Bitset 是一種很直觀的數(shù)據(jù)結(jié)構(gòu)，對(duì)應(yīng) posting list 如：

[1,3,4,7,10]

對(duì)應(yīng)的 bitset 就是：

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

每個(gè)文檔按照文檔 id 排序?qū)?yīng)其中的一個(gè) bit。Bitset 自身就有壓縮的特點(diǎn)，其用一個(gè) byte 就可以代表 8 個(gè)文檔。所以 100 萬個(gè)文檔只需要 12.5 萬個(gè) byte。但是考慮到文檔可能有數(shù)十億之多，在內(nèi)存里保存 bitset 仍然是很奢侈的事情。而且對(duì)于個(gè)每一個(gè) filter 都要消耗一個(gè) bitset，比如 age=18 緩存起來的話是一個(gè) bitset，18<=age<25 是另外一個(gè) filter 緩存起來也要一個(gè) bitset。

所以秘訣就在于需要有一個(gè)數(shù)據(jù)結(jié)構(gòu)：

• 可以很壓縮地保存上億個(gè) bit 代表對(duì)應(yīng)的文檔是否匹配 filter;
• 這個(gè)壓縮的 bitset 仍然可以很快地進(jìn)行 AND 和 OR 的邏輯操作。

Lucene 使用的這個(gè)數(shù)據(jù)結(jié)構(gòu)叫做 Roaring Bitmap。

其壓縮的思路其實(shí)很簡單。與其保存 100 個(gè) 0，占用 100 個(gè) bit。還不如保存 0 一次，然后聲明這個(gè) 0 重復(fù)了 100 遍。

這兩種合并使用索引的方式都有其用途。Elasticsearch 對(duì)其性能有詳細(xì)的對(duì)比( https://www.elastic.co/blog/frame-of-reference-and-roaring-bitmaps )。簡單的結(jié)論是：因?yàn)? Frame of Reference 編碼是如此 高效，對(duì)于簡單的相等條件的過濾緩存成純內(nèi)存的 bitset 還不如需要訪問磁盤的 skip list 的方式要快。

如何減少文檔數(shù)?

一種常見的壓縮存儲(chǔ)時(shí)間序列的方式是把多個(gè)數(shù)據(jù)點(diǎn)合并成一行。Opentsdb 支持海量數(shù)據(jù)的一個(gè)絕招就是定期把很多行數(shù)據(jù)合并成一行，這個(gè)過程叫 compaction。類似的 vivdcortext 使用 mysql 存儲(chǔ)的時(shí)候，也把一分鐘的很多數(shù)據(jù)點(diǎn)合并存儲(chǔ)到 mysql 的一行里以減少行數(shù)。

這個(gè)過程可以示例如下：

合并之后就變成了：

可以看到，行變成了列了。每一列可以代表這一分鐘內(nèi)一秒的數(shù)據(jù)。

Elasticsearch 有一個(gè)功能可以實(shí)現(xiàn)類似的優(yōu)化效果，那就是 Nested Document。我們可以把一段時(shí)間的很多個(gè)數(shù)據(jù)點(diǎn)打包存儲(chǔ)到一個(gè)父文檔里，變成其嵌套的子文檔。示例如下：

{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} 
   ] 
} 

這樣可以把數(shù)據(jù)點(diǎn)公共的維度字段上移到父文檔里，而不用在每個(gè)子文檔里重復(fù)存儲(chǔ)，從而減少索引的尺寸。

在存儲(chǔ)的時(shí)候，無論父文檔還是子文檔，對(duì)于 Lucene 來說都是文檔，都會(huì)有文檔 Id。但是對(duì)于嵌套文檔來說，可以保存起子文檔和父文檔的文檔 id 是連續(xù)的，而且父文檔總是最后一個(gè)。有這樣一個(gè)排序性作為保障，那么有一個(gè)所有父文檔的 posting list 就可以跟蹤所有的父子關(guān)系。也可以很容易地在父子文檔 id 之間做轉(zhuǎn)換。把父子關(guān)系也理解為一個(gè) filter，那么查詢時(shí)檢索的時(shí)候不過是又 AND 了另外一個(gè) filter 而已。前面我們已經(jīng)看到了 Elasticsearch 可以非常高效地處理多 filter 的情況，充分利用底層的索引。

使用了嵌套文檔之后，對(duì)于 term 的 posting list 只需要保存父文檔的 doc id 就可以了，可以比保存所有的數(shù)據(jù)點(diǎn)的 doc id 要少很多。如果我們可以在一個(gè)父文檔里塞入 50 個(gè)嵌套文檔，那么 posting list 可以變成之前的 1/50。