作者 | qiuwenchen

一、iOS 微信全文搜索技術(shù)的現(xiàn)狀

全文搜索是使用倒排索引進(jìn)行搜索的一種搜索方式。倒排索引也稱(chēng)為反向索引，是指對(duì)輸入的內(nèi)容中的每個(gè)Token建立一個(gè)索引，索引中保存了這個(gè)Token在內(nèi)容中的具體位置。全文搜索技術(shù)主要應(yīng)用在對(duì)大量文本內(nèi)容進(jìn)行搜索的場(chǎng)景。

微信終端涉及到大量文本搜索的業(yè)務(wù)場(chǎng)景主要包括聯(lián)系人、聊天記錄、收藏的搜索。這些搜索功能從 2014 年上線至今，已經(jīng)多年沒(méi)有更新底層搜索技術(shù)，聊天記錄使用的全文搜索引擎還是 SQLite FTS3，而現(xiàn)在已經(jīng)有 SQLite FTS5，收藏首頁(yè)的搜索還是使用簡(jiǎn)單的Like語(yǔ)句去匹配文本，聯(lián)系人搜索甚至用的是內(nèi)存搜索(在內(nèi)存中遍歷所有聯(lián)系人的所有屬性進(jìn)行匹配)。隨著用戶在微信上積累的數(shù)據(jù)越來(lái)越多，提升微信底層搜索技術(shù)的需求也越來(lái)越迫切。在 2021 年，我們對(duì) iOS 微信的全文搜索技術(shù)進(jìn)行了一次全面升級(jí)，本文主要介紹本次技術(shù)升級(jí)的工作經(jīng)驗(yàn)。

二、全文搜索引擎的選型與優(yōu)化

1. 搜索引擎選型

iOS 客戶端可以使用的全文搜索引擎并不多，主要有 SQLite 三個(gè)版本的 FTS 組件、Lucene 的 C++實(shí)現(xiàn)版本 CLucene 和 C 語(yǔ)言橋接版本 Lucy。這里給出了這些引擎在事務(wù)能力、技術(shù)風(fēng)險(xiǎn)、搜索能力、讀寫(xiě)性能等方面的比較。

在事務(wù)能力方面，Lucene 沒(méi)有提供完整的事務(wù)能力，因?yàn)?Lucene 使用了多文件的存儲(chǔ)結(jié)構(gòu)，它沒(méi)有保證事務(wù)的原子性。SQLite 的 FTS 組件因?yàn)榈讓舆€是使用普通的表來(lái)實(shí)現(xiàn)的，可以完美繼承 SQLite 的事務(wù)能力。

在技術(shù)風(fēng)險(xiǎn)方面，Lucene 主要應(yīng)用于服務(wù)端，在客戶端沒(méi)有大規(guī)模應(yīng)用的案例，而且 CLucene 和 Lucy 自 2013 年后官方都停止維護(hù)了，技術(shù)風(fēng)險(xiǎn)較高。SQLite 的 FTS3 和 FTS4 組件則是屬于 SQLite 的舊版本引擎，官方維護(hù)不多了，而且這兩個(gè)版本都是將一個(gè)詞的索引存到一條記錄中，極端情況下有超出 SQLite 單條記錄最大長(zhǎng)度限制的風(fēng)險(xiǎn)。SQLite 的 FTS5 組件作為最新版本引擎也已經(jīng)推出超過(guò)六年了，在安卓微信上也已經(jīng)全量應(yīng)用，所以技術(shù)風(fēng)險(xiǎn)是最低的。

在搜索能力方面，Lucene 的發(fā)展歷史比 SQLite 的 FTS 組件長(zhǎng)很多，搜索能力相比也是最豐富的。特別是 Lucene 有豐富的搜索結(jié)果評(píng)分排序機(jī)制，但這個(gè)在微信客戶端沒(méi)有應(yīng)用場(chǎng)景。因?yàn)槲覀兊乃阉鹘Y(jié)果要么是按照時(shí)間排序，要么是按照一些簡(jiǎn)單的自定義規(guī)則排序。在 SQLite 幾個(gè)版本的引擎中，F(xiàn)TS5 的搜索語(yǔ)法更加完備嚴(yán)謹(jǐn)，提供了很多接口給用戶自定義搜索函數(shù)，所以搜索能力也相對(duì)強(qiáng)一點(diǎn)。

在讀寫(xiě)性能方面，下面是用不同引擎對(duì) 100 萬(wàn)條長(zhǎng)度為 10 的隨機(jī)生成中文語(yǔ)句生成 Optimize 狀態(tài)的索引的性能數(shù)據(jù)，其中每個(gè)語(yǔ)句的漢字出現(xiàn)頻率按照實(shí)際的漢字使用頻率：

可以看到，Lucene 讀取命中數(shù)量的性能比 SQLite 好很多，說(shuō)明 Lucene 索引的文件格式很有優(yōu)勢(shì)，但是微信沒(méi)有只讀取命中數(shù)量的應(yīng)用場(chǎng)景，Lucene 的其他性能數(shù)據(jù)跟 SQLite 的差距不明顯。SQLite FTS3 和 FTS5 的大部分性能很接近，F(xiàn)TS5 索引的生成耗時(shí)比 FTS3 高一截，這個(gè)有優(yōu)化方法。

綜合考慮這些因素，我們選擇 SQLite FTS5 作為 iOS 微信全文搜索的搜索引擎。

2. 實(shí)現(xiàn) FTS5 的 Segment 自動(dòng) Merge 機(jī)制

