milvus

文本嵌入

文本嵌入模型主要用于计算文本的向量表示，这里的向量指的就是数学向量，也叫特征向量

通过文本嵌入模型，可以计算文本的特征向量，然后通过向量的相似度计算，可以找出特征相似的文本内容。

向量搜索&基于关键词搜索的区别

• 向量搜索是基于词向量的语义相似性进行的,它可以找到与查询语义上相关的结果,即使查询词和结果中的词不完全匹配。向量搜索会把词映射到一个高维向量空间,计算向量之间的相似性。这样即使词本身不匹配,只要语义上相似,也能找到相关的结果。
• 基于关键词的搜索是简单的字符串匹配。它只会返回包含完全匹配查询词的结果。如果文档使用了不同的词语,即使语义相似,也不会被匹配到。

架构

https://milvus.io/docs/architecture_overview.md

Milvus 建立在 Faiss、Annoy、HNSW 等流行的矢量搜索库之上，旨在对包含数百万、数十亿甚至数万亿矢量的密集矢量数据集进行相似性搜索。

Milvus 还支持数据分片、数据持久化、流式数据摄取、向量和标量数据之间的混合搜索、时间旅行等许多高级功能。该平台提供按需性能，并且可以进行优化以适应任何嵌入检索场景。我们建议使用 Kubernetes 部署 Milvus，以获得最佳可用性和弹性。

Milvus 采用共享存储架构，存储和计算分离，计算节点可水平扩展。Milvus 遵循数据平面和控制平面分解的原则，包括四层：接入层、协调器服务、工作节点和存储。在扩展或灾难恢复方面，这些层是相互独立的。

接入层

访问层由一组无状态代理组成，是系统的前端层和用户的端点。它验证客户端请求并减少返回结果

协调员服务

协调器服务将任务分配给工作节点并充当系统的大脑。它承担的任务包括集群拓扑管理、负载均衡、时间戳生成、数据声明和数据管理。

协调器类型有四种：根协调器（root coord）、数据协调器（data coord）、查询协调器（query coord）和索引协调器（index coord）。

• 根协调器：根坐标处理数据定义语言 (DDL) 和数据控制语言 (DCL) 请求，例如创建或删除集合、分区或索引，以及管理 TSO（时间戳 Oracle）和时间自动收录器发布。
• 查询协调器： 查询坐标管理查询节点的拓扑和负载平衡，以及从增长段到密封段的切换。
• 数据协调员：数据协调管理数据节点的拓扑，维护元数据，并触发刷新、压缩等后台数据操作。
• 索引协调器：索引坐标管理索引节点的拓扑、构建索引并维护索引元数据。

工作节点

它们遵循协调器服务的指令并执行来自代理的数据操作语言 (DML) 命令。由于存储和计算分离，工作节点是无状态的，部署在 Kubenetes 上可以促进系统横向扩展和灾难恢复。工作节点分为三种类型

• 查询节点：查询节点检索增量日志数据，并通过订阅日志代理将其转换为不断增长的段，从对象存储加载历史数据，并在向量和标量数据之间运行混合搜索。
• 数据节点：数据节点通过订阅日志代理来获取增量日志数据，处理变异请求，并将日志数据打包成日志快照并存储在对象存储中。
• 索引节点：索引节点构建索引。索引节点不需要常驻内存，可以通过Serverless框架来实现。

贮存

存储是系统的骨骼，负责数据的持久化。它包括元存储、日志代理和对象存储。

• 元存储:

  元存储存储元数据的快照，例如集合架构、节点状态和消息消费检查点。存储元数据需要极高的可用性、强一致性和事务支持，因此 Milvus 选择了 etcd 进行元存储。Milvus 还使用 etcd 进行服务注册和健康检查。

• 对象存储

  对象存储存储日志的快照文件、标量和向量数据的索引文件以及中间查询结果。Milvus 使用 MinIO 作为对象存储，可以轻松部署在 AWS S3 和 Azure Blob 这两种全球最受欢迎、最具成本效益的存储服务上。但对象存储的访问延迟较高，且按查询次数收费。为了提高性能并降低成本，Milvus 计划在基于内存或 SSD 的缓存池上实现冷热数据分离。

