探究ES suggest search

問題背景

項目中存在的問題

1.項目中主要使用ES進行數據的模糊搜索以及建議搜索，但在查詢數據量較大的索引時會出現偶現的慢查詢。

2.在進行建議搜索時，用戶如果輸入錯誤單詞無法對其進行有效糾正并進行糾正推薦。

3.多個模塊復用同一個mapping文件，在某一模塊搜索時，建議搜索常常會給出并不屬于本模塊的數據。

現有建議查詢方案

由于用戶在輸入的同時要返回建議結果，而用戶輸入的數據往往不會形成一個完整的單詞，所以使用match來進行搜索是無法搜索到結果的。

在項目中我們主要通過ES來做建議查詢和模糊搜索。搜索的語句還是比較直接的，在建議搜索和模糊搜索都是直接使用query加通配符直接來進行查詢的，這樣做的目的是盡可能匹配相似的搜索結果。

ES查詢代碼如下：

假設用戶輸入為test_pro_00，其merchant_id為4

{"query": {"bool": {"must": [{"term": {"merchant_id": 4}}],"should": [{"match": {"product_name": {"query": "test_pro_00"}}},{"match": {"product_name.keyword": {"boost": 2,"query": "test_pro_00"}}},{"wildcard": {"product_name": {"wildcard": "*test_pro_00*"}}}]}},"size": 10 }

這種思路在建議搜索時由于請求頻繁對查詢結果的返回速度要求很高，很容易就會遇到性能的問題。對于模糊搜索，在需要兩個字段進行模糊匹配時也會查詢比較慢。且無法根據不同模塊進行查詢分類。

方案選型

建議搜索，有兩種方案來解決：

1.可以使用 Fuzzy query來進行建議搜索。其核心思想是使用編輯距離來模糊匹配用戶的輸入。

2.使用suggest search解決方案。其核心思想是構建在內存中構建FST樹，從而提升查詢速度。

Fuzzy query劣勢

1.Fuzzy query的查詢是構建在term之上的，而建議搜索所遇到的更多場景則是用戶并沒有進行完整輸入。比如用戶在建議搜索時，希望查詢到的是Adam，用戶在搜索框只輸入了A，而Fuzzy query需要根據這一個字母來進行模糊匹配，其效率是很低的。

2.Fuzzy query會進行編輯距離的計算，其性能是很低的，并不能滿足建議搜索這一場景中，頻繁請求，高速返回的這一需求。

所以，我們認為suggest search更適合建議搜索這一場景。

suggest search原理

針對建議搜索這一問題，Elastic提出了suggest search解決方案。

suggest search查詢的原理主要基于Levenshtein Distance算法和FST算法，這里做一個簡單的講解。

Levenshtein Distance算法

Levenshtein Distance算法常用于計算兩個字符串間的差異，在suggest search中主要用于對用戶輸入的糾正。下面講解一個LD算法的流程來講解其原理。

算法過程

str1或str2的長度為0返回另一個字符串的長度。 if(str1.length0) return str2.length; if(str2.length0) return str1.length;

初始化(n+1)*(m+1)的矩陣d，并讓第一行和列的值從0開始增長。

掃描兩字符串（n*m級的），如果：str1[i] == str2[j]，用temp記錄為0，否則temp記為1。然后在矩陣d[i,j]賦于d[i-1,j]+1 、d[i,j-1]+1、d[i-1,j-1]+temp三者的最小值。

掃描完后，返回矩陣的最后一個值dnm即是它們的距離。

計算相似度公式：1-它們的距離/兩個字符串長度的最大值。

為了直觀表現，我將兩個字符串分別寫到行和列中，實際計算中不需要。我們用字符串“ivan1”和“ivan2”舉例來看看矩陣中值的狀況：

1、第一行和第一列的值從0開始增長

ivan1

	0	1	2	3	4	5
i	1
v	2
a	3
n	4
2	5

2、i列值的產生 Matrix[i - 1, j] + 1 ; Matrix[i, j - 1] + 1 ; Matrix[i - 1, j - 1] + t

ivan1

	0+t=0	1+1=2	2	3	4	5
