前言
這是帥丙真實事件，大家都知道很多公司都是有故障等級這麼一說的，這就是敖丙在公司背的P0級故障，敖丙差點因此
被解僱，事情經過十分驚心動魄，我的心臟病都差點復發。事故等級主要針對生產環境，劃分依據類似於bug等級。
P0屬於最高級別事故，比如崩潰，頁面無法訪問，主流程不通，主功能未實現，或者在影響面上影響很大（即使bug本身不嚴重）。
P1事故屬於高級別事故，一般屬於主功能上的分支，支線流程，核心次功能等，後面還有P2，P3等，主要根據企業實際情況劃分。
正文
敖丙之前也負責公司的商品搜索業務，因為業務體量增速太快了，商品表中的商品數據也很快躍入千萬級別，查詢的RT（response time 響應時間）也越來越高了，而且產品說需要根據更多維度去查詢商品。
因為之前我們都是根據商品的名稱去查詢的，但是電商其實都會根據很多個維度去查詢商品。
就比如大家去淘寶的查詢的時候就會發現，你搜商品名稱、顏色、標籤等等多個維度都可以找到這個商品，就比如下圖的搜索，我只是搜了【帥丙】你會發現，名字裡面也沒有連續的帥丙兩個字，有帥和丙的出來了
大家知道的傳統的關係型數據庫都是用什麼 name like %帥丙% 這樣的方式查詢的，而且查詢出來的結果肯定只能是name裡面帶帥丙的對吧。
那你還想搜別的字段比如什麼尺寸、關鍵詞、價格等等，都能搜到帥丙，這相當於是多個維度的了，傳統的關係型數據庫做不到呀。
做技術選型的時候，帥丙第一時間想到了搜索引擎。
當時市面是比較流行的有：Apache Lucene、Elasticsearch、Solr
搜索引擎我後面會講ELK（Elasticsearch、Logstash、Kibana）和Canal，我呀真的是太寵你們了，這樣會不會把你們慣壞了。
帥丙我呀，噼裡啪啦一頓操作，最後得出結論：
相對來講，如果考慮靜態搜索，Sorl相對更合適。
如果考慮實時，涉及到分佈式，Elasticsearch相對合適。
那我們商品還是要實時的呀，你後臺改了價格啥的，是不是都要實時同步出去，不然不是炸了嘛。
看到這，我想可愛的你和帥丙心中都有了答案：Elasticsearch這是個神一樣的引擎。
我這裡就做一個簡單的介紹就好了，細節的點我們後面去他的章節講，啥都寫了，敖丙哪裡有這麼多素材寫文章？
ElasticSearch是一個基於Lucene的搜索服務器。
它提供了一個分佈式多用戶能力的全文搜索引擎，基於RESTful web接口。
Elasticsearch是用Java語言開發的，並作為Apache許可條款下的開放源碼發佈，是一種流行的企業級搜索引擎。
ElasticSearch用於雲計算中，能夠達到實時搜索，穩定，可靠，快速，安裝使用方便。官方客戶端在Java、.NET（C#）、PHP、Python、Apache Groovy、Ruby和許多其他語言中都是可用的。
根據DB-Engines的排名顯示，Elasticsearch是最受歡迎的企業搜索引擎，其次是Apache Solr，也是基於Lucene。
看過敖丙之前文章的朋友都知道，我們做技術選型之前，要做什麼呀，設計！
我們要去了解這玩意的好處、壞處、常見的坑、出了問題的應急預案等等，還有他的數據同步機制啊，持久化機制啥的，就是高可用嘛。
同樣的我不大篇幅介紹了，以後都會寫的嘛，我就給大家看看我當時做的設計吧。
這個只是最初的demo，詳細的終稿我就不給大家看了，因為有很多公司內部的邏輯。
不過大家還是可以看到敖丙真的考慮了很多，還是那句話，不打沒把握的仗！
設計做好敖丙就卡卡卡 的用起來了。
說實話，真香，這玩意真的好用，學習成本也很低，查詢語句分分鐘掌握了，官網文檔把功能介紹得清晰無比。
https://www.elastic.co/cn/
用著用著重頭戲來了，你們都知道敖丙我是做電商活動的，都是什麼很高的流量打進來這樣，還是如往常一樣上線了一個活動。
這是一個月飛風高的夜晚，絲絲涼風迎面吹來，敖丙悠閒的坐在椅子上，手裡拿著破舊的茶杯，喝著外婆炒的苦荊茶，享受著這愜意的時光。
突然，說時遲那時快，運維打來了緊急電話ES集群CPU打到了99%要掛了，我的心驀然一痛，心裡還在慶幸還是集群沒崩。
然後他接著說了一句，不好集群掛了！
敖丙卒，本篇完….
開玩笑的哈，不過當時敖丙真的要死的心真的都要有了，就在崩掉的1分鐘內，就有用戶反饋搜索未響應，我第一時間想到的就是重啟，於是我一個健步衝出去，開啟電腦，進機器，輸入了重啟命令。
好了，是的好了，還好有驚無險，不過只過了10秒，集群又99%了，吶呢？
我又只能重啟了，這次沒掛，過了很久很久，直到活動結束，還是沒掛。
查找問題
但是這次影響到線上，3分鐘的搜索未響應，我想我估計明天是要去財務領工資，提前回家過年了。
還好Leader說沒事，先找到問題，把他修復掉。
你們都知道敖丙天才來的，我第一時間想到的就是看日誌，我登上去看es沒報錯，再看本身的服務，除了超時的錯誤啥都沒有，臥槽，是的當時我腦袋嗡嗡響。
不過我繼續想為啥是我的搜索掛了，會不會是有人搜了什麼奇怪的東西？
我打開了我的搜索日誌！！！
臥槽這不是吧，哪個坑爹玩意搜這麼長的一串中文，差不多250個字吧。
但是我一想，搜這麼長也不應該打掛服務啊，會不會是我寫了bug！
我臉頰流下一滴汗水，我看了看周圍，發現沒人注意到我的緊張，我故作鎮定的把它擦掉。
我仔細一想，別人查詢雖然長，就算查數據庫也沒事啊，為啥es就報錯了？會不會？
Es有Bug！沒錯肯定是Es的鍋。
那為啥會這樣呢，我直接跟老大這樣解釋也好像不行啊，
還是要被開除的吧！於是我去看看看代碼，我在關鍵詞使用了通配符，我當時是為了匹配更多內容才這麼做的，類似數據庫的like，Es的通配符就是： * 帥丙 * 這樣在關鍵詞前後加“*”號去查詢。
後面我發現就是通配符的鍋，那柯南丙就說一下為啥會這樣的問題出現。
許多有RDBMS/SQL背景的開發者，在初次踏入ElasticSearch世界的時候，很容易就想到使用通配符(Wildcard Query)來實現模糊查詢（比如用戶輸入補全)，因為這是和SQL裡like操作最相似的查詢方式，用起來感覺非常舒適。
然而帥丙的故障就揭示了，濫用Wildcard query可能帶來災難性的後果。
我當時首先復現了問題
復現方法
- 創建一個只有一條文檔的索引
POST test_index/type1/?refresh=true
{
"foo": "bar"
}
2.使用wildcard query執行一個首尾帶有通配符*的長字符串查詢
POST /test_index/_search
{
"query": {
"wildcard": {
"foo": {
"value": "輕輕的我走了，正如我輕輕的來；我輕輕的招手，作別西天的雲彩。那河畔的金柳，是夕陽中的新娘；波光裡的豔影，在我的心頭盪漾。軟泥上的青荇，油油的在水底招搖；在康河的柔波里，我甘心做一條水草！那榆蔭下的一潭，不是清泉，是天上虹；揉碎在浮藻間，沉澱著彩虹似的夢。尋夢？撐一支長篙，向青草更青處漫溯；滿載一船星輝，在星輝斑斕裡放歌。但我不能放歌，悄悄是別離的笙簫；夏蟲也為我沉默，沉默是今晚的康橋！悄悄的我走了，正如我悄悄的來；我揮一揮衣袖，不帶走一片雲彩。"
}
}
}
}
- 查看結果
{
"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)，並且執行過程中，CPU有一個很高的尖峰。
線上的查詢比我這個範例要複雜得多，會同時查幾個字段，實際測試下來，一個查詢可能會執行十幾秒鐘。
再有比較多長字符串查詢的時候，集群可能就DOS了。
探查深層次根源
為什麼對只有一條數據的索引做這個查詢開銷這麼高？ 直覺上應該是瞬間返回結果才對!
回答這個問題前，可以再做個測試，如果繼續加大查詢字符串的長度，到了一定長度後，ES直接拋異常了，服務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這個包，異常原因的字面含義是說“自動機過於複雜而無法確定狀態： 由於狀態和轉換太多，確定一個自動機需要生成的狀態超過10000個上限"
柯南丙網上查找了大量資料後，終於搞清楚了問題的來龍去脈。
為了加速通配符和正則表達式的匹配速度，Lucene4.0開始會將輸入的字符串模式構建成一個DFA (Deterministic Finite Automaton)，帶有通配符的pattern構造出來的DFA可能會很複雜，開銷很大。
比如a*bc構造出來的DFA就像下面這個圖一樣:
Lucene構造DFA的實現
看了一下Lucene的裡相關的代碼，構建過程大致如下:
- org.apache.lucene.search.WildcardQuery裡的toAutomaton方法，遍歷輸入的通配符pattern，將每個字符變成一個自動機(automaton)，然後將每個字符的自動機鏈接起來生成一個新的自動機。
<code>public static Automaton toAutomaton(Term wildcardquery) {
List<automaton> automata = new ArrayList<>();
String wildcardText = wildcardquery.text();
for (int i = 0; i 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 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);
}/<automaton>/<code>- 此時生成的狀態機是不確定狀態機，也就是Non-deterministic Finite Automaton（NFA)。
- org.apache.lucene.util.automaton.Operations類裡的determinize方法則會將NFA轉換為DFA
<code>/**
\\* Determinizes the given automaton.
\\*/<code>
\\* 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
*/
代碼註釋裡說這個過程的時間複雜度最差情況下是狀態數量的指數級別！
為防止產生的狀態過多，消耗過多的內存和CPU，類裡面對最大狀態數量做了限制
<code> /**
* Default maximum number of states that {@link Operations#determinize} should create.
*/
public static final int DEFAULT_MAX_DETERMINIZED_STATES = 10000;/<code>
在有首尾通配符，並且字符串很長的情況下，這個determinize過程會產生大量的state，甚至會超過上限。
至於NFA和DFA的區別是什麼？ 如何相互轉換？
網上有很多數學層面的資料和論文，限於帥丙算法方面有限的知識，無精力去深入探究。
但是一個粗淺的理解是: NFA在輸入一個條件的情況下，可以從一個狀態轉移到多種狀態，而DFA只會有一個確定的狀態可以轉移，因此DFA在字符串匹配時速度更快。
DFA雖然搜索的時候快，但是構造方面的時間複雜度可能比較高，特別是帶有首部通配符+長字符串的時候。
回想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 ?."
結合對上面Wildcard query底層實現的探究，也就不難理解這句話的含義了！
小結： Wildcard query應杜絕使用通配符打頭，實在不得已要這麼做，就一定需要限制用戶輸入的字符串長度。
最好換一種實現方式，通過在index time做文章，選用合適的分詞器，比如nGram tokenizer預處理數據，然後使用更廉價的term query來實現同等的模糊搜索功能。
對於部分輸入即提示的應用場景，可以考慮優先使用completion suggester, phrase/term suggeter一類性能更好,模糊程度略差的方式查詢，待suggester沒有匹配結果的時候，再fall back到更模糊但性能較差的wildcard, regex, fuzzy一類的查詢。
補充： 有同學問regex, fuzzy query是否有同樣的問題，答案是有，原因在於他們底層和wildcard一樣，都是通過將pattern構造成DFA來加速字符串匹配速度的。
回憶：為啥之前掛了一次重啟恢復了，馬上又掛了？用戶搜了兩次。。。
解決方案
其實解決這種問題很簡單，既然知道關鍵詞長了會有問題，我就做限制嘛，大家可以去看看搜索引擎某度、某寶啥的，是不是都做了長度限制？
我複製了很長的一段漢字進去百度就是這個結果咯，某寶過長都返回默認頁面了。
image-20191204205715057
如果你的產品一定要給用戶一點東西，簡單，找出一些熱詞分析出來就好了，或者給點熱搜商品兜底。
我怎麼做的呢？判斷字符串長度大於50我就直接返回空數組了，這樣對用戶體驗好點，你返回個參數錯誤或者默認錯誤別人還以為你有Bug呢對吧。
總結
其實敖丙我啥事故等級都沒背哈哈，這個算是事故，但是敖丙我這麼可愛，領導也心疼我啊，肯定不會怪我的拉，主要是我設計都考慮了很多方案和場景了，沒想到有這個坑。（yy：敖丙你個渣男，又是標題黨，人家還以為你沒工作了要養你呢！）
大家也可以通過這次事故體會到，技術選型的時候，方案的重要性了吧，就算你考慮不全，但是不至於真正的問題來了手足無措啊，並不是所有的事故都可以像這次這樣重啟就搞定了，不要存有僥倖心理，心存敬畏。
絮叨
敖丙啊，又有牌面了，得到阿里消息中間件團隊小夥伴的認可，並且發現居然是我學姐-風雲（花名）！！！
她是個好學的小姐姐，大家多多像優秀的仔學習，學姐不是做技術的，但是都在不斷學習，說實話我的眼角又溼了。
閱讀更多 敖丙Kirk 的文章
