原文地址：https://neway6655.github.io/elasticsearch/2015/09/11/elasticsearch-study-notes.html

最近在參與一個(gè)基于Elasticsearch作為底層數(shù)據(jù)框架提供大數(shù)據(jù)量(億級(jí))的實(shí)時(shí)統(tǒng)計(jì)查詢的方案設(shè)計(jì)工作梨睁，花了些時(shí)間學(xué)習(xí)Elasticsearch的基礎(chǔ)理論知識(shí)人灼，整理了一下瓷马，希望能對Elasticsearch感興趣/想了解的同學(xué)有所幫助备蚓。 同時(shí)也希望有發(fā)現(xiàn)內(nèi)容不正確或者有疑問的地方距淫，望指明厚柳，一起探討军熏，學(xué)習(xí)凌简，進(jìn)步。

介紹

Elasticsearch 是一個(gè)分布式可擴(kuò)展的實(shí)時(shí)搜索和分析引擎.

Elasticsearch 是一個(gè)建立在全文搜索引擎 Apache Lucene(TM) 基礎(chǔ)上的搜索引擎. 當(dāng)然 Elasticsearch 并不僅僅是 Lucene 那么簡單寿冕，它不僅包括了全文搜索功能蕊程，還可以進(jìn)行以下工作:

分布式實(shí)時(shí)文件存儲(chǔ)，并將每一個(gè)字段都編入索引驼唱，使其可以被搜索藻茂。

實(shí)時(shí)分析的分布式搜索引擎。

可以擴(kuò)展到上百臺(tái)服務(wù)器玫恳，處理PB級(jí)別的結(jié)構(gòu)化或非結(jié)構(gòu)化數(shù)據(jù)辨赐。

基本概念

先說Elasticsearch的文件存儲(chǔ)，Elasticsearch是面向文檔型數(shù)據(jù)庫京办，一條數(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ù)庫存儲(chǔ)就會(huì)容易想到建立一張User表臂港，有balabala的字段等森枪，在Elasticsearch里這就是一個(gè)文檔，當(dāng)然這個(gè)文檔會(huì)屬于一個(gè)User的類型审孽，各種各樣的類型存在于一個(gè)索引當(dāng)中县袱。這里有一份簡易的將Elasticsearch和關(guān)系型數(shù)據(jù)術(shù)語對照表:

關(guān)系數(shù)據(jù)庫 ? 數(shù)據(jù)庫 ? 表 ? 行 ? 列(Columns)

Elasticsearch ? 索引 ? 類型 ? 文檔 ? 字段(Fields)

一個(gè) Elasticsearch 集群可以包含多個(gè)索引(數(shù)據(jù)庫)佑力，也就是說其中包含了很多類型(表)。這些類型中包含了很多的文檔(行)打颤，然后每個(gè)文檔中又包含了很多的字段(列)漓滔。

Elasticsearch的交互，可以使用Java API乖篷，也可以直接使用HTTP的Restful API方式响驴，比如我們打算插入一條記錄，可以簡單發(fā)送一個(gè)HTTP的請求：

PUT /megacorp/employee/1{? ? "name" :? ? "John",? ? "sex" :? ? ? "Male",? ? "age" :? ? ? 25,? ? "about" :? ? "I love to go rock climbing",? ? "interests": [ "sports", "music" ]}

更新豁鲤，查詢也是類似這樣的操作，具體操作手冊可以參見Elasticsearch權(quán)威指南

索引

Elasticsearch最關(guān)鍵的就是提供強(qiáng)大的索引能力了琳骡，其實(shí)InfoQ的這篇時(shí)間序列數(shù)據(jù)庫的秘密(2)——索引寫的非常好，我這里也是圍繞這篇結(jié)合自己的理解進(jìn)一步梳理下讼溺，也希望可以幫助大家更好的理解這篇文章楣号。

Elasticsearch索引的精髓：

一切設(shè)計(jì)都是為了提高搜索的性能