i	1+1=2	取三者最小值=0
v	2	依次類推：1
a	3	2
n	4	3
2	5	4

3、V列值的產生

ivan1

	0	1	2
i	1	0	1
v	2	1	0
a	3	2	1
n	4	3	2
2	5	4	3

依次類推直到矩陣全部生成

ivan1

	0	1	2	3	4	5
i	1	0	1	2	3	4
v	2	1	0	1	2	3
a	3	2	1	0	1	2
n	4	3	2	1	0	1
2	5	4	3	2	1	1

最后得到它們的距離=1

相似度：1-1/Math.Max(“ivan1”.length,“ivan2”.length) =0.8

FST算法

FST算法主要解決快速查詢的問題。

FST是有限狀態機（FSM）,具有這樣的特性：

• 確定：意味著指定任何一個狀態，只可能最多有一個轉移可以遍歷到。
• 無環： 不可能重復遍歷同一個狀態
• transducer：接收特定的序列，終止于final狀態，同時會輸出一個值。

如下是FST算法對于mar:3，jul:7，jun:6所形成的樹狀結構。

mar:3 指字符串為mar，輸出值為3

jul:7 指字符串為mar，輸出值為7

jun:6 指字符串為mar，輸出值為6

我們可以把輸出值看做是對應關鍵字的文檔地址。

如果輸入值為j，對應FST狀態從0->1，同時繼續往后遍歷剩下的FST，可以得到建議的字符串jun,jul，同時可以得到jun的文檔地址為6+0+0=6，jul文檔地址為6+0+1=7。

FST的構建

FST的構建相對比較復雜，具體的過程可以參看這一篇文章：https://www.shenyanchao.cn/blog/2018/12/04/lucene-fst/

實戰：

在搜索框中查找字段，會很快的返回用戶的可能希望得到的數據，由于用戶每次輸入都會發送查詢請求，所以對查詢速度要求很高，ES 中使用suggest search來對建議搜索進行優化。

suggest search設計了4種類別的Suggester分別是：

Suggestion Mode

• Missing 如索引中已經存在，就不提供建議
• Popular 推薦出現詞頻更加高的詞
• Always 無論是否存在，都提供建議
• 相似性是通過Levenshtein Edit Distance的算法實現的。核心思想就是一個詞改動多少字符就可以和另外一個詞一致。提供了很多可選參數來控制相似度的模糊程度。

Phrase Suggester

• Phrase Suggester在Term Suggester上增加了一些額外的邏輯。Phrase Suggester 則是根據用戶的輸入，結合語句的信息來對用戶做語句的推薦。增加了如下參數：
  • Suggest Mode: missing, popular, always
  • Max Errors: 最多可拼錯的Terms數
  • Confidence: 限制返回結果數，默認為1

Completion Suggester

• 搜索速度很快，適合用戶輸入時進行實時搜索。

• 缺點：FST只能用于前綴查找

Context Suggester

• Completion Suggester的擴展功能

• 在很多情況下用戶輸入信息需要根據上下文進行提示，例如用戶輸入”star”

• 咖啡相關 建議”Starbucks”

• 電影相關 建議”StarWars”

詳細用法可以看這里。

Suggester精準度和召回率比較

精準度

Completion > Phrase > Term

召回率

Term > Phrase > Completion

性能

Completion > Phrase > Term

我們如何應用？

結合四種suggest進行設計

首先，針對用戶實時輸入給出建議，需要使用Completion suggest。

同時由于建議搜索需要有過濾條件，所以使用Context Suggester定義一個category作為分類。

具體數據結構如下圖(已簡化)：

{"index_patterns": ["*_master_product_index","*_master_product_index_update"],"order" : 1,"settings": {"analysis": {"normalizer": {"lowercase": {"type": "custom","char_filter": [],"filter": ["lowercase","asciifolding"]}},"filter": {"autocomplete_filter": {"type": "edge_ngram","min_gram": 1,"max_gram": 20}},"analyzer": {"autocomplete": {"type": "custom","tokenizer": "standard","filter": ["lowercase","asciifolding","autocomplete_filter"]}}}},"mappings": {"product": {"dynamic": "false","properties": {"merchant_id": {"type": "keyword"},"country": {"type": "keyword"},"product_name": {"type": "text","fields": {"t": {"type": "completion","analyzer": "standard"}},"contexts":[{"name": "merchant_id","type": "category","path": "merchant_id"},{"name": "country","type": "category","path": "country"}]}}}} }

