IM開發乾貨分享:網易雲信IM客戶端的聊天訊息全文檢索技術實踐

語言: CN / TW / HK

1、引言

在IM客戶端的使用場景中,基於本地資料的全文檢索功能扮演著重要的角色,最常用的比如:查詢聊天記錄、聯絡人,就像下圖這樣。

▲ 微信的聊天記錄查詢功能

類似於IM中的聊天記錄查詢、聯絡人搜尋這類功能,有了全文檢索能力後,確實能大大提高內容查詢的效率,不然,讓使用者手動翻找,確實降低了使用者體驗。

本文將具體來聊聊網易雲信是如何實現IM客戶端全文檢索能力的,希望能帶給你啟發。

2、關於作者

李寧:網易雲信高階前端開發工程師,負責音視訊 IM SDK 的應用開發、元件化開發及解決方案開發,對 React、PaaS 元件化設計、多平臺的開發與編譯有豐富的實戰經驗。

3、相關文章

IM客戶端全文檢索相關文章:

  1. 微信手機端的本地資料全文檢索優化之路
  2. 微信團隊分享:微信移動端的全文檢索多音字問題解決方案

網易技術團隊分享的其它文章:

  1. 網易視訊雲技術分享:音訊處理與壓縮技術快速入門
  2. 網易雲信實時視訊直播在TCP資料傳輸層的一些優化思路
  3. 網易雲信技術分享:IM中的萬人群聊技術方案實踐總結
  4. Web端即時通訊實踐乾貨:如何讓你的WebSocket斷網重連更快速?
  5. 子彈簡訊光鮮的背後:網易雲信首席架構師分享億級IM平臺的技術實踐

4、什麼是全文檢索

所謂全文檢索,就是要在大量內容中找到包含某個單詞出現位置的技術。

在傳統的關係型資料庫中,只能通過 LIKE 條件查詢來實現,這樣有幾個弊端:

  • 1)無法使用資料庫索引,需要遍歷全表,效能較差;
  • 2)搜尋效果差,只能首尾位模糊匹配,無法實現複雜的搜尋需求;
  • 3)無法得到內容與搜尋條件的相關性。

我們在 IM 的 iOS、安卓以及桌面端中都實現了基於 SQLite 等庫的本地資料全文檢索功能,但是在 Web 端和 Electron 上缺少了這部分功能。

因為在 Web 端,由於瀏覽器環境限制,能使用的本地儲存資料庫只有 IndexDB,暫不在討論的範圍內。但在 Electron 上,雖然也是內建了 Chromium 的核心,但是因為可以使用 Node.js 的能力,於是乎選擇的範圍就多了一些。本文內容我們具體以基於Electron的IM客戶端為例,來討論全文檢索技術實現(技術思路是相通的,並不侷限於具體什麼端)。

PS:如果你不瞭解什麼是Electron技術,讀一下這篇《快速瞭解Electron:新一代基於Web的跨平臺桌面技術》。

我們先來具體看下該如何實現全文檢索。

要實現全文檢索,離不開以下兩個知識點:

  • 1)倒排索引;
  • 2)分詞。

這兩個技術是實現全文檢索的技術以及難點,其實現的過程相對比較複雜,在聊全文索引的實現前,我們具體學習一下這兩個技術的原理。

5、全文檢索知識點1:倒排索引

先簡單介紹下倒排索引,倒排索引的概念區別於正排索引:

  • 1)正排索引:是以文件物件的唯一 ID 作為索引,以文件內容作為記錄的結構;
  • 2)倒排索引:是以文件內容中的單詞作為索引,將包含該詞的文件 ID 作為記錄的結構。

以倒排索引庫 search-index 舉個實際的例子:

在我們的 IM 中,每條訊息物件都有 idClient 作為唯一 ID,接下來我們輸入「今天天氣真好」,將其每個中文單獨分詞(分詞的概念我們在下文會詳細分享),於是輸入變成了「今」、「天」、「天」、「氣」、「真」、「好」。再通過 search-index 的 PUT 方法將其寫入庫中。

最後看下上述例子儲存內容的結構:

如是圖所示:可以看到倒排索引的結構,key 是分詞後的單箇中文、value 是包含該中文訊息物件的 idClient 組成的陣列。

當然:search-index 除了以上這些內容,還有一些其他內容,例如 Weight、Count 以及正排的資料等,這些是為了排序、分頁、按欄位搜尋等功能而存在的,本文就不再細細展開了。

6、全文檢索知識點2:分詞

6.1 基本概念

