5장: DiskANN과 대규모 인덱싱 전략

학습 목표

• 디스크 기반 ANN이 필요한 이유를 이해합니다
• DiskANN의 핵심 아키텍처인 Vamana 그래프를 학습합니다
• SSD I/O 최적화 전략을 파악합니다
• 10억 개 이상의 벡터 스케일에서의 동작 원리를 이해합니다
• Fresh DiskANN과 Filtered DiskANN의 확장 기능을 살펴봅니다

디스크 기반 ANN의 필요성

3장에서 살펴본 것처럼, HNSW는 모든 벡터와 그래프를 메모리에 올려야 합니다. 10억 개의 768차원 벡터를 HNSW로 서비스하려면 약 300GB 이상의 메모리가 필요합니다. 이는 단일 서버 기준으로 매우 높은 비용입니다.

반면 SSD 스토리지는 메모리보다 약 10-20배 저렴합니다. 동일한 300GB를 SSD에 저장하면 비용이 크게 절감됩니다. 문제는 SSD의 랜덤 읽기 지연시간이 메모리보다 수십 배 느리다는 점입니다.

DiskANN은 Microsoft Research에서 2019년에 발표한 알고리즘으로, 이 지연시간 격차를 극복하면서도 높은 검색 성능을 달성합니다.

Vamana 그래프

DiskANN의 핵심 인덱스 구조는 Vamana 그래프입니다. HNSW가 다층 그래프를 사용하는 반면, Vamana는 단일 레이어 그래프에 두 가지 핵심 최적화를 적용합니다.

Medoid 시작점

Vamana 그래프의 시작점(entry point)은 전체 데이터셋의 Medoid — 모든 벡터까지의 평균 거리가 가장 작은 벡터입니다. 이는 HNSW의 임의 시작점보다 훨씬 좋은 출발점을 보장합니다.

RobustPrune: 장거리 + 단거리 연결

Vamana의 핵심 알고리즘은 RobustPrune입니다. 이웃을 선택할 때 두 가지 상반된 목표의 균형을 맞춥니다.

1. 단거리 연결: 가까운 이웃과의 연결로 정밀한 검색 보장
2. 장거리 연결: 먼 이웃과의 연결로 그래프의 네비게이션 효율성 보장

파라미터 alpha가 이 균형을 제어합니다. alpha가 1보다 크면 장거리 연결을 더 많이 유지하여 그래프의 직경(diameter)을 줄입니다.

def robust_prune(node, candidates, alpha, max_degree):
    """Vamana RobustPrune 의사 코드"""
    neighbors = []
    candidates = sorted(candidates, key=lambda c: distance(node, c))
 
    while candidates and len(neighbors) < max_degree:
        # 가장 가까운 후보 선택
        closest = candidates.pop(0)
        neighbors.append(closest)
 
        # alpha 기반 필터링: 이미 선택된 이웃을 통해
        # 도달 가능한 후보 제거
        candidates = [
            c for c in candidates
            if distance(node, c) <= alpha * distance(closest, c)
        ]
 
    return neighbors

HNSW vs Vamana 비교

SSD I/O 최적화

DiskANN이 SSD에서도 빠른 검색을 달성하는 핵심 전략들을 살펴보겠습니다.

정렬된 레이아웃

벡터와 그 이웃 정보를 SSD의 연속된 섹터에 배치합니다. 노드를 방문할 때 벡터 데이터와 이웃 목록을 단일 SSD 읽기로 가져올 수 있도록 최적화합니다.

SSD 블록 레이아웃:
+------------------+------------------+------------------+
| 노드 ID          | 벡터 데이터       | 이웃 ID 목록      |
| (4 bytes)        | (D x 4 bytes)    | (R x 4 bytes)    |
+------------------+------------------+------------------+

PQ 코드 인메모리 캐시

전체 벡터는 SSD에 저장하되, PQ 압축된 벡터는 메모리에 유지합니다. 검색 과정에서 후보 노드의 대략적인 거리를 메모리의 PQ 코드로 빠르게 계산하고, 유망한 후보만 SSD에서 정확한 벡터를 읽어옵니다.

이 전략으로 10억 개의 128차원 벡터를 인덱싱할 때, PQ 코드는 약 30-40GB의 메모리만 사용하면서 원본 벡터(약 500GB)는 SSD에 둘 수 있습니다.

빔 서치와 비동기 I/O