SQLite FTS5 會(huì)把每個(gè)事務(wù)寫(xiě)入的內(nèi)容保存成一個(gè)獨(dú)立的 b 樹(shù)，稱(chēng)為一個(gè)segment，segment中保存了本次寫(xiě)入內(nèi)容中的每個(gè)詞在本次內(nèi)容中行號(hào)(rowid)、列號(hào)和字段中的每次出現(xiàn)的位置偏移，所以這個(gè)segment就是該內(nèi)容的倒排索引。多次寫(xiě)入就會(huì)形成多個(gè)segment，查詢時(shí)就需要分別查詢這些segment再匯總結(jié)果，從而segment數(shù)量越多，查詢速度越慢。

為了減少segment的數(shù)量，SQLite FTS5 引入了merge機(jī)制。新寫(xiě)入的segment的level為 0，merge操作可以把level為i的現(xiàn)有segment合并成一個(gè)level為i+1的新的segment。merge的示例如下：

FTS5 默認(rèn)的merge操作有兩種：

• 某一個(gè)level的segment達(dá)到4時(shí)就開(kāi)始在寫(xiě)入內(nèi)容時(shí)自動(dòng)執(zhí)行一部分merge操作，稱(chēng)為一次automerge。每次automerge的寫(xiě)入量跟本次更新的寫(xiě)入量成正比，需要多次automerge才能完整合并成一個(gè)新segment。Automerge在完整生成一個(gè)新的segment前，需要多次裁剪舊的segment的已合并內(nèi)容，引入多余的寫(xiě)入量。
• 本次寫(xiě)入后某一個(gè)level的segment數(shù)量達(dá)到 16 時(shí)，一次性合并這個(gè)level的segment，稱(chēng)為crisismerge。

FTS5 的默認(rèn)merge操作都是在寫(xiě)入時(shí)同步執(zhí)行的，會(huì)對(duì)業(yè)務(wù)邏輯造成性能影響，特別是crisismerge會(huì)偶然導(dǎo)致某一次寫(xiě)入操作特別久，這會(huì)讓業(yè)務(wù)性能不可控。之前的測(cè)試中 FTS5 的建索引耗時(shí)較久，也主要因?yàn)?FTS5 的merge操作比其他兩種引擎更加耗時(shí)。

我們?cè)?WCDB 中實(shí)現(xiàn) FTS5 的segment自動(dòng)merge機(jī)制，將這些merge操作集中到一個(gè)單獨(dú)子線程執(zhí)行，并且優(yōu)化執(zhí)行參數(shù)，具體如下：

• 監(jiān)聽(tīng)有 FTS5 索引的數(shù)據(jù)庫(kù)每個(gè)事務(wù)變更到的 FTS5 索引表，拋通知到子線程觸發(fā) WCDB 的自動(dòng)merge操作。
• Merge 線程檢查所有 FTS5 索引表中segment數(shù)超過(guò) 1 的 level 執(zhí)行一次merge。
• Merge時(shí)每寫(xiě)入16頁(yè)數(shù)據(jù)檢查一次有沒(méi)有其他線程的寫(xiě)入操作因?yàn)閙erge操作阻塞，如果有就立即commit，盡量減小merge對(duì)業(yè)務(wù)性能的影響。

自動(dòng)merge邏輯執(zhí)行的流程圖如下：

限制每個(gè)level的segment數(shù)量為1，可以讓 FTS5 的查詢性能最接近optimize(所有segment合并成一個(gè))之后的性能，而且引入的寫(xiě)入量是可接受的。假設(shè)業(yè)務(wù)每次寫(xiě)入量為M，寫(xiě)入了N次，那么在 merge 執(zhí)行完整之后，數(shù)據(jù)庫(kù)實(shí)際寫(xiě)入量為**MN(log2(N)+1)**。業(yè)務(wù)批量寫(xiě)入，提高M(jìn)也可以減小總寫(xiě)入量。

性能方面，對(duì)一個(gè)包含 100w 條中文內(nèi)容，每條長(zhǎng)度 100 漢字的 fts5 的表查詢?nèi)齻€(gè)詞，optimize狀態(tài)下耗時(shí)2.9ms，分別限制每個(gè)level的segment數(shù)量為2、3、4時(shí)的查詢耗時(shí)分別為4.7ms、8.9ms、15ms。100w 條內(nèi)容每次寫(xiě)入 100 條的情況下，按照 WCDB 的方案執(zhí)行merge的耗時(shí)在10s內(nèi)。

使用自動(dòng)Merge機(jī)制，可以在不影響索引更新性能的情況下，將 FTS5 索引保持在最接近Optimize的狀態(tài)，提高了搜索速度。

3. 分詞器優(yōu)化

分詞器性能優(yōu)化

分詞器是全文搜索的關(guān)鍵模塊，它實(shí)現(xiàn)將輸入內(nèi)容拆分成多個(gè)Token并提供這些Token的位置，搜索引擎再對(duì)這些Token建立索引。SQLite 的 FTS 組件支持自定義分詞器，可以按照業(yè)務(wù)需求實(shí)現(xiàn)自己的分詞器。

分詞器的分詞方法可以分為按字分詞和按詞分詞。前者只是簡(jiǎn)單對(duì)輸入內(nèi)容逐字建立索引，后者則需要理解輸入內(nèi)容的語(yǔ)義，對(duì)有具體含義的詞組建立索引。相比于按字分詞，按詞分詞的優(yōu)勢(shì)是既可以減少建索引的Token數(shù)量，也可以減少搜索時(shí)匹配的Token數(shù)量，劣勢(shì)是需要理解語(yǔ)義，而且用戶輸入的詞不完整時(shí)也會(huì)有搜不到的問(wèn)題。

