【作者】 胡文；

【导师】 王金庆； 刘钦；

【作者基本信息】 南京大学 ， 工程硕士（专业学位）， 2020， 硕士

【摘要】 随着移动互联网用户群体的扩大,用户每天在线产生的数据无比庞大并且用户对于信息消费模式要求越来越高。在线服务提供商为了争夺用户使用时间,也需要更加精准的将用户感兴趣的内容投递给用户。在线搜索、商品推荐、新闻阅读等服务的背后都隐藏着庞大的数据需要计算机从中找出用户感兴趣的内容。这一切都需要依赖最近邻搜索算法。因此,本文设计了基于局部敏感哈希(LSH)和层次性可导航小世界图(HNSW)算法的近似最近邻分布式搜索系统,主要实现了超大规模向量下索引的快速构建和高效的检索。引入局部敏感哈希和层次性可导航小世界图算法后虽然为我们拆分索引带来了理论支撑,可以极大程度提高索引的构建检索效率,但是也给系统的实现带来了较大的复杂度。由于层次性可导航小世界图构建的索引中的数据全部都保存在内存中极易丢失,另外划分后的多个子索引需要运行在集群中不同的实例上,保证系统不会出现单点故障[邓鹏,2012]也至关重要。在本文描述的系统中运用了分布式系统架构提高了搜索系统的可靠性和可用性。该系统主要包括五个模块,分别为:(1)集群信息管理模块:使用动态配置技术管理集群静态配置信息,通过心跳的方式采集数据节点的信息,使用Raft协议完成Leader选举,并通过广播的方式向Follower节点同步数据。(2)数据备份恢复模块:使用冷热备份结合的方式,实现对系统中数据的保存,保证了数据的可靠性。(3)索引分配迁移模块:实现子索引在系统启动时的自动分配。通过心跳监控索引的状态以及冗余部署技术,实现在节点故障时快速迁移,保证系统的高可用性。(4)负载均衡模块:负责优化数据在子索引中的分布,使用了局部敏感哈希算法对向量进行空间压缩,将距离较近的向量插入同一子索引,极大的提高了系统的横向扩展能力。(5)数据搜索模块:负责系统对外的数据插入和数据搜索接口,并且协调调度上述四个模块完成功能。更多还原

【Abstract】 With the expansion of mobile Internet user groups,the data generated by users online every day is extremely huge and users have higher and higher requirements for information consumption patterns.In order to compete for user time,online service providers also need to deliver content that users are interested in to users more accurately.Huge data is hidden behind online search,product recommendation,news reading and other services,which requires the computer to find out the content of interest to users.All this depends on the nearest neighbor search algorithm.Therefore,this paper designs an approximate nearest neighbor distributed search system based on local sensitive hash(LSH)and hierarchical navigable small world graph(HNSW)algorithms,which mainly realizes the rapid construction and efficient retrieval of indexes under very large-scale vectors.Although the introduction of LSH and HNSW algorithms has brought us theoretical support for splitting the index,which can greatly improve the efficiency of index construction and retrieval,it also brings greater complexity to the implementation of the system.All the data in the index built by HNSW is easily lost in memory.In addition,the divided multiple subindexes need to run on different instances in the cluster to ensure that the system will not have a single point of failure.The distributed system architecture is used in the system described in this article to improve the reliability and availability of the search system.The system mainly includes five modules,namely:(1)Cluster information management module: uses dynamic configuration technology to manage cluster static configuration information,collects data node information through heartbeat,uses Raft protocol to complete leader election,and synchronizes data with Follower nodes through broadcasting.(2)Data backup and recovery module: the combination of hot and cold backup is used to save the data in the system and ensure the reliability of the data.(3)Index management module: realize the automatic allocation of sub-indexes when the system starts.Through the heartbeat monitoring index status and redundant deployment technology,to achieve rapid migration in the event of node failure,to ensure high availability of the system.(4)Load balancing module: responsible for optimizing the distribution of data in the subindex,using a local-sensitive hash algorithm to spatially compress vectors,inserting vectors that are closer to the same sub-index,greatly improving the horizontal expansion of the system ability.(5)Data search module: responsible for the system’s external data insertion and data search interface,and coordinate the scheduling of the above four modules to complete the function.更多还原