본문 바로가기
WIKI 기술 지식 베이스

DISKANN

원문 보기 위키 갱신

대규모 시나리오, 특히 데이터셋이 수십억 또는 수조 개의 벡터를 포함하는 경우에는 표준 인메모리 인덱싱 방식(예: HNSW, IVF_FLAT)이 메모리 한계 때문에 따라잡지 못하는 경우가 많아요. DISKANN은 데이터셋 크기가 사용 가능한 RAM을 초과할 때 높은 검색 정확도와 속도를 유지함으로써 이러한 문제를 해결하는 디스크 기반 접근 방식을 제공해요.

출처: Milvus 문서

본문

개요 (Overview)

DISKANN은 효율적인 벡터 검색을 위해 두 가지 핵심 기법을 결합해요.

  • Vamana Graph – 검색 중 효율적인 네비게이션을 위해 데이터 포인트(또는 벡터)를 연결하는 디스크 기반, 그래프 기반 인덱스예요.
  • Product Quantization (PQ) – 벡터의 크기를 줄여 벡터 간 빠른 근사 거리 계산을 가능하게 하는 인메모리 압축 방법이에요.

인덱스 구축 (Index construction)

Vamana 그래프

Vamana 그래프는 DISKANN의 디스크 기반 전략의 핵심이에요. 구축 중이나 구축 후에 완전히 메모리에 상주할 필요가 없기 때문에 매우 큰 데이터셋을 처리할 수 있어요.

다음 그림은 Vamana 그래프가 어떻게 구축되는지 보여 줘요.

Diskann

  • 초기 무작위 연결: 각 데이터 포인트(벡터)는 그래프의 노드로 표현돼요. 이 노드들은 처음에 무작위로 연결되어 밀집된 네트워크를 형성해요. 일반적으로 노드는 넓은 연결성을 위해 약 500개의 에지(연결)로 시작해요.
  • 효율성을 위한 정제: 초기 무작위 그래프는 검색에 더 효율적으로 만들기 위한 최적화 과정을 거쳐요. 여기에는 두 가지 핵심 단계가 포함돼요.

중복 에지 제거(Pruning redundant edges): 알고리즘은 노드 간 거리를 기준으로 불필요한 연결을 제거해요. 이 단계는 더 높은 품질의 에지를 우선해요. max_degree 파라미터는 노드당 최대 에지 수를 제한해요. max_degree가 높을수록 그래프가 더 밀집해져 관련 이웃을 더 많이 찾을 수 있지만(리콜 향상), 메모리 사용량과 검색 시간도 늘어나요.

  • 전략적 단축키 추가(Adding strategic shortcuts): Vamana는 벡터 공간에서 멀리 떨어진 데이터 포인트를 연결하는 장거리 에지를 도입해요. 이 단축키는 검색이 중간 노드를 건너뛰고 그래프를 빠르게 점프할 수 있게 해 네비게이션을 크게 가속화해요. search_list_size 파라미터는 그래프 정제 과정의 폭을 결정해요. search_list_size가 높을수록 구축 중 이웃 검색이 확장되어 최종 정확도가 향상될 수 있지만 인덱스 구축 시간이 늘어나요.

파라미터 튜닝에 대한 자세한 내용은 DISKANN params를 참고하세요.

PQ

DISKANN은 고차원 벡터를 더 작은 표현(PQ codes)으로 압축하기 위해 PQ를 사용하며, 이를 메모리에 저장해 빠른 근사 거리 계산을 수행해요.

pq_code_budget_gb_ratio 파라미터는 이 PQ 코드를 저장하는 데 할당되는 메모리 사용량을 관리해요. 이는 벡터의 총 크기(GB)와 PQ 코드 저장을 위해 할당된 공간 사이의 비율을 나타내요. 실제 PQ 코드 예산(GB)은 다음 공식으로 계산할 수 있어요.

PQ Code Budget (GB) = vec_field_size_gb * pq_code_budget_gb_ratio