為了簡(jiǎn)化客戶端邏輯和避免用戶漏輸內(nèi)容時(shí)搜不到的問(wèn)題，iOS 微信之前的 FTS3 分詞器OneOrBinaryTokenizer是采用了一種巧妙的按字分詞算法，除了對(duì)輸入內(nèi)容逐字建索引，還會(huì)對(duì)內(nèi)容中每?jī)蓚€(gè)連續(xù)的字建索引，對(duì)于搜索內(nèi)容則是按照每?jī)蓚€(gè)字進(jìn)行分詞。下面是一個(gè)用“北京歡迎你”去搜索相同內(nèi)容的分詞例子：

相比于簡(jiǎn)單的按字分詞，這種分詞方式的優(yōu)勢(shì)是可以將搜索時(shí)匹配的Token數(shù)量接近降低一半，提高搜索速度，而且在一定程度上可以提升搜索精度，比如搜索“歡迎你北京”就匹配不到“北京歡迎你”；這種分詞方式的劣勢(shì)就是保存的索引內(nèi)容很多，基本輸入內(nèi)容的每個(gè)字都在索引中保存了三次，是一種用空間換時(shí)間的做法。

因?yàn)镺neOrBinaryTokenizer用接近三倍的索引內(nèi)容增長(zhǎng)才換取不到兩倍的搜索性能提升，不是很劃算，所以我們?cè)?FTS5 上重新開(kāi)發(fā)了一種新的分詞器VerbatimTokenizer，這個(gè)分詞器只采用基本的按字分詞，不保存冗余索引內(nèi)容。同時(shí)在搜索時(shí)，每?jī)蓚€(gè)字用引號(hào)引起來(lái)組成一個(gè)Phrase，按照 FTS5 的搜索語(yǔ)法，搜索時(shí)Phrase中的字要按順序相鄰出現(xiàn)的內(nèi)容才會(huì)命中，實(shí)現(xiàn)了跟OneOrBinaryTokenizer一樣的搜索精度。VerbatimTokenizer的分詞規(guī)則示意圖如下：

分詞器能力擴(kuò)展

VerbatimTokenizer 還根據(jù)微信實(shí)際的業(yè)務(wù)需求實(shí)現(xiàn)了五種擴(kuò)展能力來(lái)提高搜索的容錯(cuò)能力：

• 支持在分詞時(shí)將繁體字轉(zhuǎn)換成簡(jiǎn)體字。這樣用戶可以用繁體字搜到簡(jiǎn)體字內(nèi)容，用簡(jiǎn)體字也能搜到繁體字內(nèi)容，避免了因?yàn)闈h字的簡(jiǎn)體和繁體字形相近導(dǎo)致用戶輸錯(cuò)的問(wèn)題。
• 支持 Unicode 歸一化。Unicode 支持相同字形的字符用不同的編碼來(lái)表示，比如編碼為\ue9的é和編碼為\u65\u301的e?有相同的字形，這會(huì)導(dǎo)致用戶用看上去一樣的內(nèi)容去搜索結(jié)果搜不到的問(wèn)題。Unicode 歸一化就是把字形相同的字符用同一個(gè)編碼表示。
• 支持過(guò)濾符號(hào)。大部分情況下，我們不需要支持對(duì)符號(hào)建索引，符號(hào)的重復(fù)量大而且用戶一般也不會(huì)用符號(hào)去搜索內(nèi)容，但是聯(lián)系人搜索這個(gè)業(yè)務(wù)場(chǎng)景需要支持符號(hào)搜索，因?yàn)橛脩舻年欠Q(chēng)里面經(jīng)常出現(xiàn)顏文字，符號(hào)的使用量不低。
• 支持用Porter Stemming算法對(duì)英文單詞取詞干。取詞干的好處是允許用戶搜索內(nèi)容的單復(fù)數(shù)和時(shí)態(tài)跟命中內(nèi)容不一致，讓用戶更容易搜到內(nèi)容。但是取詞干也有弊端，比如用戶要搜索的內(nèi)容是“happyday”，輸入“happy”作為前綴去搜索卻會(huì)搜不到，因?yàn)椤癶appyday”取詞干變成“happydai”，“happy”取詞干變成“happi”，后者就不能成為前者的前綴。這種 badcase 在內(nèi)容為多個(gè)英文單詞拼接一起時(shí)容易出現(xiàn)，聯(lián)系人昵稱(chēng)的拼接英文很常見(jiàn)，所以在聯(lián)系人的索引中沒(méi)有取詞干，在其他業(yè)務(wù)場(chǎng)景中都用上了。
• 支持將字母全部轉(zhuǎn)成小寫(xiě)。這樣用戶可以用小寫(xiě)搜到大寫(xiě)，反之亦然。

這些擴(kuò)展能力都是對(duì)建索引內(nèi)容和搜索內(nèi)容中的每個(gè)字做變換，這個(gè)變換其實(shí)也可以在業(yè)務(wù)層做，其中的 Unicode 歸一化和簡(jiǎn)繁轉(zhuǎn)換以前就是在業(yè)務(wù)層實(shí)現(xiàn)的。但是這樣做有兩個(gè)弊端，一個(gè)是業(yè)務(wù)層每做一個(gè)轉(zhuǎn)換都需要對(duì)內(nèi)容做一次遍歷，引入冗余計(jì)算量，另一個(gè)是寫(xiě)入到索引中的內(nèi)容是轉(zhuǎn)變后的內(nèi)容，那么搜索出來(lái)的結(jié)果也是轉(zhuǎn)變后的，會(huì)和原文不一致，業(yè)務(wù)層做內(nèi)容判斷的時(shí)候容易出錯(cuò)。鑒于這兩個(gè)原因，VerbatimTokenizer將這些轉(zhuǎn)變能力都集中到了分詞器中實(shí)現(xiàn)。

