田冰，华中科技大学计算机系统结构专业22级在读博士生

VStore: in-storage graph based vector search accelerator

https://dl.acm.org/doi/abs/10.1145/3489517.3530560

今天要介绍的题目是“可计算存储架构下的大规模近似最近邻搜索研究”。随着互联网技术的不断发展，我们都知道互联网上的数据量现在是呈着爆炸式的增长，这一增长的趋势极大地促进了大数据和人工智能的蓬勃发展。虽然在摩尔定律的指导下，我们 CPU 的性能是不断增强，但是存储器的发展却远远落后于CPU，这就导致了我们所谓的冯诺依曼瓶颈的问题。加之我们大数据应用需要对海量的数据进行处理，导致我们计算单元对存储的访问越来越多。近年来由于闪存技术的不断进步，闪存的内部的带宽不断地增加，但是闪存和主机之间的 I/O 接口，它的速度实际上是远远低于SSD 就是闪存的内部的带宽的。这些趋势就意味着日益严重的冯诺依曼瓶颈问题，需要一个新的提议结构。

那么什么是冯诺依曼瓶颈？我们都知道传统的计算机架构是以计算为中心，是计算与存储分离，如果想要计算的话，就是存储器先把它的数据给传输给计算器再进行计算。我们前面也提到了，现在的 CPU 的性能是不断地提高，存储器的容量也不断的增大，但是它们之间的数据传输却存在着一个很大的问题。第一个问题是首先是数据的传输速度是比较慢的，因为在存储内存储器内部，它海量的数据都需要经过系统的这个 I/O 的总线，就是处理器和存储器之间的数据总线，然后之后才能传输给CPU。然后其次是数据传输的一个能耗比较大。那么对于像人工智能还有图计算这种 I/O 密集型的应用来说，数据搬运的能耗其实是远远大于我们 CPU 计算的一个能耗的。那么为了解决我们现有的这样一种冯诺依曼的瓶颈，现在是去中心化的领域专用架构正在迅速的一个发展的趋势。这样一个架构是利用各种高性能的一个处理单元，然后来对数据按照状态来进行处理，实现一个数量级的性能提升，并且更低的一个功耗。比如说现在我们都知道的GPU，然后 TPU，还有 NPU 。这些是主要是数据在使用的时候我们去做计算，比如训练神经网络这些东西。我们这次活动的主办方他们做的这个类脑计算，还有这个 PIM 就是存内计算，就是内存内计算，然后也在快速地发展。此外数据我们在传输的时候，我们都知道是CPU，在它要对网络的包进行一个处理，这个处理任务负担还是比较大的。可计算存储就是基于移动计算比移动数据更高效的思想，在数据存储的地方来做计算，这样可以充分利用我们存储器内部的带宽，来减少因数据移动它带来的开销。

这里我引用了存储与网络协会对可计算存储的定义，它是一种能够提供与存储仅耦合的可以计算的功能，就是赋予存储器一定的计算资源，将 CPU的一部分计算任务给卸载到存储器内部，来减少数据移动的开销。这里是两个可计算存储的通用架构，那么左边是 off-path的一个架构，就是说我存储器内部的控制器不仅处理普通的 I/O 的命令，而且还处理我们要卸载的可以计算的函数功能，就是数据的通路都是在一条路上。然后第二种就是 off-path的架构。这种是在存储器内部来，就是单独集成一个可以计算的 FPGA 的计算芯片，然后这个FPGA 计算芯片和存储器连接。

这是宏观上传统架构与可计算存储架构加持的一个进数据处理的对比。所以就是每个存储器的内部我们都可以进行计算了。之后我们就可以对存储器内部添加一些比如说数据库的过滤的操作，或者说一些数据检索的相关功能，并且由于我们有了可计算存储之后，它的扩展机制并不会受到这个 I/O 总线的限制，因为每次扩展的话，它实际上是都是利用了内部的带宽。

