原文載于Elastic中文社區(qū): https://elasticsearch.cn/article/171
許多有RDBMS/SQL背景的開發(fā)者，在初次踏入ElasticSearch世界的時候，很容易就想到使用(Wildcard Query)來實現(xiàn)模糊查詢（比如用戶輸入補全)偿警，因為這是和SQL里like操作最相似的查詢方式，用起來感覺非常舒適偶妖。然而近期我們線上一個搜索集群的故障揭示了，濫用wildcard query可能帶來災(zāi)難性的后果政溃。
故障經(jīng)過
線上有一個10來臺機器組成的集群趾访，用于某個產(chǎn)品線的產(chǎn)品搜索。數(shù)據(jù)量并不大董虱，實時更新量也不高扼鞋，并發(fā)搜索量在幾百次/s。通常業(yè)務(wù)高峰期cpu利用率不超過10%愤诱，系統(tǒng)負載看起來很低云头。 但最近這個集群不定期（1天或者隔幾天)會出現(xiàn)CPU沖高到100%的問題，持續(xù)時間從1分鐘到幾分鐘不等淫半。最嚴重的一次持續(xù)了20來分鐘溃槐，導(dǎo)致大量的用戶搜索請無求響應(yīng)，從而造成生產(chǎn)事故科吭。
問題排查
細節(jié)太多昏滴，此處略過，直接給出CPU無故飆高的原因: 研發(fā)在搜索實現(xiàn)上砌溺，根據(jù)用戶輸入的關(guān)鍵詞影涉，在首尾加上通配符，使用wildcard query來實現(xiàn)模糊搜索规伐，例如使用"迪士尼"來搜索含有“迪士尼”關(guān)鍵字的產(chǎn)品蟹倾。 然而用戶輸入的字符串長度沒有做限制，導(dǎo)致首尾通配符中間可能是很長的一個字符串猖闪。 后果就是對應(yīng)的wildcard Query執(zhí)行非常慢鲜棠，非常消耗CPU。
復(fù)現(xiàn)方法
- 創(chuàng)建一個只有一條文檔的索引
POST test_index/type1/?refresh=true
{
"foo": "bar"
}
- 使用wildcard query執(zhí)行一個首尾帶有通配符
*的長字符串查詢
POST /test_index/_search
{
"query": {
"wildcard": {
"foo": {
"value": "*在迪士尼樂園培慌，點亮心中奇夢豁陆。它是一個充滿創(chuàng)造力、冒險精神與無窮精彩的快地吵护。您可在此游覽全球最大的迪士尼城堡——奇幻童話城堡盒音，探索別具一格又令人難忘的六大主題園區(qū)——米奇大街、奇想花園馅而、夢幻世界祥诽、探險島、寶藏灣和明日世界瓮恭，和米奇朋友在一起雄坪，感覺歡樂時光開業(yè)于2016年上海國際旅游度假區(qū)秀沿路亞朵酒店位于上海市浦東新區(qū)滬南公路（滬南公路與秀沿路交匯處），臨近周浦萬達廣場屯蹦、地鐵11號線秀沿路站维哈，距離上海南站绳姨、人民廣場約20公里，距離迪線距*"
}
}
}
}
- 查看結(jié)果
{
"took": 3445,
"timed_out": false,
"_shards": {
"total": 5,
"successful": 5,
"failed": 0
},
"hits": {
"total": 0,
"max_score": null,
"hits":
}
}
即使no hits阔挠，耗時卻是驚人的3.4秒 (測試機是macbook pro, i7 CPU)飘庄，并且執(zhí)行過程中，CPU有一個很高的尖峰谒亦。
線上的查詢比我這個范例要復(fù)雜得多竭宰，會同時查幾個字段空郊，實際測試下來份招，一個查詢可能會執(zhí)行十幾秒鐘。 在有比較多長字符串查詢的時候狞甚，集群可能就DOS了锁摔。
探查深層次根源
為什么對只有一條數(shù)據(jù)的索引做這個查詢開銷這么高？ 直覺上應(yīng)該是瞬間返回結(jié)果才對!
回答這個問題前哼审，可以再做個測試谐腰，如果繼續(xù)加大查詢字符串的長度，到了一定長度后涩盾，ES直接拋異常了十气，服務(wù)器ES里異常給出的cause如下:
Caused by: org.apache.lucene.util.automaton.TooComplexToDeterminizeException: Determinizing automaton with 22082 states and 34182 transitions would result in more than 10000 states. at org.apache.lucene.util.automaton.Operations.determinize(Operations.java:741) ~[lucene-core-6.4.1.jar:6.4.1
該異常來自org.apache.lucene.util.automaton這個包，異常原因的字面含義是說
"自動機過于復(fù)雜而無法確定狀態(tài)： 由于狀態(tài)和轉(zhuǎn)換太多春霍，確定一個自動機需要生成的狀態(tài)超過10000個上限"
網(wǎng)上查找了大量資料后砸西，終于搞清楚了問題的來龍去脈。為了加速通配符和正則表達式的匹配速度址儒，Lucene4.0開始會將輸入的字符串模式構(gòu)建成一個DFA (Deterministic Finite Automaton)芹枷，帶有通配符的pattern構(gòu)造出來的DFA可能會很復(fù)雜，開銷很大莲趣。這個鏈接的博客using-dfa-for-wildcard-matching-problem鸳慈，比較形象的介紹了如何為一個帶有通配符的pattern構(gòu)建DFA。借用博客里的范例喧伞，a*bc這樣的pattern構(gòu)造出來的DFA如下圖:
Lucene構(gòu)造DFA的實現(xiàn)又是如何呢走芋？看了一下Lucene的里相關(guān)的代碼，構(gòu)建過程大致如下:
- org.apache.lucene.search.WildcardQuery里的toAutomaton方法潘鲫，遍歷輸入的通配符pattern翁逞，將每個字符變成一個自動機(automaton)，然后將每個字符的自動機鏈接起來生成一個新的自動機
public static Automaton toAutomaton(Term wildcardquery) {
List<Automaton> automata = new ArrayList<>();
String wildcardText = wildcardquery.text();
for (int i = 0; i < wildcardText.length();) {
final int c = wildcardText.codePointAt(i);
int length = Character.charCount(c);
switch(c) {
case WILDCARD_STRING:
automata.add(Automata.makeAnyString());
break;
case WILDCARD_CHAR:
automata.add(Automata.makeAnyChar());
break;
case WILDCARD_ESCAPE:
// add the next codepoint instead, if it exists
if (i + length < wildcardText.length()) {
final int nextChar = wildcardText.codePointAt(i + length);
length += Character.charCount(nextChar);
automata.add(Automata.makeChar(nextChar));
break;
} // else fallthru, lenient parsing with a trailing \
default:
automata.add(Automata.makeChar(c));
}
i += length;
}
return Operations.concatenate(automata);
}
此時生成的狀態(tài)機是不確定狀態(tài)機次舌，也就是Non-deterministic Finite Automaton（NFA)熄攘。
org.apache.lucene.util.automaton.Operations類里的determinize方法則會將NFA轉(zhuǎn)換為DFA 。
/**
* Determinizes the given automaton.
* <p>
* Worst case complexity: exponential in number of states.
* @param maxDeterminizedStates Maximum number of states created when
* determinizing. Higher numbers allow this operation to consume more
* memory but allow more complex automatons. Use
* DEFAULT_MAX_DETERMINIZED_STATES as a decent default if you don't know
* how many to allow.
* @throws TooComplexToDeterminizeException if determinizing a creates an
* automaton with more than maxDeterminizedStates
*/
public static Automaton determinize(Automaton a, int maxDeterminizedStates) {
代碼注釋里說這個過程的時間復(fù)雜度最差情況下是狀態(tài)數(shù)量的指數(shù)級別彼念！為防止產(chǎn)生的狀態(tài)過多挪圾，消耗過多的內(nèi)存和CPU浅萧，類里面對最大狀態(tài)數(shù)量做了限制
/**
* Default maximum number of states that {@link Operations#determinize} should create.
*/
public static final int DEFAULT_MAX_DETERMINIZED_STATES = 10000;
在有首尾通配符，并且字符串很長的情況下哲思，這個determinize過程會產(chǎn)生大量的state洼畅，甚至會超過上限。
至于NFA和DFA的區(qū)別是什么棚赔？ 如何相互轉(zhuǎn)換帝簇？ 網(wǎng)上有很多數(shù)學層面的資料和論文，限于鄙人算法方面有限的知識靠益，無精力去深入探究丧肴。 但是一個粗淺的理解是: NFA在輸入一個條件的情況下，可以從一個狀態(tài)轉(zhuǎn)移到多種狀態(tài)胧后，而DFA只會有一個確定的狀態(tài)可以轉(zhuǎn)移芋浮，因此DFA在字符串匹配時速度更快。 DFA雖然搜索的時候快壳快，但是構(gòu)造方面的時間復(fù)雜度可能比較高纸巷，特別是帶有首部通配符+長字符串的時候。
回想Elasticsearch官方文檔里對于wildcard query有特別說明眶痰，要避免使用通配符開頭的term瘤旨。
" Note that this query can be slow, as it needs to iterate over many terms. In order to prevent extremely slow wildcard queries, a wildcard term should not start with one of the wildcards * or ?."
結(jié)合對上面wildcard query底層實現(xiàn)的探究，也就不難理解這句話的含義了竖伯！
總結(jié)
wildcard query應(yīng)杜絕使用通配符打頭存哲，實在不得已要這么做，就一定需要限制用戶輸入的字符串長度黔夭。 最好換一種實現(xiàn)方式宏胯，通過在index time做文章，選用合適的分詞器本姥，比如nGram tokenizer預(yù)處理數(shù)據(jù)肩袍，然后使用更廉價的term query來實現(xiàn)同等的模糊搜索功能。 對于部分輸入即提示的應(yīng)用場景婚惫，可以考慮優(yōu)先使用completion suggester, phrase/term suggeter一類性能更好,模糊程度略差的方式查詢氛赐，待suggester沒有匹配結(jié)果的時候，再fall back到更模糊但性能較差的wildcard, regex, fuzzy一類的查詢先舷。
補記： 有同學問regex, fuzzy query是否有同樣的問題艰管，答案是有，原因在于他們底層和wildcard一樣蒋川，都是通過將pattern構(gòu)造成DFA來加速字符串匹配速度的牲芋。
