如何快速檢索色建？
Elasticsearch是通過(guò)Lucene的倒排索引技術(shù)實(shí)現(xiàn)比關(guān)系型數(shù)據(jù)庫(kù)更快的過(guò)濾及穗。特別是它對(duì)多條件的過(guò)濾支持非常好，比如年齡在18和30之間暑诸，性別為女性這樣的組合查詢(xún)棘捣。倒排索引很多地方都有介紹抛杨，但是其比關(guān)系型數(shù)據(jù)庫(kù)的b-tree索引快在哪里耘眨？到底為什么快呢像云？
籠統(tǒng)的來(lái)說(shuō)剂癌，b-tree索引是為寫(xiě)入優(yōu)化的索引結(jié)構(gòu)淤翔。當(dāng)我們不需要支持快速的更新的時(shí)候，可以用預(yù)先排序等方式換取更小的存儲(chǔ)空間佩谷，更快的檢索速度等好處旁壮，其代價(jià)就是更新慢。要進(jìn)一步深入的化谐檀，還是要看一下Lucene的倒排索引是怎么構(gòu)成的抡谐。
這里有好幾個(gè)概念。我們來(lái)看一個(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)閠erm沒(méi)有排序惶傻，需要全部過(guò)濾一遍才能找出特定的term。排序之后就變成了：
Ada,Carla,Elin,Kate,Patty,Sara,Selena
這樣我們可以用二分查找的方式其障，比全遍歷更快地找出目標(biāo)的term银室。這個(gè)就是 term dictionary。有了term dictionary之后励翼，可以用 logN 次磁盤(pán)查找得到目標(biāo)蜈敢。但是磁盤(pán)的隨機(jī)讀操作仍然是非常昂貴的（一次random access大概需要10ms的時(shí)間）。所以盡量少的讀磁盤(pán)汽抚，有必要把一些數(shù)據(jù)緩存到內(nèi)存里抓狭。但是整個(gè)term dictionary本身又太大了，無(wú)法完整地放到內(nèi)存里造烁。于是就有了term index否过。term index有點(diǎn)像一本字典的大的章節(jié)表。比如：
A開(kāi)頭的term ……………. Xxx頁(yè)
C開(kāi)頭的term ……………. Xxx頁(yè)
E開(kāi)頭的term ……………. Xxx頁(yè)
如果所有的term都是英文字符的話(huà)惭蟋，可能這個(gè)term index就真的是26個(gè)英文字符表構(gòu)成的了苗桂。但是實(shí)際的情況是，term未必都是英文字符告组，term可以是任意的byte數(shù)組煤伟。而且26個(gè)英文字符也未必是每一個(gè)字符都有均等的term，比如x字符開(kāi)頭的term可能一個(gè)都沒(méi)有木缝，而s開(kāi)頭的term又特別多便锨。實(shí)際的term index是一棵trie 樹(shù)：
例子是一個(gè)包含 "A", "to", "tea", "ted", "ten", "i", "in", 和 "inn" 的 trie 樹(shù)。這棵樹(shù)不會(huì)包含所有的term我碟，它包含的是term的一些前綴放案。通過(guò)term index可以快速地定位到term dictionary的某個(gè)offset，然后從這個(gè)位置再往后順序查找矫俺。再加上一些壓縮技術(shù)（搜索 Lucene Finite State Transducers） term index 的尺寸可以只有所有term的尺寸的幾十分之一吱殉，使得用內(nèi)存緩存整個(gè)term index變成可能。整體上來(lái)說(shuō)就是這樣的效果恳守。
現(xiàn)在我們可以回答“為什么Elasticsearch/Lucene檢索可以比mysql快了考婴。Mysql只有term dictionary這一層，是以b-tree排序的方式存儲(chǔ)在磁盤(pán)上的催烘。檢索一個(gè)term需要若干次的random access的磁盤(pán)操作沥阱。而Lucene在term dictionary的基礎(chǔ)上添加了term index來(lái)加速檢索，term index以樹(shù)的形式緩存在內(nèi)存中伊群。從term index查到對(duì)應(yīng)的term dictionary的block位置之后考杉，再去磁盤(pán)上找term策精，大大減少了磁盤(pán)的random access次數(shù)。
額外值得一提的兩點(diǎn)是：term index在內(nèi)存中是以FST（finite state transducers）的形式保存的崇棠，其特點(diǎn)是非常節(jié)省內(nèi)存咽袜。Term dictionary在磁盤(pán)上是以分block的方式保存的，一個(gè)block內(nèi)部利用公共前綴壓縮枕稀，比如都是Ab開(kāi)頭的單詞就可以把Ab省去询刹。這樣term dictionary可以比b-tree更節(jié)約磁盤(pán)空間。
如何聯(lián)合索引查詢(xún)萎坷？
所以給定查詢(xún)過(guò)濾條件 age=18 的過(guò)程就是先從term index找到18在term dictionary的大概位置凹联，然后再?gòu)膖erm dictionary里精確地找到18這個(gè)term，然后得到一個(gè)posting list或者一個(gè)指向posting list位置的指針哆档。然后再查詢(xún) gender=女 的過(guò)程也是類(lèi)似的蔽挠。最后得出 age=18 AND gender=女 就是把兩個(gè) posting list 做一個(gè)“與”的合并。
這個(gè)理論上的“與”合并的操作可不容易瓜浸。對(duì)于mysql來(lái)說(shuō)澳淑，如果你給age和gender兩個(gè)字段都建立了索引，查詢(xún)的時(shí)候只會(huì)選擇其中最selective的來(lái)用插佛，然后另外一個(gè)條件是在遍歷行的過(guò)程中在內(nèi)存中計(jì)算之后過(guò)濾掉杠巡。那么要如何才能聯(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 版本開(kāi)始支持通過(guò)bitmap聯(lián)合使用兩個(gè)索引识腿，就是利用了bitset數(shù)據(jù)結(jié)構(gòu)來(lái)做到的。當(dāng)然一些商業(yè)的關(guān)系型數(shù)據(jù)庫(kù)也支持類(lèi)似的聯(lián)合索引的功能造壮。Elasticsearch支持以上兩種的聯(lián)合索引方式渡讼，如果查詢(xún)的filter緩存到了內(nèi)存中（以bitset的形式），那么合并就是兩個(gè)bitset的AND耳璧。如果查詢(xún)的filter沒(méi)有緩存成箫，那么就用skip list的方式去遍歷兩個(gè)on disk的posting list。
利用 Skip List 合并
以上是三個(gè)posting list旨枯。我們現(xiàn)在需要把它們用AND的關(guān)系合并蹬昌，得出posting list的交集。首先選擇最短的posting list攀隔，然后從小到大遍歷皂贩。遍歷的過(guò)程可以跳過(guò)一些元素栖榨，比如我們遍歷到綠色的13的時(shí)候，就可以跳過(guò)藍(lán)色的3了明刷，因?yàn)?比13要小婴栽。
整個(gè)過(guò)程如下
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：
從概念上來(lái)說(shuō)准脂，對(duì)于一個(gè)很長(zhǎng)的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百萬(wàn)個(gè)文檔广料，那么性別為男的posting list里就會(huì)有50萬(wàn)個(gè)int值砾脑。用Frame of Reference編碼進(jìn)行壓縮可以極大減少磁盤(pán)占用。這個(gè)優(yōu)化對(duì)于減少索引尺寸有非常重要的意義艾杏。當(dāng)然mysql b-tree里也有一個(gè)類(lèi)似的posting list的東西韧衣，是未經(jīng)過(guò)這樣壓縮的。
因?yàn)檫@個(gè)Frame of Reference的編碼是有解壓縮成本的购桑。利用skip list畅铭，除了跳過(guò)了遍歷的成本，也跳過(guò)了解壓縮這些壓縮過(guò)的block的過(guò)程勃蜘，從而節(jié)省了cpu硕噩。
利用bitset合并
Bitset是一種很直觀(guān)的數(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萬(wàn)個(gè)文檔只需要12.5萬(wàn)個(gè)byte阳惹。但是考慮到文檔可能有數(shù)十億之多谍失，在內(nèi)存里保存bitset仍然是很奢侈的事情。而且對(duì)于個(gè)每一個(gè)filter都要消耗一個(gè)bitset莹汤，比如age=18緩存起來(lái)的話(huà)是一個(gè)bitset快鱼，18<=age<25是另外一個(gè)filter緩存起來(lái)也要一個(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í)很簡(jiǎn)單。與其保存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ǎn)單的結(jié)論是：因?yàn)镕rame of Reference編碼是如此 高效跨蟹，對(duì)于簡(jiǎn)單的相等條件的過(guò)濾緩存成純內(nèi)存的bitset還不如需要訪(fǎng)問(wèn)磁盤(pán)的skip list的方式要快雳殊。
如何減少文檔數(shù)？
一種常見(jiàn)的壓縮存儲(chǔ)時(shí)間序列的方式是把多個(gè)數(shù)據(jù)點(diǎn)合并成一行窗轩。Opentsdb支持海量數(shù)據(jù)的一個(gè)絕招就是定期把很多行數(shù)據(jù)合并成一行夯秃，這個(gè)過(guò)程叫compaction。類(lèi)似的vivdcortext使用mysql存儲(chǔ)的時(shí)候痢艺，也把一分鐘的很多數(shù)據(jù)點(diǎn)合并存儲(chǔ)到mysql的一行里以減少行數(shù)仓洼。
這個(gè)過(guò)程可以示例如下：
可以看到，行變成了列了堤舒。每一列可以代表這一分鐘內(nèi)一秒的數(shù)據(jù)色建。
Elasticsearch有一個(gè)功能可以實(shí)現(xiàn)類(lèi)似的優(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í)候卸留，無(wú)論父文檔還是子文檔走越，對(duì)于Lucene來(lái)說(shuō)都是文檔，都會(huì)有文檔Id耻瑟。但是對(duì)于嵌套文檔來(lái)說(shuō)，可以保存起子文檔和父文檔的文檔id是連續(xù)的赏酥，而且父文檔總是最后一個(gè)喳整。有這樣一個(gè)排序性作為保障，那么有一個(gè)所有父文檔的posting list就可以跟蹤所有的父子關(guān)系裸扶。也可以很容易地在父子文檔id之間做轉(zhuǎn)換框都。把父子關(guān)系也理解為一個(gè)filter，那么查詢(xún)時(shí)檢索的時(shí)候不過(guò)是又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檩咱。
