[Paper] 배턴을 넘기며: 고처리량 분산 디스크 기반 벡터 검색 with BatANN

Source: arXiv - 2512.09331v1

Overview

이 논문은 BatANN이라는 분산 디스크 기반 근사 최근접 이웃(ANN) 엔진을 소개한다. 이 엔진은 단일 노드 그래프 인덱스가 제공하는 저지연·로그 시간 보장을 유지하면서 수십억 개의 고차원 벡터를 여러 머신에 걸쳐 검색할 수 있게 한다. “배턴을 넘기는” 방식—전체 쿼리 상태를 다음 그래프 부분을 소유한 노드에 전달함—을 통해 BatANN은 지연 시간을 십밀리초 수준으로 유지하면서 거의 선형에 가까운 처리량 확장을 달성한다.

Key Contributions

• Single Global Graph Across Nodes – 여러 서버에 걸쳐 단일 ANN 그래프를 샤딩하면서 로그 탐색 경로 길이를 보존하는 최초의 오픈소스 시스템.
• Baton‑Passing Query Model – 검색 단계가 다른 머신에 저장된 이웃에 도달하면 전체 쿼리 컨텍스트를 전송하여 원격 노드가 로컬에서 탐색을 계속하고 왕복 통신을 최소화한다.
• Near‑Linear Throughput Scaling – 1억·10억 벡터 데이터셋에서 표준 TCP만 사용했을 때, 단순 scatter‑gather 기반 대비 2.5‑6.5배 높은 처리량을 입증.
• Low Latency on Disk‑Based Indexes – 인덱스가 SSD에 존재하고 데이터셋이 RAM을 크게 초과하더라도 평균 지연시간을 6 ms 이하로 유지.
• Open‑Source Release – 대규모 벡터 검색 서비스를 구축할 수 있는 프로덕션 수준 코드베이스를 커뮤니티에 제공.

Methodology

1. Graph Construction – 전체 데이터셋에 대해 HNSW‑스타일 계층적 네비게이션 그래프를 구축한 뒤, 간단한 해시 기반 샤딩 방식을 이용해 그래프 정점을 서버에 분산한다.
2. Query State Packaging – 쿼리는 현재 노드 ID, 쿼리 벡터, 그리고 후보 이웃들의 작은 우선순위 큐로 구성된다. 탐색이 다른 서버가 소유한 정점에 도달하면 이 전체 상태 패킷을 TCP로 전송한다.
3. Remote Execution – 수신 서버는 그래프 탐색을 로컬에서 재개하고, 이웃을 확장하며 후보 큐를 업데이트하고, 필요 시 다시 배턴을 전달한다. 초기 요청 이후 중앙 코디네이터는 필요하지 않다.
4. Termination – 후보 큐가 안정화될 때(즉, 더 좋은 이웃이 발견되지 않을 때) 탐색을 종료하고 최종 top‑k 결과를 클라이언트에 반환한다.
5. Evaluation – 상용 SSD를 장착한 일반 서버에서 벤치마크를 수행했으며, recall(≈0.95), 처리량(초당 쿼리 수), 평균 지연시간을 클러스터 규모(1‑10 노드)와 데이터셋 규모(1억·10억 벡터)별로 측정했다.

Results & Findings

• Scalability: 처리량이 서버를 추가함에 따라 거의 선형적으로 증가하여 배턴 패싱 방식의 효과를 입증한다.
• Network Efficiency: RDMA나 맞춤형 프로토콜 없이 순수 TCP만 사용해도 높은 성능을 달성, 데이터센터 일반 네트워킹 환경에서도 견고함을 보여준다.
• Recall vs. Speed Trade‑off: BatANN은 단일 노드 HNSW 인덱스와 동일한 recall을 유지하면서, 대규모 데이터셋에서 수십 배 높은 쿼리 속도를 제공한다.

Practical Implications

• RAG & LLM Pipelines: 개발자는 수십억 개의 임베딩을 보유한 실제적인 대규모 벡터 스토어를 Retrieval‑Augmented Generation 시스템에 연결할 수 있어, 지연시간 부담 없이 더 풍부한 컨텍스트 윈도우를 활용할 수 있다.
• Search‑as‑a‑Service: SaaS 제공자는 이미지, 오디오, 코드 스니펫 등 유사도 검색을 고처리량으로 제공하면서, 대부분의 인덱스를 저렴한 SSD‑백엔드 노드에 오프로드해 하드웨어 비용을 절감할 수 있다.
• Hybrid Cloud Deployments: BatANN은 표준 TCP 위에서 동작하므로 온‑프레미스 클러스터, 퍼블릭 클라우드, 엣지 위치 등 다양한 환경에 별도 네트워킹 스택 없이 배포 가능하다.
• Open‑Source Extensibility: 팀은 레포지토리를 포크해 커스텀 거리 측정 함수, 보안 계층(TLS, 인증) 등을 통합하거나 기존 벡터 데이터베이스(예: Milvus, Vespa)와 결합해 통합 스택을 구성할 수 있다.

Limitations & Future Work

• Sharding Simplicity: 현재 해시 기반 파티셔닝은 데이터 분포가 편향될 경우 로드 불균형을 초래할 수 있다; 그래프 구조를 고려한 고급 파티셔너가 균형을 개선할 수 있다.
• Fault Tolerance: 논문은 성능에 초점을 맞추었으며, 노드 장애 시 쿼리 정확성을 유지하는 방안은 향후 엔지니어링 과제로 남는다.
• GPU Acceleration: 모든 실험이 CPU 전용 노드에서 수행되었으며, GPU 기반 거리 계산을 도입하면 연산 집약적인 메트릭에서 처리량을 추가로 끌어올릴 수 있다.
• Dynamic Updates: 벡터 삽입·삭제는 전체 재구축 또는 복잡한 재균형이 필요하므로, 증분 업데이트 메커니즘이 향후 연구 과제로 남아 있다.

BatANN은 스마트한 쿼리‑핸드오프 전략을 통해 분산 디스크 기반 벡터 검색이 빠르고 확장 가능함을 증명한다—이는 개발자들이 페타바이트 규모 임베딩 스토어 위에 차세대 검색 서비스를 구축할 수 있는 길을 열어준다.

Authors

• Nam Anh Dang
• Ben Landrum
• Ken Birman

Paper Information

• arXiv ID: 2512.09331v1
• Categories: cs.DC, cs.IR
• Published: December 10, 2025
• PDF: Download PDF