向量数据库？那咱们就浅谈一下吧

今年自己做了不少业余的 LLM demo/PoC 级的应用，前前后后使用了几种向量数据库（Vector Database），包括尚不能称之为向量数据库的 FAISS，玩票性质的 redisearch 和 pgvector，闭源的 SAAS 服务 pinecone，以及使用 Rust 构建的 qdrant 和 lancedb。这些向量数据库各有千秋，支持的索引技术不尽相同，但它们都试图解决传统数据库或者搜索引擎在搜索高维度信息时的力不从心的问题。

我们知道，传统的关系型数据库擅长结构化数据存储，支持复杂条件下的精确匹配，但在搜索信息上和搜索引擎类似，通过前缀树，倒排索引，N-gram 索引或者类似的机制找到包含特定标记的文档，然后使用一个评分算法（如 TF-IDF，BM25）对匹配的结果排序。这种搜索强于浅层的文本匹配，但无法理解同一文本在不同表达下的语义内容或者不同上下文下拥有的语境关系。此外，对于图形，声音这样的比文本更高维度的内容，传统的方式就完全无法处理了。要想高效地检索或者匹配这样的数据，我们就要想办法为它们找到一种更好地数学表达方式，这就要用到机器学习中大家耳熟能详的 embedding 了。

什么是 Embedding？

Embedding，通常在中文中被称为“嵌入”，主要用于将高维的数据（如语句、图片或其他类型的数据）转化为向量 [v1, v2, v3, ...]。这些向量可以捕获数据的语义信息或其他重要特征。换句话说，embedding 是一切信息通过某种算法得到的数学表达。

举个例子，我们知道，在我们的语言中，有大量的关于颜色的名词，就红色而言，就有砖红色，洋红色，铁红色，珊瑚红等。那么如何数字化地表述颜色呢？由于所有颜色可以通过红绿蓝三原色组成，自然而然，我们就可以构建一个三元组，或者说三维向量 —— 每一维代表一个原色 —— 来表达颜色。如果我们把这个向量赋以不同的值，并在三维坐标系上表达出来，就是下面这个样子：

（素材来源：https://huggingface.co/spaces/jphwang/colorful_vectors）

从这个图中，如果我们深入地探索某一个向量，我们可以发现，与之相邻的向量，其性状有相似之处：

如果我们将其用于相关性搜索，那么效果如何呢？下图展示了文本匹配和向量匹配的效果：

可以看出，向量化之后的匹配效果要更好一些。有同学可能会说，这差别也不大啊？别急，我们接着看。

颜色是语义非常单一的例子，它的向量表达也很简单，只有三维。那更复杂的文本或者图片该如何表达？以下是图片向量化的一个示例：

（来源：https://www.pinecone.io/learn/vector-embeddings/）

我们可以根据其灰度值构建一个矩阵，将此矩阵的值从左上到右下依次排列就能得到一个 N 维的向量来表述这张图片。然而它对图片的语义信息的维护还是非常浅薄的，如果图片进行了一些基本的变换（拉伸，缩小，移位），它就无法匹配到。因而，我们需要用更加复杂的 ML/DL 算法提取更加有意义的，可以最大程度在语义上还原这张图片的向量。这些向量往往是成百上千维的，对于我们这样的三维人来说，已经无法用空间坐标来可视化。当我们通过各种各样机器学习算法将信息转换成信息的数学表达，也就是 embedding 之后，我们就可以轻松地对信息进行聚类，检索，匹配等等：

回到之前对于「红色」，文本搜索和语义搜索的结果差别不大的问题。这是因为我们搜索的结果集非常小且语义非常集中，如果在大量和颜色不相关的语料中搜索，对于「红色」，文本匹配很可能会匹配出「安红额想你」这样完全不相干的结果。

好，在理解了 embedding 的概念后，让我们回答下一个问题，我们为什么需要向量数据库。

为什么需要向量数据库？