4. 索引內(nèi)容支持多級(jí)分隔符

SQLite 的 FTS 索引表不支持在建表后再添加新列，但是隨著業(yè)務(wù)的發(fā)展，業(yè)務(wù)數(shù)據(jù)支持搜索的屬性會(huì)變多，如何解決新屬性的搜索問(wèn)題呢?特別是在聯(lián)系人搜索這個(gè)業(yè)務(wù)場(chǎng)景，一個(gè)聯(lián)系人支持搜索的字段非常多。一個(gè)直接的想法是將新屬性和舊屬性用分隔符拼接到一起建索引。但這樣會(huì)引入新的問(wèn)題，F(xiàn)TS5 是以整個(gè)字段的內(nèi)容作為整體去匹配的，如果用戶搜索匹配的Token在不同的屬性，那這條數(shù)據(jù)也會(huì)命中，這個(gè)結(jié)果顯然不是用戶想要的，搜索結(jié)果的精確度就降低了。

我們需要搜索匹配的Token中間不存在分隔符，那這樣可以確保匹配的Token都在一個(gè)屬性內(nèi)。同時(shí)，為了支持業(yè)務(wù)靈活擴(kuò)展，還需要支持多級(jí)分隔符，而且搜索結(jié)果中還要支持獲取匹配結(jié)果的層級(jí)、位置以及該段內(nèi)容的原文和匹配詞。這個(gè)能力 FTS5 還不沒(méi)有，而 FTS5 的自定義輔助函數(shù)支持在搜索時(shí)獲取到所有命中結(jié)果中每個(gè)命中Token的位置，利用這個(gè)信息可以推斷出這些Token中間有沒(méi)有分隔符，以及這些Token所在的層級(jí)，所以我們開(kāi)發(fā)了SubstringMatchInfo這個(gè)新的 FTS5 搜索輔助函數(shù)來(lái)實(shí)現(xiàn)這個(gè)能力。這個(gè)函數(shù)的大致執(zhí)行流程如下：

三、全文搜索應(yīng)用邏輯優(yōu)化

1. 數(shù)據(jù)庫(kù)表格式優(yōu)化

1.1非文本搜索內(nèi)容的保存方式

在實(shí)際應(yīng)用中，我們除了要在數(shù)據(jù)庫(kù)中保存需要搜索的文本的 FTS 索引，還需要額外保存這個(gè)文本對(duì)應(yīng)的業(yè)務(wù)數(shù)據(jù)的id、用于結(jié)果排序的的屬性(常見(jiàn)的是業(yè)務(wù)數(shù)據(jù)的創(chuàng)建時(shí)間)以及其他需要直接跟隨搜索結(jié)果讀出的內(nèi)容，這些都是不參與文本搜索的內(nèi)容。根據(jù)非文本搜索內(nèi)容的不同存儲(chǔ)位置，我們可以將 FTS 索引表的表格式分成兩種：

• 第一種方式是將非文本搜索內(nèi)容存儲(chǔ)在額外的普通表中，這個(gè)表保存 FTS 索引的Rowid和非文本搜索內(nèi)容的映射關(guān)系，而 FTS 索引表的每一行只保存可搜索的文本內(nèi)容，這個(gè)表格式類(lèi)似于這樣：

這種表格式的優(yōu)勢(shì)是 FTS 索引表的內(nèi)容很簡(jiǎn)單，不熟悉 FTS 索引表配置的同學(xué)不容易出錯(cuò)，而且普通表的可擴(kuò)展性好，支持添加新列;劣勢(shì)則是搜索時(shí)需要先用 FTS 索引的Rowid讀取到普通表的Rowid，這樣才能讀取到普通表的其他內(nèi)容，搜索速度慢一點(diǎn)，而且搜索時(shí)需要聯(lián)表查詢，搜索 SQL 語(yǔ)句稍微復(fù)雜一點(diǎn)。

• 第二種方式是將非文本搜索內(nèi)容直接和可搜索文本內(nèi)容一起存儲(chǔ)在 FTS 索引表中，表格式類(lèi)似于這樣：

這種方式的優(yōu)劣勢(shì)跟前一種方式恰好相反，優(yōu)勢(shì)是搜索速度快而且搜索方式簡(jiǎn)單，劣勢(shì)是擴(kuò)展性差且需要更細(xì)致的配置。

因?yàn)?iOS 微信以前是使用第二種表格式，而且微信的搜索業(yè)務(wù)已經(jīng)穩(wěn)定不會(huì)有大變化，我們現(xiàn)在更加追求搜索速度，所以我們還是繼續(xù)使用第二種表格式來(lái)存儲(chǔ)全文搜索的數(shù)據(jù)。

1.2 避免冗余索引內(nèi)容

FTS 索引表默認(rèn)對(duì)表中的每一列的內(nèi)容都建倒排索引，即便是數(shù)字內(nèi)容也會(huì)按照文本來(lái)處理，這樣會(huì)導(dǎo)致我們保存在 FTS 索引表中的非文本搜索內(nèi)容也建了索引，進(jìn)而增大索引文件的大小、索引更新的耗時(shí)和搜索的耗時(shí)，這顯然不是我們想要的。