進行建議搜索的字段為product_name字段，將他定義為text類型，同時包含一個t的fields用來作為completion搜索的字段。同時需要將數據按照country和merchant_id來進行分類。

查詢語句如下圖：

{"suggest": {"article-suggester": {"prefix": "product","completion": {"field": "product_name","contexts": {"merchant_id": [4],"country":["id"]}}}} }

同時在代碼中判斷Completion Suggester是否有返回數據，如果不存在數據，說明可能用戶存在輸入錯誤的情況，我們使用Term Suggester來推測用戶的輸入。Term查詢語句如下：

{"size": 0,"suggest": {"my-suggest" : {"term" : {"field" : "product_name.t"}}} }

性能比較（壓力測試）

在12線程100連接下進行30s壓力測試，測試結果如下：

優化前優化后

QPS	2155	3116
平均響應延遲	52ms	78ms
內存占用情況	35KB	402.8KB

可以看到使用Completion Suggester的查詢效率有了比較大的提高。但是這是有代價的，我們可以看一下索引占用內存的情況，可以看到內存膨脹了11倍。

內存優化

可以看到使用Completion suggest之后內存占用增大，在實驗中發現分類的類別越多FST所占用的內存就會越大，而我們根據merchent_id做的分類類別數目巨大，加劇了內存的膨脹。所以如果想減小內存占用需要從減少分類數目開始。

這里采用了一個比較簡單的方法——在后臺保存數據時，將merchantId直接存儲在名稱中，譬如建議搜索的數據字段為 product_name，可以將 product_name 加上其對應的merchant_id，最終為4_product_name(假設merchantId為4)，這樣查詢的時候，同樣的也可以將用戶的輸入加上merchantId進行請求，這樣便可以去除掉merchantId這個類別數量較大的分類，從而減少內存的使用。內存優化后結果如下：

優化前使用suggest search優化后進一步優化內存后

QPS	2155	3116	3019.89
平均響應延遲	78ms	52ms	62ms
內存占用情況	35KB	402.8KB	162.7KB

可以看到使用內存優化后，會導致查詢字符串增長，所以會使得QPS略微下降，但可以極大的減少內存的占用情況。

同時需要注意，在構建FST時需要避免使用 Simple analyzer，因為簡單分詞器會將數量詞篩選掉，從而導致merchant_id分類無效。

最終的數據結構如下：

{"index_patterns": ["*_master_product_index","*_master_product_index_update"],"order" : 1,"settings": {"analysis": {"normalizer": {"lowercase": {"type": "custom","char_filter": [],"filter": ["lowercase","asciifolding"]}},"filter": {"autocomplete_filter": {"type": "edge_ngram","min_gram": 1,"max_gram": 20}},"analyzer": {"autocomplete": {"type": "custom","tokenizer": "standard","filter": ["lowercase","asciifolding","autocomplete_filter"]}}}},"mappings": {"product": {"dynamic": "false","properties": {"merchant_id": {"type": "keyword"},"country": {"type": "keyword"},"product_name": {"type": "text","fields": {"t": {"type": "completion","analyzer": "standard"}},"contexts":[{"name": "country","type": "category","path": "country"}]}}}} }

查詢語句如下：

{"suggest": {"article-suggester": {"text": "4_user_input","completion": {"field": "product_name.t"}}} }

結論建議

使用suggest search會大大的提升搜索的速度，但是也會增大索引在內存中的占用。所以要慎用，在資源比較充裕時使用，或者出現性能問題的時候再考慮使用。

資料

FST算法詳解：https://www.shenyanchao.cn/blog/2018/12/04/lucene-fst/

編輯距離詳解：https://www.cnblogs.com/throwable/p/12445082.html

Elastic Search Suggesters : https://www.elastic.co/guide/en/elasticsearch/reference/6.8/search-suggesters.html

總結

以上是生活随笔為你收集整理的探究ES suggest search的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。