我们知道，embedding 是多维向量数据，通常以浮点数存储。虽然，传统数据库也可以用浮点数组来存储 embedding，但我们存储这些 embedding 的目的主要是为了高效地检索。通常情况下，我们需要在数百万甚至数百亿的向量中高效地找到与给定向量最相似的那些向量，同时，也需要高效地存储和管理海量的 embedding。这是传统数据库虽然能做，但是无法做到最优的原因。比如植根于 postgres 的 pgvector，虽然它提供了向量存储和索引，可以很方便地用 SQL 进行向量的相似性匹配，但其在处理大规模向量时依旧有很大的性能问题和存储开销。除了 pgvector，我还用过 redisearch，它在 embedding 数量仅仅在百万级规模时，就要花巨量的内存（> 16G），以及非常漫长的构建索引的时间（没有具体 benchmark，目测比 qdrant 慢了一到两个数量级）。

向量数据库是如何进行相似度查询的？

我们先把数据规模缩到最小，仅仅看如何确定两个向量的相似性。这里，最简单的方法是欧几里得距离，也就是两个向量在空间中的直线距离，有初中数学知识的人应该就可以理解这个算法。除此之外，我们还可以用余弦相似度（Cosine Similarity），点积（Dot Product）等方式来进行相似度计算。下表是 ChatGPT 帮我罗列的一些算法：

对于少量的 embedding，比如几千到几十万这样的量级，我们可以用一门支持 SIMD 处理的高效语言（比如 Rust），辅以缓存机制，直接遍历计算即可，没必要引入向量数据库。但当 embedding 的数量很多时，我们就需要借助向量数据库来查询。此刻，暴力计算已经无法满足基本的延迟需求了。所以，我们需要引入多种索引方式来提升查询的效率，这是向量数据库所擅长的。以下是一些大家常用的索引技术和方法：

1. KD-Tree（K维树）：KD-Tree是一种用于多维空间的数据结构。在向量数据库中，KD-Tree对向量的各个维度进行划分，形成一种树状结构。每个节点都存储一个向量，并在某个维度上有一个分裂值，将数据空间分为两半。对于低维数据，KD-Tree查询效率高，占用的内存相对较少。然而，随着数据维度的增加，查询效率降低，受到“维度诅咒”的影响，不适合高维数据。

2. Ball Trees：Ball Trees使用“超球体”（或简称“球”）来对数据进行分区。每个节点的球内都包含数据点的子集，而子节点的球则进一步细分该空间。Ball Trees 适用于任何度量空间，特别是在高维空间中，效果可能优于KD-Tree。它的缺点是构建过程可能相对较慢，需要更多的内存。

3. Annoy（Approximate Nearest Neighbors Oh Yeah）：Annoy是一种为大型数据集创建持久性、静态、可查询的近似最近邻索引的方法。它通过构建多棵随机投影树实现。Annoy 提供了查询速度和精确度之间的良好平衡，适用于大型数据集。然而它是一个近似方法，可能不保证总是返回真正的最近邻。

4. Product Quantization (PQ)：PQ将大向量空间分解为更小的子空间，并为这些子空间的每一个独立地学习一组有限的“代码簿”。向量被编码为这些子空间中最近的代码簿条目的索引。PQ 极大地压缩了原始向量，从而实现了存储和查询的高效率。但凡事都有双面性，由于是有损压缩，PQ 可能会损失一些精确度。

5. HNSW（Hierarchical Navigable Small World）：HNSW利用图结构，其中每个节点都是数据中的一个向量，通过一系列层次来确保快速访问。每一层都是原始数据的一个子集，上层的数据点数量比下层少。HNSW 提供了查询速度和精确度之间的良好平衡，适用于大型和高维数据集。但它需要更多的内存，构建索引的过程可能较慢。

我们以在大多数使用场景下（比如推荐系统，图像搜索）效果很好，也是绝大多数向量数据库都会实现的 HNSW 为例，详细介绍一下向量数据库中的索引是如何工作的。

HNSW 是如何工作的？

HNSW 算法是由 Yu. A. Malkov 和 D. A. Yashunin 提出的。他们在2016年发表了一篇名为“Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs”的论文（https://arxiv.org/pdf/1603.09320.pdf），详细描述了这种方法。这种方法旨在解决在高维空间中进行近似最近邻搜索的问题，这是机器学习、数据挖掘和相关领域中的常见问题。HNSW 提供了一个既高效又准确的解决方案，特别是对于非常大的数据集。

