500W數(shù)據(jù)，20Wqps分詞檢索，架構(gòu)如何設(shè)計(jì)？
有水友提問：
==
沈哥，我們有個(gè)業(yè)務(wù)，類似于“標(biāo)題分詞檢索”，并發(fā)量非常大，大概20W次每秒，數(shù)據(jù)量不是很大，大概500W級別，而且數(shù)據(jù)不會頻繁更新，平均每天更新一次，請問有什么好的方案么？
==
這是一個(gè)典型的，短文本分詞搜索的問題，簡單聊聊自己的經(jīng)驗(yàn)。
常見的文本檢索方案有哪些？
（1）數(shù)據(jù)庫LIKE法
將標(biāo)題數(shù)據(jù)存放在數(shù)據(jù)庫中，使用like來查詢，方案非常簡單，能支持簡單的模糊搜索，但不支持分詞。
畫外音：顯然不適用于本例。
（2）數(shù)據(jù)庫全文檢索法
將標(biāo)題數(shù)據(jù)存放在數(shù)據(jù)庫中，建立全文索引來檢索，方案依然簡單，利用了數(shù)據(jù)庫的能力，不用額外開發(fā)，但性能較低。
畫外音：本例的并發(fā)肯定扛不住。
（3）開源方案索引外置法
搭建lucene，solr，ES等開源搜索工具，建立索引，支持分詞，支持?jǐn)?shù)據(jù)量和吞吐量的水平擴(kuò)展。
該方案能夠很好的滿足本例的需求。但是，殺雞焉用牛刀，本例有一些業(yè)務(wù)特性：文本短，更新不頻繁，如果利用好這兩個(gè)特點(diǎn)，能有更巧妙的方案。
畫外音：任何脫離業(yè)務(wù)的架構(gòu)設(shè)計(jì)，都是耍流氓。
針對“更新不頻繁”的特性，可以使用“分詞+DAT”方案。
畫外音：分詞就不多說了。
什么是DAT？
DAT是double array trie的縮寫，是trie樹的一個(gè)變體優(yōu)化數(shù)據(jù)結(jié)構(gòu)，它在保證trie樹檢索效率的前提下，能大大減少內(nèi)存的使用，經(jīng)常用來解決檢索，信息過濾等問題。
畫外音：更具體的，可以Google一下“DAT”，DAT的缺點(diǎn)是，需要提前建立索引，索引不能實(shí)時(shí)更新。
為什么用trie樹的變種DAT，是否可以直接使用trie樹呢？
trie樹的優(yōu)點(diǎn)是，索引可以實(shí)時(shí)更新；不足是，占用內(nèi)存非常大。
本例索引無需實(shí)時(shí)更新，無法利用trie樹的優(yōu)點(diǎn)。但是，如果300W短文本建立好trie樹內(nèi)存能裝下，則可以使用trie樹，否則只能使用DAT。
普及，什么是trie樹？
trie樹，又稱單詞查找樹，經(jīng)常用于搜索引擎詞頻統(tǒng)計(jì)，短文本檢索，輸入法輸入提示等。
畫外音：什么數(shù)據(jù)結(jié)構(gòu)適合什么業(yè)務(wù)場景，一定要爛熟于胸。
它的特點(diǎn)是，能利用字符串的公共前綴來減少查詢時(shí)間，最大限度地減少無謂的字符串比較，其查詢時(shí)間復(fù)雜度只與樹的高度有關(guān)，與查詢數(shù)據(jù)量級無關(guān)，因此查詢效率非常高。
畫外音：“時(shí)間復(fù)雜度與查詢數(shù)量級無關(guān)”這個(gè)太屌了。
例如：上面的trie樹就能夠表示｛and, as, at, cn, com｝這樣5個(gè)標(biāo)題的集合，可以用來做這5個(gè)字符串的詞頻統(tǒng)計(jì)，或者檢索。
畫外音：檢索時(shí)，節(jié)點(diǎn)存儲命中該item的doc_list<doc_id>。
分詞之后，是不是需要多次掃描trie樹？
是的。
分詞之后，每個(gè)item都要掃描一次trie樹，得到的doc_list<doc_id>的交集，就是最終命中每個(gè)item的檢索結(jié)果。
針對“短文本”“500W數(shù)據(jù)”“不頻繁更新”這些特性，還能使用“分詞+內(nèi)存hash”方案。
這個(gè)方案需要先對索引進(jìn)行初始化：
對所有短文本進(jìn)行分詞，以詞的hash為key，doc_id的集合為value。
查詢的過程也很簡單：
對查詢字符串進(jìn)行分詞，對每個(gè)分詞進(jìn)行hash，直接查詢hash表格得到doc_list<doc_id>，再對每個(gè)分詞的檢索結(jié)果進(jìn)行交集。
舉個(gè)栗子進(jìn)行說明。
例如：
doc1 : 我愛北京
doc2 : 我愛到家
doc3 : 到家美好
先對短文本進(jìn)行分詞：
doc1 : 我愛北京 -> 我，愛，北京
doc2 : 我愛到家 -> 我，愛，到家
doc3 : 到家美好 -> 到家，美好
對分詞進(jìn)行hash，建立hash表：
hash(我) -> {doc1, doc2}
hash(愛) -> {doc1, doc2}
hash(北京) -> {doc1}
hash(到家) -> {doc2, doc3}
hash(美好) -> {doc3}
這樣，所有短文本初始化完畢，與trie樹類似，查詢時(shí)間復(fù)雜度與文本數(shù)據(jù)量也沒有關(guān)系。
畫外音：只與被分詞后有多少數(shù)據(jù)量，即hash桶個(gè)數(shù)有關(guān)。
查詢的過程是這樣的：
假如用戶輸入“我愛”，分詞后變?yōu)閧我，愛}，對各個(gè)分詞的hash進(jìn)行內(nèi)存檢索
hash(我)->{doc1, doc2}
hash(愛)->{doc1, doc2}
然后進(jìn)行合并，得到最后的查找結(jié)果是{doc1, doc2}。
這個(gè)方法的優(yōu)點(diǎn)是，純內(nèi)存操作，能滿足很大的并發(fā)，時(shí)延也很低，占用內(nèi)存也不大，實(shí)現(xiàn)非常簡單快速，而且冗余索引很容易水平擴(kuò)展。
畫外音：做索引高可用也不難，建立兩份一樣的hash索引即可。
它的缺點(diǎn)也很明顯，索引全內(nèi)存，沒有落地，還是需要在數(shù)據(jù)庫中存儲固化的短文本數(shù)據(jù)，如果內(nèi)存數(shù)據(jù)全丟失，數(shù)據(jù)恢復(fù)起來會比較慢。
總結(jié)
短文本，高并發(fā)，支持分詞，不用實(shí)時(shí)更新的檢索場景，可以使用：
（1）ES，殺雞用牛刀；
（2）分詞+DAT(trie)；
（3）分詞+內(nèi)存hash；
等幾種方式解決。
思路比結(jié)論重要，希望大家有收獲。
架構(gòu)師之路-分享技術(shù)思路