一、全文索引

　　Elasticsearch 是一個分布式可擴展的實時搜索和分析引擎,一個建立在全文搜索引擎 Apache Lucene(TM) 基礎上的搜索引擎。當然 Elasticsearch 并不僅僅是 Lucene 那么簡單，它不僅包括了全文搜索功能，還可以進行以下工作:

• 倒排索引：分布式實時文件存儲，并將每一個字段都編入索引，使其可以被搜索。
• 將數據和索引分離
• 索引數據存入內存
• 壓縮數據

　　1、全文索引應用場景

　　全文索引有很多應用場景，開發者最常見的莫過于日志搜索功能，生活中最常見的莫過于各種網站的搜索功能，如下圖所示的商品搜索：

　　　　

　　2、為什么有了全文索引

　　為什么不能用Mysql索引？如下圖所示，Mysql可以方便的對各個字段進行存儲，而且Mysql也有自己完備且性能較高的B+樹索引機制，可是為什么不能用作索引呢，其原因就是因為全文索引需要對一個字段的任意內容進行查詢，這就類似于Mysql的like "%***%"查詢機制，是不能走索引的。

　　　　

 　　為什么不用內存數據庫呢？我們知道一旦東西放入內存速度就會很快，即使對字段進行全文搜索也不是不可行，可是全文索引場景面臨的是大量的數據，比如日志搜索，那么對于全文搜索來說，成本變成了一個巨大的問題。

　　　　

　　因此就誕生出了全文索引。 

　　3、倒排索引原理

　　倒排索引又稱為反向索引，倒排索引源于實際應用中需要根據屬性的值來查找記錄。這種索引表中的每一項都包括一個屬性值和具有該屬性值的各記錄的地址。由于不是由記錄來確定屬性值，而是由屬性值來確定記錄的位置，因而稱為倒排索引(inverted index)。帶有倒排索引的文件我們稱為倒排索引文件，簡稱倒排文件(inverted file)。

　　ElasticSearch引擎把文檔數據寫入到倒排索引（Inverted Index）的數據結構中，倒排索引建立的是分詞（Term）和文檔（Document）之間的映射關系，在倒排索引中，數據是面向詞（Term）而不是面向文檔的。一個倒排索引由文檔中所有不重復詞的列表構成，對于其中每個詞，有一個包含它的文檔列表。

　　首先來看看原始文件：

　　　　

　　我們來看看三種形式的倒排文件：

　　　　

　　標記了出現次數：

　　　　

 　　標記了出現位置，可用作搜索高亮：

　　　　

　　4、索引分詞

　　為了提高可搜索性（例如，為小寫字母和小寫字提供相同的結果），首先對文檔進行分詞并對其進行索引。 分詞由兩部分組成：

• 將句子標記成單詞
• 將單詞規范化為標準表單 

　　默認情況下，Elasticsearch使用標準分詞器

• 標準標記器(Standard tokenizer)，用于在單詞邊界上分割單詞
• 小寫令牌過濾器(Lowercase token filter)將單詞轉換為小寫 

　　還有許多其他分詞器可用，比如對中文支持良好的ik分詞器。

　　注意：標準分詞器也使用停止令牌過濾器，但默認情況下禁用。

　　5、倒排索引-查詢過程

　　查詢包含“搜索引擎”的文檔

1. 通過倒排索引獲得“外賣”對應的文檔id列表，有2，5
2. 通過正排索引查詢1和3的完整內容
3. 返回最終結果

　　6、倒排列表（Posting List）

• 倒排列表記錄了單詞對應的文檔集合，有倒排索引項（Posting）組成
• 倒排索引項主要包含如下信息：
• 文檔id用于獲取原始信息
• 單詞頻率（TF，Term Frequency），記錄該單詞在該文檔中出現的次數，用于后續相關性算分
• 位置（Posting），記錄單詞在文檔中的分詞位置（多個），用于做詞語搜索（Phrase Query）
• 偏移（Offset），記錄單詞在文檔的開始和結束位置，用于高亮顯示

　　7、倒排索引結構