分詞就是將原先一條訊息的內容,根據語義切分成多個單字或詞句,考慮到中文分詞的效果以及需要在 Node 上執行,我們選擇了 Nodejieba 作為基礎分詞庫。

以下是 jieba 分詞的流程圖:

以“去北京大學玩”為例,我們選擇其中最為重要的幾個模組分析一下。

6.2 載入詞典

jieba 分詞會在初始化時先載入詞典,大致內容如下:

6.3 構建字首詞典

接下來會根據該詞典構建字首詞典,結構如下:

其中:“北京大”作為“北京大學”的字首,它的詞頻是0,這是為了便於後續構建 DAG 圖。

6.4 構建 DAG 圖

DAG 圖是 Directed Acyclic Graph 的縮寫,即有向無環圖。

基於字首詞典,對輸入的內容進行切分。

其中:

  • 1)“去”沒有字首,因此只有一種切分方式;
  • 2)對於“北”,則有“北”、“北京”、“北京大學”三種切分方式;
  • 3)對於“京”,也只有一種切分方式;
  • 4)對於“大”,有“大”、“大學”兩種切分方式;
  • 5)對於“學”和“玩”,依然只有一種切分方式。

如此,可以得到每個字作為字首詞的切分方式。

其 DAG 圖如下圖所示:

6.5 最大概率路徑計算

以上 DAG 圖的所有路徑如下:

去/北/京/大/學/玩

去/北京/大/學/玩

去/北京/大學/玩

去/北京大學/玩

因為每個節點都是有權重(Weight)的,對於在字首詞典裡的詞語,它的權重就是它的詞頻。因此我們的問題就是想要求得一條最大路徑,使得整個句子的權重最高。

這是一個典型的動態規劃問題,首先我們確認下動態規劃的兩個條件。

1)重複子問題:

對於節點 i 和其可能存在的多個後繼節點 j 和 k:

  • 1)任意通過i到達j的路徑的權重 = 該路徑通過i的路徑權重 + j的權重,即 R(i -> j) = R(i) + W(j);
  • 2)任意通過i到達k的路徑的權重 = 該路徑通過i的路徑權重 + k的權重,即 R(i -> k) = R(i) + W(k)。

即對於擁有公共前驅節點 i 的 j 和 k,需要重複計算到達 i 路徑的權重。

2)最優子結構:

設整個句子的最優路徑為 Rmax,末端節點為 x,多個可能存在的前驅節點為 i、j、k。

得到公式如下:

Rmax = max(Rmaxi, Rmaxj, Rmaxk) + W(x)

於是問題變成了求解 Rmaxi、Rmaxj 以及 Rmaxk,子結構裡的最優解即是全域性最優解的一部分。

如上,最後計算得出最優路徑為“去/北京大學/玩”。

6.6 HMM 隱式馬爾科夫模型

對於未登陸詞,jieba 分詞采用 HMM(Hidden Markov Model 的縮寫)模型進行分詞。

它將分詞問題視為一個序列標註問題,句子為觀測序列,分詞結果為狀態序列。

jieba 分詞作者在 issue 中提到,HMM 模型的引數基於網上能下載到的 1998 人民日報的切分語料,一個 MSR 語料以及自己收集的 TXT 小說、用 ICTCLAS 切分,最後用 Python 指令碼統計詞頻而成。

該模型由一個五元組組成,並有兩個基本假設。

五元組:

  • 1)狀態值集合;
  • 2)觀察值集合;
  • 3)狀態初始概率;
  • 4)狀態轉移概率;
  • 5)狀態發射概率。

基本假設:

  • 1)齊次性假設:即假設隱藏的馬爾科夫鏈在任意時刻 t 的狀態只依賴於其前一時刻 t-1 的狀態,與其它時刻的狀態及觀測無關,也與時刻 t 無關;
  • 2)觀察值獨立性假設:即假設任意時刻的觀察值只與該時刻的馬爾科夫鏈的狀態有關,與其它觀測和狀態無關。

狀態值集合即{ B: begin, E: end, M: middle, S: single },表示每個字所處在句子中的位置,B 為開始位置,E 為結束位置,M 為中間位置,S 是單字成詞。

觀察值集合就是我們輸入句子中每個字組成的集合。

狀態初始概率表明句子中的第一個字屬於 B、M、E、S 四種狀態的概率,其中 E 和 M 的概率都是0,因為第一個字只可能 B 或者 S,這與實際相符。

狀態轉移概率表明從狀態 1 轉移到狀態 2 的概率,滿足齊次性假設,結構可以用一個巢狀的物件表示:

