基于 SmartSSD 的近数据处理架构，用于可扩展的数十亿数据点的近似最近邻搜索

《ACM Transactions on Storage》：A SmartSSD-based Near Data Processing Architecture for Scalable Billion-point Approximate Nearest Neighbor Search

提出基于分层索引的SmartANNS方案，结合主CPU与智能SSD协作架构、动态任务调度及学习剪枝算法，使查询吞吐量较CSDANNS提升10.7倍，并实现多智能SSD的线性扩展。

　　

摘要

近似最近邻搜索（ANNS）在高维向量空间中的应用在数据库和机器学习领域变得越来越重要。大多数现有的ANNS算法需要TB级别的内存来存储数十亿规模数据集的索引，这使得它们在高性能ANNS服务中的部署成本极高。新兴的SmartSSD技术通过近数据处理器（NDP）为实现可扩展的ANNS提供了可能性。然而，直接在多个SmartSSD上采用现有的ANNS算法仍面临若干挑战。

在本文中，我们提出了SmartANNS，这是一种基于分层索引方法的、由SmartSSD支持的、适用于数十亿规模数据集的ANNS解决方案。我们提出了几种新颖的设计来实现在多个SmartSSD上的近线性扩展。首先，我们提出了一种“主机CPU + SmartSSD”协同架构，并结合了分层索引，以显著减少对SmartSSD的数据访问和计算量。其次，我们提出了基于优化数据布局的动态任务调度机制，以实现多个SmartSSD之间的负载均衡和数据重用。第三，我们进一步提出了一种基于学习的碎片剪枝算法，以消除不必要的计算。我们使用三星的商用SmartSSD实现了SmartANNS。实验结果表明，与现有的基于SmartSSD的ANNS解决方案CSDANNS相比，SmartANNS的每秒查询次数（QPS）提高了10.7倍。此外，SmartANNS能够在使用多个SmartSSD的情况下实现大规模数据集的近线性性能扩展。