　　如果詞典比較多的情況下，全放到內存是否也會出現瓶頸？倒排索引有以下三部分組成，分別是Term Index單詞索引,Term Dictionary單詞字典,Posting List倒排列表。也有的文檔把TermIndex歸并到TermDictionary中，統稱為單詞字典。

　　　　 

　　　　

　　由此可知單詞索引是單詞詞典（Term Dictionary）的B+樹實現。

　　8、檢索評分

　　elasticsearch和solr,這兩個引擎都是基于lucene服務器開發的。我們搜索一條短語或句子通過倒排索引會檢索到相關的文檔，有了這些文檔我們就需要給這些文檔進行評分進而推送給用戶。ES和solr這兩個引擎都是基于lucene服務器開發的，評分機制都是基于LUCENE的，Lucene的默認評分是TF/IDF算法。

• TF：TF代表分詞項在某個點文檔中出現的次數(term frequency)
• IDF：IDF代表代表分詞項在多少個文檔中出現(inverse document frequency)

　　TF-IDF值均可以通過倒排列表獲得。如下所示： 

　　　

• 單詞ID：記錄每個單詞的單詞編號；
• 單詞：對應的單詞；
• 文檔頻率：代表文檔集合中有多少個文檔包含某個單詞
• 倒排列表：包含單詞ID及其他必要信息
• DocId：單詞出現的文檔id
• TF：單詞在某個文檔中出現的次數
• POS：單詞在文檔中出現的位置

　　lucene的完整評分公式有6個部分組成：

• coord(q,d) 評分因子，基于文檔中出現查詢項的個數。越多的查詢項在一個文檔中，說明文檔的匹配程度越高。
• queryNorm(q)查詢的標準查詢
• tf(t in d) 指項t在文檔d中出現的次數frequency。具體值為次數的開根號。
• idf(t) 反轉文檔頻率, 出現項t的文檔數docFreq
• t.getBoost 查詢時候查詢項加權
• norm(t,d) 長度相關的加權因子

　　評分公式如下：Lucene打分公式的數學推導

 　　

二、Elasticsearch基本介紹

　　1、Elasticsearch的index

　　Elasticsearch的索引(index)是用于組織數據的邏輯命名空間（如數據庫）。Elasticsearch的索引有一個或多個分片(shard)（默認為5）。分片是實際存儲數據的Lucene索引，它本身就是一個搜索引擎。每個分片可以有零個或多個副本(replicas)（默認為1）。Elasticsearch索引還具有“類型”（如數據庫中的表），允許您在索引中對數據進行邏輯分區。Elasticsearch索引中給定“類型”中的所有文檔(documents)具有相同的屬性（如表的模式）。 

　　　　

　　圖a顯示了一個由三個主分片組成的Elasticsearch集群，每個主分片分別有一個副本。所有這些分片一起形成一個Elasticsearch索引，每個分片是Lucene索引本身。 
　　圖b演示了Elasticsearch索引，分片，Lucene索引和文檔(document)之間的邏輯關系。 

　　2、Elasticsearch集群的節點類型

　　Elasticsearch的一個實例是一個節點，一組節點形成一個集群。Elasticsearch集群中的節點可以通過三種不同的方式進行配置：

　　Master節點

• Master節點控制Elasticsearch集群，并負責在集群范圍內創建/刪除索引，跟蹤哪些節點是集群的一部分，并將分片分配給這些節點。主節點一次處理一個集群狀態，并將狀態廣播到所有其他節點，這些節點需要響應并確認主節點的信息。
• 在elasticsearch.yml中，將nodes.master屬性設置為true（默認），可以將節點配置為有資格成為主節點的節點。
• 對于大型生產集群，建議擁有一個專用主??節點來控制集群，并且不服務任何用戶請求。

　　Data節點

• 數據節點用來保存數據和倒排索引。默認情況下，每個節點都配置為一個data節點，并且在elasticsearch.yml中將屬性node.data設置為true。如果您想要一個專用的master節點，那么將node.data屬性更改為false。

