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

2018-09-06 17:58 更新

一、需求緣起

某并發(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樹
例如:上面的trie樹就能夠表示{and, as, at, cn, com}這樣5個(gè)標(biāo)題的集合。

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

龍哥:沒錯(cuò),每個(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)的。


以上內(nèi)容是否對您有幫助:
在線筆記
App下載
App下載

掃描二維碼

下載編程獅App

公眾號
微信公眾號

編程獅公眾號