• 日志经纪人

  日志代理是一个支持回放的发布-订阅系统。它负责流数据持久化、执行可靠的异步查询、事件通知以及查询结果的返回。当工作节点从系统故障中恢复时，它还能确保增量数据的完整性。Milvus 集群使用 Pulsar 作为日志代理；Milvus 独立版使用 RocksDB 作为日志代理。此外，日志代理可以很容易地替换为Kafka和Pravega等流数据存储平台。

数据插入

Milvus 中的每个集合指定多个分片，每个分片对应一个虚拟通道（vchannel）。如下图所示，Milvus 为日志代理中的每个 vchannel 分配一个物理通道（pchannel）。任何传入的插入/删除请求都会根据主键的哈希值路由到分片。

由于 Milvus 没有复杂的事务，DML 请求的验证被前移到代理。代理将从 TSO（时间戳 Oracle）请求每个插入/删除请求的时间戳，TSO 是与根协调器并置的计时模块。随着旧时间戳被新时间戳覆盖，时间戳用于确定正在处理的数据请求的顺序。代理从数据坐标中批量检索信息，包括实体的段和主键，以提高整体吞吐量并避免中央节点负担过重。

DML（数据操作语言）操作和DDL（数据定义语言）操作都会写入日志序列，但DDL操作由于出现频率较低，只分配一个通道。

Vchannels在底层日志代理节点中维护。每个通道在物理上都是不可分割的，并且可供任何节点使用，但只能用于一个节点。当数据摄取速率达到瓶颈时，需要考虑两件事：日志代理节点是否过载并需要扩展，以及是否有足够的分片来保证每个节点的负载平衡。

上图封装了日志序列写入过程中涉及的四个组件：代理、日志代理、数据节点和对象存储。该过程涉及四个任务：DML请求的验证、日志序列的发布订阅、流式日志到日志快照的转换以及日志快照的持久化。这四个任务彼此解耦，以确保每个任务都由其相应的节点类型处理。同一类型的节点是平等的，可以独立弹性伸缩，以适应各种数据负载，特别是海量且高波动的流数据。

HNSW

参考

• 数据库内核杂谈（三十六）- 向量数据库（4）quantization 和 HNSW
• 数据库内核杂谈（三十四）- 向量数据库（2）深入浅出聊存储
• 数据库内核杂谈（三十五）- 向量数据库（3）Inverted File Index 和 Locality Sensitive Hashing

Hierarchical Navigable Small Worlds

HNSW 在查询速度和准确度上有非常好的平衡，也因此成为最受欢迎的 vector search 的算法。要学习 HNSW，需要先熟悉两个概念，skip-list（跳表）和 Navigable Small Worlds (NSW)。

Skip-List（跳表）

Skip List–跳表

先在索引找 1、4、7、9，遍历到一级索引的 9 时，发现 9 的后继节点是 13，比 10 大，于是不往后找了，而是通过 9 找到原始链表的 9，然后再往后遍历找到了我们要找的 10，遍历结束。有没有发现，加了一级索引后，查找路径：1、4、7、9、10，查找节点需要遍历的元素相对少了，我们不需要对 10 之前的所有数据都遍历，查找的效率提升了。

那如果加二级索引呢？这就是跳表的思想，用“空间换时间”，通过给链表建立索引，提高了查找的效率。

当数据量足够大时，效率提升会很大。使得链表能够实现二分查找。由此可以看出，当元素数量较多时，索引提高的效率比较大，近似于二分查找。跳表是可以实现二分查找的有序链表。

假如一直往原始列表中添加数据，但是不更新索引，就可能出现两个索引节点之间数据非常多的情况，极端情况，跳表退化为单链表，从而使得查找效率从 O(logn) 退化为 O(n)。

