논문 읽기｜HM-ANN: ANNS가 이기종 메모리를 만났을 때
HM-ANN: 이기종 메모리에서의 효율적인 10억 포인트 최근접 이웃 검색은 2020년 신경정보처리시스템 학회(NeurIPS 2020)에서 채택된 연구 논문입니다. 이 논문에서는 HM-ANN이라 불리는 그래프 기반 유사도 검색을 위한 새로운 알고리즘이 제안됩니다. 이 알고리즘은 최신 하드웨어 환경에서 메모리 이질성과 데이터 이질성을 모두 고려합니다. HM-ANN은 압축 기술 없이 단일 머신에서 10억 규모 유사도 검색을 가능하게 합니다. 이기종 메모리(HM)는 빠르지만 작은 동적 랜덤 액세스 메모리(DRAM)와 느리지만 큰 영구 메모리(PMem)의 조합을 나타냅니다. HM-ANN은 특히 데이터셋이 DRAM에 들어가지 않는 경우 낮은 검색 지연 시간과 높은 검색 정확도를 달성합니다. 이 알고리즘은 최신 근사 최근접 이웃(ANN) 검색 솔루션에 비해 뚜렷한 이점을 가집니다.
동기
ANN 검색 알고리즘은 등장 이래 제한된 DRAM 용량으로 인해 쿼리 정확도와 쿼리 지연 시간 사이의 근본적인 트레이드오프를 제기해 왔습니다. 빠른 쿼리 접근을 위해 인덱스를 DRAM에 저장하려면 데이터 포인트 수를 제한하거나 압축된 벡터를 저장해야 하며, 둘 다 검색 정확도를 떨어뜨립니다. 그래프 기반 인덱스(예: Hierarchical Navigable Small World, HNSW)는 뛰어난 쿼리 실행 시간 성능과 쿼리 정확도를 갖습니다. 그러나 이러한 인덱스도 10억 규모 데이터셋에서 작동할 때 1TiB 수준의 DRAM을 소비할 수 있습니다.
DRAM이 원시 형식의 10억 규모 데이터셋을 저장하지 않도록 하는 다른 우회 방법도 있습니다. 데이터셋이 단일 머신의 메모리에 들어가기에는 너무 클 때, 데이터셋 포인트의 product quantization과 같은 압축 접근 방식이 사용됩니다. 그러나 압축된 데이터셋을 사용하는 이러한 인덱스의 재현율은 양자화 과정에서 정밀도가 손실되기 때문에 일반적으로 낮습니다. Subramanya et al. [1]은 Disk-ANN이라는 접근 방식으로 SSD(solid-state drive)를 활용하여 단일 머신에서 10억 규모 ANN 검색을 달성하는 방법을 탐구하며, 여기서 원시 데이터셋은 SSD에 저장되고 압축 표현은 DRAM에 저장됩니다.
이기종 메모리 소개
HMxx를 포함한 메모리/스토리지 계층 구조 그림 이름
HMxx를 포함한 메모리/스토리지 계층 구조 그림 이름
출처: http://nvmw.ucsd.edu/nvmw2021-program/nvmw2021-data/nvmw2021-paper63-presentation_slides.pdf
이기종 메모리(HM)는 빠르지만 작은 DRAM과 느리지만 큰 PMem의 조합을 나타냅니다. DRAM은 모든 최신 서버에서 찾을 수 있는 일반적인 하드웨어이며, 접근 속도는 비교적 빠릅니다. Intel® Optane™ DC Persistent Memory Modules와 같은 새로운 PMem 기술은 NAND 기반 플래시(SSD)와 DRAM 사이의 격차를 메워 I/O 병목을 제거합니다. PMem은 SSD처럼 내구성이 있으며, 메모리처럼 CPU에서 직접 주소 지정이 가능합니다. Renen et al. [2]는 구성된 실험 환경에서 PMem 읽기 대역폭이 DRAM보다 2.6배 낮고, 쓰기 대역폭은 7.5배 낮다는 것을 발견했습니다.
HM-ANN 설계
HM-ANN은 압축 없이 단일 머신에서 실행되는 정확하고 빠른 10억 규모 ANN 검색 알고리즘입니다. HM-ANN의 설계는 HNSW의 아이디어를 일반화하며, HNSW의 계층 구조는 자연스럽게 HM에 적합합니다. HNSW는 여러 계층으로 구성됩니다—계층 0만 전체 데이터셋을 포함하고, 나머지 각 계층은 바로 아래 계층의 요소 부분집합을 포함합니다.
3개 계층을 가진 HNSW의 예
출처: https://arxiv.org/pdf/1603.09320.pdf
- 데이터셋의 일부만 포함하는 상위 계층의 요소들은 전체 스토리지의 작은 부분을 소비합니다. 이러한 관찰은 이들을 DRAM에 배치하기에 적절한 후보로 만듭니다. 이렇게 하면 HM-ANN에서의 검색 대부분이 상위 계층에서 발생할 것으로 예상되며, 이는 DRAM의 빠른 접근 특성 활용을 극대화합니다. 그러나 HNSW의 경우 대부분의 검색은 하위 계층에서 발생합니다.
- 최하위 계층은 전체 데이터셋을 담고 있으므로 PMem에 배치하기에 적합합니다. 계층 0에 접근하는 것은 더 느리기 때문에, 각 쿼리가 접근하는 부분을 작게 유지하고 접근 빈도를 줄이는 것이 바람직합니다.
그래프 구축 알고리즘
HM-ANN의 그래프 구축 예시
출처: http://nvmw.ucsd.edu/nvmw2021-program/nvmw2021-data/nvmw2021-paper63-poster.pdf
HM-ANN 구축의 핵심 아이디어는 계층 0에서의 검색을 위해 더 나은 탐색을 제공하도록 고품질 상위 계층을 만드는 것입니다. 따라서 대부분의 메모리 접근은 DRAM에서 발생하고, PMem에서의 접근은 줄어듭니다. 이를 가능하게 하기 위해 HM-ANN의 구축 알고리즘에는 하향식 삽입 단계와 상향식 승격 단계가 있습니다.
하향식 삽입 단계는 최하위 계층이 PMem에 배치될 때 탐색 가능한 small-world 그래프를 구축합니다.
상향식 승격 단계는 정확도를 크게 잃지 않으면서 DRAM에 배치되는 상위 계층을 형성하기 위해 하위 계층의 피벗 포인트를 승격합니다. 계층 0의 요소들에 대한 고품질 투영이 계층 1에 생성되면, 계층 0에서의 검색은 몇 번의 홉만으로 쿼리의 정확한 최근접 이웃을 찾습니다.
- 승격에 HNSW의 무작위 선택을 사용하는 대신, HM-ANN은 계층 0에서 차수가 가장 높은 요소들을 계층 1로 승격하는 고차수 승격 전략을 사용합니다. 더 높은 계층의 경우, HM-ANN은 승격률을 기반으로 고차수 노드를 상위 계층으로 승격합니다.
- HM-ANN은 계층 0에서 계층 1로 더 많은 노드를 승격하고, 계층 1의 각 요소에 대해 더 큰 최대 이웃 수를 설정합니다. 상위 계층의 노드 수는 사용 가능한 DRAM 공간에 의해 결정됩니다. 계층 0은 DRAM에 저장되지 않으므로, DRAM에 저장되는 각 계층을 더 조밀하게 만들면 검색 품질이 향상됩니다.
그래프 검색 알고리즘
HM-ANN의 그래프 검색 예시
출처: http://nvmw.ucsd.edu/nvmw2021-program/nvmw2021-data/nvmw2021-paper63-poster.pdf
검색 알고리즘은 두 단계로 구성됩니다: 빠른 메모리 검색과 프리페칭을 사용하는 병렬 계층-0 검색입니다.
빠른 메모리 검색
HNSW에서와 마찬가지로, DRAM에서의 검색은 최상위 계층의 진입점에서 시작한 다음 최상위 계층부터 계층 2까지 1-greedy 검색을 수행합니다. 계층 0에서 검색 공간을 좁히기 위해, HM-ANN은 계층 1에서 후보 목록의 크기를 제한하는 efSearchL1 검색 예산으로 검색을 수행합니다. 해당 목록의 후보들은 계층 0에서의 검색을 위한 여러 진입점으로 사용되어 계층 0의 검색 품질을 향상합니다. HNSW가 하나의 진입점만 사용하는 반면, HM-ANN에서는 계층 0과 계층 1 사이의 간격이 다른 두 계층 사이의 간격보다 더 특별하게 처리됩니다.
프리페칭을 사용하는 병렬 계층-0 검색
하위 계층에서 HM-ANN은 앞서 계층 1 검색에서 얻은 후보들을 균등하게 분할하고, 이를 진입점으로 보고 스레드를 사용해 병렬 multi-start 1-greedy 검색을 수행합니다. 각 검색의 상위 후보들을 수집하여 최적의 후보들을 찾습니다. 알려진 바와 같이, 계층 1에서 계층 0으로 내려가는 것은 정확히 PMem으로 가는 것입니다. 병렬 검색은 PMem의 지연 시간을 숨기고 메모리 대역폭을 최대한 활용하여, 검색 시간을 늘리지 않고 검색 품질을 향상합니다.
HM-ANN은 메모리 액세스가 발생하기 전에 PMem에서 데이터를 프리페치하기 위해 DRAM에 소프트웨어 관리 버퍼를 구현한다. 레이어 1을 검색할 때, HM-ANN은 efSearchL1에 있는 후보들의 이웃 요소와 레이어 1에서 이웃 요소들의 연결을 PMem에서 버퍼로 비동기적으로 복사한다. 레이어 0에서 검색이 발생할 때, 액세스될 데이터의 일부는 이미 DRAM에 프리페치되어 있으며, 이는 PMem 액세스 지연 시간을 숨기고 더 짧은 쿼리 시간으로 이어진다. 이는 대부분의 메모리 액세스가 DRAM에서 발생하고 PMem의 메모리 액세스가 줄어드는 HM-ANN의 설계 목표와 일치한다.
평가
이 논문에서는 광범위한 평가가 수행된다. 모든 실험은 Intel Xeon Gold 6252 CPU@2.3GHz가 탑재된 머신에서 수행된다. 빠른 메모리로 DDR4(96GB)를 사용하고 느린 메모리로 Optane DC PMM(1.5TB)을 사용한다. 다섯 개의 데이터셋이 평가된다: BIGANN, DEEP1B, SIFT1M, DEEP1M, GIST1M. 십억 규모 테스트의 경우 다음 방식들이 포함된다: 십억 규모 양자화 기반 방법(IMI+OPQ 및 L&C), 비압축 기반 방법(HNSW 및 NSG).
십억 규모 알고리즘 비교
Table 1.
표 1에서는 서로 다른 그래프 기반 인덱스의 빌드 시간과 저장 공간을 비교한다. HNSW는 가장 짧은 빌드 시간을 보이며, HM-ANN은 HNSW보다 8%의 추가 시간이 필요하다. 전체 저장 공간 사용량 측면에서 HM-ANN 인덱스는 HSNW보다 5–13% 더 크다. 이는 레이어 0에서 레이어 1로 더 많은 노드를 승격시키기 때문이다.
Figure 1.
그림 1에서는 서로 다른 인덱스의 쿼리 성능을 분석한다. 그림 1 (a)와 (b)는 HM-ANN이 1ms 이내에 > 95%의 top-1 recall을 달성함을 보여준다. 그림 1 (c)와 (d)는 HM-ANN이 4 ms 이내에 > 90%의 top-100 recall을 얻음을 보여준다. HM-ANN은 다른 모든 접근 방식보다 최고의 지연 시간 대비 recall 성능을 제공한다.
백만 규모 알고리즘 비교
Figure 2.
그림 2에서는 순수 DRAM 설정에서 서로 다른 인덱스의 쿼리 성능을 분석한다. HNSW, NSG, HM-ANN은 DRAM에 적합한 세 개의 백만 규모 데이터셋으로 평가된다. HM-ANN은 여전히 HNSW보다 더 나은 쿼리 성능을 달성한다. 그 이유는 99% recall 목표를 달성하기 위해 HM-ANN의 총 거리 계산 수(평균 850/query)가 HNSW의 총 거리 계산 수(평균 900/query)보다 낮기 때문이다.
고차수 승격의 효과
그림 3에서는 동일한 구성에서 무작위 승격과 고차수 승격 전략을 비교한다. 고차수 승격은 기준선을 능가한다. 고차수 승격은 각각 95%, 99%, 99.5% recall 목표에 도달하는 데 무작위 승격보다 1.8배, 4.3배, 3.9배 더 빠르게 수행된다.
메모리 관리 기법의 성능 이점
그림 5는 HM-ANN의 각 최적화가 개선에 어떻게 기여하는지 보여주기 위해 HNSW와 HM-ANN 사이의 일련의 단계를 포함한다. BP는 인덱스 구축 중 Bottom-up Promotion을 의미한다. PL0는 Parallel layer-0 search를 나타내며, DP는 PMem에서 DRAM으로의 데이터 프리페칭을 나타낸다. 단계적으로 HM-ANN의 검색 성능은 더욱 향상된다.
결론
HM-ANN이라고 불리는 새로운 그래프 기반 인덱싱 및 검색 알고리즘은 그래프 기반 ANN의 계층적 설계를 HM의 메모리 이질성에 매핑한다. 평가 결과 HM-ANN은 십억 포인트 데이터셋에서 새로운 최첨단 인덱스에 속함을 보여준다.
학계뿐만 아니라 산업계에서도 영구 저장 장치에 인덱스를 구축하는 데 초점이 맞춰지는 추세가 보입니다. DRAM의 부담을 덜기 위해 Disk-ANN [1]은 SSD 위에 구축된 인덱스로, 처리량은 PMem보다 상당히 낮습니다. 그러나 HM-ANN의 구축에는 여전히 며칠이 걸리며, Disk-ANN과 비교했을 때 큰 차이가 확립되지 않았습니다. PMem의 특성, 예를 들어 PMem의 세분성(256 Bytes)을 인지하고 스트리밍 명령어를 사용해 캐시라인을 우회하는 것을 더 신중하게 활용한다면 HM-ANN의 구축 시간을 최적화할 수 있다고 믿습니다. 또한 향후 내구성 있는 저장 장치를 사용하는 더 많은 접근법이 제안될 것이라고 믿습니다.
Reference
[1]: Suhas Jayaram Subramanya and Devvrit and Rohan Kadekodi and Ravishankar Krishaswamy and Ravishankar Krishaswamy: DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node, NIPS, 2019
DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node - Microsoft Research
DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node
[2]: Alexander van Renen and Lukas Vogel and Viktor Leis and Thomas Neumann and Alfons Kemper: Persistent Memory I/O Primitives, CoRR & DaMoN, 2019
계속 읽기
We spent 8 years making vector databases faster. Then we stopped.
Rarely queried embeddings still need to stay searchable. See how Vector Lakebase enables on-demand vector search without always-on compute costs.
How Zilliz Ended Up at the Center of NVIDIA’s Unstructured Data Story at GTC 2026
If unstructured data is the context of AI, then the ceiling of AI applications will be set not just by models, but by how mature the infrastructure for unstructured data becomes.
Zilliz Cloud BYOC Now Available Across AWS, GCP, and Azure
Zilliz Cloud BYOC is now generally available on all three major clouds. Deploy fully managed vector search in your own AWS, GCP, or Azure account — your data never leaves your VPC.