P = {

    B: {E: -0.510825623765990, M: -0.916290731874155},

    E: {B: -0.5897149736854513, S: -0.8085250474669937},

    M: {E: -0.33344856811948514, M: -1.2603623820268226},

    S: {B: -0.7211965654669841, S: -0.6658631448798212},

}

P['B']['E'] 表示從狀態 B 轉移到狀態 E 的概率(結構中為概率的對數,方便計算)為 0.6,同理,P['B']['M'] 表示下一個狀態是 M 的概率為 0.4,說明當一個字處於開頭時,下一個字處於結尾的概率高於下一個字處於中間的概率,符合直覺,因為二個字的詞比多個字的詞要更常見。

狀態發射概率表明當前狀態,滿足觀察值獨立性假設,結構同上,也可以用一個巢狀的物件表示:

P = {

    B: {'突': -2.70366861046, '肅': -10.2782270947, '適': -5.57547658034},

    M: {'要': -4.26625051239, '合': -2.1517176509, '成': -5.11354837278},

    S: {……},

    E: {……},

}

P['B']['突'] 的含義就是狀態處於 B,觀測的字是“突”的概率的對數值等於 -2.70366861046。

最後,通過 Viterbi 演算法,輸入觀察值集合,將狀態初始概率、狀態轉移概率、狀態發射概率作為引數,輸出狀態值集合(即最大概率的分詞結果)。關於 Viterbi 演算法,本文不再詳細展開,有興趣的讀者可以自行查閱。

7、技術實現

上節中介紹的全文檢索這兩塊技術,是我們架構的技術核心。基於此,我們對IM 的 Electron 端技術架構做了改進。以下將詳細介紹之。

7.1 架構圖詳解

考慮到全文檢索只是 IM 中的一個功能,為了不影響其他 IM 的功能,並且能更快的迭代需求,所以採用瞭如下的架構方案。

架構圖如下:

如上圖所示,右邊是之前的技術架構,底層儲存庫使用了 indexDB,上層有讀寫兩個模組。

讀寫模組的具體作用是:

  • 1)當用戶主動傳送訊息、主動同步訊息、主動刪除訊息以及收到訊息的時候,會將訊息物件同步到 indexDB;
  • 2)當用戶需要查詢關鍵字的時候,會去 indexDB 中遍歷所有的訊息物件,再使用 indexOf 判斷每一條訊息物件是否包含所查詢的關鍵字(類似 LIKE)。

那麼,當資料量大的時候,查詢的速度是非常緩慢的。

左邊是加入了分詞以及倒排索引資料庫的新的架構方案,這個方案不會對之前的方案有任何影響,只是在之前的方案之前加了一層。

現在,讀寫模組的工作邏輯:

  • 1)當用戶主動傳送訊息、主動同步訊息、主動刪除訊息以及收到訊息的時候,會將每一條訊息物件中的訊息經過分詞後同步到倒排索引資料庫;
  • 2)當用戶需要查詢關鍵字的時候,會先去倒排索引資料庫中找出對應訊息的 idClient,再根據 idClient 去 indexDB 中找出對應的訊息物件返回給使用者。

7.2 架構優點

該方案有以下4個優點:

  • 1)速度快:通過 search-index 實現倒排索引,從而提升了搜尋速度。
  • 2)跨平臺:因為 search-index 與 indexDB 都是基於 levelDB,因此 search-index 也支援瀏覽器環境,這樣就為 Web 端實現全文檢索提供了可能性;
  • 3)獨立性:倒排索引庫與 IM 主業務庫 indexDB 分離;
  • 4)靈活性:全文檢索以外掛的形式接入。

針對上述第“3)”點:當 indexDB 寫入資料時,會自動通知到倒排索引庫的寫模組,將訊息內容分詞後,插入到儲存隊列當中,最後依次插入到倒排索引資料庫中。當需要全文檢索時,通過倒排索引庫的讀模組,能快速找到對應關鍵字的訊息物件的 idClient,根據 idClient 再去 indexDB 中找到訊息物件並返回。

針對上述第“4)”點:它暴露出一個高階函式,包裹 IM 並返回新的經過繼承擴充套件的 IM,因為 JS 面向原型的機制,在新的 IM 中不存在的方法,會自動去原型鏈(即老的 IM)當中查詢,因此,使得外掛可以聚焦於自身方法的實現上,並且不需要關心 IM 的具體版本,並且外掛支援自定義分詞函式,滿足不同使用者不同分詞需求的場景

7.3 使用效果