我们在原始链表中随机的选 n/2 个元素做为一级索引是不是也能通过索引提高查找的效率呢？当原始链表中元素数量足够大，且抽取足够随机的话，我们得到的索引是均匀的。

所以，我们可以维护一个这样的索引：随机选 n/2 个元素做为一级索引、随机选 n/4 个元素做为二级索引、随机选 n/8 个元素做为三级索引，依次类推，一直到最顶层索引。这里每层索引的元素个数已经确定，且每层索引元素选取的足够随机，所以可以通过索引来提升跳表的查找效率。

Navigable Small World

首先想象一个网络，网络上有许多节点，这些节点有些相互联通。每个节点会和联通的节点有短距离、中距离或者长距离的连接。

在执行搜索时，我们将从某个预先设定的的入口点开始搜索。从那里，我们通过比较搜索点和这个点以及其联通的点的距离，并跳转到距离搜索点节点最近的节点。这个过程重复，直到我们找到最近的邻居。这种搜索称为贪心搜索。这个算法适用于数百或数千个节点的小型 NSW，但对于更大的 NSW 则效率比较低。一个优化方法是通过增加每个节点的短距离、中距离和长距离连接的节点的数量，但这会增加网络的整体复杂性，并导致搜索时间变长。

将向量数据集中的所有向量想象成 NSW 中的点，长距离连接的点表示彼此不相似的两个向量，短距离连接的点则相反，表示两个近似的向量。通过这种方式，将整个数据集向量构建成 NSW，我们可以通过贪婪算法遍历 NSW，朝着越来越接近搜索向量的顶点方向移动，完成近邻搜索。

HNSW 的查询和构建

诞生了结合跳表和 NSW 的 HNSW：与跳表一样，HNSW 是一个多层级的数据结构，每层不是链表，而是由 NSW 构成

HNSW 图的最上层有很少的节点，且节点间的距离都很长。而最底层则包括所有节点和最短的链接。搜索过程如下：给定一个查询向量，我们先进入最上层的一个预定义的搜索起点，并通过贪婪算法朝着与我们的查询向量最近的邻居方向前进。一旦到达最近的节点，我们就在第二层重复此过程。这个过程一直持续到最底层，直到我们找到最近的邻居节点，搜索结束。

HNSW 的另一个优势，区别于我们已经学习过的其他向量存储方式，就是更高效地支持插入新的向量。插入操作和跳表的插入操作类似。对于某个向量 v，我们先通过搜索算法，找到这个向量在最底层的位置：

• 首先遍历图的第一层，找到它的最近邻居，然后移到其下方的层次；然后，再次遍历图，以在第二层找到它的最近邻居；这个过程一直持续，直到在最底层的图中找到最近的邻居。
• 第二步，需要确定向量 v 和哪些现有节点建立连接（顶点之间的连接）。通常会设定一个预定义的参数 M，它决定了我们可以添加的双向链接的最大数量。这些链接通常设置为 v 的最近邻居。与跳表一样，查询向量在上层出现的概率呈指数递减，可以试用一个随机函数来判断是否要创建上层的节点。

算法参数

相同数量级的数据集，维度越大，RAM占用越大，搜索时间越长。

• M在构造过程中为每个新元素创建的双向链接的数量。（在建表期间每个向量的边数目）

  M的合理范围在[2,200]。M越高，对于本身具有高维特征的数据集来讲，recall可能越高，性能越好；M越低，对于本身具有低维特征的数据集来讲，性能越好。

  建议M：12，16，32。因为特征已经选择过了，维度一般不会太高。

• efConstruction最近邻居的动态列表的大小（在搜索期间使用）。

  efConstruction 越大，构造时间越长，index quality越好。有时，efConstruction 增加的过快并不能提升index quality。有一种方法可以检查efConstruction 的选择是否可以接受。计算recall，当ef=efConstruction ，在M值时，如果recall低于0.9，那么可以适当增加efConstruction 的数值。

优化

