2021年iOS微信全文搜索技术升级技术升级选型与优化

一、iOS微信全文搜索技术现状

全文搜索是一种使用倒排索引进行搜索的搜索方法。倒排索引，也称为反向索引，是指为输入内容中的每一个Token建立一个索引，索引存储了该Token在内容中的具体位置。全文搜索技术主要用于搜索大量文本内容的场景。

微信终端涉及大量文字搜索的业务场景主要包括搜索联系人、聊天记录、收藏等。自 2014 年这些搜索功能上线以来，底层搜索技术已经多年没有更新。聊天记录使用的全文搜索引擎还是FTS3，现在有了FTS5。收藏夹主页上的搜索仍然使用简单的 Like 语句来匹配文本，以及联系人搜索。它甚至使用内存搜索（遍历内存中所有联系人的所有属性进行匹配）。随着用户在微信上积累的数据越来越多，改进微信底层搜索技术的需求也越来越迫切。2021年全面升级iOS微信全文搜索技术。

二、全文搜索引擎的选择与优化 1、搜索引擎的选择

iOS客户端可以使用的全文搜索引擎并不多。FTS组件主要有三个版本，C++实现版和C语言桥接版Lucy。以下是这些引擎在交易能力、技术风险、搜索能力、读写性能等方面的对比。

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

技术风险方面，主要用在服务端，客户端没有大规模应用，而且Lucy和Lucy的官方维护从2013年就停止了，所以技术风险很高。FTS3和FTS4组件属于老版本引擎，官方维护不多，两个版本都将一个词的索引存储在一个记录中，极端情况下存在超过一个词的最大长度的风险单记录。FTS5组件作为最新版本的引擎，已经推出六年多，在安卓微信上已经全面应用，技术风险最低。

在搜索能力方面，FTS组件的发展历史比FTS组件要长得多，搜索能力也是最丰富的。尤其是有丰富的搜索结果打分排序机制，但在微信客户端还没有应用场景。因为我们的搜索结果要么按时间排序，要么按一些简单的自定义规则排序。在引擎的几个版本中，FTS5的搜索语法更加完整和严谨，并且提供了很多接口供用户自定义搜索功能，因此搜索能力比较强。

在读写性能方面，以下是100万个随机生成的长度为10的中文句子不同引擎生成的索引的性能数据。每个句子中的汉字频率以实际汉语频率为准人物：

可以看到读取命中数的性能比要好很多，说明索引的文件格式是很有优势的，但是微信没有只读取命中数的应用场景，两者之间的差距其他性能数据不明显。FTS3和FTS5的大部分性能都非常接近。FTS5 索引的生成时间比 FTS3 略高。对此有一些优化方法。

考虑到这些因素，我们选择FTS5作为iOS微信全文搜索的搜索引擎。

2.实现FTS5的自动Merge机制

FTS5会将每个事务写入的内容保存为一棵独立的b-tree，称为one，其中本次写入的内容中的每个单词分别存储在内容的行号（rowid）、列号和字段中。每次出现的位置偏移量，所以这是内容的倒排索引。多次写入将导致多次。查询的时候，需要分别查询这些，然后再聚合结果，所以数量越多，查询速度越慢。

为了减少数量，FTS5 引入了合并机制。新写入的层级为0，合并操作可以将现有层级i合并成新的层级i+1。合并示例如下：

FTS5 中有两种默认的合并操作：

当某个级别达到4级时，开始在写入内容时自动执行一部分合并操作，调用一次。每次的写入量与本次更新的写入量成正比，需要多次才能完全合并成一个新的。在完全生成新内容之前，需要对旧的合并内容进行多次裁剪，从而引入冗余写入。本次写入后某一层数达到16个时，调用该层的一次性合并。

FTS5默认的merge操作在写的时候是同步执行的，会影响业务逻辑的性能。尤其是某个写操作偶尔会需要很长时间，这会让业务性能变得不可控。在之前的测试中，FTS5的索引耗时比较长，主要是FTS5的merge操作比其他两个引擎更耗时。