回到今天要分享的这篇文章，就是通过利用前面讲的可计算存储设备对基于图的向量搜索，做了一个加速器。这篇文章是发表在 22 年的芯片领域的顶会 DAC'22上面。向量搜索，目前它的兴起主要是有两个原因，那首先是由于我们智能手机，物联网设备，还有社交媒体，比如说抖音快手它们的快速发展，这种不受结构的数据比如说视频、图像以及文本呈着一个爆炸式的增长，那么根据这个IDC的数据表明，到2025 年大约有 80% 的数据都是非结构化的。那更重要的是，我们的非结构化的数据，它现在是很难直接被计算机系统识别，通常需要使用其语义特征，来实现高质量的数据处理。

以非结构化数据的检索为例，传统的解决方案是利用手动特征对图像进行检索，他们的检索的准确度往往都比较低，质量会比较差。但是目前随着深度学习的不断发展，现有是利用一个深度的神经网络技术来获取我们文本，图片还有视频的一个语义特征，将它们映射到一个高维的 embedding上面，以获得更高的一个检索的准确度，那么这一种非结构化的数据在经过神经网络进行编码为高维向量之后，剩下的工作就是我们今天要讲的向量搜索了。

向量搜索它是一种数据的处理方式，那它的定义就是我们在一个数据集当中，每个实例都是一个包含d个特征的一个向量，假设我们现在是有一个查询向量的，这时向量搜索的目的就是找到我们这个向量数据库中根据用户定义的距离计算函数，找到与查询向量最接近的 k 个邻居。

现在搜索目前是大概是有 4 种方法，分别是暴力搜索、基于哈希的检索、基于树的检索以及目前比较就是最好的方法就是基于图的检索，基于图的向量搜索，它的核心的基础就是我们把这样一个高维的向量，把它作为点，向量之间的距离，给它表征成为向量之间的边，就是向量之间的距离越近，那么它们就越可能成为邻居。那整个查询的过程大概就是从起始点开始。迭代的从邻居节点，寻找与查询点距离最近的节点，这样不断地在图上进行迭代的查找，直到找到满足我们想要的与查询向量最近的向量的时候，这个时候就是满足了条件，然后才终止。那么由于基于图的方法它表现出非常好的一个性能，所以现在已经有大量的研究工作对基于图的方法做优化，比如说最基础的是KGraph，然后现后来的HNSW ，NSG 等等。

然而随着语义信息丰富的数据集增多，基于图的向量搜索也对数据中心的生产系统提出了更高的要求和挑战。首先需要以更低的延迟进行搜索，并且还要达到更高的准确度。以推荐系统为例，就是由于我们查询必须在到达现在搜索阶段之前，穿过多个阶段。因此现在搜索其实它的执行时间仅仅就是要求为微妙级别，甚至是更短。但是如果我们使用 CPU 来查询 10 亿规模的一个向量数据集的话，实际上所需要的时间要超过 100 毫秒。其次是我们需要更小的内存占用，还有更低的成本。虽然我们基于图的向量搜索，它表现出非常优异的查询性能，但是这样一种结构，它消耗会消耗大量的一个内存空间，比如这个SIFT1Billion。对于 10 亿级规模的话，如果我们要在这样一个数据集上构建一个图的话，它的索引大小就就要占到 200 多GB，那么 200 多个 GB 实际上是就是对数据中心内存空间的压力还是比较大的，所以如果我们能减少小的内存占用，那么就可以释放我们机器上搜索阶段所占用的资源，然后来降低数据中心的总的一个拥有的成本。

所以为了从应用层面和系统层面对这个相应搜索进行分析，这篇文章它们是分别运行了 GIST1M 和 DEEP1B 这两个数据集，那么对于应用层面，他们在执行相似的查询过程中顶点的轨迹，可以发现如果两个查询他们的距离特别近的话，那么他们在迭代查询的过程中实际上是会有大量的数据是被重用的。同时对于系统层面的话，如果将 DEEP1B 的图的索引和相应的数据全都存储到 SSD 的话，那么可以发现大约有 75% 的总的能耗的一个消耗是由 NAND闪存芯片，还有 I/O 接口之间的数据传输产生的那么这样一种现象就表现出一个显著的 I/O 瓶颈问题。

