作者：sauronzhang、flashlin、fengshanliu，微信后台开发工程师
出处:
1.背景
在一些推荐系统、图片检索、文章去重等场景中，对基于特征数据进行k近邻检索有着广泛的需求：
支持亿级索引的检索，同时要求非常高的检索性能；
支持索引的批量实时更新；
支持多模型、多版本以灵活开展ABTest实验；
支持过滤器、过期删除以排除不符合特定条件的数据。
在经过调研后，发现已有的解决方案存在以下问题：
在学术界中，已经存在有成熟并开源的ANN搜索库，然而这些搜索库仅仅是作为单机引擎存在，而不能作为高性能、可依赖、可拓展的分布式组件为推荐系统提供服务；
在业界中，大多数的组件都是基于ANN搜索库做一层简单的封装，在可拓展、高可用上的表现达不到在线系统的要求；而对于少数在实现上已经较为成熟的分布式检索系统，在功能上却难以做到紧跟业务发展；
而在更新机制上，很多组件都是要么只支持离线更新、要么只支持在线接口更新，无法满足在微信侧小至秒级千数量、大至小时级亿数量的索引更新需求，因此需要可以兼顾近实时更新及离线大批量更新的分布式系统。
基于上述的这些要求以及业内组件的限制，我们借助WFS和Chubby设计并实现了SimSvr，它是一个高性能、功能丰富的特征检索组件，具有以下特点：
分布式可伸缩的架构，支持亿级以上的索引量，以及索引的并发加速查询，实现了10ms以内检索数亿的索引；
高性能召回引擎，使用了召回性能极佳的hnswlib作为首选召回引擎，大部分请求可在2ms内完成检索；
集群化管理，集成了完善的数据调度及动态路由功能；
多样的更新机制，支持任务式更新及自动更新，同时也支持全量更新与增量更新，跨越秒级千数量到小时级亿数量的索引更新；
读写分离的机制，在离线利用庞大的计算资源加速构建索引的同时，不影响在线服务的高性能读；
丰富的功能特性，支持轻量embeddingkv库、单表多索引、多版本索引、过滤器、过期删除等特性。
2.检索引擎
2.1引擎的选择
ANN问题在学术界已被长期研究，并且已有成熟的开源ANN搜索库存在，如nmslib、hnswlib、faiss等。在SimSvr中，性能及集群的存储容量是最主要考量的两个指标，因此选择了以下两个检索引擎：
在ann-benchmarks中检索性能最好的hnswlib，能够满足在线服务对召回率及检索耗时的高要求（大于90%召回率的情况下，能在1ms内完成召回）；
faiss的IVFx_HNSWy+PQz算法，支持将向量压缩10~30倍，能够满足资源有限情况下的高维大数据量的索引要求（亿级索引数据，容纳在内存64G的机器上）。
ANN检索引擎效果对比
2.2巧妙利用资源，提升50%的数据容纳量
hnswlib是单机检索引擎，在资源使用方面仅考虑了单模型的情况；而SimSvr是提供在线服务的组件，一般容纳了多个模型；
SimSvr在大部分场景下，拥有读写分离的特点；
基于以上特点，我们在引入hnswlib之后，进行了资源整合，使得SimSvr单机情况下可以容纳更多的模型索引：
极限情况下（以worker线程数80、部署10张2kw索引量的表为例）：
现网运营中（以某现网模块(11台实例机器，worker线程240）为例）：
2.3点积距离召回率从62.6%到97.8%的蜕变心路历程
HNSW算法在余弦距离表现优秀，但在点乘距离的数据集上存在效果差的情况；
点乘距离非度量空间（metricspace)，不满足三角不等式，距离比较没有传递性；
维基百科中关于度量空间的定义:
hnswlib中说明点积属于非度量空间：
而在论文Non-metricSimilarityGraphsforMaximumInnerProductSearch中，提到了将点乘距离转换为余弦距离计算的方法，我们将这种方法简称为ip2cos；
2.4如何使用faiss省下2h的训练时间并提升30%的召回率
在faiss中增加了batchkmeans聚类方法，在保证较好聚类效果的同时大幅加快训练速度。IVF系类方法训练耗时主要体现在需要从数据中学习nlist个聚类中心，对于千万级数据nlist的大小在20万以上，在cpu上使用传统kmeans方法训练会非常耗时，下面展示在128维、IP距离、1000万条数据的情况下batchkmeans对训练速度的加速效果：
从结果中可以看到，在相同迭代轮次下，不使用batchkmeans的方法训练耗时更长，且没有很好收敛，导致召回率不高。
3.总体设计
3.1数据结构-为达成一个小目标，需要做出怎样的改变
为了满足单模块多模型的需求，SimSvr使用了表的概念进行多模型的管理；另外，为支持亿级以上HNSW索引的表，并且希望能够并发加速构建索引，我们根据单表的数据情况，将一张表分成了多个sharding，使得每个sharding承担表数据的其中一部分：
tablei的索引，由shard0、shard1、…、shardn构成一份完整的索引数据；而sect的数量则决定了表的副本数（可用于伸缩读能力、提供容灾等）。
在SimSvr中，我们将一个shardi_sectj称之为一个container，这是SimSvr中最小的数据调度和加载单位。
3.2系统架构-如何支撑亿级索引、5毫秒级的检索
SimSvr架构
SimSvr与FeatureKV一样，涉及的外部依赖也是三个：
Chubby：用来保存元数据、路由信息、worker资源信息等；SimSvr中的数据协同、分布式任务执行均是依赖于Chubby；
USER_FS：业务侧存放原始数据的分布式文件系统，可以是WFS/HDFS，该文件系统的路径及信息保存在表/任务的元信息中；
SimSvr_FS：Simsvr使用的分布式文件系统，用于存放生成的索引文件或者原始的增量数据文件。
worker
负责对外提供检索服务，通过对Chubby的轮询检查索引的更新，进而将索引加载至本机以提供服务；
每台worker负责的数据，由master进行调度，worker根据master保存在Chubby上的分配信息进行数据的加载/卸载；
worker的数据是根据master分配得来的，除此之外没有其他状态的差别，因此worker是易于扩缩容的。
master
数据调度：通过表的元信息及worker状态，将未分配的数据或者失效worker上的数据调度给其他有效的worker；
生成路由表：根据worker的数据加载情况及状态，生成集群的路由表；
感知数据更新：检查表的自动更新目录，若最大数字目录发生了增长，则建一个任务以供trainer进行索引的构建；
master是一个无状态的服务，通过Chubby提供的分布式锁保证数据调度以及路由生成的唯一执行。
trainer
负责构建表的索引及资源回收；
trainer单次可构建一张表中一个sharding的索引，因此如果表有多个sharding时，可通过增加trainer的个数实现构建索引的并发加速；
trainer是无状态的服务，通常部署在微信Yard系统上，充分了利用微信闲置机器上的资源。
数据自动更新
在建表时，对其指定了一个fs的目录，该目录下，是一系列数字递增的目录；
当业务侧需要更新索引时，将最新的数据dump到更大的数字目录中；
master感知最大数字目录的更新，从而更新了元信息；
trainer感知元信息的更新并触发建索引；
worker加载索引完成索引的更新。
数据任务式更新
由业务侧主动通过接口的调用，创建一个索引任务；
在索引任务中，指定了数据的配置信息（如fs信息及路径等）；
trainer按照表的任务序列，执行任务并构建索引；
worker加载索引完成索引的更新。
3.3数据调度-鸡蛋怎么放在多个篮子中
SimSvr在每张表创建时就指定了sharding数n及sect数m，因此这张表拥有了n*m个Conatiner以供master调度；
master会根据worker的健康情况及资源使用情况进行数据的调度及路由表的生成；
路由表带有递增的版本号，可根据版本号感知路由的变化。
worker定期轮询Chubby获取数据的调度情况及最新的路由表信息；
client首次请求时，将随机请求一台worker获取最新的路由表信息并将其缓存在本地；
client在本地有路由表的情况下，将根据表的数据分布情况，带上版本号并发地向目标worker发起请求，最终合并所有sharding的结果，将其返回给业务端。
3.4系统拓展-篮子装满了该怎么办
SimSvr将表拆分成了更小粒度的数据调度单位，且不要求每台机器上的数据一样，因此可以用拓展机器的方式，将集群的存储容量扩大；
对于单表而言，当读能力达到瓶颈时，可以单独扩展此表的读副本数；
4.近实时增量更新的挑战-十秒内完成索引的更新
数据一致性与持久化
对于大多数的分布式存储组件来说，都是使用raft或者paxos等一致性协议保证数据一致性并持久化至本机上；
对于SimSvr来说，每张表会被分为多个sharding，且sharding数不保证为奇数；
在worker中加入一致性组件及额外的存储引擎，会使得整体的结构变得复杂；
最终在考量后，结合业务的批量增量更新的特点，选择了先将数据落地fs，再由worker拉取数据加载的方案；在这种方案下，1000以内数量的key插入，能够在10s内完成，达到了业务的要求。
增量持久化
增量更新的性能保障
由于在线建索引是非常消耗cpu资源的过程，因此为了不影响现网的读服务，worker仅提供少量的cpu资源用于增量数据的更新；
对于小批量的增量数据，worker可以直接加载存放在fs上的数据并直接进行索引的在线插入；
对于大批量的增量数据，为了避免影响读服务及大增量更新慢的问题，SimSvr将大批量数据在trainer进行合并且并发重建索引，最后再由worker直接加载建好的索引。
增量更新
5.丰富的功能特性
5.1支持额外的特征存储库
这类数据，仅仅只需要查询的功能，并且与同个模型同个版本产出的索引库相互作用，产生正确的召回效果；
基于这种原子性更新的特性，SimSvr支持了额外的特征存储库，用于存储与模型一同更新且仅用于查询的特征数据，帮助业务省去了数据同步与对齐的烦恼。
5.2支持原子性更新的单表多索引
在推荐系统中，ABTest是非常常见的，多个模型的实验往往也是需要同时进行的；
另外，在某些场景下，同一个模型会产生不同的索引数据，在线上使用时要求同模型的索引要同时生效；
对于以上两种情况，如果使用多表支持多模型，在索引更新上存在生效时间的差异从而无法支持；
SimSvr对于这种情况，支持了同一张表多份索引的原子性更新，保证了索引能够同时生效。
5.3多版本索引
在ABTest场景下，除了有多模型间的实验，还有相同模型不同版本数据的实验；
在相同模型中，版本迭代/不同版本进行实验的场景是广泛存在的；
如果使用多表支持这样的多版本索引，不管在业务方的使用上，还是在SimSvr的管理上，都显得不是那么地优雅；
对此，SimSvr支持了同一张表的多版本管理，并且多版本支持在现网下同时进行服务，业务可以按需请求目标版本，进行灵活的实验。
5.4支持布隆过滤器、阈值过滤器等
通过增加召回结果并在结果中进行过滤，对于重度用户，一样存在上述问题，并且还会导致不必要的性能开销；
SimSvr改造hnswlib，嵌入了过滤器的逻辑，使得其支持在检索过程中实时对符合特定条件的key进行过滤，保证了召回结果的有效性。
5.5支持过期删除
对于一些推荐系统来说，对于数据的时效性要求是非常高的，在数据过了其最佳召回时间段之后，就不应该出现在召回结果中，以免出现不合时宜的尴尬；
SimSvr支持导入带过期时间的数据，在现网召回过程中，实时淘汰过期的key以达到准确的召回要求。
6.现网运营情况
搜一搜基于SimSvr建立小程序优质文章的向量索引，提升小程序文章搜索的优质结果召回率。新方案相比旧方案，优质结果召回率提升7%；
7.总结
出处: