张存义 快手技术团队 2021-11-29 稿

背景及挑战

随着深度学习的不断发展和落地，图片、视频、音频、用户行为、爱好等非结构化数据得以通过向量进行表征，随之而来在快手内部搜广推、安全、内容理解等多个业务场景中便衍生出了大量且相近的K近似最近邻检索需求，如何高效服务好这一系列需求成为一个重要的方向和基础能力。

Faiss、Hnsw、ScaNN等多种向量检索开源算法库，成为工业界向量检索工程基础。但是开源库与高性能、高易用、高可靠的服务及平台之间还存在着较大的鸿沟与挑战：

• 性能挑战： 开源算法不一定代表最优性能！需要不断自研提升开源算法性能吞吐进而降低服务部署成本，吞吐 = 金钱；
• 易用性挑战： 开源算法通常是不易用的。开源算法功能比较单一太底层，没有提供面向业务的功能，重复建设成本高；
• 超大规模挑战： 如何设计合理的在线、离线架构支持超大规模数据集(百亿)、超高并发(百万级qps)等特殊业务场景需求，对工程能力挑战极大；
• 综合检索场景挑战： 单纯向量检索能力已不能满足实际业务中复杂场景检索需求，更高级的结构化检索能力成为工业界新的发展方向，融合"非结构化数据向量检索"+"结构化数据布尔检索"的综合检索实现，才能满足类似于(Brand = Adidas) and (Pirce in [100-200]) and (Location = Beijing) and (Ann dis : top 100) results 等相关性限制条件下的复杂场景向量检索需求；
• 算法及超参挑战： 实际生产中业务场景极度复杂，向量检索算法数十种，但没有'银弹'算法适用所有场景，每种算法又有众多的超参影响精度和性能，如何合理选择算法及其并使用合理参数来达到最优的效果是一项十分复杂的工程，需要不断的积累与探索；
• 接入效率挑战： 需求到线上服务需要多长时间？在业务需求很多的情况下，效率往往会成为使用方更大的关注点；
• more ......

面对诸如以上不同层面的问题和挑战，有必要将很多共性需求和解决方法抽象出来形成一种最佳实践，进而形成平台化服务。为此我们设计开发了 「繁星」向量检索平台 ，致力于解决以上问题和挑战，服务公司业务发展。

平台目标

在充分调研业界现状后，由"搜索技术部" 主导并联合 "AI 平台部"联合自研 「繁星」向量检索平台 ，并对向量检索中算法优化、硬件加速、异构计算、引擎架构、中台能力、稳定性建设、辅助工具等多方向进行了深度的探索和研究。

作为快手SigmaAI通用能力建设的重要组成部分，我们全力打造一个高性能、高可靠、高易用的向量检索平台，满足各主要场景下的通用业务需求，并具备特殊业务场景定制化服务的能力，以达到成果复用，降本增效的目标。

• 高性能

  • 业界最新算法优化与自研算法升级两条线路并行，保证算法的先进性，最大化利用硬件性能，降低机器成本；
  • 复杂场景支持：复杂目标检索求解、高并发查询、海量数据索引、语义检索、结构化查询等场景，深度支持高精尖领域需求；

• 高易用

• 基于一站式向量检索中台系统，提供简单易用的页面化接入方式，打通公司各类基础设施，分钟级接入，需求到服务的全自动化部署；

• 抽象并组件化输出常见业务场景"功能"插件，屏蔽底层算法差异，智能适配业务场景，提升用户迭代效率；

• 高稳定

• 完善SLA体系：全面监控运维和报警体系、容灾降级策略、人工Oncall机制等保障P0服务99.99%可用性，P1服务99.9%可用性。

业务现状

截止2021年10月底，「繁星」平台已经广泛服务于快手内部多个核心业务部门：平台托管在线服务数数百个，索引量超千亿，峰值qps 达500万/s，同时深度支持千亿版权查重库等多个特殊业务场景；此外基于向量检索能力之上还拓展出了拍照搜商品、视频搜视频等多媒体内容检索能力，并在线上落地。

文本搜索场景 - 相似文本	拍照搜商品 - 多媒体检索

架构层级图

「繁星」内部架构针对算法优化、功能增强、高并发、易用性等主要目标特性分别进行了抽象和层次化设计，整体架构高内聚低耦合，每一层均能做到独立serve和高效迭代开发，功能引擎的组件化设计使得非常多通用业务需求沉淀落地，配置化支持多业务需求。