DiskANN의 검색은 빔 서치(Beam Search) 기반입니다. 여러 후보 경로를 동시에 탐색하면서, SSD 읽기를 비동기 I/O로 파이프라이닝합니다.

async def diskann_search(query, entry_point, beam_width, top_k):
    """DiskANN 검색 개념 (의사 코드)"""
    # 메모리의 PQ 코드로 시작점 주변 후보 평가
    beam = [entry_point]
    visited = set()
    results = []
 
    while beam:
        # PQ 코드로 후보 거리 대략 계산 (메모리)
        pq_distances = compute_pq_distances(query, beam)
 
        # 유망한 후보 W개의 정확한 벡터를 SSD에서 비동기 읽기
        promising = select_top(beam, pq_distances, beam_width)
        exact_vectors = await async_ssd_read(promising)
 
        # 정확한 거리 계산
        for node, vector in zip(promising, exact_vectors):
            dist = exact_distance(query, vector)
            results.append((node, dist))
            visited.add(node)
 
        # 새 후보 = 방문한 노드의 이웃 중 미방문 노드
        beam = get_unvisited_neighbors(promising, visited)
 
    return sorted(results, key=lambda x: x[1])[:top_k]

10억+ 벡터 스케일 성능

DiskANN은 Microsoft의 내부 벤치마크에서 다음과 같은 성능을 보고했습니다.

같은 데이터셋에서 인메모리 HNSW는 수백 GB의 메모리가 필요한 반면, DiskANN은 PQ 코드와 메타데이터만 메모리에 유지하므로 메모리 사용량이 5-10배 적습니다.

Fresh DiskANN: 동적 업데이트

초기 DiskANN은 정적 인덱스만 지원했습니다. 벡터를 추가하거나 삭제하려면 전체 인덱스를 재구축해야 했습니다. Fresh DiskANN은 이 한계를 해결합니다.

동적 업데이트 메커니즘

Fresh DiskANN은 두 가지 구조를 유지합니다.

1. 메인 인덱스 (SSD): 대부분의 벡터를 저장하는 정적 Vamana 그래프
2. 델타 인덱스 (메모리): 새로 추가/삭제된 벡터를 임시 저장하는 인메모리 인덱스

검색 시 두 인덱스를 모두 탐색하고 결과를 병합합니다. 델타 인덱스가 일정 크기에 도달하면 메인 인덱스와 병합(compaction)합니다.

Filtered DiskANN

Filtered DiskANN은 메타데이터 필터링과 벡터 검색을 효율적으로 결합합니다. 일반적인 접근법은 벡터 검색 후 필터를 적용(사후 필터링)하거나, 필터를 먼저 적용한 뒤 벡터 검색(사전 필터링)하는 것입니다. 두 방식 모두 극단적인 경우 성능이 급격히 떨어집니다.

Filtered DiskANN은 필터 조건별로 별도의 시작점(entry point)을 유지하고, 그래프 탐색 과정에서 필터 조건에 맞는 노드만 방문하도록 최적화합니다. 이를 통해 필터 선택성(selectivity)이 매우 높거나 낮은 경우에도 안정적인 성능을 유지합니다.

언제 DiskANN을 선택할 것인가

DiskANN을 채택한 솔루션들

• Microsoft Azure AI Search: DiskANN 기반의 벡터 인덱스
• pgvectorscale: PostgreSQL 확장으로 StreamingDiskANN 인덱스 제공
• Weaviate: 실험적으로 DiskANN 기반 인덱스 지원

정리

이번 장에서는 디스크 기반 ANN 알고리즘인 DiskANN의 아키텍처와 최적화 전략을 심층 분석했습니다. Vamana 그래프의 RobustPrune 알고리즘, PQ 인메모리 캐시, 비동기 I/O 파이프라이닝을 통해 SSD에서도 높은 검색 성능을 달성합니다. Fresh DiskANN으로 동적 업데이트가 가능해졌고, Filtered DiskANN으로 메타데이터 필터링도 효율적으로 처리할 수 있습니다.

3장부터 5장까지 세 가지 핵심 ANN 인덱싱 알고리즘을 살펴보았습니다. 다음 장부터는 이 알고리즘들을 실제로 사용하는 벡터 데이터베이스 솔루션들을 하나씩 심층 분석합니다. 6장에서는 완전 관리형 서비스인 Pinecone을 다루겠습니다.