1、搜索引擎為什么快？

倒排索引核心原理

概括的說，一個(gè)優(yōu)秀的搜索引擎的設(shè)計(jì)，至少應(yīng)該具備以下幾點(diǎn)要求：

• 高效的壓縮算法

• 快速的編碼和解碼算法

• 合理的數(shù)據(jù)結(jié)構(gòu)

• 通用最小化算法

結(jié)合以上幾點(diǎn)，后面我將通過一個(gè)案例來講解，倒排索引的基本原理是什么。在了解“倒排索引”之前，我們先來看一下何為“索引”。

一本漢語字典，如果我們想要從中找到某個(gè)字，通常我們會(huì)通過字典最前面的拼音檢索或者是部首檢索來查找。其實(shí)漢語字典的正文本身就是一個(gè)索引，比如我們要查找“吳”字，很自然的就想到了“吳”的拼音是“wu”，w在26個(gè)字母中在很靠后的位置，基本上就可以確定“吳”字的大致位置，然后按照字典序可以在w字母的漢字里精確的找到這個(gè)字，因?yàn)闈h字本身就是按照字典序排列的，這種按照一定規(guī)則排序的目錄在關(guān)系型數(shù)據(jù)庫中一般叫做“聚集索引”

除了這種索引，通常我們還了解一種類似于“偏旁部首”的檢索方式稱之為“非聚集索引”，我們這里不展開來討論什么是聚集索引和非聚集索引。但是我們可以確定的是，不管是什么索引，它的目的都是幫助我們快速檢索數(shù)據(jù)的。

在數(shù)據(jù)庫領(lǐng)域里，索引可以概括為一種幫助我們快速檢索數(shù)據(jù)的以文件形式落地的數(shù)據(jù)結(jié)構(gòu)。

以MySQL為例，如圖1-1所示：

左側(cè)是MySql安裝文件的data目錄，右側(cè)使我們使用數(shù)據(jù)庫客戶端打開數(shù)據(jù)庫后的樣式，左側(cè)文件分別對應(yīng)了右側(cè)數(shù)據(jù)庫中的數(shù)據(jù)庫名，我們以“mysql”這個(gè)數(shù)據(jù)庫為例，文件夾中每個(gè)文件都有若干個(gè)不同后綴的同名文件，分別對應(yīng)右側(cè)某個(gè)數(shù)據(jù)表，不同的后綴代表不同的數(shù)據(jù)類型，其中.frm文件代表當(dāng)前文件存儲(chǔ)的是數(shù)據(jù)表的表結(jié)構(gòu)，.MYD和.MYI文件則代表了當(dāng)前文件是myisam存儲(chǔ)引擎下的數(shù)據(jù)文件和索引文件，.ibd則代表當(dāng)前文件是innodb存儲(chǔ)引擎下的索引文件，只不過innodb的數(shù)據(jù)和索引使用了同一個(gè)文件。

不管是元數(shù)據(jù)還是索引數(shù)據(jù)，他們最終都是以“文件”的形式存儲(chǔ)在磁盤中的，只不過不同的文件內(nèi)部使用的數(shù)據(jù)結(jié)構(gòu)各不相同。而MySql使用的數(shù)據(jù)結(jié)構(gòu)是B+Trees。但是這種數(shù)據(jù)結(jié)構(gòu)并不適用于倒排索引，原因我們會(huì)在后面的文章中提到。

ES倒排原理

假設(shè)需要對下面兩個(gè)工地的信息進(jìn)行倒排索引的創(chuàng)建：

文檔ID為001，工地名稱為“北京海淀花園小區(qū)”；
文檔ID為002，工地名稱為“北京朝陽星空小區(qū)”。

首先，ES將文檔交給分析器進(jìn)行處理，處理的過程包括字符過濾、分詞和分詞過濾，最終的處理結(jié)果是文檔內(nèi)容被表示為一系列關(guān)鍵詞信息（關(guān)鍵詞本身以及它在文檔中出現(xiàn)的位置信息和詞性信息）的集合。如下圖所示。