所以为了在大规模的销量数据集上提供一个更高成本效益的一个方案，然后这篇文章提出了一种基于可计算存储的向量搜索的解决方案。它是将原本的基于图的向量搜索这样一个功能，全部都卸载到了可计算存储设备内部，然后让可计算存储设备做相应搜索，将结果直接返回给主机。而不是说在搜索的过程中，主机不断地从SSD当中出取数据，再计算结果。这样的话，由于数据的读取和计算都是在存储器内部，那么就避免了我们传统操作系统当中这些复杂的一个数据 I/O 的存储栈，还释放了我们 CPU 和 DRAM 的一个内存资源。

Vstore 这篇文章它是嵌入到了 SSD 的控制器内部，可以看到它是有 4 个模块的，分别是查询编排引擎、向量搜索引擎、地址生成器和最后的请求编排。那么查询编排引擎就是负责重新的组织传入的查询的执行顺序，因为它之前观察到的现象就是如果两个查询向量的距离比较近的话，那么它们在查询过程中数据的重用率比较高，所以它们就利用这样一个特性，然后做了一个查询的请求编排，让相似的查询之间按顺序的进行执行，这样的话数据重用率就比较高。然后向量搜索引擎就是对基于图的向量搜索算法做了一个定制化的芯片加速器，把原来基于图的向量搜索给硬件化了。后面我主要是对以下这 3 个做详细地介绍。

首先是查询的编排，它主要是通过在存储器内部，缓冲一个查询的Buffer，然后来捕获定义时，固定时间窗口内的查询，选择与当前加速器中正在执行查询相似的查询，那这样的话，如果当前的这个查询执行完之后，查询 6 与查询 9 他们距离比较近，那么就意味着他们的数据重复率比较高，所以就调整这个窗口内的执行顺序。让和正在查询的这样一个向量与它们距离比较近，然后就优先进行查询，比如说 3 和 6 与 9 距离比较近，那么就优先执行 3 和6。调整后，还要对后面就是窗口内的其他的查询，也进行给编排，他们计算剩余的查询它们之间的一个距离关系，让距离相近的查询，然后按顺序这样查找。

在图上进行不断地迭代，搜索过程中要不断地去请求大量的节点和对应的邻居，然后这里它在 SSD 里面是分别维护了 3 个缓冲区，分别是边缓冲区和顶点缓冲区，还有地址缓冲区。因为在 SSD 的内部它要请求节点或者邻居数据的话，首先要检查对应的缓冲区当中有没有被命中，如果命中的话就直接做计算就可以了。那么如果有命中的话，就要向底层的 flash 上面去取数据。但是我们SSD内部是没有传统操作系统当中文件系统的这样一层抽象的，所以不能够直接去读取数据。这里它是做了一个地址生成器，把向量对应的顶点，映射到对应的闪存的物理页当中。映射之后，如果要读取顶点8，就是要读取 flash 的页面2。但是由于我们闪 SSD 内部它是以页粒度为读取单位的，就是我们每次读取的时候，它的单位都是以页粒度为大小，一个页粒度的大小通常是4KB左右，而我们每个向量和边它们大小通常是几十到几百B这么大。所以说有可能会出现同一个物理页当中包含多个向量顶点和多个邻居，这样的话就可能会出现一种情况，就是数据页面的冗余访问。比如这里有一个情况就是顶点8，它对应的是物理页2，那么在取完顶点 8 之后，后续的请求当中顶点 7 它也要去读取页面2，如果按这样一个顺序指引的话，就是读取了重复的页面2，来去获取顶点 8 和顶点 7 的数据。这样的话实际上增加了读取延迟，这里它是做了一个合并请求的一个方案，就是它也是在内部先缓冲一些请求，依次就是做地址映射，然后比如说得到页面 2 是对应着顶点8，还定还对应着顶点7，那么就将这两个页面请求进行合并，合并成一个请求之后再去发送给闪存的控制器，这样的话就可以减少冗余的页面访问。还有一种情况就是SSD 内部它是实际上是有多个通道。现在 SSD 的高带宽主要的一个原因其实也就是由于它内部是有多个channel，然后多个 channel 可以并行地去工作。所以这篇文章他们为了充分的利用SSD内部的这样一种并行性，他们是做了一个请求的一个类似于请求的一个调度的，他们将每一个到来的闪存的请求，通过一个哈希函数将不同的闪存页请求进行分区，然后这样的话可以就是充分地利用多个 channel并行访问的这样一个优势，来提高数据的读取效率，充分地利用通道级的并行。