另一層意思：為了提高搜索的性能，難免會(huì)犧牲某些其他方面怒坯，比如插入/更新竖席，否則其他數(shù)據(jù)庫不用混了:)

前面看到往Elasticsearch里插入一條記錄敬肚，其實(shí)就是直接PUT一個(gè)json的對象束析，這個(gè)對象有多個(gè)fields，比如上面例子中的name, sex, age, about, interests员寇，那么在插入這些數(shù)據(jù)到Elasticsearch的同時(shí)，Elasticsearch還默默1的為這些字段建立索引–倒排索引蝶锋，因?yàn)镋lasticsearch最核心功能是搜索。

Elasticsearch是如何做到快速索引的

InfoQ那篇文章里說Elasticsearch使用的倒排索引比關(guān)系型數(shù)據(jù)庫的B-Tree索引快扳缕，為什么呢？

什么是B-Tree索引?

上大學(xué)讀書時(shí)老師教過我們躯舔，二叉樹查找效率是logN，同時(shí)插入新的節(jié)點(diǎn)不必移動(dòng)全部節(jié)點(diǎn)丧失，所以用樹型結(jié)構(gòu)存儲(chǔ)索引，能同時(shí)兼顧插入和查詢的性能布讹。

因此在這個(gè)基礎(chǔ)上，再結(jié)合磁盤的讀取特性(順序讀/隨機(jī)讀)描验，傳統(tǒng)關(guān)系型數(shù)據(jù)庫采用了B-Tree/B+Tree這樣的數(shù)據(jù)結(jié)構(gòu)：

為了提高查詢的效率，減少磁盤尋道次數(shù)挠乳，將多個(gè)值作為一個(gè)數(shù)組通過連續(xù)區(qū)間存放，一次尋道讀取多個(gè)數(shù)據(jù)盟蚣，同時(shí)也降低樹的高度。

什么是倒排索引?

繼續(xù)上面的例子屎开，假設(shè)有這么幾條數(shù)據(jù)(為了簡單马靠，去掉about, interests這兩個(gè)field):

IDNameAgeSex

1Kate24Female

2John24Male

3Bill29Male

ID是Elasticsearch自建的文檔id，那么Elasticsearch建立的索引如下:

Name:

TermPosting List

Kate1

John2

Bill3

Age:

TermPosting List

24[1,2]

293

Sex:

TermPosting List

Female1

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é)束了渐北，精彩的部分才剛開始…

通過posting list這種索引方式似乎可以很快進(jìn)行查找，比如要找age=24的同學(xué)铭拧，愛回答問題的小明馬上就舉手回答：我知道赃蛛，id是1搀菩，2的同學(xué)焊虏。但是秕磷，如果這里有上千萬的記錄呢？如果是想通過name來查找呢？

Term Dictionary

Elasticsearch為了能快速找到某個(gè)term瘟芝，將所有的term排個(gè)序褥琐，二分法查找term，logN的查找效率敌呈，就像通過字典查找一樣，這就是Term Dictionary】暮椋現(xiàn)在再看起來，似乎和傳統(tǒng)數(shù)據(jù)庫通過B-Tree的方式類似啊析显，為什么說比B-Tree的查詢快呢？

Term Index

B-Tree通過減少磁盤尋道次數(shù)來提高查詢性能分尸，Elasticsearch也是采用同樣的思路歹嘹，直接通過內(nèi)存查找term箩绍，不讀磁盤尺上，但是如果term太多，term dictionary也會(huì)很大尖昏，放內(nèi)存不現(xiàn)實(shí)构资，于是有了Term Index，就像字典里的索引頁一樣迹淌，A開頭的有哪些term，分別在哪頁唉窃，可以理解term index是一顆樹：?

這棵樹不會(huì)包含所有的term纹笼，它包含的是term的一些前綴。通過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查到對應(yīng)的term dictionary的block位置之后，再去磁盤上找term羽峰，大大減少了磁盤隨機(jī)讀的次數(shù)添瓷。