我们在WCDB中实现FTS5的自动合并机制，将这些合并操作集中到单个子线程中执行，并优化执行参数，如下：

监控带有FTS5索引的数据库的每个事务变化到的FTS5索引表，并向子线程抛出通知，触发WCDB的自动合并操作。Merge线程检查FTS5索引表中超过1层的所有层并执行合并。合并时，每写入16页数据，检查是否有其他线程的写入操作，因为合并操作被阻塞。如果存在，请立即尝试将合并对业务绩效的影响降至最低。

自动合并逻辑执行流程图如下：

将每个级别的数量限制为 1 可使 FTS5 查询性能最接近（全部合二为一）性能，并且引入的写入量是可以接受的。假设每个业务的写入量为M，写入N次，那么在执行完merge之后，数据库的实际写入量为**MN(log2(N)+1)**。业务是批量写入的，增加M也可以减少总的写入量。

性能方面，在包含100w条中文内容，每条长度为100个汉字的fts5表中查询三个词，在状态下耗时2.9ms，每级数限制为2时的查询时间，分别为 3 和 4。它们分别为 4.7ms、8.9ms 和 15ms。当100w条内容一次写入100条时，按照WCDB方案执行合并的时间不到10s。

使用自动 Merge 机制，FTS5 索引可以保持在最接近的状态，而不会影响索引更新性能，从而提高搜索速度。

3.优化性能优化

分词器是全文搜索的关键模块。它将输入内容拆分为多个标记并提供这些标记的位置。然后搜索引擎在这些标记上建立一个索引。FTS 组件支持自定义分词器，您可以根据业务需要实现自己的分词器。

分词器的分词方法可以分为分词和分词。前者只是逐词索引输入内容，而后者则需要理解输入内容的语义并索引具有特定含义的短语。与分词相比，分词的优势在于不仅可以减少用于索引的token数量，还可以减少搜索时匹配的token数量。无法解决的问题。

iOS 微信之前的 FTS3 分词器为了简化客户端逻辑，避免用户错过输入时找不到内容的问题，采用了巧妙的分词算法。索引中每两个连续的词被索引，对于搜索内容，每两个词进行分词。下面是一个使用“北京欢迎你”来搜索相同内容的分词示例：

与简单的分词相比，这种分词方法的优势在于可以将搜索时匹配的token数量减少近一半，提高搜索速度，一定程度上提高了搜索准确率。比如搜索“欢迎来到北京”不能匹配到“北京欢迎你”；这种分词方法的缺点是节省了大量的索引内容，基本输入内容的每个单词在索引中保存了3次直线搜索方法,无约束优化方法,约束优化方法，是一种以空间换时间的方式。

因为用近三倍的索引内容增加来换取不到两倍的搜索性能提升并不是很划算，所以我们在 FTS5 上重新开发了新的分词器。这个分词器只使用基本的逐词分割。不保存冗余索引内容。同时，在检索时，每两个单词用引号括起来组成一个。根据 FTS5 的搜索语法，搜索中的单词只有按顺序相邻出现才会被命中，达到了相同的搜索精度。分词规则示意图如下：

标记器功能扩展

根据微信的实际业务需求，还实现了五种扩展能力，提高搜索的容错能力：

这些扩展功能是对索引内容和搜索内容中的每个单词进行转换。这种转变实际上可以在业务层完成。规范化和简繁转换之前都是在业务层实现的。然而，这种方式有两个缺点。一是业务层每次转换都需要遍历内容，引入了冗余计算。另一种是写入索引的内容是转换后的内容，那么搜索到的结果也进行了转换，会与原文不一致，业务层在进行内容判断时容易出错。由于这两个原因，这些转换能力集中在分词器中。

4.索引内容支持多级分隔符

FTS索引表不支持建表后添加新列，但随着业务的发展，会出现更多支持业务数据查询的属性。如何解决新属性的搜索问题？尤其是在联系人搜索的业务场景中，支持搜索联系人的字段非常多。一个简单的想法是使用分隔符连接新旧属性以创建索引。但这会带来新的问题。FTS5 将整个字段的内容作为一个整体进行匹配。如果用户在不同的属性中搜索匹配的 Token，数据也会命中。这个结果显然不是用户想要的。搜索 结果的准确性降低。