架构全景图

特性介绍

「繁星」向量检索平台具备丰富的“算法特性”、“功能特性”及"架构特性"，我们主要选择几个主要特性进行展开介绍：

关键特性一：算法多样性及先进性

自研Starry检索框架屏蔽了不同算法接口及使用上的差异，实现无缝接入多种最新、最强开源及自研ANN、KNN算法的能力，目前已支持:

• 图类型算法：HNSW、NSSG
• IVFPQ类算法：ScaNN(Google)，自研Starry IMI-PQ(超大规模)
• 综合类库：Faiss
• 内积空间检索：ScaNN(Google)，自研基于图的检索算法
• 复杂目标空间：自研多目标GPU-KNN与CPU-ANN算法
• GPU支持：SONG(百度)，自研GPU KNN，Faiss-GPU

向量检索算法繁多我们在跟进业界最新算法的同时，针对特殊场景/特殊算法进行算法深度自研与优化，来满足不同业务需求：

• 超大规模数据集查重场景检索算法自研：

基于IMIPQ的改进算法结合LOPQ技术，实现更好空间划分能力同时最小化量化误差，结合内存重排、SIMD指令优化加速等工程优化，在索引数千亿的场景下，实现新查重系统吞吐相比旧系统提升数倍，节省上千台机器；

• HNSW及ScaNN算法优化：

向量检索是内存密集型兼计算密集型的任务，分别从向量压缩、指令加速、图重排、缓存优化、只读优化等多方面对当前性能最好的两个开源算法(HNSW与ScaNN)进行了工程优化，尤其是与Intel深度合作优化SIMD相关算子，同时配合SIMD自适应技术，在不同硬件环境下自动选择最优指令实现，达到综合场景下的最优表现。

如下图所示，优化后的HNSW算法及ScaNN算法相比开源版本取得了25%-36%不等的性能收益。

• MIPS(最大内积搜索)技术研究：

由于内积度量空间是非度量空间，常见向量检索算法无法直接应用，业界常见解决方式是向量尾部增加1维辅助值后，将内积距离转换为等价欧式距离在进行NNS检索（简称MIPS-to-NNS方法），但其存在对数据分布敏感、向量模限制等限制。在论文(Non-metric Similarity Graphs for Maximum Inner Product Search) 中作者提出ip-NSW方法能够有效降低低模候选的计算量从而大大提升检索速度；2020年，Google发布的ScaNN算法针对MIPS问题对IVFPQ算法进行了各向异性矢量量化优化，获得了小数据集场景下业界最佳的表现性能，但其依然无法支持实时数据；

结合业界最新研究，自主实现了基于空间变换的图检索技术，充分利用变换后Delaunay Graph的高连通性提高了有向边的有效性，获得了比相比ip-Nsw 数倍、相比ScaNN 10%+的吞吐提升；

• 多目标检索及复杂目标检索算法自研：

推荐、广告场景中，用户最终长时间观看视频或是否进行购买取决于多个因素，如推荐场景需要同时考虑follow、like、ctr等因素，广告场景则需要考虑ctr、cvr、bid等因素，也即多个子目标决定综合收益， 这时之前单目标求解问题的方式不再适用，需要求解多目标综合最优解，典型的如：

语义搜索场景中，简单双塔模型Query-Candidate交互过晚，且Cosine(余弦距离)、InnerProduct(内积距离)等常见向量相似距离偏简单已不能充分表达Query-Candidate之间的关系，限制了模型的效果，深度学习匹配计算等方式不断衍生。

自研实现了复杂目标相似近邻检索算法，在50w测试集4目标dim=32场景下，same-1000达95%以上时，吞吐相比暴力计算提升十倍。

关键特性二：丰富引擎功能

Starry引擎抽象线上业务共性，实现大量功能Feature，覆盖绝大部分业务场景，配置即代码。本节开头图中已有列举，这里针对几个颇具代表性的业务功能进行重点介绍。

• 结构化查询能力：

复杂场景中(如电商搜索、本地生活)，希望通过非结构化数据(向量数据)增加泛化的语义召回能力，同时辅以query-doc类别、位置信息、价格信息等结构化数据进行布尔检索能力进行相关性约束，提升综合检索效果；

Starry引擎参考AnalyticDB思路并改进优化，针对不同数据形式实现了不同类型索引：向量索引、哈希索引、B+tree索引，经过对查询的耗时预估生成最优执行计划，再进行查询下发，获得结构化查询过程最优吞吐，比相关开源版本实现更优更灵活。