FTS5 支持給索引表中的列添加UNINDEXED約束，這樣 FTS5 就不會(huì)對(duì)這個(gè)列建索引了，所以給可搜索文本內(nèi)容之外的所有列添加這個(gè)約束就可以避免冗余索引。

1.3 降低索引內(nèi)容的大小

前面提到，倒排索引主要保存文本中每個(gè)Token對(duì)應(yīng)的行號(hào)(rowid)、列號(hào)和字段中的每次出現(xiàn)的位置偏移，其中的行號(hào)是 SQLite 自動(dòng)分配的，位置偏移是根據(jù)業(yè)務(wù)的實(shí)際內(nèi)容，這兩個(gè)我們都決定不了，但是列號(hào)是可以調(diào)整的。

在 FTS5 索引中，一個(gè)Token在一行中的索引內(nèi)容的格式是這樣的：

從中可以看出，如果我們把可搜索文本內(nèi)容設(shè)置在第一列的話(多個(gè)可搜索文本列的話，把內(nèi)容多的列放到第一列)，就可以少保存列分割符0x01和列號(hào)，這樣可以明顯降低索引文件大小。

所以我們最終的表格式是這樣：

1.4 索引文件大小優(yōu)化數(shù)據(jù)

下面是 iOS 微信優(yōu)化前后的平均每個(gè)用戶的索引文件大小對(duì)比：

2. 索引更新邏輯優(yōu)化

為了將全文搜索邏輯和業(yè)務(wù)邏輯解耦，iOS 微信的 FTS 索引是不保存在各個(gè)業(yè)務(wù)的數(shù)據(jù)庫(kù)中的，而是集中保存到一個(gè)專(zhuān)用的全文搜索數(shù)據(jù)庫(kù)，各個(gè)業(yè)務(wù)的數(shù)據(jù)有更新之后再異步通知全文搜索模塊更新索引。整體流程如下：

這樣做既可以避免索引更新拖慢業(yè)務(wù)數(shù)據(jù)更新的速度，也能避免索引數(shù)據(jù)更新出錯(cuò)甚至索引數(shù)據(jù)損壞對(duì)業(yè)務(wù)造成影響，讓全文搜索功能模塊能夠充分獨(dú)立。

2.1 保證索引和數(shù)據(jù)的一致

業(yè)務(wù)數(shù)據(jù)和索引數(shù)據(jù)分離且異步同步的好處很多，但實(shí)現(xiàn)起來(lái)也很難，最難的問(wèn)題是如何保證業(yè)務(wù)數(shù)據(jù)和索引數(shù)據(jù)的一致，也即要保證業(yè)務(wù)數(shù)據(jù)和索引數(shù)據(jù)要逐條對(duì)應(yīng)，不多不少。曾經(jīng) iOS 微信在這里踩了很多坑，打了很多補(bǔ)丁都不能完整解決這個(gè)問(wèn)題，我們需要一個(gè)更加體系化的方法來(lái)解決這個(gè)問(wèn)題。

為了簡(jiǎn)化問(wèn)題，我們可以把一致性問(wèn)題可以拆成兩個(gè)方面分別處理，一個(gè)是保證所有業(yè)務(wù)數(shù)據(jù)都有索引，這個(gè)用戶的搜索結(jié)果就不會(huì)有缺漏;第二個(gè)是保證所有索引都對(duì)應(yīng)一個(gè)有效的業(yè)務(wù)數(shù)據(jù)，這樣用戶就不會(huì)搜到無(wú)效的結(jié)果。

要保證所有業(yè)務(wù)數(shù)據(jù)都有索引，首先要找到或者構(gòu)造一種一直增長(zhǎng)的數(shù)據(jù)來(lái)描述業(yè)務(wù)數(shù)據(jù)更新的進(jìn)度，這個(gè)進(jìn)度數(shù)據(jù)的更新和業(yè)務(wù)數(shù)據(jù)的更新能保證原子性，而且根據(jù)這個(gè)進(jìn)度的區(qū)間能拿出業(yè)務(wù)數(shù)據(jù)更新的內(nèi)容，這樣我們就可以依賴這個(gè)進(jìn)度來(lái)更新索引。在微信的業(yè)務(wù)中，不同業(yè)務(wù)的進(jìn)度數(shù)據(jù)不同，聊天記錄是使用消息的rowid，收藏是使用收藏跟后臺(tái)同步的updateSequence，而聯(lián)系人找不到這種一直增長(zhǎng)的進(jìn)度數(shù)據(jù)，我們是通過(guò)在聯(lián)系人數(shù)據(jù)庫(kù)中標(biāo)記有新增或有更新的聯(lián)系人的微信號(hào)來(lái)作為索引更新進(jìn)度。進(jìn)度數(shù)據(jù)的使用方法如下：

無(wú)論業(yè)務(wù)數(shù)據(jù)是否保存成功、更新通知是否到達(dá)全文搜索模塊、索引數(shù)據(jù)是否保存成功，這套索引更新邏輯都能保證保存成功的業(yè)務(wù)數(shù)據(jù)都能成功建到索引。這其中的一個(gè)關(guān)鍵點(diǎn)是數(shù)據(jù)和進(jìn)度要在同個(gè)事務(wù)中一起更新，而且要保存在同個(gè)數(shù)據(jù)庫(kù)中，這樣才能保證數(shù)據(jù)和進(jìn)度的更新的原子性(WCDB 創(chuàng)建的數(shù)據(jù)庫(kù)因?yàn)槭褂肳AL模式而無(wú)法保證不同數(shù)據(jù)庫(kù)的事務(wù)的原子性)。還有一個(gè)操作圖中沒(méi)有畫(huà)出，具體是微信啟動(dòng)時(shí)如果檢查到業(yè)務(wù)進(jìn)度小于索引進(jìn)度，這種一般意味著業(yè)務(wù)數(shù)據(jù)損壞后被重置了，這種情況下要?jiǎng)h掉索引并重置索引進(jìn)度。