以上就是大致的 SSD 内部的加速器的设计，然后他们实验用 FPGA 做了一个硬件，又做了一个模拟器的方案，他们分别采用了三种矢量搜索平台作为一个评估基准，分别是CPU， GPU 和 ZipNN。实验是选择了 5 种不同规模的数据集，然后通过 QPS 来衡量它们的搜索效率。功耗的话它们是主要通过功率的，效率就是每瓦特每秒的查询次数来评估，后面主要对这两个指标进行介绍。

首先是性能指标，他们FPGA的实现方案是这个蓝色三角后模拟器的方案是橙色的圆，CPU 的方案和其他 GPU 方案都是这些黑线。可以看到 FPGA 的方案实际上是提供了比 CPU 平台高很多的一个性能，那么随着数据集的规模增大，他们用的这个 FPGA 平台是比较就性能不是特别好，所以他的这样一个方案是比不过 GPU 方案的。但是他们这个 V-SIM做的一个方案是要比CPU、 GPU 和 ZipNN 性能都要好的。这样一种性能提升实际上就是来源于他们定制了一种硬件实现的优化，比如说前面消除了冗余的数据访问，还有并行的利用SSD 内部的多 channel 的这样一种特性。

对于能源效率的话，这个 V-FPGA 就是这个浅蓝色是要明显的比 CPU 的方案要好。他们这个模拟器的方案是比所有的方案都要好，FPGA的方案他们可能比不过 GPU 或者说其他优化的方案，但是他们这个模拟器的方案是要比所有的方案都要好。这是由于他们将计算移动到了数据附近，减少了主机到 SSD 的一个 I/O 接口，还有主机的 DRAM 以及闪存芯片所产生的能源成本。

然后以上就是Vstore它这篇文章的主要内容，这篇文章由于它是发表在了 DAC 上面， 6 页左右，所以说内容会比较紧凑，然后比较少。通过以上的分享，我们基于他们的工作，我们也有了一些思考。然后首先就是对于磁盘这样一种方案，它的数据集规模往往是非常大的，比如说 10 亿级别或者说百亿级别，那么这样一种情况下，我们还按照原来单个基于图的索引的方案的话，可能并不能达到非常好的一个性能。目前的研究方案表明，通过基于树和图的结合，或者说基于聚类，或者基于分区与图的结合这样一种索引,在超大规模的ANN场景中会表现出一个更好的一个性能。因为我们可计算存储的话，它主要针对的场景，也就是我们平常在主机里面，就是在 DRAM 里面数据集放不下，然后存储到 SSD 里，那存储的SSD 里就是对应着超大规模的一个情况。并且我们还发现就是现有的工作对这个 ANN卸载到可计算存储设备的方案中，实际上都没有考虑到可计算存储设备的一个处理能力，并且还没有考虑到就是有了主机的 CPU 和存储器的可计算存储这样一种异构的计算资源环境它们之间的协作的可能。

这里我们做了一个简单的实验，通过将 CPU 和可计算存储设备一起去做这样一个搜索的过程，那可以发现通就是适当的调整它们的卸载比例，也可以达到一个最佳的一个查询性能，这边 0: 10 是不进行卸载，对，这边 0: 10 是全部进行卸载，就是所有的任务都放到可计算存储设备内进行处理。然后 10: 0 是不进行卸载，就是全部放在 CPU 里，然后如果 4: 6 的话，实际上这个搜索效率是要比这两个方案要高出两倍的，就在协同的情况下。然后基于此，我们现在正在做的一个工作就是通过构建一种多探针的分区图的索引方式，来达到一个访存优化和高效并行的软硬件协同的方案。