WheatField
WheatField

iBookmark 检索速度提升

October 28, 20241265 words, 7 min read
Authors

在之前的一篇博客《使用 upstash + supabase 做一个 AI 书签管理器》中,我介绍了怎么用 upstashsupabase 做一个 AI 书签管理器,整个架构如下:

使用下来体验还不错,通常情况下,组合几个关键词就能搜到想要的内容。但也有几个问题,UI 的问题就先不说了,作为一名艺术细胞缺失的程序员,讨论 UI 就有点自不量力了。

功能上有两个核心问题,1) 召回结果相关性,2) 召回速度问题。

相关性很依赖于向量模型,目前使用的是 BAAI/bge-m3,效果多数情况下还不错,但有时候也有点拉跨,比如一条关于 索尼相机 的推文跟很多 query 的相似度都在 0.75 左右,迷一样的文本。

但相关性现在还不是大问题,毕竟条目还不多,只有几百条。召回后通过相似度排一下序,再通过人工调整好 query,基本上能找到想要的内容。

速度问题就比较大了,查询时最多只能说流畅,但远说不上丝滑。速度这里又分两个维度:

  1. 存储速度。
  2. 检索速度。

存储

一条内容的存储路径是:文本获取 -> 文本向量化 -> 存储。

其中前两步最耗时,尤其是文本获取。在前一篇博客中也提过,比较难搞的是获取推文内容,有时候还不得不使用 playwright 模拟浏览器环境,速度自然就慢下来了。但好在存储可以离线执行,用户(我自己)一般保存书签后也不会马上去看实时结果,只要别存掉,问题就不大。

几个推文读取 API

一个题外话,这两天意外发现了几个免费的 twitter API,专门用于获取推文内容:

  1. https://cdn.syndication.twimg.com/tweet-result?id=1808326779083579400&token=123
  2. https://react-tweet.vercel.app/api/tweet/1849799664125739303,react-tweet 项目对上述 API 的封装。
  3. https://r.jina.ai/twitter_url,Jina AI 提供的 API,除了推特,也支持其他平台内容获取。

检索

查询时,快的要 1s,慢的要好几秒,取决于网速及 upstash 的后台查询速度。

为了加速检索,目前上了一个笨办法,通过 upstash redis 对查询进行缓存,也就是通过精准匹配复用已经查询过的结果,从而减少相似度计算。 已缓存的 query 速度提升明显,但局限性也很大。一是覆盖面比较窄,二是相似 query 的缓存利用率很低,比如 iPhone 16 价格iPhone 16 多少钱 是两个不同的 queries,但完全可以复用相同的结果。

稍微智能一点的方法可以通过模糊匹配或者相似度查询相似 queries,然后再返回缓存结果。 但这样无疑又增加了复杂度和成本,时间上也多了一层开销。

倒排索引 + query 相似度查询

还一个空间换时间的思路是,先从文本着手,对文本进行 query 提取,比如让 LLM 生成一些可能的 queries,然后把 queries 和文本的映射关系存储下来。后续查询时,可参考上面提到的办法,通过相似 query 的缓存结果来加速检索。

形式化地,给定 query qq,先从 queries 数据库中找出相似的 queries qq',然后将所有与 qq' 关联的文本作为候选集,即:

C(q)={tqTqQ,sim(q,q)ϵ} C(q) = \{t_{q'} \in T \mid q' \in \mathcal{Q}, \text{sim}(q, q') \geq \epsilon\}

然后对候选集进行重排序并取 top-k:

R(q)=topk(rerank(C(q)),k) R(q) = \text{topk}(\text{rerank}(C(q)), k)

其中 ϵ\epsilon 是相似度阈值(e.g., 0.95),Q\mathcal{Q} 是 queries 数据库,kk 是返回结果的数量 (e.g., 10),rerank()\text{rerank}(\cdot) 是重排序函数。

有用吗?

这里面有两个小问题:

  • Q1. 在时间开销上, 两步法是否真的比一步到位法省时?
  • Q2. 你说的 rerank 到底是什么样的 rerank?

QQ' 表示提前生成的可能的 queries 集合,simϵ(q,Q)\text{sim}_\epsilon(q, Q') 表示从 QQ' 中选出与 qq 相似度大于 ϵ\epsilon 的 queries。如果

T(simϵ(q,Q))T(simϵ(q,T))(EQ-3)T(\text{sim}_\epsilon(q, Q')) \ll T(\text{sim}_\epsilon(q', T)) \tag{EQ-3}

那确实可以加速检索。因此,针对问题 Q2,rerank 这里可以有很多种实现方法,比如通过相似度打分:

score(q,t)tC(q)=sim(q,q)sim(q,t) \text{score}(q, t)_{t \in C(q)} = \text{sim}(q, q') \cdot \text{sim}(q', t)

其中 sim(q,t)\text{sim}(q', t) 可以提前预先计算并存储。

回头再审视前面的时间假设 (EQ-3),如果采用向量化再用近似最近邻搜索(ANN - HNSW)的方法,那只看查询的时间,复杂度是

O(n2d)+O(logm) O(n^2 \cdot d) + O(\log m)

其中 nn 是文本 (query) 长度,dd 是向量维度,mm 是候选集大小,一步到位和两步法在这一点是没区别的。但相关性查询这点,可以考虑采用更朴素的方法,比如 TF-IDF 或者 BM25。因此,对于问题 Q1,答案是:两步法在查询时间上可以做到比一步到位法更省时,但可能省不了太多,而且效果上会打折扣。