| 摘要: |
| 在大模型时代, 向量数据库的广泛应用推动了向量索引规模的急剧膨胀. 如何在磁盘级向量索引中高效支持大规模向量的更新操作, 并同时提供高性能的查询服务, 已成为近年来的重要研究课题. 针对当前领先算法 FreshDiskANN 在查询与更新混合负载场景中面临的查询吞吐瓶颈和极端查询延迟过高等问题, 受到日志合并思想在次级索引中成功应用的启发, 提出了一种基于LSM (log-structured merge)思想的更新友好型磁盘向量索引框架LSMDiskANN. 在继承 FreshDiskANN架构的基础上, 设计并实现了包含磁盘中间层的3层架构, 同时引入了磁盘组件搜索参数的动态确定机制以及面向合并操作删除阶段的重布局算法, 从而进一步降低查询延迟和合并过程中的 I/O 开销. 实验结果表明, 在多个经典大规模高维向量数据集上, LSMDiskANN系统查询吞吐量最高提升35.5%, 更新吞吐量最高提升14.24%, 极端查询延迟最多降低73.45%, 所提出的框架和策略能够有效提升系统在混合负载场景下的整体性能与稳定性. |
| 关键词: 向量数据库 磁盘向量索引 动态向量索引 日志合并 |
| DOI：10.13328/j.cnki.jos.007513 |
| 分类号:TP311 |
| 基金项目:国家重点研发计划(2023YFB4503604) |
|
| LSMDiskANN: Update-friendly Disk-resident Vector Index Framework |
|
QIU Hai-Lang1, PENG Yu-Wei1, PENG Zhi-Yong1,2
|
|
1.School of Computer Science, Wuhan University, Wuhan 430072, China;2.Big Data Institute, Wuhan University, Wuhan 430072, China
|
| Abstract: |
| In the era of large models, the widespread use of vector databases has led to a rapid expansion in the scale of vector indexes. How to efficiently support large-scale vector updates in disk-based vector indexes while maintaining high query performance has become an important research problem in recent years. FreshDiskANN, as a leading algorithm, suffers from query throughput bottlenecks and high tail latency under mixed query-update workloads. Inspired by the successful application of log-structured merge (LSM) in secondary indexes, LSMDiskANN is proposed as an update-friendly disk-resident vector index framework based on the LSM paradigm. Building on the FreshDiskANN architecture, a three-level structure including a disk intermediate level is designed and implemented. In addition, a dynamic parameter selection mechanism for disk component search and a re-layout strategy for the deletion phase of compaction are introduced to further reduce query latency and I/O overhead during merges. Experimental results show that on multiple large-scale, high-dimensional datasets, query throughput is improved by up to 35.5%, update throughput by up to 14.24%, and tail query latency is reduced by up to 73.45%. The proposed framework and strategies effectively enhance overall performance and stability under mixed workloads. |
| Key words: vector database disk vector index dynamic vector index log-structured merge (LSM) |
