【数据库设计】向量搜索HNSW算法优化

做向量存储的过程中，遇到向量搜索的情况处理，HNSW算法是目前向量搜索的主要算法之一，采用的是图算法，主要的问题是使用内存大，训练时间长。做算法优化过程中获得部分技巧，分享出来。

一、算法本身的优化

        对ENTERPOINTER的优化，算法中层的数据NODE可以是多个，这时有个选择的问题，需要对HNSW 算法本身进行修改，需要进行后处理，因为当时插入数据节点时是局部的，并不是全局视角，这个是HNSW算法中可以优化的点，但也不是说局部的点在后续算法中不能保证是全局的，因为这和数据的分布式强相关，现在的邻居选择不能表示后面更优的邻居选择，有个概率的问题。

        HNSW层数的优化，虽然层数的算法是按指数衰减来计算的，保证随机性，层高也应该是有个限制，毕竟对运算的数据量有要求，可以根据数据集合的大小来进行层数的限制，数据量大，层数可以多些，层数多也意味着内存要求大。比如10000个点的数据，通过指数衰减算法，实验多次的结果是上到5层的数据量极少，随机上到10层几乎没有。依次类推，数据集合越大才会有数据上的比较高的层数。

        动态列表数量的优化，网上有大量的介绍，主要是性能和效果的平衡，属于调优的部分，是跷跷板。

        不同层选用邻居的算法，HNSW的论文中的两种选择邻居的算法，建议可以这样操作，在0层采用SIMPLE算法，在中间层采用SIMPLE和HEURISTIC算法交替，高层采用HEURISTIC算法。

二、流式计算的优化方法

        IO的设计上可以使用流式算法，提高IO的效率，通过窗口算法解决单点和批量数据的获取效率问题；

        向量计算可以使用GUP,NPU进行大量的流式处理，充分利用硬件的性能资源

三、并行化设计的优化方法

        HNSW算法的并行化设计，对于单层的NSW的图，是不能进行并行化设计的，因为节点的插入有可能是否关系的，建立的INDEX的邻居列表中是存在前后关系的，需要获得邻居关系。所谓的并行化的设计应该是层和层的并行化设计，不同层的数据操作当然可以进行并行计算。需要一个任务的的配合机制，防止不同任务对同一个NSW同时进行INDEX的操作。

        另一个就是向量计算的过程，HNSW算法中向量的距离计算是主要的运算量，特别是高维度向量的距离计算，计算量大，可以进行并行化设计，充分利用硬件资源，多核，GPU,NPU等等。

        向量数据进行预处理，进行聚类的操作，将数据按聚类的方式进行分片，分片后的数据进行并行处理。

        由于向量集合数据大，IO上的并行设计也是可以考虑的，特别是SSD, NVM等硬件的多通道的使用上，也可以进行IO的并行化设计，提高IO的效率。

四、内存容量的优化方法

        向量数据的压缩，降低维度，由于HNSW算法对内存有较高的要求，内存容量是最大的瓶颈，为了缓解内存的压力，使用量化PQ算法，有效减小内存的使用量，当然性能也会提高，但精度也会下降，数据进行的采样压缩，是有损的。

        第二个方式，是借用其他的专用存储，使用其高效的数据缓存方式，来减小本机运行HNSW算法的内存消耗，如使用专用的存储集群，KV存储或缓存系统进行，相当于在内存使用转嫁到其他存储缓存系统中，如类似的HNSW+ REDIS的方案结合。

        本机缓存的的缓存策略，LRU, LFU的效果，测试的情况来看不如LRU-K， 和W_LFU的算法，缓存的数据随机性比较强，导致缓存效果不佳，而LRU-K，和W_LFU将缓存进行分级处理，有前置的算法可以大大提高应对数据随机性的缓存要求，提高命中率。