Speculative scheduling for in-storage graph-based approximate nearest neighbor search

국문 초록 (Abstract)

본 논문은 SSD에 상주하는 그래프 기반 근사 최근접 이웃 (ANN) 탐색에서, 플래시 특유의 읽기 장애를 해결하기 위한 읽기 재시도로 인해 가변적인 읽기 지연 시간으로 인한 탐색 지연 시간 증가 및 내부 병렬성 저하 문제를 다룬다. 기존 빔 확장은 동시성을 높이지만 모든 확장을 동등 취급해 가치 낮은 확장에도 자원이 소모되고 지연 변동성 자체를 완화하지 못한다는 한계를 가진다.
이를 해결하기 위해 SSD의 자원 상태를 알고 추측적으로 탐색을 진행하는 알고리즘을 제안한다. 매 확장 단계에서 가장 가치가 높은 확장을 정규(normal)로 보장하고, 나머지 후보는 추측(speculative)으로 표시해 SSD 채널 및 칩이 유휴 상태인 경우에만 기회적으로 처리하며, 자원 경합을 일으키면 즉시 취소한다. 취소로 인한 정확도 저하를 막기 위해 모든 추측 요청들을 관리하고 (i) 해당 노드가 후속 단계에서 최우선 후보로 지정되면 자연 재검토, (ii) 탐색 종료 직전 상위 후보들에 대해 한정한 일괄 재검토를 수행하여 정확도를 보장한다. 두 동작은 경량 In-Storage Processing (ISP) 제어 유닛으로 구현된다.
평가는 MQSim에 탐색 알고리즘을 통합하여 수행하였으며, ISP를 위한 유닛과 읽기 재시도 변동을 포함한 환경에서 DiskANN, DiskANN++과 교차 비교하였다. 결과적으로 동일 리콜에서 더 낮은 지연을 일관되게 달성했으며, 읽기 재시도 강도가 증가해도 정규화 지연의 증가율이 완만하였다.
본 연구는 스케줄링의 효과로 인한 성능 향상을 패킹 여부에 상관없이 일관되게 검증했으며, 패킹과 결합 시 상호 보완적인 관계를 통해 더 좋은 성능을 나타냄을 보였다. 제안한 탐색 알고리즘은 SSD 상주 ANN 탐색의 지연 안정성과 처리 효율을 동시에 효과적으로 개선한다.

다국어 초록 (Multilingual Abstract)

Graph-based search for approximate vector similarity is essential in AI applications, such as retrieval-augmented generation. To support large-scale searches, vector search graphs are often stored on storage devices like SSDs. However, flash storage exhibits high and unpredictable read latency due to device-level characteristics. Static SSD scheduling exacerbates tail latency in the search process and degrades overall performance.
To address this, we introduce dynamic, SSD-aware scheduling mechanisms that classify expansions into mandatory and droppable or speculative requests, handling speculative requests only when channel and chip resources are idle and dropping them under contention. To preserve accuracy caused by dropping requests, we bound speculative request and perform selective re-examination of candidates before termination. These optimizations deliver significant performance gains over existing SSD-based graph search systems, including DiskANN and DiskANN++.

목차 (Table of Contents)

• Chapter 1. INTRODUCTION 1
• Chapter 2. Background 4
• 1. SSD Preliminary 4
• 2. Reliability Problems in NAND Flash 6
• 3. DiskANN Search 9
• 4. Packing 12
• Chapter 3. SEARCH ALGORITHM 14
• 1. Limitations of Beamsearch 15
• 2. Search Algorithm High-level Overview 17
• 3. Search Algorithm Details 21
• 4. Search SSD Structure 23
• Chapter 4. EVALUATION 25
• 1. Experimental Setup 25
• 2. Experimental Results 28
• Chapter 6. DISCUSSIONS 33
• Chapter 7. CONCLUSION 35