對(duì)于每個(gè)索引都對(duì)應(yīng)有效的業(yè)務(wù)數(shù)據(jù)，這就要求業(yè)務(wù)數(shù)據(jù)刪除之后索引也要必須刪掉?，F(xiàn)在業(yè)務(wù)數(shù)據(jù)的刪除和索引的刪除是異步的，會(huì)出現(xiàn)業(yè)務(wù)數(shù)據(jù)刪掉之后索引沒(méi)刪除的情況。這種情況會(huì)導(dǎo)致兩個(gè)問(wèn)題，一個(gè)是冗余索引會(huì)導(dǎo)致搜索速度變慢，但這個(gè)問(wèn)題出現(xiàn)概率很小，這個(gè)影響可以忽略不計(jì);第二個(gè)問(wèn)題是會(huì)導(dǎo)致用戶搜到無(wú)效數(shù)據(jù)，這個(gè)是要避免的。因?yàn)橐耆珓h掉所有無(wú)效索引成本比較高，所以我們采用了惰性檢查的方法來(lái)解決這個(gè)問(wèn)題，具體做法是搜索結(jié)果要顯示給用戶時(shí)，才檢查這個(gè)數(shù)據(jù)是否有效，無(wú)效的話不顯示這個(gè)搜索結(jié)果并異步刪除對(duì)應(yīng)的索引。因?yàn)橛脩粢黄聊芸吹降臄?shù)據(jù)很少，所以檢查邏輯帶來(lái)的性能消耗也可以忽略不計(jì)。而且這個(gè)檢查操作實(shí)際上也不算是額外加的邏輯，為了搜索結(jié)果展示內(nèi)容的靈活性，我們也要在展示搜索結(jié)果時(shí)讀出業(yè)務(wù)數(shù)據(jù)，這樣也就順帶做了數(shù)據(jù)有效性的檢查。

2.2 建索引速度優(yōu)化

索引只有在搜索的時(shí)候才會(huì)用到，它的更新優(yōu)先級(jí)并沒(méi)有業(yè)務(wù)數(shù)據(jù)那么高，可以盡量攢更多的業(yè)務(wù)數(shù)據(jù)才去批量建索引。批量建索引有以下三個(gè)好處：

• 減少磁盤(pán)的寫(xiě)入次數(shù)，提高平均建索引速度。
• 在一個(gè)事務(wù)中，建索引 SQL 語(yǔ)句的解析結(jié)果可以反復(fù)使用，可以減少 SQL 語(yǔ)句的解析次數(shù)，進(jìn)而提高平均建索引速度。
• 減少生成 Segment 的數(shù)量，從而減少M(fèi)erge Segment帶來(lái)的讀寫(xiě)消耗。

當(dāng)然，也不能保留太多業(yè)務(wù)數(shù)據(jù)不建索引，這樣用戶要搜索時(shí)會(huì)來(lái)不及建索引，從而導(dǎo)致搜索結(jié)果不完整。有了前面的Segment自動(dòng)Merge機(jī)制，索引的寫(xiě)入速度非?？煽?，只要控制好量，就不用擔(dān)心批量建索引帶來(lái)的高耗時(shí)問(wèn)題。我們綜合考慮了低端機(jī)器的建索引速度和搜索頁(yè)面的拉起時(shí)間，確定了最大批量建索引數(shù)據(jù)條數(shù)為 100 條。同時(shí)，我們會(huì)在內(nèi)存中 cache 本次微信運(yùn)行期間產(chǎn)生的未建索引業(yè)務(wù)數(shù)據(jù)，在極端情況下給沒(méi)有來(lái)得及建索引的業(yè)務(wù)數(shù)據(jù)提供相對(duì)內(nèi)存搜索，保證搜索結(jié)果的完整性。因?yàn)?cache 上一次微信運(yùn)行期間產(chǎn)生的未建索引數(shù)據(jù)需要引入額外的磁盤(pán) IO，所以微信啟動(dòng)后會(huì)觸發(fā)一次建索引邏輯，對(duì)現(xiàn)有的未建索引業(yè)務(wù)數(shù)據(jù)建一次索引?？偨Y(jié)一下觸發(fā)建索引的時(shí)機(jī)有三個(gè)：

• 未建索引業(yè)務(wù)數(shù)據(jù)達(dá)到 100 條。
• 進(jìn)入搜索界面。
• 微信啟動(dòng)。

2.3 刪除索引速度優(yōu)化

索引的刪除速度經(jīng)常是設(shè)計(jì)索引更新機(jī)制時(shí)比較容易忽視的因素，因?yàn)楸粍h除的業(yè)務(wù)數(shù)據(jù)量容易被低估，會(huì)被誤以為是低概率場(chǎng)景，但實(shí)際被用戶刪除的業(yè)務(wù)數(shù)據(jù)可能會(huì)達(dá)到 50%，是個(gè)不可忽視的主場(chǎng)景。而且 SQLite 是不支持并行寫(xiě)入的，刪除索引的性能也會(huì)間接影響到索引的寫(xiě)入速度，會(huì)為索引更新引入不可控因素。

