微信全文搜索耗时降94%？我们用了这种方案

微信邦

导语 |微信终端涉及到大量文本搜索的业务场景，主要包括联系人搜索、聊天记录搜索和收藏搜索等。近期微信团队对 IOS 微信的全文搜索技术进行了一次全面升级，本文将分享其选型与优化思路，详细解析全文搜索的应用数据库表格式、索引更新和搜索逻辑的优化细节。希望本文对你有帮助。

目录

1 IOS 微信全文搜索技术的现状2 全文搜索引擎的选型与优化   
    2.1 搜索引擎选型
    2.2 实现 FTS5 的 Segment 自动 Merge 机制
    2.3 分词器优化
    2.4 索引内容支持多级分隔符
3 全文搜索应用逻辑优化
    3.1 数据库表格式优化
    3.2 索引更新逻辑优化
    3.3 搜索逻辑优化
4 总结

01

IOS 微信全文搜索技术的现状
全文搜索是使用倒排索引进行搜索的一种搜索方式。倒排索引也称为反向索引——对输入的内容中的每个 Token 建立一个索引，索引中保存了这个 Token 在内容中的具体位置。全文搜索技术主要应用在对大量文本内容进行搜索的场景。
微信终端涉及到大量文本搜索的业务场景主要包括联系人、聊天记录、收藏。这些搜索功能多年没有更新底层搜索技术，聊天记录使用的全文搜索引擎还是 SQLite FTS3，而现在已经有 SQLite FTS5；收藏首页的搜索还是使用简单的 Like 语句来匹配文本；联系人搜索甚至用的是内存搜索（在内存中遍历所有联系人的所有属性进行匹配）。
用户在微信上积累的数据越来越多，提升微信底层搜索技术的需求也越来越迫切。在近几年，业务团队对 IOS 微信的全文搜索技术进行了一次全面升级，本文主要介绍技术升级的工作经验。


02
全文搜索引擎的选型与优化
2.1 搜索引擎选型IOS 客户端可以使用的全文搜索引擎并不多，主要有 SQLite 三个版本的 FTS 组件、Lucene 的 C++实现版本 CLucene 和 C 语言桥接版本 Lucy。这里给出了这些引擎在事务能力、技术风险、搜索能力、读写性能等方面的比较。

• 在事务能力方面：Lucene 没有提供完整的事务能力，因为 Lucene 使用了多文件的存储结构，没有保证事务的原子性。SQLite 的 FTS 组件因为底层使用普通的表来实现，可以完美继承 SQLite 的事务能力。
  

• 在技术风险方面：Lucene 主要应用于服务端，在客户端没有大规模应用的案例。自 2013 年起 CLucene 和 Lucy 官方都停止维护了，技术风险较高。SQLite 的 FTS3 和 FTS4 组件则是属于 SQLite 的旧版本引擎，官方维护不多，而且这两个版本都是将一个词的索引存到一条记录中，极端情况下有超出 SQLite 单条记录最大长度限制的风险。SQLite 的 FTS5 组件作为最新版本引擎已推出超六年，在安卓微信上也已经全量应用，所以其技术风险是最低的。
  

• 在搜索能力方面：Lucene 的发展历史比 SQLite 的 FTS 组件长很多，搜索能力相比而言最丰富。Lucene 有丰富的搜索结果评分排序机制，但这个在微信客户端没有应用场景。因为微信搜索结果要么是按照时间排序，要么是按照一些简单的自定义规则排序。在 SQLite 几个版本的引擎中，FTS5 的搜索语法更加完备严谨。它提供了很多接口给用户自定义搜索函数，所以搜索能力相对强一点。
  

• 在读写性能方面，下面是用不同引擎对 100 万条长度为 10 的随机生成中文语句生成 Optimize 状态的索引的性能数据，其中每个语句的汉字出现频率按照实际的汉字使用频率：
  

可以看到，Lucene 读取命中数量的性能比 SQLite 好很多，说明 Lucene 索引的文件格式很有优势。但是微信没有只读取命中数量的应用场景，Lucene 的其他性能数据跟 SQLite 的差距不明显。SQLite FTS3 和 FTS5 的大部分性能很接近，FTS5 索引的生成耗时比 FTS3 高一截，但这个有优化方法。
综合考虑这些因素，我们选择 SQLite FTS5 作为 IOS 微信全文搜索的搜索引擎。
2.2 实现 FTS5 的 Segment 自动 Merge 机制
SQLite FTS5 会把每个事务写入的内容保存成一个独立的 b 树，称为一个 segment 。segment 中保存了本次写入内容中每个词的行号（rowid）、列号和字段中每次出现的位置偏移，所以这个 segment 就是该内容的倒排索引。多次写入就会形成多个 segment 。查询时需要分别查询这些 segment 再汇总结果。从而， segment 数量越多，查询速度越慢。
为了减少 segment 的数量，SQLite FTS5 引入了 merge 机制。新写入的 segment 的 level 为 0，merge 操作可以把level为i的现有 segment 合并成一个 level 叫 i+1的新的 segment 。
merge 的示例如下：


FTS5 默认的merge操作有两种：

• 某一个 level 的 segment 达到4时，就开始在写入内容时自动执行一部分 merge 操作，称为一次 automerge 。每次 automerge 的写入量跟本次更新的写入量成正比，需要多次 automerge 才能完整合并成一个新 segment 。automerge 在完整生成一个新的 segment 前，需要多次裁剪旧的 segment 的已合并内容，引入多余的写入量。
• 本次写入后某一个 level 的 segment 数量达到 16 时，一次性合并这个 level 的 segment ，称为 crisismerge 。
  

FTS5 的默认 merge 操作都是在写入时同步执行的。这会对业务逻辑造成性能影响，特别是 crisismerge 会偶然导致某一次写入操作特别久，这会让业务性能不可控。之前的测试中 FTS5 的建索引耗时较久，也主要因为 FTS5 的 merge 操作比其他两种引擎更加耗时。
我们在 WCDB 中实现 FTS5 的 segment 自动 merge 机制，将这些 merge 操作集中到一个单独子线程执行，并且优化执行参数，具体如下：

• 首先，监听有 FTS5 索引的数据库每个事务变更到的 FTS5 索引表，抛通知到子线程触发 WCDB 的自动 merge 操作。
• 其次，merge 线程检查所有 FTS5 索引表中 segment 数，超过 1 的 level 执行一次 merge 。
• 最后，merge时每写入 16 页数据检查一次有没有其他线程的写入操作因为 merge 操作阻塞，如果有就立即 commit ，尽量减小 merge 对业务性能的影响。
  

自动 merge 逻辑执行的流程如下：