• 丰富数据单元：

索引内多Bucket、多Version、多Segment数据单元设计以及类LSM-tree的更新机制，支撑实现了索引淘汰，分桶查询，索引版本控制等复杂查询功能和数据管理功能。

• 基于Trainer-Worker模式的近实时索引构建体系：

填补了大量类数据库的近实时增删改查能力，同时为大规模离线索引构建提供了时效性更好的可选项，同时一写多读、读写分离的模式，有效实现索引一致性，节省了多副本重复构建索引的成本消耗。

• 设计并实现Hive2Hive离线大规模索引查询工具：

业务场景经常会有离线数据集A查询数据集B中TopK近邻并将结果落到Hive表C中的需求，数据集A、B通常都在10亿甚至更高量级，搭建临时在线服务存在大量的人工维护成本(资源申请、扩容、用后清理下线等)，效率低下；基于MapReduce数据处理流设计并实现离线大规模索引查询工具：索引分库、构建、查询、落表多操作流式自动化处理，同时结合索引和检索分库算法查询空间降至全空间的1/N，得以快速完成海量数据查询任务，目前该工具已投入多个业务生产当中；

关键特性三：基于Lambda架构的分布式可伸缩大规模索引体系 及 高效在线检索架构

为了支撑百亿级数据定期更新+大qps实时更新的场景需求，本平台采用搜索场景的经典Lambda大数据处理体系实现，基于此架构带来了如下好处：

• Lambda大数据处理体系优点：

  • 实时性满足：秒级索引可查；
  • 海量数据支撑：静态索引可通过分片策略快速横向扩展系统容量，支撑百亿级别索引；
  • 高性能：动静索引的分离意味着索引的读写分离得以实现，针对只读场景可以进行特定的吞吐和内存优化，节省检索成本；
  • 鲁棒性、容错性提升：定期索引的存在可以使得索引可以快速从机器不稳定或动态数据丢失中恢复出来；
  • 可扩展性增强：静态索引的容器云部署可以做到，分钟级扩缩容，运维成本低；

• 高效在线检索架构：

  • Proxy层的引入，有效隔离了底层动静索引、分布式索引细节，用户获得一致性服务体验；同时有效实现了特征托管能力，避免高查询流量下特征重复计算或重复获取的问题；
  • Proxy层网络协议全链路异步化和Brpc优化，使得非常少资源就能完成超高请求转发等高层逻辑，同时与Leaf层的Batch化打通使得系统充分利用底层算法的Batch加速能力，进而实现系统支持单服务百万级查询qps的能力；

关键特性四：高效自动化接入

繁星向量检索平台依托自研Starry Platform Web Server，需求对外Web化承接，对内实现一键化自动部署，减少人工成本。

• 基于自研策略框架，打通公司底层内主要基础设施：容器云、KwaiFlow、Kconf、Btqueue等，实现底层一键式索引构建、服务部署，提升服务效率；
• 面向用户我们提供足够丰富的用户选项，充分暴露平台能力，减少用户需求对接成本，实现10min+需求接入；

后续规划

随着智能化、向量化的不断演进，向量检索方向的研究和应用肯定是持续且长远的，如下几个方向是我们需要持续投入和研究的：

• 公司平台深度集成：繁星向量检索平台将会与公司大数据AI平台进行深度集成，实现向量训练、预估、存储、检索一站式体验，服务更广范围内的用户；
• 算法层面：如何吸收业界最新研究成果，解决实际业务问题，实现自我创新的同时在公司内获得更大的成本和业务收益；
• 大规模索引问题求解：索引规模急剧扩张时，在小规模索引场景运行良好的机制可能就会变得不可行了，比如图索引周期建库重复计算及时效性问题、高并发qps支撑能力等都需要专门研究解决；
• 超参调优：虽然我们在超参调优方面已经积累了一些离线测试数据及配套调优工具，但是相关能力如何能够更快速、更有效的适配不同算法和业务场景并与自动化平台更好的结合，是我们后面重点研究的一个方向；
• 向量检索能力延伸：服务业务是我们的最终目标，但业务场景是复杂多变的，向量检索的能力范围也在不断的外延并与实际业务结合产生新的方向，这需要我们不断拓展能力边界来适应这种变化，比如：复杂目标向量检索、语义检索、拍照与商品检索等。