作者 | KG沈劍

?有水友提問：

沈哥，我們有個(gè)業(yè)務(wù)，類似于“標(biāo)題分詞檢索”，并發(fā)量非常大，大概20W次每秒，數(shù)據(jù)量不是很大，大概500W級(jí)別，而且數(shù)據(jù)不會(huì)頻繁更新，平均每天更新一次，請問有什么好的方案么？

這是一個(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ù)量級(jí)無關(guān)，因此查詢效率非常高。

畫外音：“時(shí)間復(fù)雜度與查詢數(shù)量級(jí)無關(guān)”這個(gè)太屌了。

例如：上面的trie樹就能夠表示｛and, as, at, cn, com｝這樣5個(gè)標(biāo)題的集合，可以用來做這5個(gè)字符串的詞頻統(tǒng)計(jì)，或者檢索。

畫外音：檢索時(shí)，節(jié)點(diǎn)存儲(chǔ)命中該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ù)庫中存儲(chǔ)固化的短文本數(shù)據(jù)，如果內(nèi)存數(shù)據(jù)全丟失，數(shù)據(jù)恢復(fù)起來會(huì)比較慢。

總結(jié)?

短文本，高并發(fā)，支持分詞，不用實(shí)時(shí)更新的檢索場景，可以使用：

• ES，殺雞用牛刀；
• 分詞+DAT(trie)；
• 分詞+內(nèi)存hash；

等幾種方式解決。

思路比結(jié)論重要，希望大家有收獲。?