微信邦

 找回密码
 立即注册

QQ登录

只需一步,快速开始

查看: 342|回复: 0

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

[复制链接]
发表于 2023-2-21 08:38:49 | 显示全部楼层 |阅读模式
导语 |微信终端涉及到大量文本搜索的业务场景,主要包括联系人搜索、聊天记录搜索和收藏搜索等。近期微信团队对 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 逻辑执行的流程如下:

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

微信邦网联系QQ|Archiver|手机版|小黑屋|鲁公网安备 37082802000167号|微信邦 ( 鲁ICP备19043418号-5 )

GMT+8, 2024-4-25 08:29 , Processed in 0.110776 second(s), 19 queries .

Powered by Discuz! X3.4

© 2001-2013 Wxuse Inc. | Style by ytl QQ:1400069288

快速回复 返回顶部 返回列表