使用瞭如上架構後,經過我們的測試,在資料量 20W 的級別上,搜尋時間從最開始的十幾秒降到一秒內,搜尋速度快了 20 倍左右。

8、本文小結

本文中,我們便基於 Nodejieba 和 search-index 在 Electron 上實現了IM聊天訊息的全文檢索,加快了聊天記錄的搜尋速度。

當然,後續我們還會針對以下方面做更多的優化,比如以下兩點:

1)寫入效能 :在實際的使用中,發現當資料量大了以後,search-index 依賴的底層資料庫 levelDB 會存在寫入效能瓶頸,並且 CPU 和記憶體的消耗較大。經過調研,SQLite 的寫入效能相對要好很多,從觀測來看,寫入速度只與資料量成正比,CPU 和記憶體也相對穩定,因此,後續可能會考慮用將 SQLite 編譯成 Node 原生模組來替換 search-index。

2)可擴充套件性 :目前對於業務邏輯的解耦還不夠徹底。倒排索引庫當中儲存了某些業務欄位。後續可以考慮倒排索引庫只根據關鍵字查詢訊息物件的 idClient,將帶業務屬性的搜尋放到 indexDB 中,將倒排索引庫與主業務庫徹底解耦。

以上,就是本文的全部分享,希望我的分享能對大家有所幫助。

附錄:更多IM乾貨技術文章

新手入門一篇就夠:從零開發移動端IM

從客戶端的角度來談談移動端IM的訊息可靠性和送達機制

移動端IM中大規模群訊息的推送如何保證效率、實時性?

移動端IM開發需要面對的技術問題

IM訊息送達保證機制實現(一):保證線上實時訊息的可靠投遞

IM訊息送達保證機制實現(二):保證離線訊息的可靠投遞

如何保證IM實時訊息的“時序性”與“一致性”?

一個低成本確保IM訊息時序的方法探討

IM單聊和群聊中的線上狀態同步應該用“推”還是“拉”?

IM群聊訊息如此複雜,如何保證不丟不重?

談談移動端 IM 開發中登入請求的優化

移動端IM登入時拉取資料如何作到省流量?

淺談移動端IM的多點登入和訊息漫遊原理

完全自已開發的IM該如何設計“失敗重試”機制?

通俗易懂:基於叢集的移動端IM接入層負載均衡方案分享

微信對網路影響的技術試驗及分析(論文全文)

微信技術分享:微信的海量IM聊天訊息序列號生成實踐(演算法原理篇)

自已開發IM有那麼難嗎?手把手教你自擼一個Andriod版簡易IM (有原始碼)

融雲技術分享:解密融雲IM產品的聊天訊息ID生成策略

適合新手:從零開發一個IM服務端(基於Netty,有完整原始碼)

拿起鍵盤就是幹:跟我一起徒手開發一套分散式IM系統

適合新手:手把手教你用Go快速搭建高效能、可擴充套件的IM系統(有原始碼)

IM裡“附近的人”功能實現原理是什麼?如何高效率地實現它?

IM訊息ID技術專題(一):微信的海量IM聊天訊息序列號生成實踐(演算法原理篇)

IM開發寶典:史上最全,微信各種功能引數和邏輯規則資料彙總

IM開發乾貨分享:我是如何解決大量離線訊息導致客戶端卡頓的

零基礎IM開發入門(一):什麼是IM系統?

零基礎IM開發入門(二):什麼是IM系統的實時性?

零基礎IM開發入門(三):什麼是IM系統的可靠性?

零基礎IM開發入門(四):什麼是IM系統的訊息時序一致性?

一套億級使用者的IM架構技術乾貨(下篇):可靠性、有序性、弱網優化等

IM掃碼登入技術專題(三):通俗易懂,IM掃碼登入功能詳細原理一篇就夠

理解IM訊息“可靠性”和“一致性”問題,以及解決方案探討

阿里技術分享:閒魚IM基於Flutter的移動端跨端改造實踐

融雲技術分享:全面揭祕億級IM訊息的可靠投遞機制

IM開發乾貨分享:如何優雅的實現大量離線訊息的可靠投遞

IM開發乾貨分享:有贊移動端IM的元件化SDK架構設計實踐

IM開發乾貨分享:網易雲信IM客戶端的聊天訊息全文檢索技術實踐

>> 更多同類文章 ……

本文已同步釋出於“即時通訊技術圈”公眾號。

▲ 本文在公眾號上的連結是:點此進入。同步釋出連結是:http://www.52im.net/thread-3651-1-1.html

「其他文章」