5000字詳述Elasticsearch倒排索引算法(建議收藏)
來(lái)源：博客園?
鏈接：
https://www.cnblogs.com/dreamroute/p/8484457.html
介紹
Elasticsearch 是一個(gè)分布式可擴(kuò)展的實(shí)時(shí)搜索和分析引擎,一個(gè)建立在全文搜索引擎 Apache Lucene(TM) 基礎(chǔ)上的搜索引擎.當(dāng)然 Elasticsearch 并不僅僅是 Lucene 那么簡(jiǎn)單，它不僅包括了全文搜索功能，還可以進(jìn)行以下工作:
分布式實(shí)時(shí)文件存儲(chǔ)，并將每一個(gè)字段都編入索引，使其可以被搜索。
實(shí)時(shí)分析的分布式搜索引擎。
可以擴(kuò)展到上百臺(tái)服務(wù)器，處理PB級(jí)別的結(jié)構(gòu)化或非結(jié)構(gòu)化數(shù)據(jù)。
基本概念
先說(shuō)Elasticsearch的文件存儲(chǔ)，Elasticsearch是面向文檔型數(shù)據(jù)庫(kù)，一條數(shù)據(jù)在這里就是一個(gè)文檔，用JSON作為文檔序列化的格式，比如下面這條用戶數(shù)據(jù)：
{
"name" : "John",
"sex" : "Male",
"age" : 25,
"birthDate": "1990/05/01",
"about" : "I love to go rock climbing",
"interests": [ "sports", "music" ]
}
用Mysql這樣的數(shù)據(jù)庫(kù)存儲(chǔ)就會(huì)容易想到建立一張User表，有balabala的字段等，在Elasticsearch里這就是一個(gè)文檔，當(dāng)然這個(gè)文檔會(huì)屬于一個(gè)User的類型，各種各樣的類型存在于一個(gè)索引當(dāng)中。這里有一份簡(jiǎn)易的將Elasticsearch和關(guān)系型數(shù)據(jù)術(shù)語(yǔ)對(duì)照表:
關(guān)系數(shù)據(jù)庫(kù) ? 數(shù)據(jù)庫(kù) ? 表 ? 行 ? 列(Columns)
Elasticsearch ? 索引(Index) ? 類型(type) ? 文檔(Docments) ? 字段(Fields)
一個(gè) Elasticsearch 集群可以包含多個(gè)索引(數(shù)據(jù)庫(kù))，也就是說(shuō)其中包含了很多類型(表)。這些類型中包含了很多的文檔(行)，然后每個(gè)文檔中又包含了很多的字段(列)。Elasticsearch的交互，可以使用Java API，也可以直接使用HTTP的Restful API方式，比如我們打算插入一條記錄，可以簡(jiǎn)單發(fā)送一個(gè)HTTP的請(qǐng)求：
PUT /megacorp/employee/1
{
"name" : "John",
"sex" : "Male",
"age" : 25,
"about" : "I love to go rock climbing",
"interests": [ "sports", "music" ]
}
更新，查詢也是類似這樣的操作，具體操作手冊(cè)可以參見(jiàn)Elasticsearch權(quán)威指南
索引
Elasticsearch最關(guān)鍵的就是提供強(qiáng)大的索引能力了，其實(shí)InfoQ的這篇時(shí)間序列數(shù)據(jù)庫(kù)的秘密(2)——索引寫(xiě)的非常好，我這里也是圍繞這篇結(jié)合自己的理解進(jìn)一步梳理下，也希望可以幫助大家更好的理解這篇文章。
Elasticsearch索引的精髓：
一切設(shè)計(jì)都是為了提高搜索的性能
另一層意思：為了提高搜索的性能，難免會(huì)犧牲某些其他方面，比如插入/更新，否則其他數(shù)據(jù)庫(kù)不用混了。前面看到往Elasticsearch里插入一條記錄，其實(shí)就是直接PUT一個(gè)json的對(duì)象，這個(gè)對(duì)象有多個(gè)fields，比如上面例子中的name, sex, age, about, interests，那么在插入這些數(shù)據(jù)到Elasticsearch的同時(shí)，Elasticsearch還默默1的為這些字段建立索引--倒排索引，因?yàn)镋lasticsearch最核心功能是搜索。
Elasticsearch是如何做到快速索引的
InfoQ那篇文章里說(shuō)Elasticsearch使用的倒排索引比關(guān)系型數(shù)據(jù)庫(kù)的B-Tree索引快，為什么呢？
什么是B-Tree索引?
上大學(xué)讀書(shū)時(shí)老師教過(guò)我們，二叉樹(shù)查找效率是logN，同時(shí)插入新的節(jié)點(diǎn)不必移動(dòng)全部節(jié)點(diǎn)，所以用樹(shù)型結(jié)構(gòu)存儲(chǔ)索引，能同時(shí)兼顧插入和查詢的性能。因此在這個(gè)基礎(chǔ)上，再結(jié)合磁盤(pán)的讀取特性(順序讀/隨機(jī)讀)，傳統(tǒng)關(guān)系型數(shù)據(jù)庫(kù)采用了B-Tree/B+Tree這樣的數(shù)據(jù)結(jié)構(gòu)：
為了提高查詢的效率，減少磁盤(pán)尋道次數(shù)，將多個(gè)值作為一個(gè)數(shù)組通過(guò)連續(xù)區(qū)間存放，一次尋道讀取多個(gè)數(shù)據(jù)，同時(shí)也降低樹(shù)的高度。
什么是倒排索引?
繼續(xù)上面的例子，假設(shè)有這么幾條數(shù)據(jù)(為了簡(jiǎn)單，去掉about, interests這兩個(gè)field):
| ID | Name | Age | Sex |
| -- |:------------:| -----:| -----:|
| 1 | Kate | 24 | Female
| 2 | John | 24 | Male
| 3 | Bill | 29 | Male
ID是Elasticsearch自建的文檔id，那么Elasticsearch建立的索引如下:
Name:
| Term | Posting List |
| -- |:----:|
| Kate | 1 |
| John | 2 |
| Bill | 3 |
Age:
| Term | Posting List |
| -- |:----:|
| 24 | [1,2] |
| 29 | 3 |
Sex:
| Term | Posting List |
| -- |:----:|
| Female | 1 |
| Male | [2,3] |
Posting List
Elasticsearch分別為每個(gè)field都建立了一個(gè)倒排索引，Kate, John, 24, Female這些叫term，而[1,2]就是Posting List。Posting list就是一個(gè)int的數(shù)組，存儲(chǔ)了所有符合某個(gè)term的文檔id。
看到這里，不要認(rèn)為就結(jié)束了，精彩的部分才剛開(kāi)始...
通過(guò)posting list這種索引方式似乎可以很快進(jìn)行查找，比如要找age=24的同學(xué)，愛(ài)回答問(wèn)題的小明馬上就舉手回答：我知道，id是1，2的同學(xué)。但是，如果這里有上千萬(wàn)的記錄呢？如果是想通過(guò)name來(lái)查找呢？
Term Dictionary
Elasticsearch為了能快速找到某個(gè)term，將所有的term排個(gè)序，二分法查找term，logN的查找效率，就像通過(guò)字典查找一樣，這就是Term Dictionary?，F(xiàn)在再看起來(lái)，似乎和傳統(tǒng)數(shù)據(jù)庫(kù)通過(guò)B-Tree的方式類似啊，為什么說(shuō)比B-Tree的查詢快呢？
Term Index
B-Tree通過(guò)減少磁盤(pán)尋道次數(shù)來(lái)提高查詢性能，Elasticsearch也是采用同樣的思路，直接通過(guò)內(nèi)存查找term，不讀磁盤(pán)，但是如果term太多，term dictionary也會(huì)很大，放內(nèi)存不現(xiàn)實(shí)，于是有了Term Index，就像字典里的索引頁(yè)一樣，A開(kāi)頭的有哪些term，分別在哪頁(yè)，可以理解term index是一顆樹(shù)：
這棵樹(shù)不會(huì)包含所有的term，它包含的是term的一些前綴。通過(guò)term index可以快速地定位到term dictionary的某個(gè)offset，然后從這個(gè)位置再往后順序查找。
所以term index不需要存下所有的term，而僅僅是他們的一些前綴與Term Dictionary的block之間的映射關(guān)系，再結(jié)合FST(Finite State Transducers)的壓縮技術(shù)，可以使term index緩存到內(nèi)存中。從term index查到對(duì)應(yīng)的term dictionary的block位置之后，再去磁盤(pán)上找term，大大減少了磁盤(pán)隨機(jī)讀的次數(shù)。
這時(shí)候愛(ài)提問(wèn)的小明又舉手了:"那個(gè)FST是神馬東東啊?"
一看就知道小明是一個(gè)上大學(xué)讀書(shū)的時(shí)候跟我一樣不認(rèn)真聽(tīng)課的孩子，數(shù)據(jù)結(jié)構(gòu)老師一定講過(guò)什么是FST。但沒(méi)辦法，我也忘了，這里再補(bǔ)下課：
FSTs are finite-state machines that?map?a?term (byte sequence)?to an arbitrary?output.
假設(shè)我們現(xiàn)在要將mop, moth, pop, star, stop and top(term index里的term前綴)映射到序號(hào)：0，1，2，3，4，5(term dictionary的block位置)。最簡(jiǎn)單的做法就是定義個(gè)Map
??表示一種狀態(tài)
-->表示狀態(tài)的變化過(guò)程，上面的字母/數(shù)字表示狀態(tài)變化和權(quán)重
將單詞分成單個(gè)字母通過(guò)??和-->表示出來(lái)，0權(quán)重不顯示。如果??后面出現(xiàn)分支，就標(biāo)記權(quán)重，最后整條路徑上的權(quán)重加起來(lái)就是這個(gè)單詞對(duì)應(yīng)的序號(hào)。
FSTs are finite-state machines that map a term (byte sequence) to an arbitrary output.
FST以字節(jié)的方式存儲(chǔ)所有的term，這種壓縮方式可以有效的縮減存儲(chǔ)空間，使得term index足以放進(jìn)內(nèi)存，但這種方式也會(huì)導(dǎo)致查找時(shí)需要更多的CPU資源。
后面的更精彩，看累了的同學(xué)可以喝杯咖啡……
壓縮技巧
Elasticsearch里除了上面說(shuō)到用FST壓縮term index外，對(duì)posting list也有壓縮技巧。?
小明喝完咖啡又舉手了:"posting list不是已經(jīng)只存儲(chǔ)文檔id了嗎？還需要壓縮？"
嗯，我們?cè)倏椿刈铋_(kāi)始的例子，如果Elasticsearch需要對(duì)同學(xué)的性別進(jìn)行索引(這時(shí)傳統(tǒng)關(guān)系型數(shù)據(jù)庫(kù)已經(jīng)哭暈在廁所……)，會(huì)怎樣？如果有上千萬(wàn)個(gè)同學(xué)，而世界上只有男/女這樣兩個(gè)性別，每個(gè)posting list都會(huì)有至少百萬(wàn)個(gè)文檔id。Elasticsearch是如何有效的對(duì)這些文檔id壓縮的呢？
Frame Of Reference
增量編碼壓縮，將大數(shù)變小數(shù)，按字節(jié)存儲(chǔ)
首先，Elasticsearch要求posting list是有序的(為了提高搜索的性能，再任性的要求也得滿足)，這樣做的一個(gè)好處是方便壓縮，看下面這個(gè)圖例：?
如果數(shù)學(xué)不是體育老師教的話，還是比較容易看出來(lái)這種壓縮技巧的。
未壓縮之前，6個(gè)整數(shù)，每個(gè)整數(shù)用4個(gè)字節(jié)壓縮，一共需要24個(gè)字節(jié)；通過(guò)將數(shù)據(jù)增量編碼，將73，300，302...，變成73, 227, 2，沒(méi)有丟掉數(shù)據(jù)信息的情況下，將數(shù)據(jù)減小。標(biāo)識(shí)位8，本身需要一個(gè)字節(jié)空間，表示73,227,2每個(gè)數(shù)都用8bit =?1byte來(lái)存儲(chǔ)，需要1byte * 3 = 3bytes內(nèi)存空間來(lái)存儲(chǔ)，標(biāo)識(shí)位5，本身需要1個(gè)字節(jié)空間存儲(chǔ)，表示30，11，29都用5bit來(lái)存儲(chǔ)，5bit * 3 = 15bit，但是需要16bit = 2bytes來(lái)存儲(chǔ)，那么8，73,227,2，5，30，11，29,一共需要1 +?3?+ 1 + 2 = 7bytes空間即可。
原理就是通過(guò)增量，將原來(lái)的大數(shù)變成小數(shù)僅存儲(chǔ)增量值，再精打細(xì)算按bit排好隊(duì)，最后通過(guò)字節(jié)存儲(chǔ)，而不是大大咧咧的盡管是2也是用int(4個(gè)字節(jié))來(lái)存儲(chǔ)。
Roaring bitmaps
說(shuō)到Roaring bitmaps，就必須先從bitmap說(shuō)起。Bitmap是一種數(shù)據(jù)結(jié)構(gòu)，假設(shè)有某個(gè)posting list：
[1,3,4,7,10]
對(duì)應(yīng)的bitmap就是：
[1,0,1,1,0,0,1,0,0,1]
非常直觀，用0/1表示某個(gè)值是否存在，比如10這個(gè)值就對(duì)應(yīng)第10位，對(duì)應(yīng)的bit值是1，這樣用一個(gè)字節(jié)就可以代表8個(gè)文檔id，舊版本(5.0之前)的Lucene就是用這樣的方式來(lái)壓縮的，但這樣的壓縮方式仍然不夠高效，如果有1億個(gè)文檔，那么需要12.5MB的存儲(chǔ)空間，這僅僅是對(duì)應(yīng)一個(gè)索引字段(我們往往會(huì)有很多個(gè)索引字段)。于是有人想出了Roaring bitmaps這樣更高效的數(shù)據(jù)結(jié)構(gòu)。
Bitmap的缺點(diǎn)是存儲(chǔ)空間隨著文檔個(gè)數(shù)線性增長(zhǎng)，Roaring bitmaps需要打破這個(gè)魔咒就一定要用到某些指數(shù)特性：
將posting list按照65535為界限分塊，比如第一塊所包含的文檔id范圍在0~65535之間，第二塊的id范圍是65536~131071，以此類推。再用<商，余數(shù)>的組合表示每一組id，這樣每組里的id范圍都在0~65535內(nèi)了，剩下的就好辦了，既然每組id不會(huì)變得無(wú)限大，那么我們就可以通過(guò)最有效的方式對(duì)這里的id存儲(chǔ)。
細(xì)心的小明這時(shí)候又舉手了:"為什么是以65535為界限?"
程序員的世界里除了1024外，65535也是一個(gè)經(jīng)典值，因?yàn)樗?2^16-1，正好是用2個(gè)字節(jié)能表示的最大數(shù)，一個(gè)short的存儲(chǔ)單位，注意到上圖里的最后一行“If a block has more than 4096 values, encode as a bit set, and otherwise as a simple array using 2 bytes per value”，如果是大塊，用節(jié)省點(diǎn)用bitset存，小塊就豪爽點(diǎn)，2個(gè)字節(jié)我也不計(jì)較了，用一個(gè)short[]存著方便。
那為什么用4096來(lái)區(qū)分大塊還是小塊呢？
個(gè)人理解：都說(shuō)程序員的世界是二進(jìn)制的，4096*2bytes ＝ 8192bytes < 1KB, 磁盤(pán)一次尋道可以順序把一個(gè)小塊的內(nèi)容都讀出來(lái)，再大一位就超過(guò)1KB了，需要兩次讀。
聯(lián)合索引
上面說(shuō)了半天都是單field索引，如果多個(gè)field索引的聯(lián)合查詢，倒排索引如何滿足快速查詢的要求呢？
利用跳表(Skip list)的數(shù)據(jù)結(jié)構(gòu)快速做“與”運(yùn)算，或者
利用上面提到的bitset按位“與”
先看看跳表的數(shù)據(jù)結(jié)構(gòu)：
將一個(gè)有序鏈表level0，挑出其中幾個(gè)元素到level1及l(fā)evel2，每個(gè)level越往上，選出來(lái)的指針元素越少，查找時(shí)依次從高level往低查找，比如55，先找到level2的31，再找到level1的47，最后找到55，一共3次查找，查找效率和2叉樹(shù)的效率相當(dāng)，但也是用了一定的空間冗余來(lái)?yè)Q取的。
假設(shè)有下面三個(gè)posting list需要聯(lián)合索引：
如果使用跳表，對(duì)最短的posting list中的每個(gè)id，逐個(gè)在另外兩個(gè)posting list中查找看是否存在，最后得到交集的結(jié)果。
如果使用bitset，就很直觀了，直接按位與，得到的結(jié)果就是最后的交集。
總結(jié)和思考
Elasticsearch的索引思路:
將磁盤(pán)里的東西盡量搬進(jìn)內(nèi)存，減少磁盤(pán)隨機(jī)讀取次數(shù)(同時(shí)也利用磁盤(pán)順序讀特性)，結(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)不利于查詢
關(guān)于最后一點(diǎn)，個(gè)人認(rèn)為有多個(gè)因素:
其中一個(gè)(也許不是最重要的)因素: 上面看到的壓縮算法，都是對(duì)Posting list里的大量ID進(jìn)行壓縮的，那如果ID是順序的，或者是有公共前綴等具有一定規(guī)律性的ID，壓縮比會(huì)比較高；
全文檢索
前面是針對(duì)單個(gè)字段，name,age說(shuō)明的快速索引解決方案，elastic通常是全文檢索，文檔類型的，通常需要將文檔分詞。比如有這樣2個(gè)文檔：
The quick brown fox jumped over the lazy dog
Quick brown foxes leap over lazy dogs in summer
為了創(chuàng)建倒排索引，我們首先將每個(gè)文檔的 content 域拆分成單獨(dú)的 詞（我們稱它為 詞條 或 tokens ），創(chuàng)建一個(gè)包含所有不重復(fù)詞條的排序列表，然后列出每個(gè)詞條出現(xiàn)在哪個(gè)文檔。結(jié)果如下所示：
Term ? ? ?Doc_1 ?Doc_2-------------------------Quick ? | ? ? ? | ?XThe ? ? | ? X ? |brown ? | ? X ? | ?Xdog ? ? | ? X ? |dogs ? ?| ? ? ? | ?Xfox ? ? | ? X ? |foxes ? | ? ? ? | ?Xin ? ? ?| ? ? ? | ?Xjumped ?| ? X ? |lazy ? ?| ? X ? | ?Xleap ? ?| ? ? ? | ?Xover ? ?| ? X ? | ?Xquick ? | ? X ? |summer ?| ? ? ? | ?Xthe ? ? | ? X ? |
那么，對(duì)于brown這個(gè)詞來(lái)說(shuō)，Posting list就是[1, 2]，quick的Posting list就是[2]，當(dāng)然了，對(duì)于大小寫(xiě)，同義詞都是要考慮的，這樣就變成了前面的單個(gè)詞那樣，同樣利用倒排索引，增量編碼，大數(shù)變小數(shù)，使用字節(jié)存儲(chǔ)。
--end--