跳转到内容
Jason's Study

Annoy — Spotify 的随机森林近似最近邻索引

是什么

Annoy（Approximate Nearest Neighbors Oh Yeah）是 Spotify 工程师 Erik Bernhardsson 在 2013 年写的近似最近邻库。C++ 内核 + Python 绑定，专门解决”我有几千万条向量，怎么快速找出和查询向量最像的 50 个”。

日常类比：你想在一座有 5000 万本书的图书馆找”最像这本”的书。逐本比对要好几天。Annoy 的做法是先按随机方向把书房一刀切两半（“放音乐类那侧 / 放小说类那侧”），递归切到每个角落只剩 30 本左右。这样一棵树就建好了。再多建 50 棵切法不同的树，每次查询时让 50 棵树并行投票给候选书，最后只精确比对这些候选。

这就是”随机投影森林”——Annoy 的全部本质。

为什么重要

不理解 Annoy（或它代表的 ANN 思路），下面这些事都没法解释：

  • 为什么 Spotify / Netflix 给你推歌、推剧能在 100 毫秒内从几千万候选里挑出来
  • 为什么”向量相似度搜索”在 LLM 时代成了 RAG / 推荐 / 搜索的底层基建
  • 为什么生产环境的 ANN 库总在”召回率 / 延迟 / 内存”三角里挣扎
  • 为什么 Annoy 在 HNSW / FAISS 兴起后还有人用——它有一个别人很难复制的特性：mmap 友好

核心要点

Annoy 的工作流可以拆成 三步：

  1. 建一棵随机投影树：在每个节点上随机挑两个点，用它们的中垂面（垂直平分面）把数据切成两半。递归切到节点里只剩 ≤ K 个点（K 默认约 30）就停。

  2. 建一片森林：树切得”准不准”取决于运气——一棵树可能恰好把两个相似点切到不同侧。所以多建几十到几百棵，让随机性互相抵消。每棵独立、可并行建。

  3. 查询时多树合并：拿查询向量从每棵树往下走，把走到的叶子节点候选合到一起，再对这些候选精确算距离取 top-k。候选取多少由参数 search_k 控制——越大越准、越慢。

加上一个工程关键点：整片森林序列化成单个文件，用 mmap 加载。多个进程零拷贝共享同一份索引，索引比 RAM 大也能跑（操作系统按需调页）。这是 Spotify 上线时的核心考量。

直觉对照：

  • k-d 树按坐标轴对齐方向切（“x 轴上 < 50 / >= 50”），高维下退化
  • Annoy 树按随机方向切（任意方向的超平面），对维度灾难鲁棒得多
  • HNSW 图根本不切空间，建一张可导航的多层图

切空间的难题是高维下”对的切法”几乎肯定切错——Annoy 干脆放弃找最优切法，靠多次随机 + 投票逼近。

实践案例

案例 1：30 行 Python 跑通

from annoy import AnnoyIndex
import random


f = 40  # 向量维度
t = AnnoyIndex(f, 'angular')  # 五种距离之一
for i in range(1000):
    v = [random.gauss(0, 1) for _ in range(f)]
    t.add_item(i, v)


t.build(10)         # 建 10 棵树
t.save('test.ann')  # 序列化到磁盘


# 后续进程加载（mmap，不读完整文件）
u = AnnoyIndex(f, 'angular')
u.load('test.ann')
print(u.get_nns_by_item(0, 5))  # 跟 0 号最像的 5 个

注意：build() 之后不能再 add_item——Annoy 是只读索引。要加数据必须重建。

案例 2：search_k 怎么选

# 默认 search_k = n_trees * n（n 是想要的近邻数）
t.get_nns_by_item(0, 100)                # 默认
t.get_nns_by_item(0, 100, search_k=10000)  # 更准更慢

经验法则：召回率不够先调大 search_k，调到延迟到极限再加 n_trees。先调查询时参数、再调建索引参数——这点跟很多 ANN 库通用。

案例 3：Spotify 实际怎么用

Spotify 给每首歌训出一个嵌入向量（早期是协同过滤 + 深度模型）。几千万首歌 = 几千万个 200 维向量。线上推荐时拿用户最近听的歌的向量，调 get_nns_by_vector 查最像的几百首做候选，再交给排序模型挑 30 首。

mmap 在这里的价值：几十个 worker 进程共享一份索引，每个不用各自加载几 GB。