因?yàn)閯h除索引的時(shí)候是拿著業(yè)務(wù)數(shù)據(jù)的 id 去刪除的，所以提高刪除索引速度的方式有兩種：

• 建一個(gè)業(yè)務(wù)數(shù)據(jù)id到 FTS 索引的rowid的普通索引。
• 在 FTS 索引表中去掉業(yè)務(wù)數(shù)據(jù)Id那一列的UNINDEXED約束，給業(yè)務(wù)數(shù)據(jù)Id添加倒排索引。

這里倒排索引其實(shí)沒(méi)有普通索引那么高效，有兩個(gè)原因：

• 倒排索引相比普通索引還帶了很多額外信息，搜索效率低一些。
• 如果需要多個(gè)業(yè)務(wù)字段才能確定一條倒排索引時(shí)，倒排索引是建不了聯(lián)合索引的，只能匹配其中一個(gè)業(yè)務(wù)字段，其他字段就是遍歷匹配，這種情況搜索效率會(huì)很低。

2.4 索引更新性能優(yōu)化數(shù)據(jù)

聊天記錄的優(yōu)化前后索引性能數(shù)據(jù)如下：

收藏的優(yōu)化前后索引性能數(shù)據(jù)如下：

3. 搜索邏輯優(yōu)化

用戶在 iOS 微信的首頁(yè)輸入內(nèi)容搜索時(shí)，搜索的整體流程如下：

用戶變更搜索框的內(nèi)容之后，會(huì)并行發(fā)起所有業(yè)務(wù)的搜索任務(wù)，各個(gè)搜索任務(wù)執(zhí)行完之后才再將搜索結(jié)果返回到主線程給頁(yè)面展示。這個(gè)邏輯會(huì)隨著用戶變更搜索內(nèi)容而繼續(xù)重復(fù)。

3.1 單個(gè)搜索任務(wù)支持并行執(zhí)行

雖然現(xiàn)在不同搜索任務(wù)已經(jīng)支持并行執(zhí)行，但是不同業(yè)務(wù)的數(shù)據(jù)量和搜索邏輯差別很大，數(shù)據(jù)量大或者搜索邏輯復(fù)雜的任務(wù)耗時(shí)會(huì)很久，這樣還不能充分發(fā)揮手機(jī)的并行處理能力。我們還可以將并行處理能力引入單個(gè)搜索任務(wù)內(nèi)，這里有兩種處理方式：

• 對(duì)于搜索數(shù)據(jù)量大的業(yè)務(wù)(比如聊天記錄搜索)，可以將索引數(shù)據(jù)均分存儲(chǔ)到多個(gè) FTS 索引表(注意這里不均分的話還是會(huì)存在短板效應(yīng))，這樣搜索時(shí)可以并行搜索各個(gè)索引表，然后匯總各個(gè)表的搜索結(jié)果，再進(jìn)行統(tǒng)一排序。這里拆分的索引表數(shù)量既不能太多也不能太少，太多會(huì)超出手機(jī)實(shí)際的并行處理能力，也會(huì)影響其他搜索任務(wù)的性能，太少又不能充分利用并行處理能力。以前微信用了十個(gè) FTS 表存儲(chǔ)聊天記錄索引，現(xiàn)在改為使用四個(gè) FTS 表。
• 對(duì)于搜索邏輯復(fù)雜的業(yè)務(wù)(比如聯(lián)系人搜索)，可以將可獨(dú)立執(zhí)行的搜索邏輯并行執(zhí)行。比如在聯(lián)系人搜索任務(wù)中，我們將聯(lián)系人的普通文本搜索、拼音搜索、標(biāo)簽和地區(qū)的搜索、多群成員的搜索并行執(zhí)行，搜完之后再合并結(jié)果進(jìn)行排序。這里為什么不也用拆表的方式呢?因?yàn)檫@種搜索結(jié)果數(shù)量少的場(chǎng)景，搜索的耗時(shí)主要是集中在搜索索引的環(huán)節(jié)，索引可以看做一顆 B 樹(shù)，將一顆 B 樹(shù)拆分成多個(gè)，搜索耗時(shí)并不會(huì)成比例下降。

3.2 搜索任務(wù)支持中斷

用戶在搜索框持續(xù)輸入內(nèi)容的過(guò)程中可能會(huì)自動(dòng)多次發(fā)起搜索任務(wù)，如果在前一次發(fā)起的搜索任務(wù)還沒(méi)執(zhí)行完時(shí)，就再次發(fā)起搜索任務(wù)，那前后兩次搜索任務(wù)就會(huì)互相影響對(duì)方性能。這種情況在用戶輸入內(nèi)容從短到長(zhǎng)的過(guò)程中還挺容易出現(xiàn)的，因?yàn)樗阉魑谋径痰臅r(shí)候命中結(jié)果就很多，搜索任務(wù)也就更加耗時(shí)，從而更有機(jī)會(huì)撞上后面的搜索任務(wù)。太多任務(wù)同時(shí)執(zhí)行還會(huì)容易引起手機(jī)發(fā)燙、爆內(nèi)存的問(wèn)題。所以我們需要讓搜索任務(wù)支持隨時(shí)中斷，這樣就可以在后一次搜索任務(wù)發(fā)起的時(shí)候，能夠中斷前一次的搜索任務(wù)，避免任務(wù)量過(guò)多的問(wèn)題。