　　Client節點

    如果將node.master和node.data設置為false，則將節點配置為客戶端節點，并充當負載平衡器，將傳入的請求路由到集群中的不同節點。 
    若你連接的是作為客戶端的節點，該節點稱為協調節點(coordinating node)。協調節點將客戶機請求路由到集群中對應分片所在的節點。對于讀取請求，協調節點每次選擇不同的分片來提供請求以平衡負載。 
    在我們開始審查發送到協調節點的CRUD請求如何通過集群傳播并由引擎執行之前，讓我們看看Elasticsearch如何在內部存儲數據，以低延遲為全文搜索提供結果。

三、Elasticsearch實現原理分析

　　1、write(寫)/create(創建)操作實現原理

　　當您向協調節點發送請求以索引新文檔時，將執行以下操作：

• 所有在Elasticsearch集群中的節點都包含：有關哪個分片存在于哪個節點上的元數據。協調節點(coordinating node)使用文檔ID（默認）將文檔路由到對應的分片。Elasticsearch將文檔ID以murmur3作為散列函數進行散列，并通過索引中的主分片數量進行取模運算，以確定文檔應被索引到哪個分片。 
  • shard = hash(document_id) % (num_of_primary_shards)

• 當節點接收到來自協調節點的請求時，請求被寫入到translog，并將該文檔添加到內存緩沖區。如果請求在主分片上成功，則請求將并行發送到副本分片。只有在所有主分片和副本分片上的translog被fsync’ed后，客戶端才會收到該請求成功的確認。

• 內存緩沖區以固定的間隔刷新（默認為1秒），并將內容寫入文件系統緩存中的新段。此分段的內容更尚未被fsync’ed(未被寫入文件系統)，分段是打開的，內容可用于搜索。
• translog被清空，并且文件系統緩存每隔30分鐘進行一次fsync，或者當translog變得太大時進行一次fsync。這個過程在Elasticsearch中稱為flush。在刷新過程中，內存緩沖區被清除，內容被寫入新的文件分段(segment)。當文件分段被fsync’ed并刷新到磁盤，會創建一個新的提交點（其實就是會更新文件偏移量，文件系統會自動做這個操作）。舊的translog被刪除，一個新的開始。

　　下圖顯示了寫入請求和數據流程： 

　　　　

　　2、Update和Delete實現原理

　　刪除和更新操作也是寫操作。但是，Elasticsearch中的文檔是不可變的(immutable)，因此不能刪除或修改。那么，如何刪除/更新文檔呢？ 
　　磁盤上的每個分段(segment)都有一個.del文件與它相關聯。當發送刪除請求時，該文檔未被真正刪除，而是在.del文件中標記為已刪除。此文檔可能仍然能被搜索到，但會從結果中過濾掉。當分段合并時，在.del文件中標記為已刪除的文檔不會被包括在新的合并段中。 
    至于更新，創建新文檔時，Elasticsearch將為該文檔分配一個版本號。對文檔的每次更改都會產生一個新的版本號。當執行更新時，舊版本在.del文件中被標記為已刪除，并且新版本在新的分段中編入索引。舊版本可能仍然與搜索查詢匹配，但是從結果中將其過濾掉。 

　　3、Read的實現原理

　　讀操作由兩個階段組成：

• 查詢階段（Query Phase）
• 獲取階段（Fetch Phase）

　　查詢階段(Query Phase)

　　在此階段，協調節點將搜索請求路由到索引(index)中的所有分片(shards)（包括：主要或副本）。分片獨立執行搜索，并根據相關性分數創建一個優先級排序結果。所有分片將匹配的文檔和相關分數的文檔ID返回給協調節點。協調節點創建一個新的優先級隊列，并對全局結果進行排序?？梢杂泻芏辔臋n匹配結果，但默認情況下，每個分片將前10個結果發送到協調節點，協調創建優先級隊列，從所有分片中分選結果并返回前10個匹配。

　　獲取階段(Fetch Phase)

　　在協調節點對所有結果進行排序，已生成全局排序的文檔列表后，它將從所有分片請求原始文檔。 
　　所有的分片都會豐富文檔并將其返回到協調節點。