踩过的坑

  1. 建好后不能加点。要加新向量必须从头重建，Spotify 通常每天离线重建一次。如果业务需要”实时加向量”，Annoy 不合适，得用 HNSW。

  2. 维度太高效果掉。随机投影在 50–200 维表现好，超过 500 维树的切分越来越不准，召回率跌得快。高维场景该用 PQ 量化或 HNSW。

  3. angular 距离不是余弦相似度本身。Annoy 内部用的是 sqrt(2 - 2*cos(θ))，是余弦距离的单调变换，排序结果一致但数值不一样。看到”距离 1.4”不要以为很差。

  4. n_trees 和 search_k 解耦不彻底。理论上前者管建索引、后者管查询，但树越多每次查询遍历的节点也越多，不是免费的。

  5. 多进程 fork 后 mmap 会退化。一些 Web 框架 fork 后 mmap 区域可能被复制，反而吃更多内存。生产建议用 prefork 或显式共享。

适用 vs 不适用场景

适用：

  • 静态/准静态向量集（每天/每小时重建一次能接受）
  • 索引比 RAM 大、需要靠 mmap 调页
  • 多进程共享一份索引（Web 服务、推荐召回）
  • 中等维度（50–300）、千万到亿级向量

不适用：

  • 实时增删向量 → 用 HNSWlib / FAISS IVF
  • 极高维（>500） → 用带量化的方案（FAISS PQ / ScaNN）
  • 超大规模（10 亿 +） → FAISS GPU / ScaNN
  • 要求最高召回率 → HNSW 通常领先

历史小故事（可跳过）

  • 2013 年：Erik Bernhardsson 在 Spotify 做音乐推荐，需要一个能在内存受限机器上跑、且能多进程共享的 ANN 库。当时没有满意方案，他自己写了 Annoy，开源到 GitHub。
  • 2015 年：博客《Nearest Neighbors and Vector Models》系列爆火，Annoy 成为 Python ANN 生态事实标准。
  • 2017–2018 年：Erik 自己开了 ann-benchmarks 项目，定期跑各家 ANN 库的对比。HNSW 系列在召回-延迟图上稳定领先。
  • 2018+：HNSWlib / FAISS 在性能上压过 Annoy，但 Annoy 的 mmap + 极简 API 在”召回服务”场景仍有不可替代的位置。

参数调优一张表

想要调什么代价
召回率更高先调大 search_k（查询时）单次查询变慢
还要更高再加大 n_trees（建索引时）索引文件变大、建索引变慢
内存压力减小 n_trees，依赖 mmap 调页命中率下降时 IO 增多
索引文件太大用 on_disk_build，一边建一边写盘建索引更慢

调参顺序的核心心法：查询时参数优先于建索引参数——前者改一改马上看效果，后者改了要重建。

一行心智模型

“把一堆向量随机切成几十棵不同的树，查询时每棵树各推几个候选，合起来再精确比对——再用 mmap 让多进程零拷贝共享。”

这句话能讲清楚 Annoy 90% 的设计。剩下 10% 是工程细节（节点格式、内存对齐、距离公式优化）。

学到什么

  1. 随机性 + 多次重复 = 鲁棒近似——一棵树切错了不要紧，五十棵投票就稳了。这是工程上把”准确算法”换成”近似算法”的通用思路。
  2. 工程约束塑造算法选择——Annoy 不是最快也不是最准的，但 mmap 友好这一条让它在 Spotify 的多进程架构里赢了。算法没有”最好”，只有”最匹配约束的”。
  3. 不可变数据结构在生产更好用——只读索引让多进程共享、缓存预热、回滚都简单。要”既能加又能查”通常要付出复杂度代价。
  4. 召回率 / 延迟 / 内存 三角永远存在——任何 ANN 库都在这三者之间做权衡，理解它就能选库、调参不再蒙。

延伸阅读

关联

  • hnsw —— 分层小世界图，召回-延迟通常领先 Annoy
  • faiss —— 内核选择多、支持 GPU，但部署复杂度更高
  • bentley-1975-kdtree —— k-d 树，低维场景的精确最近邻；Annoy 是它在高维下的近似版本
  • ance-2020 —— 用近似最近邻做大规模检索训练
  • colbert-2020 —— 后期交互检索，候选召回阶段常用 ANN

反向链接

  • colbert-2020 —— ColBERT — 让 BERT 检索既准又能扛大规模
  • faiss —— FAISS — 向量检索的标准件库
  • hnswlib —— hnswlib — HNSW 论文作者写的参考实现，业界向量库都基于它