在前文中，简单地梳理了一下ANN的一些发展，其中简单地提了一句Milvus这个产品。事实上，19年10月我刚进入阿里云ADB向量组实习的时候，Milvus刚刚开源出来，并且很快就成为一个很重要的竞争对手，但大部分时候如果以查询性能为主要评价指标的话，这些系统其实并没太大差别，因为底下使用的核心算法都是一样的。当ANN算法到了一个接近天花板的位置的时候，一个功能完备的系统也许是更重要的。
Milvus论文(Milvus: A Purpose-Built Vector Data Management System)发表在了SIGMOD2021上，虽然现在还没有出官方的版本，但是论文一作已经在其个人主页上放出了论文，正好可以提前拜读一下。想到阿里的ADBV和PASE之前也都发了数据库的顶会，说明趁着AI的热度，向量数据库的前景还是很好的。阿里的系统是将传统的数据库进行扩展，把向量作为一个属性加入进去，而Milvus是一个专业处理向量数据的系统，就像现在很多的处理某些数据的系统，比如图数据库，时间序列数据库等。下图展示了Milvus的优点，本文主要介绍的是它在异构计算平台上的优化和它所支持的复杂查询上的优势。
面向异构计算平台
基于CPU的优化
对于常见的IVF类的索引，其实一个不可避免的问题就是遍历向量去找最近的结果，当然这里的遍历肯定不是指的真正的全量的向量数据，而是比如去找邻近的聚类分区，或者在某个聚类分区下找topk结果。假设现在有m条query，记作\(q_1, q_2, ..., q_m\)，底库数据有n条向量，一般m远小于n。为了提高查询吞吐量，一般会做query间的并行，这很简单，但是对于不同query都需要访问全量数据，无法复用，会有很多cache miss，然后在m比较小的时候不能充分使用CPU。
Milvus做的优化是给一小批query打包成一个块，让他们可以复用要遍历的向量数据，为了达到比较好的cache命中率，每个query块的大小选择是根据L3 cache的大小来设置的。然后对向量数据做并行，而不是query级别的并行，因为向量数目n一般较大。
基于GPU和CPU异构平台的优化
GPU的显存是一个稀缺资源，每当数据量较大的时候，总会出现CPU和GPU之间的数据交换。Milvus提出了两种优化，一是充分使用PCIe的带宽，适当增大每次传输数据的量，第二点是根据query数量来决定是否要在GPU进行全部的计算，需要有较大的batch size才能在GPU上换来较大的收益，否则在GPU和CPU做一个任务的划分。
面向复杂的查询
Attribute-Filtering查询
这里的Attributed-Filtering也就是和结构化过滤条件相结合的融合查询，比如和该商品图片较相似的并且价格在某个区间的这类查询。阿里巴巴基于AnalyticDB做的高维向量解决方案ADBV系统研究了这个问题，Milvus基本把几种plan的方式都实现了，然后提出一个所谓"partition-based"的方案，但其实就是基于某个常用的结构化属性分区，对于用到这个属性且过滤效果好的话，那自然查询效率就上去了。但这个点个人认为实在不值得写上去，本身选择常用属性做分区就是一个很玄学的事情。
Multi-Vector查询
不过Milvus提出了一种新的查询，即多向量查询。考虑到某些时候需要多个向量来描述一个人，比如正面照，侧面照等。假设一个实例包含\(μ\)个向量，\(v_0, v_1, ..., v_{μ-1}\)，相似度函数为\(f\)，聚合函数\(g\)（一般为加权求和，用于多个相似度的聚合），则实例\(X\)和\(Y\)的相识度可以被描述为\(g(f(X.v_0, Y.v_0), ..., f(X.v_{μ-1}, Y.v_{μ-1}))\)。下面给出两种方法。
Vector fusion。假设相似度函数为点积，假设把实例\(e\)参与到相似度计算的向量合并成一个向量\([e.v_0, e.v_1, ..., e.v_{μ-1}]\)，若聚合函数为加权和，则聚合后的query向量可以表示为\([w_0 q.v_0, w_1 q.v_1, ..., w_{μ-1} q.v_{μ-1}]\)，所以问题就转化成聚合query向量和拼接后的底库向量的ANN查询问题。这个方案简单高效，但限制在于相似度函数必须是"decomposable"的，比如点积，当然如果向量是归一化处理过的，那么余弦距离或者欧式距离也是转化成点积的。
Iterative merging。为了适应更加一般的情况，作者提出了一种更加通用的方案，算法整体基于NRA，NRA是一种求元组topk的算法，要求在每个属性（向量）上有序，然后不断地调用getNext()方法获取下一个结果。但是ANN算法往往不能很高效地获取getNext()，需要跑一次完整的查询，所以这里可以适当放松一些限制，设置k'，一次获取k'个结果，如果算法没有停止，再将k'放大。
实验
实验部分有个事情让我奇怪，Milvus比较了一些商业系统并因为“商业原因”把它们记作A，B，C，但是在很多时候又透露出阿里的那几个系统在实验结果上的差距，这不知道是什么套路，莫不是这几个商业系统并不是阿里的系统？而且性能差距也忒大了点。。但现在感觉此类系统文章的实验部分其实只能仅供一乐，因为实验肯定按照有利的一面去做的，其实更多的譬如稳定性等方面很难用实验去衡量。
总结
看下来Milvus这篇文章，整体看起来创新点还是比较零散的，比较新颖的点在于CPU和GPU异构平台的支持，以及第一次讨论了Multi-vector这类查询，论文在最后提到了他们目前的工作重点是将Milvus推到云上，以及尝试支持新硬件如FPGA等。未来Milvus和它的公司Zilliz会发展成什么样，我们拭目以待。