這時(shí)候愛提問的小明又舉手了:”那個(gè)FST是神馬東東啊?”

一看就知道小明是一個(gè)上大學(xué)讀書的時(shí)候跟我一樣不認(rèn)真聽課的孩子，數(shù)據(jù)結(jié)構(gòu)老師一定講過什么是FST坯汤。但沒辦法搀愧，我也忘了，這里再補(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位置)。最簡單的做法就是定義個(gè)Map盟猖，大家找到自己的位置對應(yīng)入座就好了，但從內(nèi)存占用少的角度想想值依，有沒有更優(yōu)的辦法呢碟案？答案就是：FST(理論依據(jù)在此，但我相信99%的人不會(huì)認(rèn)真看完的)

??表示一種狀態(tài)

–>表示狀態(tài)的變化過程辆亏，上面的字母/數(shù)字表示狀態(tài)變化和權(quán)重

將單詞分成單個(gè)字母通過??和–>表示出來鳖目，0權(quán)重不顯示。如果??后面出現(xiàn)分支彻磁，就標(biāo)記權(quán)重狸捅，最后整條路徑上的權(quán)重加起來就是這個(gè)單詞對應(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里除了上面說到用FST壓縮term index外，對posting list也有壓縮技巧嗤堰。 小明喝完咖啡又舉手了:”posting list不是已經(jīng)只存儲(chǔ)文檔id了嗎梁棠？還需要壓縮斗埂？”

嗯，我們再看回最開始的例子男娄，如果Elasticsearch需要對同學(xué)的性別進(jìn)行索引(這時(shí)傳統(tǒng)關(guān)系型數(shù)據(jù)庫已經(jīng)哭暈在廁所……)，會(huì)怎樣模闲？如果有上千萬個(gè)同學(xué)尸折，而世界上只有男/女這樣兩個(gè)性別，每個(gè)posting list都會(huì)有至少百萬個(gè)文檔id实夹。 Elasticsearch是如何有效的對這些文檔id壓縮的呢亮航？

Frame Of Reference

增量編碼壓縮，將大數(shù)變小數(shù)缴淋，按字節(jié)存儲(chǔ)

首先，Elasticsearch要求posting list是有序的(為了提高搜索的性能露氮，再任性的要求也得滿足)，這樣做的一個(gè)好處是方便壓縮沦辙，看下面這個(gè)圖例：?

如果數(shù)學(xué)不是體育老師教的話讹剔，還是比較容易看出來這種壓縮技巧的。

原理就是通過增量延欠，將原來的大數(shù)變成小數(shù)僅存儲(chǔ)增量值，再精打細(xì)算按bit排好隊(duì)兔综，最后通過字節(jié)存儲(chǔ)，而不是大大咧咧的盡管是2也是用int(4個(gè)字節(jié))來存儲(chǔ)软驰。

Roaring bitmaps

說到Roaring bitmaps心肪，就必須先從bitmap說起。Bitmap是一種數(shù)據(jù)結(jié)構(gòu)硬鞍，假設(shè)有某個(gè)posting list：

[1,3,4,7,10]

對應(yīng)的bitmap就是：

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

非常直觀戴已，用0/1表示某個(gè)值是否存在锅减，比如10這個(gè)值就對應(yīng)第10位，對應(yīng)的bit值是1怔匣，這樣用一個(gè)字節(jié)就可以代表8個(gè)文檔id，舊版本(5.0之前)的Lucene就是用這樣的方式來壓縮的每瞒，但這樣的壓縮方式仍然不夠高效，如果有1億個(gè)文檔呐矾，那么需要12.5MB的存儲(chǔ)空間，這僅僅是對應(yīng)一個(gè)索引字段(我們往往會(huì)有很多個(gè)索引字段)蜒犯。于是有人想出了Roaring bitmaps這樣更高效的數(shù)據(jù)結(jié)構(gòu)荞膘。

Bitmap的缺點(diǎn)是存儲(chǔ)空間隨著文檔個(gè)數(shù)線性增長，Roaring bitmaps需要打破這個(gè)魔咒就一定要用到某些指數(shù)特性：

將posting list按照65535為界限分塊羽资，比如第一塊所包含的文檔id范圍在0~65535之間，第二塊的id范圍是65536~131071潮改，以此類推。再用<商汇在，余數(shù)>的組合表示每一組id脏答，這樣每組里的id范圍都在0~65535內(nèi)了糕殉，剩下的就好辦了殖告，既然每組id不會(huì)變得無限大，那么我們就可以通過最有效的方式對這里的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來區(qū)分采用數(shù)組還是bitmap的閥值呢榜跌？

這個(gè)是從內(nèi)存大小考慮的，當(dāng)block塊里元素超過4096后悄蕾，用bitmap更蚀「。空間： 采用bitmap需要的空間是恒定的: 65536/8 = 8192bytes 而如果采用short[]，所需的空間是: 2*N(N為數(shù)組元素個(gè)數(shù)) 小明手指一掐N=4096剛好是邊界:

聯(lián)合索引

上面說了半天都是單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越往上佛吓，選出來的指針元素越少垂攘，查找時(shí)依次從高level往低查找淤刃，比如55，先找到level2的31陨仅，再找到level1的47铝侵，最后找到55，一共3次查找咪鲜，查找效率和2叉樹的效率相當(dāng)，但也是用了一定的空間冗余來換取的猾警。

假設(shè)有下面三個(gè)posting list需要聯(lián)合索引：

如果使用跳表隆敢，對最短的posting list中的每個(gè)id，逐個(gè)在另外兩個(gè)posting list中查找看是否存在穴墅，最后得到交集的結(jié)果温自。

如果使用bitset，就很直觀了悼泌，直接按位與，得到的結(jié)果就是最后的交集隘世。

總結(jié)和思考

Elasticsearch的索引思路:

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

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

不需要索引的字段，一定要明確定義出來主儡，因?yàn)槟J(rèn)是自動(dòng)建索引的