• 分段创建几个索引库，同时搜索，取距离值最小的作为最终的结果。
• 加入了pca降维。主要原因是数据集很大，搜索时间过长，加上精度不理想（不相似的与相似的区分不开）。将特征从1280降到了128。

对比其他

Pinecone

https://www.pinecone.io/

完全托管，不能私有化部署，不考虑

Vespa

https://python.langchain.com/docs/integrations/providers/vespa

https://vespa.ai/

距离度量总结

9个数据科学中常见距离度量总结以及优缺点概述

欧氏距离 Euclidean Distance

从最常见的距离度量开始，即欧几里得距离。最好将距离量度解释为连接两个点的线段的长度。

尽管这是一种常用的距离度量，但欧几里德距离并不是比例不变的，这意味着所计算的距离可能会根据要素的单位而发生偏斜。通常，在使用此距离度量之前，需要对数据进行标准化。

缺点

此外，随着数据维数的增加，欧氏距离的用处也就越小。这与维数的诅咒有关，维数的诅咒与高维空间不能像期望的二维或3维空间那样起作用。

优点

您拥有低维数据并且向量的大小非常重要时，欧几里得距离的效果非常好。

余弦相似度 Cosine Similarity

余弦相似度经常被用作解决高维数欧几里德距离问题的方法。余弦相似度就是两个向量夹角的余弦。如果将向量归一化为长度均为1，则向量的内积也相同。

缺点：

余弦相似度的一个主要缺点是没有考虑向量的大小，而只考虑它们的方向

优点：

当我们对拥有的高维数据向量的大小不关注时，通常会使用余弦相似度。对于文本分析，当数据由字数表示时，此度量非常常用。例如，当一个单词在一个文档中比另一个单词更频繁出现时，这并不一定意味着一个文档与该单词更相关。可能是文件长度不均匀，计数的重要性不太重要。然后，我们最好使用忽略幅度的余弦相似度。

汉明距离 Hamming Distance

汉明距离是两个向量之间不同值的个数。它通常用于比较两个相同长度的二进制字符串。它还可以用于字符串，通过计算不同字符的数量来比较它们之间的相似程度。

缺点

当两个向量的长度不相等时，很难使用汉明距离。为了了解哪些位置不匹配，您可能希望比较相同长度的向量。此外，只要它们不同或相等，就不会考虑实际值。因此，当幅度是重要指标时，建议不要使用此距离指标。

优点

典型的用例包括数据通过计算机网络传输时的错误纠正/检测。它可以用来确定二进制字中失真的数目，作为估计误差的一种方法。

曼哈顿距离 Manhattan Distance

曼哈顿距离，通常称为出租车距离或城市街区距离，计算实值向量之间的距离。想象描述均匀网格(如棋盘)上物体的向量。曼哈顿距离是指两个矢量之间的距离，如果它们只能移动直角。在计算距离时不涉及对角线移动。

缺点

曼哈顿距离在高维数据中似乎可以工作，但它比欧几里得距离更不直观，尤其是在高维数据中使用时。

优点

当数据集具有离散和/或二进制属性时，Manhattan似乎工作得很好，因为它考虑了在这些属性的值中实际可以采用的路径。以欧几里得距离为例，它会在两个向量之间形成一条直线，但实际上这是不可能的。

切比雪夫距离 Chebyshev Distance

切比雪夫距离定义为两个向量在任意坐标维度上的最大差值。换句话说，它就是沿着一个轴的最大距离。由于其本质，它通常被称为棋盘距离，因为国际象棋的国王从一个方格到另一个方格的最小步数等于切比雪夫距离。

缺点

这使得它很难像欧氏距离或余弦相似度那样作通用的距离度量，因此，建议您只在绝对确定它适合您的用例时才使用它。

优点

切比雪夫距离可用于提取从一个正方形移动到另一个正方形所需的最小移动次数。此外，在允许无限制八向移动的游戏中，这可能是有用的方法。切比雪夫距离经常用于仓库物流，因为它非常类似于起重机移动一个物体的时间。