여기서:

  • vec_field_size_gb는 벡터의 총 크기(GB)예요.
  • pq_code_budget_gb_ratio는 사용자 정의 비율로, 총 데이터 크기 중 PQ 코드에 예약되는 분율을 나타내요. 이 파라미터는 검색 정확도와 메모리 리소스 사이의 트레이드오프를 허용해요. 파라미터 튜닝에 대한 자세한 내용은 DISKANN configs를 참고하세요.

기본 PQ 방법에 대한 기술적 세부 사항은 IVF_PQ를 참고하세요.

검색 과정 (Search process)

인덱스(디스크의 Vamana 그래프와 메모리의 PQ 코드)가 구축되면 DISKANN은 다음과 같이 ANN 검색을 수행해요.

Diskann 2

  • 쿼리와 진입점: 쿼리 벡터가 제공되어 가장 가까운 이웃을 찾아요. DISKANN은 Vamana 그래프의 선택된 진입점에서 시작하는데, 이는 종종 데이터셋의 전역 중심점에 가까운 노드예요. 전역 중심점은 모든 벡터의 평균을 나타내며, 원하는 이웃을 찾기 위한 그래프 통과 거리를 최소화하는 데 도움이 돼요.
  • 이웃 탐색: 알고리즘은 현재 노드의 에지에서 잠재적 후보 이웃(그림의 빨간 원)을 수집하며, 인메모리 PQ 코드를 활용해 이 후보들과 쿼리 벡터 사이의 거리를 근사해요. 이 잠재적 후보 이웃들은 Vamana 그래프에서 선택된 진입점에 에지로 직접 연결된 노드들이에요.
  • 정확한 거리 계산을 위한 노드 선택: 근사 결과에서 가장 유망한 이웃의 하위 집합(그림의 초록 원)이 원래의 압축되지 않은 벡터를 사용해 정밀 거리 평가를 위해 선택돼요. 이는 디스크에서 데이터를 읽어야 하므로 시간이 걸릴 수 있어요. DISKANN은 정확도와 속도 사이의 이 섬세한 균형을 제어하기 위해 두 가지 파라미터를 사용해요.

beam_width_ratio: 검색의 폭을 제어하는 비율로, 이웃을 탐색하기 위해 병렬로 선택되는 후보 이웃 수를 결정해요. beam_width_ratio가 클수록 탐색이 넓어져 정확도는 높아질 수 있지만 계산 비용과 디스크 I/O가 늘어나요. 빔 폭, 즉 선택되는 노드 수는 다음 공식으로 결정돼요: Beam width = Number of CPU cores * beam_width_ratio.

  • search_cache_budget_gb_ratio: 자주 접근되는 디스크 데이터를 캐시하기 위해 할당되는 메모리 비율이에요. 이 캐싱은 디스크 I/O를 최소화해, 데이터가 이미 메모리에 있으므로 반복 검색을 더 빠르게 만들어요.

파라미터 튜닝에 대한 자세한 내용은 DISKANN configs를 참고하세요.

  • 반복 탐색: 검색은 후보 집합을 반복적으로 정제하며, 충분한 수의 이웃을 찾을 때까지 근사 평가(PQ 사용) 다음 정밀 검사(디스크의 원래 벡터 사용)를 반복해요.

Milvus에서 DISKANN 활성화 (Enable DISKANN in Milvus)

기본적으로 Milvus에서는 DISKANN이 비활성화되어 있어 RAM에 잘 맞는 데이터셋에 대한 인메모리 인덱스의 속도를 우선해요. 하지만 거대한 데이터셋으로 작업하거나 DISKANN의 확장성과 SSD 최적화를 활용하고 싶다면 쉽게 활성화할 수 있어요.

Milvus에서 DISKANN을 활성화하는 방법은 다음과 같아요.

  • Milvus 설정 파일 업데이트

Milvus 설정 파일을 찾아보세요. (이 파일을 찾는 방법은 Milvus Configuration에 관한 문서를 참고하세요.)

queryNode.enableDisk 파라미터를 찾아 값을 true로 설정해요.

 queryNode:
     enableDisk: true # Enables query nodes to load and search using the on-disk index
  • DISKANN을 위한 저장소 최적화