3、其次，ES根據(jù)分析結(jié)果建立文檔-詞語矩陣，用以表示詞語和文檔的包含關(guān)系，如圖所示。

4、文檔-詞語矩陣建立完成之后，接著需要建立基于詞語的倒排索引。ES會(huì)遍歷文檔詞語矩陣中的每一個(gè)詞語，然后將包含該詞語的文檔信息與該詞語建立一種映射關(guān)系。映射關(guān)系中的詞語集合叫作Term Dictionary。映射中的文檔集合信息不僅包含文檔ID，還包含詞語在文檔中的位置和詞頻信息，包含這些文檔信息的結(jié)構(gòu)叫作Posting List。對于一個(gè)規(guī)模很大的文檔集合來說，可能包含幾十萬甚至上百萬的詞語集合，能否快速定位某個(gè)詞語，直接影響搜索時(shí)的響應(yīng)速度。因此需要一種高效的數(shù)據(jù)結(jié)構(gòu)對映射關(guān)系中的詞語集合進(jìn)行索引，這種結(jié)構(gòu)叫作Term Index。上述3種結(jié)構(gòu)結(jié)合在一起就構(gòu)成了ES的倒排索引結(jié)構(gòu)，邏輯關(guān)系如圖所示。

本例中的倒排索引結(jié)構(gòu)如圖所示。

2、實(shí)際es中倒排索引的存儲(chǔ)結(jié)構(gòu)

2.1 倒排表（Posting List）

索引文件中分別存儲(chǔ)了不同的數(shù)據(jù)

其中倒排表包含某個(gè)詞項(xiàng)的所有id的數(shù)據(jù)存儲(chǔ)了在.doc文件中；

2.2 詞項(xiàng)字典（Term Dictionary）

詞項(xiàng)字典包含了index field的所有經(jīng)過normalization token filters處理之后的詞項(xiàng)數(shù)據(jù)，最終存儲(chǔ)在.tim文件中。

所謂normalization其實(shí)是一個(gè)如去重、時(shí)態(tài)統(tǒng)一、大小寫統(tǒng)一、近義詞處理等類似的相關(guān)操作；詞項(xiàng)索引就是為了加速詞項(xiàng)字典檢索的一種數(shù)據(jù)結(jié)構(gòu)，落地文件為.tip。.tip文件和.tim文件的數(shù)據(jù)結(jié)構(gòu)如下圖2-2所示

2.3 詞項(xiàng)索引（Term Index）

需要一種高效的數(shù)據(jù)結(jié)構(gòu)對映射關(guān)系中的詞語集合也就是Term Dictionary進(jìn)行索引，這種結(jié)構(gòu)叫作Term Index。Term Index最開始是用字典樹實(shí)現(xiàn)，luncence4.0之后采用FST來優(yōu)化。

3、字典樹：Trie（Prefix Tree）原理

Lucene中對倒排索引Term DIctionary以及Term Index的數(shù)據(jù)壓縮和優(yōu)化算法，最簡單的理解，Term Index 就像一本詞典的目錄一樣

但是實(shí)際上Term可以是任意的 byte 數(shù)組，而不僅僅是英文字符，因此實(shí)際的 Term Index 是一棵 Trie Tree：

如圖所示是一棵 Trie Tree。這棵 Trie Tree 不會(huì)包含所有的 term，它包含的是 term 的一些前綴。通過 Term Index 可以快速地定位到 Term Dictionary 的某個(gè) offset，然后從這個(gè)位置再往后順序查找。再加上一些壓縮技術(shù) e.g. FST，Term Index 需要的存儲(chǔ)空間非常小，可能只有所有 term 占用空間的幾十分之一，因此 Term Index 被完全緩存在內(nèi)存中是沒有問題的。

使用了 Term Index 后，ES的倒排索引整體效果如下