HNSW 的主要思想是构建这样一个图，其中任何一对顶点之间的路径都可以通过少量步骤遍历。它的思想跟六次握手规则（人与人之间的社会关系距离不超过6个）有异曲同工之妙。因此，HNSW 把向量划分到不同的层中，最高层有最少的向量，最底层有完整的向量，层与层之间的关系类似于跳表。而每一层中的向量，可以通过 NSW 算法构建成一个图，然后我们就可以使用贪婪算法找到这个图中里和目标向量最接近的向量。直接介绍 HNSW 可能难以理解，我们把这两个过程分开来看。

首先我们看对应 HNSW 中 Hierarchical 对应的算法：跳表。对于跳表是如何工作的，相信大家都非常熟悉，这里就不详细展开。下图是在跳表中查找元素20 的过程，可以看到，从高层到低层的查询过程可以大大减少遍历次数，达到 O(logn) 的效率：

接下来我们看 NSW。如果我们要找到图中某个点最相近的点，我们可以在图中任选一点，通过贪心算法不断移动到离目标相对最近的点，直至无法移动到更好的节点。如下图：

一开始，我们选择 A 作为入口点。它有两个邻居 B 和 D。节点 D 比 B 更接近查询。因此，我们移动到 D。节点 D 有三个邻居 C、E 和 F。E 是距离查询最近的邻居，因此我们移动到 E。最后，搜索过程将一步步移动到节点 L。由于 L 的所有邻居都比 L 本身距离查询更远，因此我们停止算法并返回 L 作为查询的答案。

这种算法的弊端是有可能在达到局部最优解时就提前停止。我们可以通过使用多个入口点来提高搜索的准确性。

好，理解了这两种算法后，我们将其组合，看看 HNSW 是如何运作的。我们以下图为例：

黑色的向量是我们要寻找的目标，我们想知道，离它最近的向量都有哪些。我们从最高层，也就是 layer 2 开始，任选一个入口点，然后找到该层对应的，离目标向量最近的向量。就像跳表一样，通常我们可以很快缩小查询的范围，然后进入到下一层，此时入口点就是上一层最接近的点，然后我们继续同样的动作，直至最下面一层。

在 HNSW 中插入也是类似的方法，只不过我们需要随机确定这个点出现的最大层 l。比如下图，新插入的点的 l = 2，也就是说它只会出现在 0，1，2 三层中，不会出现在更上面的位置。于查询过程同样，我们从最上层一步步往下找，找到第 2 层中离插入点最近的点，然后选择 M 个点构建邻居关系，然后在第 1 层和第 0 层依葫芦画瓢：

好，现在大家对 HNSW 是如何高效构建和查询就有了一个比较直观的认知。这个小节中的图片来自文章：https://towardsdatascience.com/similarity-search-part-4-hierarchical-navigable-small-world-hnsw-2aad4fe87d37，大家可以在那篇文章中解到 HNSW 算法更详细的介绍。

向量数据库都有哪些使用场景？

了解了向量数据库核心的索引是如何运作之后，我们来看看向量数据库的主要使用场景。从上面的介绍我们可以看到，凡是需要进行信息的相似度查询的地方，我们都可以使用向量数据库进行高效地查询。以下是一些典型的使用场景：

1. 图像搜索和检索：当每张图像都通过特定的深度学习模型（如CNN）转化为高维向量后，向量数据库可以帮助快速找到与查询图像内容相似的其他图像。
2. 视频检索：与图像检索类似，视频片段或帧也可以转化为向量，并在数据库中进行高效查询。
3. 音频和语音搜索：音频片段或语音可以转化为高维向量，然后在数据库中查找相似的音频或语音。
4. 知识图谱和语义搜索：实体和关系可以转化为向量形式，并在知识图谱中进行语义查询。
5. 推荐系统：用户和商品都可以通过其属性或行为转化为高维向量。然后，通过查找最近的向量来实现个性化推荐。
6. 自然语言处理 (NLP)：文本、单词或短语经过词嵌入或BERT等模型转化为向量后，可以在向量数据库中查找语义上相近的文本或词汇。
7. 生物信息学与化学：各种生物序列、化学物质和药物分子等可以被转化为向量，并在数据库中进行相似性查询。
8. 异常检测：在高维数据中，向量数据库可以帮助快速找到与正常数据点偏差较大的异常数据点。
9. 3D 模型和形状搜索：3D模型可以转化为高维向量形式，并在数据库中进行相似形状的查询。
10. 医学影像分析：例如MRI、CT扫描等医学影像可以转化为向量，并在数据库中进行疾病模式匹配。

