Spotify 开源 ANN 搜索库 Voyager，比 Annoy 快 10 倍

Spotify 最近开源了Voyager，一个近似最近邻（Approximate Nearest-Neighbor，ANN）搜索库。Voyager 基于Hierarchical Navigable Small Word（HNSW）算法，比 Spotify 之前的 ANN 库 Annoy 快 10 倍。

Spotify 使用 ANN 来支持其音乐推荐功能，比如 Discover Weekly。他们于 2013 年开发了 Annoy 来执行 ANN 搜索，但在 10 年后的当前规模下表现不佳。部分原因是由于底层算法：Annoy 使用树分区算法，而 Voyager 使用更新的 HNSW 算法。Voyager 比 Annoy 使用的内存少 4 倍，比 hnswlib（HNSW 的实现之一）少 16 倍。根据 Spotify 机器学习工程师和 Voyager 贡献者 Peter Sobot 所说：

Voyager 结合了 HNSW 更高的精度和速度，提供了经过充分测试、具有完善文档、可以在生产环境中使用的 Java 和 Python 绑定。Voyager 的理念是提供一个稳定、可靠、可在生产环境中使用的库，让任何人都可以在其应用中添加近似最近邻检索功能，无论使用的是 Python 还是 Java。

Spotify 的推荐功能首先通过机器学习算法计算歌曲或 音轨 的 Embedding。两个音轨在播放列表中频繁出现，它们在 Embedding 空间中就会被映射得越近。用户也根据他们所听的歌曲被映射到这个空间。为了推荐用户可能喜欢的歌曲，Spotify 使用 ANN 搜索来找到与用户在 Embedding 空间中位置接近的音轨。Spotify 还可以使用 ANN 进行歌曲去重：通过计算音频数据的 Embedding，ANN 可以识别具有基本相同音频的音轨。

像 Spotify 这样的规模，要快速执行这种搜索要困难得多：他们的嵌入向量有数千个维度，目录中包含了数百万音轨。Annoy 显然无法提供足够好的性能，于是 Spotify 的工程师们尝试使用现有的开源库 hnswlib，但"遇到了问题"。其核心代码存在 Spotify 工程师无法修复的错误。他们还希望拥有更简单的 API。这导致他们开发了 Voyager，该项目考虑到了 Spotify 的生产基础设施需求。

Voyager 的设计目标是快速和轻量级。其 API 针对 Java 和 Python 做了绑定，但库本身没有 Java 依赖，并且仅需要 Python 的 NumPy 库。该库可以在 Intel 和 ARM 芯片架构的机器（Linux 和 MacOS）和 Windows （Intel 芯片架构）上运行。

用户在 Hacker News 上将 Voyager 其与其前身 Annoy 进行了比较：

我看到的最大区别是，Annoy 使用只读索引文件（如文档所述："树一旦创建，就无法再添加更多的项"），而 Voyager 允许你随时调用.add_item。

Peter Sobot 在 Twitter 的某个关于 Voyager 的帖子中回答道：

我认为 Voyager 是一个可嵌入、超轻量、快速的向量搜索库。Voyager 没有向量数据库的花哨功能，但它没有依赖，并且只有大约 300KB。

Voyager 的源代码可以在 GitHub 上获取。Voyager 已经提交到 ANN-Benchmarks 页面，但尚未运行基准测试。

原文链接：

https://www.infoq.com/news/2023/11/spotify-ann-voyager/