搜索任務(wù)支持中斷的實(shí)現(xiàn)方式是給每個(gè)搜索任務(wù)設(shè)置一個(gè)CancelFlag，在搜索邏輯執(zhí)行時(shí)每搜到一個(gè)結(jié)果就判斷一下CancelFlag是否置位，如果置位了就立即退出任務(wù)。外部邏輯可以通過(guò)置位CancelFlag來(lái)中斷搜索任務(wù)。邏輯流程如下圖所示：

為了讓搜索任務(wù)能夠及時(shí)中斷，我們需要讓檢查CancelFlag的時(shí)間間隔盡量相等，要實(shí)現(xiàn)這個(gè)目標(biāo)就要在搜索時(shí)避免使用 OrderBy 子句對(duì)結(jié)果進(jìn)行排序。因?yàn)?FTS5 不支持建立聯(lián)合索引，所以在使用OrderBy子句時(shí)，SQLite 在輸出第一個(gè)結(jié)果前會(huì)遍歷所有匹配結(jié)果進(jìn)行排序，這就讓輸出第一個(gè)結(jié)果的耗時(shí)幾乎等于輸出全部結(jié)果的耗時(shí)，中斷邏輯就失去了意義。不使用OrderBy子句就對(duì)搜索邏輯添加了兩個(gè)限制：

• 從數(shù)據(jù)庫(kù)讀取所有結(jié)果之后再排序。我們可以在讀取結(jié)果時(shí)將用于排序的字段一并讀出，然后在讀完所有結(jié)果之后再對(duì)所有結(jié)果執(zhí)行排序。因?yàn)榕判虻暮臅r(shí)占總搜索耗時(shí)的比例很低，加上排序算法的性能大同小異，這種做法對(duì)搜索速度的影響可以忽略。
• 不能使用分段查詢。在全文搜索這個(gè)場(chǎng)景中，分段查詢其實(shí)是沒(méi)有什么作用的。因?yàn)榉侄尾樵兙鸵獙?duì)結(jié)果排序，對(duì)結(jié)果排序就要遍歷所有結(jié)果，所以分段查詢并不能降低搜索耗時(shí)(除非按照 FTS 索引的Rowid分段查詢，但是Rowid不包含實(shí)際的業(yè)務(wù)信息)。

3.3 搜索讀取內(nèi)容最少化

搜索時(shí)讀取內(nèi)容的量也是決定搜索耗時(shí)的一個(gè)關(guān)鍵因素。FTS 索引表實(shí)際是有多個(gè) SQLite 普通表組成的，這其中一些表格存儲(chǔ)實(shí)際的倒排索引內(nèi)容，還有一個(gè)表格存儲(chǔ)用戶保存到 FTS 索引表的全部原文。當(dāng)搜索時(shí)讀取Rowid以外的內(nèi)容時(shí)，就需要用Rowid到保存原文的表的讀取內(nèi)容，索引表輸出結(jié)果的內(nèi)部執(zhí)行過(guò)程如下：

所以讀取內(nèi)容越少輸出結(jié)果的速度越快，而且讀取內(nèi)容過(guò)多也會(huì)有消耗內(nèi)存的隱患。我們采用的方式是搜索時(shí)只讀取業(yè)務(wù)數(shù)據(jù) id 和用于排序的業(yè)務(wù)屬性，排好序之后，在需要給用戶展示結(jié)果時(shí)，才用業(yè)務(wù)數(shù)據(jù) id 按需讀取業(yè)務(wù)數(shù)據(jù)具體內(nèi)容出來(lái)展示。這樣做的擴(kuò)展性也會(huì)很好，可以在不更改存儲(chǔ)內(nèi)容的情況下，根據(jù)各個(gè)業(yè)務(wù)的需求不斷調(diào)整搜索結(jié)果展示的內(nèi)容。

這里還有一個(gè)要特別提一下的地方，就是搜索時(shí)盡量不要讀取高亮信息(SQLite 的highlight函數(shù)有這個(gè)能力)。因?yàn)橐@取高亮字段不僅要將文本的原文讀取出來(lái)，還要對(duì)文本原文再次分詞，才能定位命中位置的原文內(nèi)容，搜索結(jié)果多的情況下分詞帶來(lái)的消耗非常明顯。那展示搜索結(jié)果時(shí)如何獲取高亮匹配內(nèi)容呢?我們采用的方式是將用戶的搜索文本進(jìn)行分詞，然后在展示結(jié)果時(shí)查找每個(gè)Token在展示文本中的位置，然后將那個(gè)位置高亮顯示。同樣因?yàn)橛脩粢黄量吹降慕Y(jié)果數(shù)量是很少的，這里的高亮邏輯帶來(lái)的性能消耗可以忽略。

當(dāng)然在搜索規(guī)則很復(fù)雜的情況下，直接讀取高亮信息是比較方便，比如聯(lián)系人搜索就使用前面提到的SubstringMatchInfo函數(shù)來(lái)讀取高亮內(nèi)容。這里主要還是因?yàn)橐x取匹配內(nèi)容所在的層級(jí)和位置用于排序，所以逐個(gè)結(jié)果重新分詞的操作在所難免。

3.4 搜索性能優(yōu)化數(shù)據(jù)

下面是微信各搜索業(yè)務(wù)優(yōu)化前后的搜索耗時(shí)對(duì)比：

四、總結(jié)

目前 iOS 微信已經(jīng)將這套新全文搜索技術(shù)方案全量應(yīng)用到聊天記錄、聯(lián)系人和收藏的搜索業(yè)務(wù)中。使用新方案之后，全文搜索的索引文件占用空間更小，索引更新耗時(shí)更少，搜索速度也更快了，可以說(shuō)全文搜索的性能得到了全方位提升。