DISKANN에서 최상의 성능을 보장하려면 Milvus 데이터를 빠른 NVMe SSD에 저장하는 것이 좋아요. Milvus Standalone과 Cluster 배포 모두에 대해 이렇게 하는 방법은 다음과 같아요.

  • Milvus Standalone

Milvus 컨테이너 내에서 Milvus 데이터 디렉터리를 NVMe SSD에 마운트해요. docker-compose.yml 파일이나 다른 컨테이너 관리 도구로 이 작업을 수행할 수 있어요.

  • 예를 들어 NVMe SSD가 /mnt/nvme에 마운트되어 있다면, docker-compose.yml의 volumes 섹션을 이렇게 업데이트해요.
 volumes:
      - /mnt/nvme/volumes/milvus:/var/lib/milvus
  • Milvus Cluster

QueryNode와 IndexNode 컨테이너 양쪽에서 Milvus 데이터 디렉터리를 NVMe SSD에 마운트해요. 컨테이너 오케스트레이션 설정을 통해 이 작업을 수행할 수 있어요.

  • 두 노드 유형 모두에서 데이터를 NVMe SSD에 마운트하면 검색과 인덱싱 연산 모두에 빠른 읽기와 쓰기 속도를 보장해요.

이 변경을 한 뒤 Milvus 인스턴스를 재시작해 설정이 적용되게 해요. 이제 Milvus는 DISKANN의 기능을 활용해 대규모 데이터셋을 처리하고 효율적이고 확장 가능한 벡터 검색을 제공해요.

DISKANN 구성 (Configure DISKANN)

DISKANN 관련 파라미터는 Milvus 설정 파일(milvus.yaml)을 통해서만 구성할 수 있어요.

# milvus.yaml
common:
  DiskIndex:
    MaxDegree: 56  # Maximum degree of the Vamana graph
    SearchListSize: 100  # Size of the candidate list during building graph
    PQCodeBudgetGBRatio: 0.125  # Size limit on the PQ code (compared with raw data)
    SearchCacheBudgetGBRatio: 0.1 # Ratio of cached node numbers to raw data
    BeamWidthRatio: 4 # Ratio between the maximum number of IO requests per search iteration and CPU number

파라미터 설명에 대한 자세한 내용은 DISKANN params를 참고하세요.

DISKANN 파라미터 (DISKANN params)

DISKANN 파라미터를 미세 조정하면 속도, 정확도, 메모리 사용량 사이의 적절한 균형을 맞춰 특정 데이터셋과 검색 워크로드에 맞게 동작을 조정할 수 있어요.

인덱스 구축 파라미터 (Index building params)

이 파라미터들은 DISKANN 인덱스가 어떻게 구축되는지에 영향을 줘요. 조정하면 인덱스 크기, 구축 시간, 검색 품질에 영향을 줄 수 있어요.

아래 목록의 모든 인덱스 구축 파라미터는 Milvus 설정 파일(milvus.yaml)을 통해서만 구성할 수 있어요.