現(xiàn)在我們可以很清楚地知道為什么ES的檢索要比MySQL快得多了。在MySQL中，即使建立了索引，但索引是以B+ Tree的形式存儲(chǔ)在磁盤上的，在數(shù)據(jù)量比較大的情況下，想要檢索到一條記錄，需要若干次的random access的磁盤操作。而ES在Term Dictionary（相當(dāng)于MySQL中的索引）的基礎(chǔ)上，又添加了Term Index這一結(jié)構(gòu)，并且直接以Trie Tree的形式緩存在內(nèi)存中。在檢索一個(gè)term時(shí)，只需要從Term Index查找到對應(yīng)的Term Dictionary的block的位置，再到磁盤上去訪問對應(yīng)的數(shù)據(jù)，大大減少了對磁盤的random access操作的次數(shù)。

2.4減小Term Index存儲(chǔ)空間 —— FST

Term Index要被直接緩存在內(nèi)存中以提升查找速度，那么就必然要采用某種結(jié)構(gòu)來壓縮Term Index。Term Index在內(nèi)存中就是以FST（Finite State Transducers，有限狀態(tài)轉(zhuǎn)換機(jī)）的形式來存儲(chǔ)的。

FST是一種類Trie Tree，使用FSM作為數(shù)據(jù)結(jié)構(gòu)，可以理解為key -> value形式。

• 空間占用?。和ㄟ^對前綴和后綴的重復(fù)利用，壓縮了存儲(chǔ)空間；

• 查詢速度快：時(shí)間復(fù)雜度為O(len(str))；

3、Elasticsearch其它優(yōu)化

Elasticsearch 的基礎(chǔ)是 Lucene，所有的索引和文檔數(shù)據(jù)是存儲(chǔ)在本地的磁盤中，具體的路徑可在 ES 的配置文件…/config/elasticsearch.yml中配置，如下：

#
# Path to directory where to store the data (separate multiple locations by comma):
#
path.data: /path/to/data
#
# Path to log files:
#
path.logs: /path/to/logs

磁盤在現(xiàn)代服務(wù)器上通常都是瓶頸。Elasticsearch重度使用磁盤，你的磁盤能處理的吞吐量越大，你的節(jié)點(diǎn)就越穩(wěn)定。這里有一些優(yōu)化磁盤I/O的技巧：

• 使用SSD就像其他地方提過的，他們比機(jī)械磁盤優(yōu)秀多了。

• 使用RAID0。條帶化RAID會(huì)提高磁盤IO，代價(jià)顯然就是當(dāng)一塊硬盤故障時(shí)整個(gè)就故障了。不要使用鏡像或者奇偶校驗(yàn)RAID，因?yàn)楦北疽呀?jīng)提供了這個(gè)功能。

• 另外，使用多塊硬盤，并允許Elasticsearch 通過多個(gè)path data目錄配置把數(shù)據(jù)條帶化分配到它們上面。

• 不要使用遠(yuǎn)程掛載的存儲(chǔ)，比如NFS或者SMB/CIFS。這個(gè)引入的延遲對性能來說完全是背道而馳的。

優(yōu)化-分片策略

合理設(shè)置分片數(shù)

分片和副本的設(shè)計(jì)為 ES 提供了支持分布式和故障轉(zhuǎn)移的特性，但并不意味著分片和副本是可以無限分配的。而且索引的分片完成分配后由于索引的路由機(jī)制，我們是不能重新修改分片數(shù)的。

可能有人會(huì)說，我不知道這個(gè)索引將來會(huì)變得多大，并且過后我也不能更改索引的大小，所以為了保險(xiǎn)起見，還是給它設(shè)為 1000 個(gè)分片吧。但是需要知道的是，一個(gè)分片并不是沒有代價(jià)的。需要了解：

• 一個(gè)分片的底層即為一個(gè) Lucene 索引，會(huì)消耗一定文件句柄、內(nèi)存、以及 CPU運(yùn)轉(zhuǎn)。

• 每一個(gè)搜索請求都需要命中索引中的每一個(gè)分片，如果每一個(gè)分片都處于不同的節(jié)點(diǎn)還好， 但如果多個(gè)分片都需要在同一個(gè)節(jié)點(diǎn)上競爭使用相同的資源就有些糟糕了。