我们需要搜索中间没有分隔符的匹配Token，这样可以保证匹配的Token都在一个属性中。同时，为了支持灵活的业务扩展，还需要支持多级分隔符，搜索结果也需要支持匹配结果的级别和位置，以及原文和匹配词的内容。FTS5尚不具备该能力，FTS5的自定义辅助功能支持在搜索时获取每个命中Token在所有命中结果中的位置。利用这些信息，可以推断出这些Token之间是否存在分隔符，以及这些Token的位置。层次结构，所以我们开发了这个新的 FTS5 搜索助手函数来实现这个功能。

三、全文检索应用逻辑优化 1、数据库表格式优化 1.1 如何保存非文本检索内容

在实际应用中，除了保存待搜索文本在数据库中的FTS索引外，我们还需要额外保存文本对应的业务数据的id和用于对结果进行排序的属性（通常是创建业务数据的时间）以及其他需要在搜索结果之后直接读出的内容，这些都是不参与文本搜索的内容。根据非文本搜索内容存储位置的不同，我们可以将FTS索引表的表格式分为两种：

这种表格式的优点是FTS索引表的内容很简单，不熟悉FTS索引表配置的同学不容易出错，通用表扩展性好，支持新增列; 缺点是搜索时需要先使用FTS索引的Rowid读取到普通表的Rowid，这样才能读取普通表的其他内容，搜索速度较慢，而且搜索需要一个链接表查询，查询SQL语句稍微复杂一些。

这种方法的优缺点与前一种方法正好相反。优点是搜索速度快，搜索方法简单。缺点是扩展性差，需要更详细的配置。

因为iOS微信曾经使用第二种表格格式，而微信的搜索业务一直很稳定，不会有太大变化，所以我们现在更加追求搜索速度，所以我们继续使用第二种表格格式来存储全文搜索数据。

1.2 避免冗余索引内容

FTS索引表默认为表中每一列的内容建立倒排索引，即使是数字内容也会按照文本进行处理，这会导致我们保存在FTS索引表中的非文本搜索内容还要建一个索引，然后增加索引文件的大​​小，索引更新的耗时和查找的耗时，这显然不是我们想要的。

FTS5 支持对索引表中的列添加约束，这样 FTS5 不会索引该列，因此对除可搜索文本内容以外的所有列添加此约束可以避免冗余索引。

1.3 减小索引内容的大小

前面说过，倒排索引主要保存文本中每个Token对应的字段中每次出现的行号（rowid）、列号和位置偏移量。行号是自动分配的，位置偏移量是根据业务的实际内容我们无法决定的，但是列号是可以调整的。

在FTS5索引中，一行Token的索引内容格式如下：

从中可以看出，如果我们在第一列设置可搜索文本内容（如果有多个可搜索文本列，则将内容较多的列放在第一列），可以少列分隔符0x01和列号，这可以显着减小索引文件的大​​小。

所以我们的最终表格格式如下所示：

1.4 索引文件大小优化数据

下面是iOS微信优化前后每个用户的平均索引文件大小对比：

2.索引更新逻辑优化

为了将全文搜索逻辑和业务逻辑解耦，iOS微信的FTS索引并没有存储在各个业务的数据库中，而是集中存储在专门的全文搜索数据库中。各业务数据更新后，异步通知全文。搜索模块更新索引。总体流程如下：

这样既可以防止索引更新拖慢业务数据更新速度，又可以防止索引数据更新错误甚至索引数据损坏影响业务，使全文检索功能模块完全独立.

2.1 保证索引和数据的一致性

业务数据和索引数据的分离和异步同步的好处很多，但是很难实现。最难的问题是如何保证业务数据和索引数据的一致性，即保证业务数据和索引数据要一一对应，不多也不少。一旦iOS微信在这里踩了很多坑，很多补丁都无法彻底解决这个问题，我们需要更系统的方法来解决这个问题。