파라미터 설명 값 범위 튜닝 제안
Vamana MaxDegree Vamana 그래프에서 각 데이터 포인트가 가질 수 있는 최대 연결(에지) 수를 제어해요. 타입: Integer
범위: [1, 512]
기본값: 56		 값이 높을수록 더 밀집한 그래프를 만들어 리콜이 높아질 수 있지만 메모리 사용량과 구축 시간도 늘어나요. 대부분의 경우 [10, 100] 범위 내 값을 권장해요.
SearchListSize 인덱스 구축 중 각 노드의 최근접 이웃을 검색할 때 사용하는 후보 풀 크기를 정의해요. 그래프에 추가되는 각 노드에 대해 알고리즘은 지금까지 찾은 최상의 search_list_size 후보 목록을 유지해요. 이 목록이 더 이상 개선될 수 없으면 이웃 검색이 멈춰요. 최종 후보 풀에서 상위 max_degree개 노드가 최종 에지를 형성하기 위해 선택돼요. 타입: Integer
범위: [1, int_max]
기본값: 100		 search_list_size가 클수록 각 노드의 진정한 최근접 이웃을 찾을 가능성이 높아져 더 높은 품질의 그래프와 더 나은 검색 성능(리콜)을 얻을 수 있어요. 하지만 인덱스 구축 시간이 크게 늘어나요. 항상 max_degree보다 크거나 같은 값으로 설정해야 해요.
SearchCacheBudgetGBRatio 인덱스 구축 중 그래프에서 자주 접근되는 부분을 캐시하기 위해 할당되는 메모리 양을 제어해요. 타입: Float
범위: [0.0, 0.3)
기본값: 0.10		 값이 높을수록 캐싱에 더 많은 메모리를 할당해 디스크 I/O를 크게 줄이지만 시스템 메모리를 더 많이 소모해요. 값이 낮을수록 캐싱에 메모리를 덜 사용해 디스크 접근 필요성이 늘어날 수 있어요. 대부분의 경우 [0.0, 0.3) 범위 내 값을 권장해요.
PQ PQCodeBudgetGBRatio 압축되지 않은 데이터 크기와 비교한 PQ 코드(데이터 포인트의 압축 표현)의 크기를 제어해요. 타입: Float
범위: (0.0, 0.25]
기본값: 0.125		 비율이 높을수록 PQ 코드에 메모리 비중을 더 많이 할당해 원본 벡터에 대한 더 많은 정보를 효과적으로 저장하므로 검색 결과가 더 정확해져요. 하지만 더 많은 메모리가 필요해 대규모 데이터셋 처리 용량이 제한돼요. 비율이 낮을수록 메모리 사용량을 줄이지만, PQ 코드가 더 적은 정보를 유지하므로 정확도를 희생할 수 있어요. 메모리 제약이 우려되는 시나리오에 적합하며 더 큰 데이터셋 인덱싱을 가능하게 할 수 있어요. 대부분의 경우 (0.0625, 0.25] 범위 내 값을 권장해요.

인덱스별 검색 파라미터 (Index-specific search params)

이 파라미터들은 DISKANN이 어떻게 검색을 수행하는지에 영향을 줘요. 조정하면 검색 속도, 지연 시간, 리소스 사용량에 영향을 줄 수 있어요.

아래 목록의 BeamWidthRatio는 Milvus 설정 파일(milvus.yaml)을 통해서만 구성할 수 있어요.

아래 목록의 search_list는 SDK의 검색 파라미터에서만 구성할 수 있어요.

파라미터 설명 값 범위 튜닝 제안
Vamana BeamWidthRatio 사용 가능한 CPU 코어 수 대비 최대 병렬 디스크 I/O 요청 수를 결정해 검색 중 병렬 처리 정도를 제어해요. 타입: Float
범위: [1, max(128 / CPU number, 16)]
기본값: 4.0		 값이 높을수록 병렬 처리가 늘어나 강력한 CPU와 SSD가 있는 시스템에서 검색을 빨라지게 할 수 있어요. 하지만 너무 높게 설정하면 과도한 리소스 경합이 발생할 수 있어요. 대부분의 경우 [1.0, 4.0] 범위 내 값을 권장해요.
search_list 검색 연산 중 그래프를 탐색하면서 알고리즘이 유지하는 후보 풀의 크기를 결정해요. 값이 클수록 진정한 최근접 이웃을 찾을 가능성(리콜 향상)이 높아지지만 검색 지연도 늘어나요. 타입: Integer
범위: [1, int_max]
기본값: 100		 성능과 정확도의 좋은 균형을 위해 이 값을 가져오려는 결과 수(top_k)와 같거나 약간 크게 설정하는 것을 권장해요.

더 알아보기 (Learn more)

  • HNSW — 다른 인메모리 인덱스 방식
  • IVF_FLAT — 다른 인메모리 인덱스 방식
  • IVF_PQ — PQ 양자화 기술

함께 읽는 실무 이야기

우리 조직에도 적용하고 싶다면, AI 시스템 구축 서비스를 살펴보세요.