• 用于計(jì)算相關(guān)度的詞項(xiàng)統(tǒng)計(jì)信息是基于分片的。如果有許多分片，每一個(gè)都只有很少的數(shù)據(jù)會(huì)導(dǎo)致很低的相關(guān)度。

一個(gè)業(yè)務(wù)索引具體需要分配多少分片可能需要架構(gòu)師和技術(shù)人員對業(yè)務(wù)的增長有個(gè)預(yù)先的判斷，橫向擴(kuò)展應(yīng)當(dāng)分階段進(jìn)行。為下一階段準(zhǔn)備好足夠的資源。 只有當(dāng)你進(jìn)入到下一個(gè)階段，你才有時(shí)間思考需要作出哪些改變來達(dá)到這個(gè)階段。一般來說，我們遵循一些原則：

• 控制每個(gè)分片占用的硬盤容量不超過 ES 的最大 JVM 的堆空間設(shè)置（一般設(shè)置不超過 32G，參考下文的 JVM 設(shè)置原則），因此，如果索引的總?cè)萘吭?500G 左右，那分片大小在 16 個(gè)左右即可；當(dāng)然，最好同時(shí)考慮原則 2。

• 考慮一下 node 數(shù)量，一般一個(gè)節(jié)點(diǎn)有時(shí)候就是一臺(tái)物理機(jī)，如果分片數(shù)過多，大大超過了節(jié)點(diǎn)數(shù)，很可能會(huì)導(dǎo)致一個(gè)節(jié)點(diǎn)上存在多個(gè)分片，一旦該節(jié)點(diǎn)故障，即使保持了 1 個(gè)以上的副本，同樣有可能會(huì)導(dǎo)致數(shù)據(jù)丟失，集群無法恢復(fù)。所以， 一般都設(shè)置分片數(shù)不超過節(jié)點(diǎn)數(shù)的 3 倍。

• 主分片，副本和節(jié)點(diǎn)最大數(shù)之間數(shù)量，我們分配的時(shí)候可以參考以下關(guān)系：

節(jié)點(diǎn)數(shù)<=主分片數(shù) *（副本數(shù)+1）

推遲分片分配

對于節(jié)點(diǎn)瞬時(shí)中斷的問題，默認(rèn)情況，集群會(huì)等待一分鐘來查看節(jié)點(diǎn)是否會(huì)重新加入，如果這個(gè)節(jié)點(diǎn)在此期間重新加入，重新加入的節(jié)點(diǎn)會(huì)保持其現(xiàn)有的分片數(shù)據(jù)，不會(huì)觸發(fā)新的分片分配。這樣就可以減少 ES 在自動(dòng)再平衡可用分片時(shí)所帶來的極大開銷。

通過修改參數(shù) delayed_timeout ，可以延長再均衡的時(shí)間，可以全局設(shè)置也可以在索引級(jí)別進(jìn)行修改：

#PUT /_all/_settings
{
    "settings": {
        "index.unassigned.node_left.delayed_timeout": "5m"
    }
}

優(yōu)化-路由選擇

當(dāng)我們查詢文檔的時(shí)候， Elasticsearch 如何知道一個(gè)文檔應(yīng)該存放到哪個(gè)分片中呢？它其實(shí)是通過下面這個(gè)公式來計(jì)算出來：

shard = hash(routing) % number_of_primary_shards

routing 默認(rèn)值是文檔的 id，也可以采用自定義值，比如用戶 id。

不帶routing查詢

在查詢的時(shí)候因?yàn)椴恢酪樵兊臄?shù)據(jù)具體在哪個(gè)分片上，所以整個(gè)過程分為2個(gè)步驟

• 分發(fā)：請求到達(dá)協(xié)調(diào)節(jié)點(diǎn)后，協(xié)調(diào)節(jié)點(diǎn)將查詢請求分發(fā)到每個(gè)分片上。