为了简化问题，我们可以将一致性问题分为两个方面分别处理。一是保证所有业务数据都有索引，这样用户的搜索结果就不会丢失；二是保证所有索引都对应一个有效的业务数据，这样用户就不会发现无效的结果。

要保证所有业务数据都有索引，首先要找到或构造一种一直在增长的数据来描述业务数据更新的进度。这个进度数据的更新和业务数据的更新可以保证原子性，根据这个进度的间隔可以取出业务数据更新的内容，这样我们就可以依靠这个进度来更新索引。在微信业务中，不同业务的进度数据是不同的。聊天记录使用消息的rowid，集合使用集合与后台同步，联系人找不到这种一直在增加的进度数据。新增或更新联系人的微信账号在数据库中标记为索引更新进度。进度数据使用如下：

无论业务数据是否保存成功，更新通知是否到达全文搜索模块，或者索引数据是否保存成功直线搜索方法,无约束优化方法,约束优化方法，这套索引更新逻辑都能保证成功保存的业务数据能够成功内置到索引。重点之一是数据和进度必须在同一个事务中一起更新，并且存储在同一个数据库中，这样才能保证数据和进度更新的原子性（WCDB创建的数据库使用WAL模式和不能保证不同数据库中事务的原子性）。还有一个未显示的操作图。具体来说，微信启动时，如果检查到业务进度小于索引进度，这通常意味着业务数据在损坏后已被重置。在这种情况下，删除索引并重置索引。日程。

每个索引对应有效的业务数据，要求删除业务数据后必须删除索引。目前业务数据的删除和索引的删除是异步的，业务数据删除后索引不会被删除。这种情况会导致两个问题。一是冗余索引会减慢搜索速度，但出现这个问题的概率很小，影响可以忽略不计。第二个问题是用户会发现无效数据。这是要避免的。因为完全删除所有无效索引的成本比较高，所以我们采用惰性检查的方法来解决这个问题。具体方法是只有在搜索结果要显示给用户时才检查数据是否有效。如果无效，不会显示搜索结果。并异步删除对应的索引。由于用户在一屏上能看到的数据非常少，因此校验逻辑带来的性能消耗也可以忽略不计。而这个检查操作实际上并不是一个额外的逻辑。为了显示搜索结果的灵活性，我们还需要在显示搜索结果时读出业务数据，这也检查了数据的有效性。

2.2 索引速度优化

索引只在搜索时使用，其更新优先级不如业务数据高。在批量建立索引之前，可以尽可能多地保存业务数据。批量索引具有以下三个好处：

当然，不能不做索引就保留太多的业务数据，这样当用户想搜索的时候，来不及建索引，导致搜索结果不完整。有了之前的自动Merge机制，索引的写入速度是非常可控的。只要控制好量，就不用担心批量索引带来的耗时高的问题。我们综合考虑了低端机器的索引速度和搜索页面的上拉时间，确定批量索引数据的最大数量为100个。同时，我们将缓存这期间产生的未索引的业务数据内存中的微信操作，并且在极端情况下为没有来得及建立索引的业务数据提供相对内存搜索，以保证搜索结果的完整性。因为上一次微信操作缓存时产生的未索引数据需要引入额外的磁盘IO，所以微信启动后会触发一个索引逻辑，为已有的未索引业务数据建立索引。总结一下，触发索引的时候有3次：

2.3 删除索引速度优化

索引删除的速度往往是设计索引更新机制时容易忽略的一个因素，因为删除的业务数据量很容易被低估，可能被误认为是小概率场景，但用户实际删除的业务数据可能达到50%，是一个不容忽视的主场景。此外，不支持并行写入。删除索引的性能也会间接影响索引的写入速度，从而为索引更新引入不可控因素。

因为删除索引时使用业务数据的id来删除索引，所以有两种方法可以提高删除索引的速度：

这里的倒排索引实际上不如普通索引高效，原因有二：

2.4 索引更新性能优化数据

聊天记录优化前后的索引性能数据如下：