如何快速實(shí)現(xiàn)高并發(fā)短文檢索

一、需求緣起

---

某并發(fā)量很大，數(shù)據(jù)量適中的業(yè)務(wù)線需要實(shí)現(xiàn)一個(gè)“標(biāo)題檢索”的功能：

（1）并發(fā)量較大，每秒20w次

（2）數(shù)據(jù)量適中，大概200w數(shù)據(jù)

（3）是否需要分詞：是

（4）數(shù)據(jù)是否實(shí)時(shí)更新：否

二、常見潛在解決方案及優(yōu)劣

---

（1）數(shù)據(jù)庫搜索法

具體方法：將標(biāo)題數(shù)據(jù)存放在數(shù)據(jù)庫中，使用like來檢索

優(yōu)點(diǎn)：方案簡單

缺點(diǎn)：不能實(shí)現(xiàn)分詞，并發(fā)量扛不住

（2）數(shù)據(jù)庫全文檢索法

具體方法：將標(biāo)題數(shù)據(jù)存放在數(shù)據(jù)庫中，建立全文索引來檢索

優(yōu)點(diǎn)：方案簡單

缺點(diǎn)：并發(fā)量扛不住

（3）使用開源方案將索引外置

具體方法：搭建lucene，solr，ES等開源外置索引方案

優(yōu)點(diǎn)：性能比上面兩種好

缺點(diǎn)：并發(fā)量可能有風(fēng)險(xiǎn)，系統(tǒng)比較重，為一個(gè)簡單的業(yè)務(wù)搭建一套這樣的系統(tǒng)成本較高

三、58龍哥的建議

---

問1：龍哥，58同城第一屆編程大賽的題目好像是“黃反詞過濾”，你是冠軍，當(dāng)時(shí)是用DAT來實(shí)現(xiàn)的么？

龍哥：是的

畫外音：什么是DAT？

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

問2：上面的業(yè)務(wù)場景可以使用DAT來實(shí)現(xiàn)么？

龍哥：DAT更新數(shù)據(jù)比較麻煩，不能增量

問3：那直接使用trie樹可以么？

龍哥：trie樹比較占內(nèi)存

畫外音：什么是trie樹？

普及：trie樹，又稱單詞查找樹，是一種樹形結(jié)構(gòu)，是一種哈希樹的變種。典型應(yīng)用是用于統(tǒng)計(jì)，保存大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)。它的優(yōu)點(diǎn)是：利用字符串的公共前綴來減少查詢時(shí)間，最大限度地減少無謂的字符串比較，查詢效率比哈希樹高。（來源：百度百科）

例如：上面的trie樹就能夠表示｛and, as, at, cn, com｝這樣5個(gè)標(biāo)題的集合。

問4：如果要支持分詞，多個(gè)分詞遍歷trie樹，還需要合并對吧？

龍哥：沒錯，每個(gè)分詞遍歷一次trie樹，可以得到doc_id的list，多個(gè)分詞得到的list合并，就是最終的結(jié)果。

問5：龍哥，還有什么更好，更輕量級的方案么？

龍哥：用trie樹，數(shù)據(jù)會膨脹文檔數(shù)*標(biāo)題長度這么多，標(biāo)題越長，文檔數(shù)越多，內(nèi)存占用越大。有個(gè)一個(gè)方案，內(nèi)存量很小，和標(biāo)題長度無關(guān)，非常帥氣。

問6：有相關(guān)文章么，推薦一篇？

龍哥：可能網(wǎng)上沒有，我簡單說一下吧，核心思想就是“內(nèi)存hash ＋ ID list”

索引初始化步驟為：對所有標(biāo)題進(jìn)行分詞，以詞的hash為key，doc_id的集合為value

查詢的步驟為：對查詢詞進(jìn)行分詞，對分詞進(jìn)行hash，直接查詢hash表格，獲取doc_id的list，然后多個(gè)詞進(jìn)行合并

=====例子=====

例如：

doc1 : 我愛北京
doc2 : 我愛到家

doc3 : 到家美好

先標(biāo)題進(jìn)行分詞：

doc1 : 我愛北京 -> 我，愛，北京
doc2 : 我愛到家 -> 我，愛，到家

doc3 : 到家美好 -> 到家，美好

對分詞進(jìn)行hash，建立hash + ID list：

hash(我) -> {doc1, doc2}
hash(愛) -> {doc1, doc2}
hash(北京) -> {doc1}
hash(到家) -> {doc2, doc3}

hash(美好) -> {doc3}

這樣，所有標(biāo)題的初始化就完畢了，你會發(fā)現(xiàn)，數(shù)據(jù)量和標(biāo)題的長度沒有關(guān)系。

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

hash(我)->{doc1, doc2}

hash(愛)->{doc1, doc2}

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

=====例子END=====

問7：這個(gè)方法有什么優(yōu)點(diǎn)呢？

龍哥：存內(nèi)存操作，能滿足很大的并發(fā)，時(shí)延也很低，占用內(nèi)存也不大，實(shí)現(xiàn)非常簡單快速

問8：有什么不足呢？和傳統(tǒng)搜索有什么區(qū)別咧？

龍哥：這是一個(gè)快速過度方案，因?yàn)?span style="color:#e33737;">索引本身沒有落地，還是需要在數(shù)據(jù)庫中存儲固化的標(biāo)題數(shù)據(jù)，如果不做高可用，數(shù)據(jù)恢復(fù)起來會比較慢。當(dāng)然做高可用也是很容易的，建立兩份一樣的hash索引即可。另外，沒有做水平切分，但數(shù)據(jù)量非常非常非常大時(shí)，還是要做水平切分改進(jìn)的。