同樣的道理，對于String類型的字段，不需要analysis的也需要明確定義出來踪央，因?yàn)槟J(rèn)也是會(huì)analysis的

選擇有規(guī)律的ID很重要臀玄，隨機(jī)性太大的ID(比如java的UUID)不利于查詢

關(guān)于最后一點(diǎn)畅蹂，個(gè)人認(rèn)為有多個(gè)因素:

其中一個(gè)(也許不是最重要的)因素: 上面看到的壓縮算法，都是對Posting list里的大量ID進(jìn)行壓縮的累贤，那如果ID是順序的少漆，或者是有公共前綴等具有一定規(guī)律性的ID，壓縮比會(huì)比較高示损；

另外一個(gè)因素: 可能是最影響查詢性能的，應(yīng)該是最后通過Posting list里的ID到磁盤中查找Document信息的那步始鱼，因?yàn)镋lasticsearch是分Segment存儲(chǔ)的脆贵，根據(jù)ID這個(gè)大范圍的Term定位到Segment的效率直接影響了最后查詢的性能，如果ID是有規(guī)律的会烙，可以快速跳過不包含該ID的Segment筒捺，從而減少不必要的磁盤讀次數(shù)，具體可以參考這篇如何選擇一個(gè)高效的全局ID方案(評(píng)論也很精彩)

后續(xù)再結(jié)合實(shí)際開發(fā)及調(diào)優(yōu)工作分享更多內(nèi)容焙矛，敬請期待！

Reference

Elasticsearch權(quán)威指南

時(shí)間序列數(shù)據(jù)庫的秘密(2)——索引

Elasticsearch默認(rèn)會(huì)為每個(gè)字段根據(jù)value的類型分別建立索引贫导，如果不想為某些字段建立索引或者不做分詞分析的話，需要通過FieldMapping注明?