我们来着重看一下语义搜索（Semantic Search）这个场景。在我今年4月份发于 B 站的系列视频：用 ChatGPT 构建数据库助手 中，我展示了如何使用 langChain + FAISS + OpenAI embedding 构建一个简单的 SQL 助手。所有这一类问题都可以用以下的架构来完成：

这里，和向量数据库有关的主要是如何把文本信息转换成 embedding，这样才能很好地存储和查询。如果你只是是一个应用开发者，那么 OpenAI 提供的 embedding 模型可以很好地帮你生成带有上下文感知的，富含语义信息的 embedding。虽然那个视频中我使用了 FAISS 简单地作为向量数据库，但在生产环境中，我们应该使用更完备的向量数据库。

如何选择合适的向量数据库？

选择合适的向量数据库需要考虑多个因素，因为不同的应用和场景可能对性能、可扩展性、持久性和其他功能有不同的需求。以下是在选择向量数据库时需要考虑的关键因素：

1. 数据规模与查询速度：如果您的应用中有大量的数据需要索引，那么需要一个能够有效处理大规模数据的数据库。此外，查询速度是另一个关键指标，特别是对于实时应用。
2. 搜索准确性：根据应用的需求，评估近似搜索的准确性。有些方法可能更快，但牺牲了一定的准确性。目前在我个人的使用中，我还没有发现在搜索准确性上，不同的向量数据库，如 qdrant，lancedb，redisearch 等有明显的区别。
3. 索引构建时间：有些向量数据库在处理大量数据时，其索引构建过程可能会很慢。根据应用的需求，评估这是否是一个关键因素。前文说过，在百万向量这个级别，我发现 redisearch 构建索引的速度就明显低于 qdrant 一个甚至多个量级。
4. 特性和功能：考虑其他功能，如数据更新、删除，重建索引，过滤等。我发现，很多时候，对复杂的应用，传统数据库的过滤功能是一个很有用的特性，比如，你可以机遇向量相似性来搜索类似的商品，同时你想限制搜索结果仅仅显示价格在特定区间并且有库存的商品。在我实验过的几个数据库中，貌似 qdrant 对 filter 支持地最好。
5. 开发和社区支持：选择一个有活跃社区和良好文档的数据库可以节省大量的开发时间，并在遇到问题时获得帮助。我个人一般会避开非开源的或者 license 不友好的向量数据库，因此，我仅仅对 pinecone 做了小量实验后，就换用了其他的向量数据库。
6. 灵活性与定制性：根据您的需求，评估数据库是否允许定制索引和查询策略，是否容易二次开发。因为我个人偏好 Rust，所以我也特别偏好于用 Rust 撰写的 qdrant 和 lancedb。它们都提供了 Rust SDK/API，并且在我需要的时候，我可以修改其源码来满足我的特定需求。
7. 集成与兼容性：考虑如何将数据库集成到现有的技术堆栈中。它是否支持您喜欢的编程语言？是否有REST API，GRPC 或其他方式与现有系统集成？由于目前向量数据库的主要使用场景还是跟 AI/ML 强相关，所以大多数向量数据库都会优先提供 python 的 SDK。对于其他语言的开发者而言，可能只能自己撰写或者依赖第三方提供的 SDK。
8. 成本：评估总体成本，包括服务器、存储和开发时间。在这个层面，我觉得 lancedb 很有前途，它是目前唯一可用的支持无服务器部署的向量数据库 —— 也就是说，你可以将 lancedb 嵌入到你的应用程序中，甚至访问 s3 来获取数据。lancedb 官网上有一篇关于使用 aws lambda function 访问 s3 上的 db 进行语义搜索的例子，我没有亲测，但从 lancedb 的 dataset layout 上来看，这是可行的，唯一的不确定性在于延迟有多大。但无论如何，如果你的整个技术栈放在无服务器上，又要提供语义搜索能力，lancedb 是目前最好的选择。我个人认为无服务器将会是数据库的一个重大方向，很开心看到 neon 在无服务关系新数据库上的崛起；同样的，我也希望 lancedb 能在无服务向量数据库上打下一片天地。

好吧，就讲这么多，娃又嫌我在电脑前坐得时间太长了。