思考幾個問題：
- 為什麼搜索是 近實時 的？
- 為什麼文檔的 CRUD (創建-讀取-更新-刪除) 操作是 實時 的?
複習一遍從上到下的整體結構
這裡有篇文章講解的很形象：
這是集群cluster。
這是節點Node：就是個機器。
由一個或者多個節點，多個綠色小方塊組合在一起形成一個ElasticSearch的索引。
在一個索引下，分佈在多個節點裡的綠色小方塊稱為分片：Shard。
一個分片就是一個Lucene Index。
在Lucene裡面有很多小的Segment，即為存儲的最小管理單元。
我們分別從Node維度、Shard維度、Segment維度來闡明為啥Elasticsearch這麼快。
Node節點維度
多節點的集群方案，提高了整個系統的併發處理能力。
多節點的集群方案
路由一個文檔到一個分片中：當索引一個文檔的時候，文檔會被存儲到一個主分片中。 Elasticsearch 如何知道一個文檔應該存放到哪個分片中呢？實際上，這個過程是根據下面這個公式決定的：
shard = hash(routing) % number_of_primary_shards
routing 是一個可變值，默認是文檔的 _id ，也可以設置成一個自定義的值。這就解釋了為什麼我們要在創建索引的時候就確定好主分片的數量 並且永遠不會改變這個數量：因為如果數量變化了，那麼所有之前路由的值都會無效，文檔也再也找不到了。
確定了在哪個分片中，可以判定其在哪個節點上。
協調節點
節點分為主節點 Master Node、數據節點 Data Node和客戶端節點 Client Node（單純為了做請求的分發和彙總）。每個節點都可以接受客戶端的請求，每個節點都知道集群中任一文檔位置，所以可以直接將請求轉發到需要的節點上。當接受請求後，節點變為「協調節點」。從這個角度，整個系統可以接受更高的併發請求，當然搜索的就更快了。
以更新文檔為例：
- 客戶端向 Node 1 發送更新請求。
- 它將請求轉發到主分片所在的 Node 3 。
- Node 3 從主分片檢索文檔，修改 _source 字段中的 JSON ，並且嘗試重新索引主分片的文檔。 如果文檔已經被另一個進程修改，它會重試步驟 3 ，超過 retry_on_conflict 次後放棄。
- 如果 Node 3 成功地更新文檔，它將新版本的文檔並行轉發到 Node 1 和 Node 2 上的副本分片，重新建立索引。 一旦所有副本分片都返回成功， Node 3 向協調節點也返回成功，協調節點向客戶端返回成功。
樂觀併發控制
Elasticsearch 中使用的這種方法假定衝突是不可能發生的，並且不會阻塞正在嘗試的操作。因為沒有阻塞，所以提升了索引的速度，同時可以通過_version字段來保證併發情況下的正確性：
PUT /website/blog/1?version=1
{
"title": "My first blog entry",
"text": "Starting to get the hang of this..."
}
控制在我們索引中的文檔只有現在的_version為 1 時，本次更新才能成功。
Shard分片維度
副本分片
可以設置分片的副本數量來提升高併發場景下的搜索速度，但是同時會降低索引的效率。
Segment的不變性
在底層採用了分段的存儲模式，使它在讀寫時幾乎完全避免了鎖的出現，大大提升了讀寫性能。
- 不需要鎖。如果你從來不更新索引，你就不需要擔心多進程同時修改數據的問題。
- 一旦索引被讀入內核的文件系統緩存，便會留在哪裡，由於其不變性。只要文件系統緩存中還有足夠的空間，那麼大部分讀請求會直接請求內存，而不會命中磁盤。這提供了很大的性能提升。
- 其它緩存(像filter緩存)，在索引的生命週期內始終有效。它們不需要在每次數據改變時被重建，因為數據不會變化。
- 寫入單個大的倒排索引允許數據被壓縮，減少磁盤 I/O 和 需要被緩存到內存的索引的使用量。
怎樣在保留不變性的前提下實現倒排索引的更新？即用上文提到的_version，創建更多的索引文檔。實際上一個 UPDATE 操作包含了一次 DELETE 操作（僅記錄標誌待Segment Merge 的時候才真正刪除）和一次 CREATE 操作。
提升寫入速度
為了提升寫索引速度，並且同時保證可靠性，Elasticsearch 在分段的基礎上，增加了一個 translog ，或者叫事務日誌，在每一次對 Elasticsearch 進行操作時均進行了日誌記錄。
一個文檔被索引之後，就會被添加到內存緩衝區，並且 追加到了 translog
分片每秒被刷新（refresh）一次：
- 這些在內存緩衝區的文檔被寫入到一個新的段中，且沒有進行 fsync 操作。
- 這個段被打開，使其可被搜索。
- 內存緩衝區被清空。
這個進程繼續工作，更多的文檔被添加到內存緩衝區和追加到事務日誌
每隔一段時間--例如 translog 變得越來越大--索引被刷新（flush）；一個新的 translog 被創建，並且一個全量提交被執行:
- 所有在內存緩衝區的文檔都被寫入一個新的段。
- 緩衝區被清空。
- 一個提交點被寫入硬盤。
- 文件系統緩存通過 fsync 被刷新（flush）。
- 老的 translog 被刪除。
Segment在被refresh之前，數據保存在內存中，是不可被搜索的，這也就是為什麼 Lucene 被稱為提供近實時而非實時查詢的原因。
但是如上這種機制避免了隨機寫，數據寫入都是 Batch 和 Append，能達到很高的吞吐量。同時為了提高寫入的效率，利用了文件緩存系統和內存來加速寫入時的性能，並使用日誌來防止數據的丟失。
對比LSM樹
LSM-Tree 示意圖如下，可見 Lucene 的寫入思想和 LSM-Tree 是一致的：
Segment段維度
倒排索引
終於說到倒排索引了，都說倒排索引提升了搜索的速度，那麼具體採用了哪些架構或者數據結構來達成這一目標？
如上是Lucene中實際的索引結構。用例子來說明上述三個概念：
ID是文檔id，那麼建立的索引如下:
Name：
Age：
Sex：
Posting List
可見為每個 field 都建立了一個倒排索引。Posting list就是一個int的數組，存儲了所有符合某個term的文檔id。實際上，除此之外還包含：文檔的數量、詞條在每個文檔中出現的次數、出現的位置、每個文檔的長度、所有文檔的平均長度等，在計算相關度時使用。
Term Dictionary
假設我們有很多個 term，比如：
Carla,Sara,Elin,Ada,Patty,Kate,Selena
如果按照這樣的順序排列，找出某個特定的 term 一定很慢，因為 term 沒有排序，需要全部過濾一遍才能找出特定的 term。排序之後就變成了：
Ada,Carla,Elin,Kate,Patty,Sara,Selena
這樣我們可以用二分查找的方式，比全遍歷更快地找出目標的 term。這個就是 term dictionary。有了 term dictionary 之後，可以用 logN 次磁盤查找得到目標。
Term Index
但是磁盤的隨機讀操作仍然是非常昂貴的（一次 random access 大概需要 10ms 的時間）。所以儘量少的讀磁盤，有必要把一些數據緩存到內存裡。但是整個 term dictionary 本身又太大了，無法完整地放到內存裡。於是就有了 term index。term index 有點像一本字典的大的章節表。比如：
A 開頭的 term ……………. Xxx 頁
C 開頭的 term ……………. Yyy 頁
E 開頭的 term ……………. Zzz 頁
如果所有的 term 都是英文字符的話，可能這個 term index 就真的是 26 個英文字符表構成的了。但是實際的情況是，term 未必都是英文字符，term 可以是任意的 byte 數組。而且 26 個英文字符也未必是每一個字符都有均等的 term，比如 x 字符開頭的 term 可能一個都沒有，而 s 開頭的 term 又特別多。實際的 term index 是一棵 trie 樹：
例子是一個包含 "A", "to", "tea", "ted", "ten", "i", "in", 和 "inn" 的 trie 樹。這棵樹不會包含所有的 term，它包含的是 term 的一些前綴。通過 term index 可以快速地定位到 term dictionary 的某個 offset，然後從這個位置再往後順序查找。
現在我們可以回答“為什麼 Elasticsearch/Lucene 檢索可以比 mysql 快了。Mysql 只有 term dictionary 這一層，是以 b-tree 排序的方式存儲在磁盤上的。檢索一個 term 需要若干次的 random access 的磁盤操作。而 Lucene 在 term dictionary 的基礎上添加了 term index 來加速檢索，term index 以樹的形式緩存在內存中。從 term index 查到對應的 term dictionary 的 block 位置之後，再去磁盤上找 term，大大減少了磁盤的 random access 次數。
FST(finite-state transducer)
實際上，Lucene 內部的 Term Index 是用的「變種的」trie樹，即 FST 。FST 比 trie樹好在哪？trie樹只共享了前綴，而 FST 既共享前綴也共享後綴，更加的節省空間。
一個FST是一個6元組 (Q, I, O, S, E, f):
- Q是一個有限的狀態集
- I是一個有限的輸入符號集
- O是一個有限的輸出符號集
- S是Q中的一個狀態，稱為初始狀態
- E是Q的一個子集，稱為終止狀態集
- f是轉換函數, f ⊆ Q × (I∪{ε}) × (O∪{ε}) × Q，其中ε表示空字符。
- 即從一個狀態q1開始，接收一個輸入字符i，可以到達另一個狀態q2，併產生輸出o。
例如有下面一組映射關係：
cat -> 5
deep -> 10
do -> 15
dog -> 2
dogs -> 8
可以用下圖中的FST來表示：
這篇文章講的很好：關於Lucene的詞典FST深入剖析
想想為啥不用 HashMap，HashMap 也能實現有序Map？耗內存啊！犧牲了一點性能來節約內存，旨在把所有Term Index都放在內存裡面，最終的效果是提升了速度。如上可知，FST是壓縮字典樹後綴的圖結構，她擁有Trie高效搜索能力，同時還非常小。這樣的話我們的搜索時，能把整個FST加載到內存。
總結一下，FST有更高的數據壓縮率和查詢效率，因為詞典是常駐內存的，而 FST 有很好的壓縮率，所以 FST 在 Lucene 的最新版本中有非常多的使用場景，也是默認的詞典數據結構。
詞典的完整結構
Lucene 的tip文件即為 Term Index 結構，tim文件即為 Term Dictionary 結構。由圖可視，tip中存儲的就是多個FST，
FST中存儲的是。即為前文提到的從 term index 查到對應的 term dictionary 的 block 位置之後，再去磁盤上找 term，大大減少了磁盤的 random access 次數。
可以形象地理解為，Term Dictionary 就是新華字典的正文部分包含了所有的詞彙，Term Index 就是新華字典前面的索引頁，用於表明詞彙在哪一頁。
但是 FST 即不能知道某個Term在Dictionary(.tim)文件上具體的位置，也不能僅通過FST就能確切的知道Term是否真實存在。它只能告訴你，查詢的Term可能在這些Blocks上，到底存不存在FST並不能給出確切的答案，因為FST是通過Dictionary的每個Block的前綴構成，所以通過FST只可以直接找到這個Block在.tim文件上具體的File Pointer，並無法直接找到Terms。
如何聯合索引查詢？
回到上面的例子，給定查詢過濾條件 age=24 的過程就是先從 term index 找到 18 在 term dictionary 的大概位置，然後再從 term dictionary 裡精確地找到 18 這個 term，然後得到一個 posting list 或者一個指向 posting list 位置的指針。然後再查詢 sex=Female 的過程也是類似的。最後得出 age= 24 AND sex=Female 就是把兩個 posting list 做一個“與”的合併。
這個理論上的“與”合併的操作可不容易。對於 mysql 來說，如果你給 age 和 gender 兩個字段都建立了索引，查詢的時候只會選擇其中最 selective 的來用，然後另外一個條件是在遍歷行的過程中在內存中計算之後過濾掉。那麼要如何才能聯合使用兩個索引呢？有兩種辦法：
- 使用 skip list 數據結構。同時遍歷 gender 和 age 的 posting list，互相 skip；
- 使用 bitset 數據結構，對 gender 和 age 兩個 filter 分別求出 bitset，對兩個 bitset 做 AN 操作。
Elasticsearch 支持以上兩種的聯合索引方式，如果查詢的 filter 緩存到了內存中（以 bitset 的形式），那麼合併就是兩個 bitset 的 AND。如果查詢的 filter 沒有緩存，那麼就用 skip list 的方式去遍歷兩個 on disk 的 posting list。
利用 Skip List 合併
用一個例子來說明如何使用 skip list 的思路來做合併（參考Lucene學習總結之七：Lucene搜索過程解析(5)）：
- 倒排表最初如下，可見每個 posting list 已經是排好序的：
- 將每個 posting list 按照第一篇的文檔號從小到大進行排列：
- 稱擁有最小文檔號的倒排表稱為first，再取最後一個 posting list 的文檔號為 doc（很明顯做交集可以跳過之前的文檔）。即，doc = 8，first指向第0項，advance到大於8的第一篇文檔，也即文檔10，然後設doc = 10，first指向第1項。
- doc = 10，first指向第1項，advance到文檔11，然後設doc = 11，first指向第2項。
- doc = 11，first指向第3項，advance到文檔11，然後設doc = 11，first指向第4項。
- 以此類推，first指向最後一項。即，doc = 11，first指向第7項，advance到文檔11，然後設doc = 11，first指向第0項。
- doc = 11，first指向第0項，advance到文檔11，然後設doc = 11，first指向第1項。
- doc = 11，first指向第1項。因為11 < 11為false，因而結束循環，返回doc = 11。這時候我們會發現，在循環退出的時候，所有的倒排表的第一篇文檔都是11，故11為所有 skip list 的公共項。
- 按照此法再外層循環，得到剩餘的公共項。
Advance操作是什麼？就是 skip list 提供的快速跳躍的特性。
另外一方面，對於一個很長的 posting list，比如：
[1,3,13,101,105,108,255,256,257]
我們可以把這個 list 分成三個 block：
[1,3,13] [101,105,108] [255,256,257]
然後可以構建出 skip list 的第二層：
[1,101,255]
1,101,255 分別指向自己對應的 block。這樣就可以很快地跨 block 的移動指向位置了。
Lucene 自然會對這個 block 再次進行壓縮。其壓縮方式叫做 Frame Of Reference 編碼。示例如下：
考慮到頻繁出現的 term（所謂 low cardinality 的值），比如 gender 裡的男或者女。如果有 1 百萬個文檔，那麼性別為男的 posting list 裡就會有 50 萬個 int 值。用 Frame of Reference 編碼進行壓縮可以極大減少磁盤佔用。這個優化對於減少索引尺寸有非常重要的意義。當然 mysql b-tree 裡也有一個類似的 posting list 的東西，是未經過這樣壓縮的。
因為這個 Frame of Reference 的編碼是有解壓縮成本的。利用 skip list，除了跳過了遍歷的成本，也跳過了解壓縮這些壓縮過的 block 的過程，從而節省了 cpu。
這也可以看到，Lucene 為了省內存真是做到了極致。
利用 bitset 合併
Bitset 是一種很直觀的數據結構，對應 posting list 如：
[1,3,4,7,10]
對應的 bitset 就是：
[1,0,1,1,0,0,1,0,0,1]
每個文檔按照文檔 id 排序對應其中的一個 bit。Bitset 自身就有壓縮的特點，其用一個 byte 就可以代表 8 個文檔。所以 100 萬個文檔只需要 12.5 萬個 byte。但是考慮到文檔可能有數十億之多，在內存裡保存 bitset 仍然是很奢侈的事情。而且對於個每一個 filter 都要消耗一個 bitset，比如 age=18 緩存起來的話是一個 bitset，18<=age<25 是另外一個 filter 緩存起來也要一個 bitset。
所以秘訣就在於需要有一個數據結構：
可以很壓縮地保存上億個 bit 代表對應的文檔是否匹配 filter；
這個壓縮的 bitset 仍然可以很快地進行 AND 和 OR 的邏輯操作。
Lucene 使用的這個數據結構叫做 Roaring Bitmap。
其壓縮的思路其實很簡單。與其保存 100 個 0，佔用 100 個 bit。還不如保存 0 一次，然後聲明這個 0 重複了 100 遍。
為什麼是以65535為界限？程序員的世界裡除了1024外，65535也是一個經典值，因為它=2^16-1，正好是用2個字節能表示的最大數，一個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”，如果是大塊，用節省點用bitset存，小塊就豪爽點，2個字節我也不計較了，用一個short[]存著方便。
在 Lucene 7.0之後，Lucene 針對 bitset的稠稀性，採用不同的存儲方式：當 bitset比較稀疏時，直接存儲DocID；當 bitset 稠密時，則直接存儲 bitset 的Bits數據。根據數據的分佈情況不同，採用適當的結構不僅可以提高空間的利用率，還能提高遍歷的效率。
總結
Elasticsearch/Lucene 為了提升索引和搜索的效率，從上層到底層，使用了各種巧妙的數據結構和設計，靠優秀的理論加極致的優化，做到查詢性能上的極致。
閱讀更多 Java之高級架構 的文章
關鍵字: 詳解 ElasticSearch 一文