• 聚合：協(xié)調(diào)節(jié)點(diǎn)搜集到每個(gè)分片上查詢結(jié)果，在將查詢的結(jié)果進(jìn)行排序，之后給用戶返回結(jié)果。

帶routing查詢

查詢的時(shí)候，可以直接根據(jù)routing 信息定位到某個(gè)分配查詢，不需要查詢所有的分配，經(jīng)過協(xié)調(diào)節(jié)點(diǎn)排序。向上面自定義的用戶查詢，如果routing 設(shè)置為userid 的話，就可以直接查詢出數(shù)據(jù)來，效率提升很多。

寫入速度優(yōu)化

ES 的默認(rèn)配置，是綜合了數(shù)據(jù)可靠性、寫入速度、搜索實(shí)時(shí)性等因素。實(shí)際使用時(shí)，我們需要根據(jù)公司要求，進(jìn)行偏向性的優(yōu)化。

針對于搜索性能要求不高，但是對寫入要求較高的場景，我們需要盡可能的選擇恰當(dāng)寫優(yōu)化策略。綜合來說，可以考慮以下幾個(gè)方面來提升寫索引的性能.

• 加大Translog Flush，目的是降低Iops、Writeblock。

• 增加Index Refesh間隔，目的是減少Segment Merge的次數(shù)。

• 調(diào)整Bulk 線程池和隊(duì)列。

• 優(yōu)化節(jié)點(diǎn)間的任務(wù)分布。

• 優(yōu)化Lucene層的索引建立，目的是降低CPU及IO

優(yōu)化存儲(chǔ)設(shè)備

ES 是一種密集使用磁盤的應(yīng)用，在段合并的時(shí)候會(huì)頻繁操作磁盤，所以對磁盤要求較高，當(dāng)磁盤速度提升之后，集群的整體性能會(huì)大幅度提高。

合理使用合并

Lucene 以段的形式存儲(chǔ)數(shù)據(jù)。當(dāng)有新的數(shù)據(jù)寫入索引時(shí)， Lucene 就會(huì)自動(dòng)創(chuàng)建一個(gè)新的段。

隨著數(shù)據(jù)量的變化，段的數(shù)量會(huì)越來越多，消耗的多文件句柄數(shù)及 CPU 就越多，查詢效率就會(huì)下降。

由于 Lucene 段合并的計(jì)算量龐大，會(huì)消耗大量的 I/O，所以 ES 默認(rèn)采用較保守的策略，讓后臺(tái)定期進(jìn)行段合并。

減少 Refresh 的次數(shù)

Lucene 在新增數(shù)據(jù)時(shí)，采用了延遲寫入的策略，默認(rèn)情況下索引的refresh_interval 為1 秒。

Lucene 將待寫入的數(shù)據(jù)先寫到內(nèi)存中，超過 1 秒（默認(rèn)）時(shí)就會(huì)觸發(fā)一次 Refresh，然后 Refresh 會(huì)把內(nèi)存中的的數(shù)據(jù)刷新到操作系統(tǒng)的文件緩存系統(tǒng)中。

如果我們對搜索的實(shí)效性要求不高，可以將 Refresh 周期延長，例如 30 秒。

這樣還可以有效地減少段刷新次數(shù)，但這同時(shí)意味著需要消耗更多的 Heap 內(nèi)存。

加大 Flush 設(shè)置

Flush 的主要目的是把文件緩存系統(tǒng)中的段持久化到硬盤，當(dāng) Translog 的數(shù)據(jù)量達(dá)到 512MB 或者 30 分鐘時(shí)，會(huì)觸發(fā)一次 Flush。

index.translog.flush_threshold_size 參數(shù)的默認(rèn)值是 512MB，我們進(jìn)行修改。

增加參數(shù)值意味著文件緩存系統(tǒng)中可能需要存儲(chǔ)更多的數(shù)據(jù)，所以我們需要為操作系統(tǒng)的文件緩存系統(tǒng)留下足夠的空間。

減少副本的數(shù)量

