圖解 ElasticSearch 搜索原理

摘要

先自上而下,後自底向上的介紹 ElasticSearch 的底層工作原理,試圖回答以下問題:

版本

elasticsearch 版本: elasticsearch-2.2.0

內容

圖解 ElasticSearch

雲上的集羣

集羣裏的盒子

雲裏面的每個白色正方形的盒子代表一個節點——Node。

節點之間

在一個或者多個節點直接,多個綠色小方塊組合在一起形成一個 ElasticSearch 的索引。

索引裏的小方塊

在一個索引下,分佈在多個節點裏的綠色小方塊稱爲分片——Shard。

Shard=Lucene Index

一個 ElasticSearch 的 Shard 本質上是一個 Lucene Index。

Lucene 是一個 Full Text 搜索庫(也有很多其他形式的搜索庫),ElasticSearch 是建立在 Lucene 之上的。接下來的故事要說的大部分內容實際上是 ElasticSearch 如何基於 Lucene 工作的。

圖解 Lucene

Mini 索引——segment

在 Lucene 裏面有很多小的 segment,我們可以把它們看成 Lucene 內部的 mini-index。

Segment 內部

有着許多數據結構

最最重要的 Inverted Index

Inverted Index 主要包括兩部分:

  1. 一個有序的數據字典 Dictionary(包括單詞 Term 和它出現的頻率)。
  2. 與單詞 Term 對應的 Postings(即存在這個單詞的文件)。

當我們搜索的時候,首先將搜索的內容分解,然後在字典裏找到對應 Term,從而查找到與搜索相關的文件內容。

查詢 “the fury”

自動補全(AutoCompletion-Prefix)

如果想要查找以字母 “c” 開頭的字母,可以簡單的通過二分查找(Binary Search)在 Inverted Index 表中找到例如 “choice”、“coming” 這樣的詞(Term)。

昂貴的查找

如果想要查找所有包含 “our” 字母的單詞,那麼系統會掃描整個 Inverted Index,這是非常昂貴的。

在此種情況下,如果想要做優化,那麼我們面對的問題是如何生成合適的 Term。

問題的轉化

對於以上諸如此類的問題,我們可能會有幾種可行的解決方案:

解決拼寫錯誤

一個 Python 庫 爲單詞生成了一個包含錯誤拼寫信息的樹形狀態機,解決拼寫錯誤的問題。

Stored Field 字段查找

當我們想要查找包含某個特定標題內容的文件時,Inverted Index 就不能很好的解決這個問題,所以 Lucene 提供了另外一種數據結構 Stored Fields 來解決這個問題。本質上,Stored Fields 是一個簡單的鍵值對 key-value。默認情況下,ElasticSearch 會存儲整個文件的 JSON source。

Document Values 爲了排序,聚合

即使這樣,我們發現以上結構仍然無法解決諸如:排序、聚合、facet,因爲我們可能會要讀取大量不需要的信息。

所以,另一種數據結構解決了此種問題:Document Values。這種結構本質上就是一個列式的存儲,它高度優化了具有相同類型的數據的存儲結構。

爲了提高效率,ElasticSearch 可以將索引下某一個 Document Value 全部讀取到內存中進行操作,這大大提升訪問速度,但是也同時會消耗掉大量的內存空間。

總之,這些數據結構 Inverted Index、Stored Fields、Document Values 及其緩存,都在 segment 內部。

搜索發生時

搜索時,Lucene 會搜索所有的 segment 然後將每個 segment 的搜索結果返回,最後合併呈現給客戶。

Lucene 的一些特性使得這個過程非常重要:

緩存的故事

當 ElasticSearch 索引一個文件的時候,會爲文件建立相應的緩存,並且會定期(每秒)刷新這些數據,然後這些文件就可以被搜索到。

隨着時間的增加,我們會有很多 segments,

所以 ElasticSearch 會將這些 segment 合併,在這個過程中,segment 會最終被刪除掉

這就是爲什麼增加文件可能會使索引所佔空間變小,它會引起 merge,從而可能會有更多的壓縮。

舉個栗子

有兩個 segment 將會 merge

這兩個 segment 最終會被刪除,然後合併成一個新的 segment

這時這個新的 segment 在緩存中處於 cold 狀態,但是大多數 segment 仍然保持不變,處於 warm 狀態。

以上場景經常在 Lucene Index 內部發生的。

在 Shard 中搜索

ElasticSearch 從 Shard 中搜索的過程與 Lucene Segment 中搜索的過程類似。

與在 Lucene Segment 中搜索不同的是,Shard 可能是分佈在不同 Node 上的,所以在搜索與返回結果時,所有的信息都會通過網絡傳輸。

需要注意的是:

1 次搜索查找 2 個 shard = 2 次分別搜索 shard

對於日誌文件的處理

當我們想搜索特定日期產生的日誌時,通過根據時間戳對日誌文件進行分塊與索引,會極大提高搜索效率。

當我們想要刪除舊的數據時也非常方便,只需刪除老的索引即可。

在上種情況下,每個 index 有兩個 shards

如何 Scale

shard 不會進行更進一步的拆分,但是 shard 可能會被轉移到不同節點上

所以,如果當集羣節點壓力增長到一定的程度,我們可能會考慮增加新的節點,這就會要求我們對所有數據進行重新索引,這是我們不太希望看到的,所以我們需要在規劃的時候就考慮清楚,如何去平衡足夠多的節點與不足節點之間的關係。

節點分配與 Shard 優化

路由 Routing

每個節點,每個都存留一份路由表,所以當請求到任何一個節點時,ElasticSearch 都有能力將請求轉發到期望節點的 shard 進一步處理。

一個真實的請求

Query

Query 有一個類型 filtered,以及一個 multi_match 的查詢

Aggregation

根據作者進行聚合,得到 top10 的 hits 的 top10 作者的信息

請求分發

這個請求可能被分發到集羣裏的任意一個節點

上帝節點

這時這個節點就成爲當前請求的協調者(Coordinator),它決定:

路由

在真實搜索之前

ElasticSearch 會將 Query 轉換成 Lucene Query

然後在所有的 segment 中執行計算

對於 Filter 條件本身也會有緩存

但 queries 不會被緩存,所以如果相同的 Query 重複執行,應用程序自己需要做緩存

所以,

返回

搜索結束之後,結果會沿着下行的路徑向上逐層返回。

參考

參考來源:

SlideShare: Elasticsearch From the Bottom Up

Youtube: Elasticsearch from the bottom up

Wiki: Document-term matrix

Wiki: Search engine indexing

Skip list

Standford Edu: Faster postings list intersection via skip pointers

StackOverflow: how an search index works when querying many words?

StackOverflow: how does lucene calculate intersection of documents so fast?

Lucene and its magical indexes

misspellings 2.0c: A tool to detect misspellings

本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源https://www.cnblogs.com/richaaaard/p/5226334.html