最近在了解Elasticsearch這款工具時举农，碰到了幾篇比較好的科普文章，特意引過來鹃两，以備日后反復(fù)學(xué)習(xí)
介紹
Elasticsearch 是一個分布式可擴展的實時搜索和分析引擎,一個建立在全文搜索引擎 Apache Lucene? 基礎(chǔ)上的搜索引擎.當(dāng)然 Elasticsearch 并不僅僅是 Lucene 那么簡單，它不僅包括了全文搜索功能，還可以進(jìn)行以下工作:
分布式實時文件存儲啊犬，并將每一個字段都編入索引，使其可以被搜索壁查。
實時分析的分布式搜索引擎觉至。
可以擴展到上百臺服務(wù)器，處理PB級別的結(jié)構(gòu)化或非結(jié)構(gòu)化數(shù)據(jù)睡腿。
基本概念
先說Elasticsearch的文件存儲语御，Elasticsearch是面向文檔型數(shù)據(jù)庫，一條數(shù)據(jù)在這里就是一個文檔席怪，用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ù)庫存儲就會容易想到建立一張User表，有balabala的字段等挂捻，在Elasticsearch里這就是一個文檔碉纺，當(dāng)然這個文檔會屬于一個User的類型，各種各樣的類型存在于一個索引當(dāng)中。這里有一份簡易的將Elasticsearch和關(guān)系型數(shù)據(jù)術(shù)語對照表:
關(guān)系數(shù)據(jù)庫 ? 數(shù)據(jù)庫 ? 表 ? 行 ? 列(Columns)
Elasticsearch ? 索引(Index) ? 類型(type) ? 文檔(Docments) ? 字段(Fields)
一個 Elasticsearch 集群可以包含多個索引(數(shù)據(jù)庫)骨田，也就是說其中包含了很多類型(表)耿导。這些類型中包含了很多的文檔(行)，然后每個文檔中又包含了很多的字段(列)态贤。Elasticsearch的交互舱呻，可以使用Java API，也可以直接使用HTTP的Restful API方式抵卫，比如我們打算插入一條記錄狮荔，可以簡單發(fā)送一個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)鍵的就是提供強大的索引能力了殖氏，其實InfoQ的這篇時間序列數(shù)據(jù)庫的秘密(2)——索引寫的非常好，我這里也是圍繞這篇結(jié)合自己的理解進(jìn)一步梳理下姻采，也希望可以幫助大家更好的理解這篇文章雅采。
Elasticsearch索引的精髓：
一切設(shè)計都是為了提高搜索的性能
另一層意思：為了提高搜索的性能，難免會犧牲某些其他方面慨亲，比如插入/更新婚瓜，否則其他數(shù)據(jù)庫不用混了。前面看到往Elasticsearch里插入一條記錄刑棵，其實就是直接PUT一個json的對象巴刻，這個對象有多個fields，比如上面例子中的name, sex, age, about, interests蛉签，那么在插入這些數(shù)據(jù)到Elasticsearch的同時胡陪，Elasticsearch還默默1的為這些字段建立索引–倒排索引，因為Elasticsearch最核心功能是搜索碍舍。
Elasticsearch是如何做到快速索引的
InfoQ那篇文章里說Elasticsearch使用的倒排索引比關(guān)系型數(shù)據(jù)庫的B-Tree索引快柠座，為什么呢？
什么是B-Tree索引?
上大學(xué)讀書時老師教過我們片橡，二叉樹查找效率是logN妈经，同時插入新的節(jié)點不必移動全部節(jié)點，所以用樹型結(jié)構(gòu)存儲索引捧书，能同時兼顧插入和查詢的性能吹泡。因此在這個基礎(chǔ)上，再結(jié)合磁盤的讀取特性(順序讀/隨機讀)经瓷，傳統(tǒng)關(guān)系型數(shù)據(jù)庫采用了B-Tree/B+Tree這樣的數(shù)據(jù)結(jié)構(gòu)：
為了提高查詢的效率爆哑，減少磁盤尋道次數(shù)，將多個值作為一個數(shù)組通過連續(xù)區(qū)間存放了嚎，一次尋道讀取多個數(shù)據(jù)泪漂，同時也降低樹的高度。
什么是倒排索引?
繼續(xù)上面的例子歪泳，假設(shè)有這么幾條數(shù)據(jù)(為了簡單萝勤，去掉about, interests這兩個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分別為每個field都建立了一個倒排索引呐伞，Kate, John, 24, Female這些叫term敌卓，而[1,2]就是Posting List。Posting list就是一個int的數(shù)組伶氢，存儲了所有符合某個term的文檔id趟径。
看到這里，不要認(rèn)為就結(jié)束了癣防，精彩的部分才剛開始…
通過posting list這種索引方式似乎可以很快進(jìn)行查找蜗巧，比如要找age=24的同學(xué)，愛回答問題的小明馬上就舉手回答：我知道蕾盯，id是1幕屹，2的同學(xué)。但是级遭，如果這里有上千萬的記錄呢望拖？如果是想通過name來查找呢？
Term Dictionary
Elasticsearch為了能快速找到某個term挫鸽，將所有的term排個序说敏，二分法查找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也會很大，放內(nèi)存不現(xiàn)實上遥，于是有了Term Index搏屑，就像字典里的索引頁一樣，A開頭的有哪些term粉楚，分別在哪頁辣恋，可以理解term index是一顆樹：
這棵樹不會包含所有的term亮垫，它包含的是term的一些前綴。通過term index可以快速地定位到term dictionary的某個offset伟骨，然后從這個位置再往后順序查找饮潦。
所以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稀并，大大減少了磁盤隨機讀的次數(shù)。
這時候愛提問的小明又舉手了:“那個FST是神馬東東啊?”
一看就知道小明是一個上大學(xué)讀書的時候跟我一樣不認(rèn)真聽課的孩子单默，數(shù)據(jù)結(jié)構(gòu)老師一定講過什么是FST碘举。但沒辦法，我也忘了搁廓，這里再補下課：
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前綴)映射到序號：0殴俱，1，2枚抵，3线欲，4，5(term dictionary的block位置)汽摹。最簡單的做法就是定義個Map<string, integer="">李丰，大家找到自己的位置對應(yīng)入座就好了，但從內(nèi)存占用少的角度想想逼泣，有沒有更優(yōu)的辦法呢趴泌？答案就是：FST(理論依據(jù)在此，但我相信99%的人不會認(rèn)真看完的)
??表示一種狀態(tài)
–>表示狀態(tài)的變化過程拉庶，上面的字母/數(shù)字表示狀態(tài)變化和權(quán)重
將單詞分成單個字母通過??和–>表示出來嗜憔，0權(quán)重不顯示。如果??后面出現(xiàn)分支氏仗，就標(biāo)記權(quán)重吉捶，最后整條路徑上的權(quán)重加起來就是這個單詞對應(yīng)的序號。
FSTs are finite-state machines that map a term (byte sequence) to an arbitrary output.
FST以字節(jié)的方式存儲所有的term皆尔，這種壓縮方式可以有效的縮減存儲空間呐舔，使得term index足以放進(jìn)內(nèi)存，但這種方式也會導(dǎo)致查找時需要更多的CPU資源慷蠕。
后面的更精彩珊拼，看累了的同學(xué)可以喝杯咖啡……
壓縮技巧
Elasticsearch里除了上面說到用FST壓縮term index外，對posting list也有壓縮技巧流炕。
小明喝完咖啡又舉手了:“posting list不是已經(jīng)只存儲文檔id了嗎澎现？還需要壓縮仅胞？”
嗯，我們再看回最開始的例子剑辫，如果Elasticsearch需要對同學(xué)的性別進(jìn)行索引(這時傳統(tǒng)關(guān)系型數(shù)據(jù)庫已經(jīng)哭暈在廁所……)饼问，會怎樣？如果有上千萬個同學(xué)揭斧，而世界上只有男/女這樣兩個性別，每個posting list都會有至少百萬個文檔id峻堰。 Elasticsearch是如何有效的對這些文檔id壓縮的呢讹开？
Frame Of Reference
增量編碼壓縮，將大數(shù)變小數(shù)捐名，按字節(jié)存儲
首先旦万，Elasticsearch要求posting list是有序的(為了提高搜索的性能，再任性的要求也得滿足)镶蹋，這樣做的一個好處是方便壓縮成艘，
看下面這個圖例：
如果數(shù)學(xué)不是體育老師教的話，還是比較容易看出來這種壓縮技巧的贺归。
原理就是通過增量淆两，將原來的大數(shù)變成小數(shù)僅存儲增量值，再精打細(xì)算按bit排好隊拂酣，最后通過字節(jié)存儲秋冰，而不是大大咧咧的盡管是2也是用int(4個字節(jié))來存儲。
Roaring bitmaps
說到Roaring bitmaps婶熬，就必須先從bitmap說起剑勾。Bitmap是一種數(shù)據(jù)結(jié)構(gòu)，假設(shè)有某個posting list：
[1,3,4,7,10]
對應(yīng)的bitmap就是：
[1,0,1,1,0,0,1,0,0,1]
非常直觀赵颅，用0/1表示某個值是否存在虽另，比如10這個值就對應(yīng)第10位，對應(yīng)的bit值是1饺谬，這樣用一個字節(jié)就可以代表8個文檔id捂刺，舊版本(5.0之前)的Lucene就是用這樣的方式來壓縮的，但這樣的壓縮方式仍然不夠高效募寨，如果有1億個文檔叠萍，那么需要12.5MB的存儲空間，這僅僅是對應(yīng)一個索引字段(我們往往會有很多個索引字段)绪商。于是有人想出了Roaring bitmaps這樣更高效的數(shù)據(jù)結(jié)構(gòu)苛谷。
Bitmap的缺點是存儲空間隨著文檔個數(shù)線性增長，Roaring bitmaps需要打破這個魔咒就一定要用到某些指數(shù)特性：
將posting list按照65535為界限分塊格郁，比如第一塊所包含的文檔id范圍在0-65535之間腹殿，第二塊的id范圍是65536-131071独悴，以此類推。再用<商锣尉，余數(shù)>的組合表示每一組id刻炒，這樣每組里的id范圍都在0-65535內(nèi)了，剩下的就好辦了自沧，既然每組id不會變得無限大坟奥，那么我們就可以通過最有效的方式對這里的id存儲。
細(xì)心的小明這時候又舉手了:“為什么是以65535為界限?”
程序員的世界里除了1024外拇厢，65535也是一個經(jīng)典值爱谁，因為它=2^16-1，正好是用2個字節(jié)能表示的最大數(shù)孝偎，一個short的存儲單位访敌，注意到上圖里的最后一行“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é)省點用bitmap存寺旺，小塊就豪爽點，2個字節(jié)我也不計較了势决，用一個short[]存著方便阻塑。
那為什么用4096來區(qū)分大塊還是小塊呢？
0-65535需要65536個bit來存儲果复，65536/8 = 8192 B / 2 = 4096 short叮姑，所以當(dāng)一塊少于4096個值時，不值得采用bitmap類型來存儲据悔，簡單的采用short數(shù)組即可传透。
具體可參考這篇文章 RoaringBitmap數(shù)據(jù)結(jié)構(gòu)及原理
聯(lián)合索引
上面說了半天都是單field索引，如果多個field索引的聯(lián)合查詢极颓，倒排索引如何滿足快速查詢的要求呢朱盐？
利用跳表(Skip list)的數(shù)據(jù)結(jié)構(gòu)快速做“與”運算，或者
利用上面提到的bitset按位“與”
先看看跳表的數(shù)據(jù)結(jié)構(gòu)：
將一個有序鏈表level0菠隆，挑出其中幾個元素到level1及l(fā)evel2兵琳，每個level越往上，選出來的指針元素越少骇径，查找時依次從高level往低查找躯肌，比如55，先找到level2的31破衔，再找到level1的47清女，最后找到55，一共3次查找晰筛，查找效率和2叉樹的效率相當(dāng)嫡丙，但也是用了一定的空間冗余來換取的拴袭。
假設(shè)有下面三個posting list需要聯(lián)合索引：
如果使用跳表，對最短的posting list中的每個id曙博，逐個在另外兩個posting list中查找看是否存在拥刻，最后得到交集的結(jié)果。
如果使用bitset父泳，就很直觀了般哼，直接按位與，得到的結(jié)果就是最后的交集惠窄。
總結(jié)和思考
Elasticsearch的索引思路:
將磁盤里的東西盡量搬進(jìn)內(nèi)存蒸眠，減少磁盤隨機讀取次數(shù)(同時也利用磁盤順序讀特性)，結(jié)合各種奇技淫巧的壓縮算法睬捶，用及其苛刻的態(tài)度使用內(nèi)存。
所以近刘，對于使用Elasticsearch進(jìn)行索引時需要注意:
不需要索引的字段擒贸，一定要明確定義出來，因為默認(rèn)是自動建索引的
同樣的道理觉渴，對于String類型的字段介劫，不需要analysis的也需要明確定義出來，因為默認(rèn)也是會analysis的
選擇有規(guī)律的ID很重要案淋，隨機性太大的ID(比如java的UUID)不利于查詢
關(guān)于最后一點座韵，個人認(rèn)為有多個因素:
其中一個(也許不是最重要的)因素: 上面看到的壓縮算法，都是對Posting list里的大量ID進(jìn)行壓縮的踢京，那如果ID是順序的誉碴，或者是有公共前綴等具有一定規(guī)律性的ID，壓縮比會比較高瓣距；
另外一個因素: 可能是最影響查詢性能的黔帕，應(yīng)該是最后通過Posting list里的ID到磁盤中查找Document信息的那步，因為Elasticsearch是分Segment存儲的蹈丸，根據(jù)ID這個大范圍的Term定位到Segment的效率直接影響了最后查詢的性能成黄，如果ID是有規(guī)律的，可以快速跳過不包含該ID的Segment逻杖，從而減少不必要的磁盤讀次數(shù)奋岁，具體可以參考這篇如何選擇一個高效的全局ID方案(評論也很精彩)
另外補充下Elasticsearch對于String 類型的數(shù)據(jù)的分詞方式 ：Elasticsearch——分詞器對String的作用
