作者 | KG沈劍

?有水友提問(wèn)：

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

這是一個(gè)典型的，短文本分詞搜索的問(wèn)題，簡(jiǎn)單聊聊自己的經(jīng)驗(yàn)。

常見(jiàn)的文本檢索方案有哪些？

(1) 數(shù)據(jù)庫(kù)LIKE法?

將標(biāo)題數(shù)據(jù)存放在數(shù)據(jù)庫(kù)中，使用like來(lái)查詢，方案非常簡(jiǎn)單，能支持簡(jiǎn)單的模糊搜索，但不支持分詞。

畫外音：顯然不適用于本例。

(2) 數(shù)據(jù)庫(kù)全文檢索法?

將標(biāo)題數(shù)據(jù)存放在數(shù)據(jù)庫(kù)中，建立全文索引來(lái)檢索，方案依然簡(jiǎn)單，利用了數(shù)據(jù)庫(kù)的能力，不用額外開(kāi)發(fā)，但性能較低。

畫外音：本例的并發(fā)肯定扛不住。?

(3) 開(kāi)源方案索引外置法

搭建lucene，solr，ES等開(kāi)源搜索工具，建立索引，支持分詞，支持?jǐn)?shù)據(jù)量和吞吐量的水平擴(kuò)展。

該方案能夠很好的滿足本例的需求。但是，殺雞焉用牛刀，本例有一些業(yè)務(wù)特性：文本短，更新不頻繁，如果利用好這兩個(gè)特點(diǎn)，能有更巧妙的方案。

畫外音：任何脫離業(yè)務(wù)的架構(gòu)設(shè)計(jì)，都是耍流氓。?

針對(duì)“更新不頻繁”的特性，可以使用“分詞+DAT”方案。

畫外音：分詞就不多說(shuō)了。

什么是DAT？?

DAT是double array trie的縮寫，是trie樹(shù)的一個(gè)變體優(yōu)化數(shù)據(jù)結(jié)構(gòu)，它在保證trie樹(shù)檢索效率的前提下，能大大減少內(nèi)存的使用，經(jīng)常用來(lái)解決檢索，信息過(guò)濾等問(wèn)題。

畫外音：更具體的，可以Google一下“DAT”，DAT的缺點(diǎn)是，需要提前建立索引，索引不能實(shí)時(shí)更新。

為什么用trie樹(shù)的變種DAT，是否可以直接使用trie樹(shù)呢？?

trie樹(shù)的優(yōu)點(diǎn)是，索引可以實(shí)時(shí)更新；不足是，占用內(nèi)存非常大。

本例索引無(wú)需實(shí)時(shí)更新，無(wú)法利用trie樹(shù)的優(yōu)點(diǎn)。但是，如果300W短文本建立好trie樹(shù)內(nèi)存能裝下，則可以使用trie樹(shù)，否則只能使用DAT。

普及，什么是trie樹(shù)？?

trie樹(shù)，又稱單詞查找樹(shù)，經(jīng)常用于搜索引擎詞頻統(tǒng)計(jì)，短文本檢索，輸入法輸入提示等。

畫外音：什么數(shù)據(jù)結(jié)構(gòu)適合什么業(yè)務(wù)場(chǎng)景，一定要爛熟于胸。

它的特點(diǎn)是，能利用字符串的公共前綴來(lái)減少查詢時(shí)間，最大限度地減少無(wú)謂的字符串比較，其查詢時(shí)間復(fù)雜度只與樹(shù)的高度有關(guān)，與查詢數(shù)據(jù)量級(jí)無(wú)關(guān)，因此查詢效率非常高。

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

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

畫外音：檢索時(shí)，節(jié)點(diǎn)存儲(chǔ)命中該item的doc_list<doc_id>。

分詞之后，是不是需要多次掃描trie樹(shù)？ 

是的。

分詞之后，每個(gè)item都要掃描一次trie樹(shù)，得到的doc_list<doc_id>的交集，就是最終命中每個(gè)item的檢索結(jié)果。

針對(duì)“短文本”“500W數(shù)據(jù)”“不頻繁更新”這些特性，還能使用“分詞+內(nèi)存hash”方案。

這個(gè)方案需要先對(duì)索引進(jìn)行初始化：對(duì)所有短文本進(jìn)行分詞，以詞的hash為key，doc_id的集合為value。

查詢的過(guò)程也很簡(jiǎn)單：?對(duì)查詢字符串進(jìn)行分詞，對(duì)每個(gè)分詞進(jìn)行hash，直接查詢hash表格得到doc_list<doc_id>，再對(duì)每個(gè)分詞的檢索結(jié)果進(jìn)行交集。

舉個(gè)栗子進(jìn)行說(shuō)明。

例如：

• doc1 : 我愛(ài)北京
• doc2 : 我愛(ài)到家
• doc3 : 到家美好

先對(duì)短文本進(jìn)行分詞：

• doc1 : 我愛(ài)北京 -> 我，愛(ài)，北京
• doc2 : 我愛(ài)到家 -> 我，愛(ài)，到家
• doc3 : 到家美好 -> 到家，美好

對(duì)分詞進(jìn)行hash，建立hash表：

• hash(我) -> {doc1, doc2}
• hash(愛(ài)) -> {doc1, doc2}
• hash(北京) -> {doc1}
• hash(到家) -> {doc2, doc3}
• hash(美好) -> {doc3}

這樣，所有短文本初始化完畢，與trie樹(shù)類似，查詢時(shí)間復(fù)雜度與文本數(shù)據(jù)量也沒(méi)有關(guān)系。

畫外音：只與被分詞后有多少數(shù)據(jù)量，即hash桶個(gè)數(shù)有關(guān)。

查詢的過(guò)程是這樣的：

假如用戶輸入“我愛(ài)”，分詞后變?yōu)閧我，愛(ài)}，對(duì)各個(gè)分詞的hash進(jìn)行內(nèi)存檢索：

• hash(我)->{doc1, doc2}
• hash(愛(ài))->{doc1, doc2}

然后進(jìn)行合并，得到最后的查找結(jié)果是{doc1, doc2}。

這個(gè)方法的優(yōu)點(diǎn)是，純內(nèi)存操作，能滿足很大的并發(fā)，時(shí)延也很低，占用內(nèi)存也不大，實(shí)現(xiàn)非常簡(jiǎn)單快速，而且冗余索引很容易水平擴(kuò)展。

畫外音：做索引高可用也不難，建立兩份一樣的hash索引即可。

它的缺點(diǎn)也很明顯，索引全內(nèi)存，沒(méi)有落地，還是需要在數(shù)據(jù)庫(kù)中存儲(chǔ)固化的短文本數(shù)據(jù)，如果內(nèi)存數(shù)據(jù)全丟失，數(shù)據(jù)恢復(fù)起來(lái)會(huì)比較慢。

總結(jié)?

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

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

等幾種方式解決。

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