ES 為了保證集群的可用性，提供了 Replicas（副本）支持，然而每個(gè)副本也會(huì)執(zhí)行分析、索引及可能的合并過程，所以 Replicas 的數(shù)量會(huì)嚴(yán)重影響寫索引的效率。

當(dāng)寫索引時(shí)，需要把寫入的數(shù)據(jù)都同步到副本節(jié)點(diǎn)，副本節(jié)點(diǎn)越多，寫索引的效率就越慢。

如果我們需要大批量進(jìn)行寫入操作，可以先禁止Replica復(fù)制，設(shè)置

index.number_of_replicas: 0 關(guān)閉副本。在寫入完成后， Replica 修改回正常的狀態(tài)。

內(nèi)存設(shè)置

ES 默認(rèn)安裝后設(shè)置的內(nèi)存是 1GB，對于任何一個(gè)現(xiàn)實(shí)業(yè)務(wù)來說，這個(gè)設(shè)置都太小了。如果是通過解壓安裝的 ES，則在 ES 安裝文件中包含一個(gè) jvm.option 文件，添加如下命令來設(shè)置 ES 的堆大小， Xms 表示堆的初始大小， Xmx 表示可分配的最大內(nèi)存，都是 1GB。

確保 Xmx 和 Xms 的大小是相同的，其目的是為了能夠在 Java 垃圾回收機(jī)制清理完堆區(qū)后不需要重新分隔計(jì)算堆區(qū)的大小而浪費(fèi)資源，可以減輕伸縮堆大小帶來的壓力。

假設(shè)你有一個(gè) 64G 內(nèi)存的機(jī)器，按照正常思維思考，你可能會(huì)認(rèn)為把 64G 內(nèi)存都給ES 比較好，但現(xiàn)實(shí)是這樣嗎， 越大越好？雖然內(nèi)存對 ES 來說是非常重要的，但是答案是否定的！

因?yàn)?ES 堆內(nèi)存的分配需要滿足以下兩個(gè)原則：

• 不要超過物理內(nèi)存的 50%： Lucene 的設(shè)計(jì)目的是把底層 OS 里的數(shù)據(jù)緩存到內(nèi)存中。Lucene 的段是分別存儲(chǔ)到單個(gè)文件中的，這些文件都是不會(huì)變化的，所以很利于緩存，同時(shí)操作系統(tǒng)也會(huì)把這些段文件緩存起來，以便更快的訪問。如果我們設(shè)置的堆內(nèi)存過大， Lucene 可用的內(nèi)存將會(huì)減少，就會(huì)嚴(yán)重影響降低 Lucene 的全文本查詢性能。

• 堆內(nèi)存的大小最好不要超過 32GB：在 Java 中，所有對象都分配在堆上，然后有一個(gè) Klass Pointer 指針指向它的類元數(shù)據(jù)。這個(gè)指針在 64 位的操作系統(tǒng)上為 64 位， 64 位的操作系統(tǒng)可以使用更多的內(nèi)存（2^64）。在 32 位的系統(tǒng)上為 32 位， 32 位的操作系統(tǒng)的最大尋址空間為 4GB（2^32）。但是 64 位的指針意味著更大的浪費(fèi)，因?yàn)槟愕闹羔槺旧泶罅恕＠速M(fèi)內(nèi)存不算，更糟糕的是，更大的指針在主內(nèi)存和緩存器（例如 LLC, L1 等）之間移動(dòng)數(shù)據(jù)的時(shí)候，會(huì)占用更多的帶寬。

最終我們都會(huì)采用 31 G 設(shè)置

-Xms 31g

-Xmx 31g

假設(shè)你有個(gè)機(jī)器有 128 GB 的內(nèi)存，你可以創(chuàng)建兩個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)內(nèi)存分配不超過 32 GB。也就是說不超過 64 GB 內(nèi)存給 ES 的堆內(nèi)存，剩下的超過 64 GB 的內(nèi)存給 Lucene。文章來源地址http://www.zghlxwxcb.cn/news/detail-758816.html

重要配置

巧用緩存