ScaNN 인덱스에 대한 간략한 소개

ScaNN은 대규모 벡터 검색의 익숙한 과제인 쿼리 처리량을 늘리고 메모리 사용량을 줄이면서도 결과 품질에 큰 타격을 입히지 않는 방법에 대한 Google의 해답입니다 . 개념적으로 ScaNN은 고전적인 IVF+PQ 레시피(거친 클러스터링과 공격적인 제품 양자화)에서 시작하지만, 성능의 경계를 의미 있게 바꾸는 두 가지 중요한 혁신이 겹쳐져 있습니다:

• 점수 인식 정량화 목표는 실제 이웃의 상대적 순서를 더 잘 보존하여 압축이 심한 상황에서도 순위 품질을 개선합니다.

• FastScan은 SIMD에 최적화된 4비트 PQ 룩업 경로로, CPU 레지스터 내에 더 많은 작업을 유지함으로써 기존의 메모리 부하 병목 현상을 줄여줍니다.

실제로는 리콜에 민감하지 않은 추천 워크로드와 같이 일부 리콜을 높은 QPS와 훨씬 작은 메모리 사용 공간(종종 벡터를 원래 크기의 ~1/16로 압축)과 교환해도 괜찮을 때 강력한 선택입니다.

이 포스팅에서는 기준선으로서 IVFPQ를 다시 살펴보고, 이를 기반으로 ScaNN이 도입한 주요 최적화를 살펴본 다음, 측정된 성능에 대한 논의의 근거가 되는 실험 결과로 마무리하겠습니다.

IVFPQ 요약

ScaNN은 2020년에 Google에서 제안했으며, 이 논문에서는 GloVe 데이터 세트에서 HNSW보다 3배의 성능 향상을 보고하고 있습니다. 자세한 내용은 원본 논문과 오픈 소스 구현을 참조하세요.

ScaNN을 소개하기 전에, ScaNN이 동일한 전체 프레임워크 위에 구축되었으므로 IVFPQ에 대해 간략히 살펴보겠습니다.

IVFPQ는 고차원 벡터 데이터베이스에서 효율적이고 대규모의 근사 근사 이웃(ANN) 검색에 사용되는 알고리즘인Inverted File with Product Quantization의 약자입니다. 이는 검색 속도, 메모리 사용량, 정확도의 균형을 맞추기 위해 반전 파일 인덱스(IVF) 와 제품 양자화(PQ)라는 두 가지 기술을 결합한 하이브리드 접근 방식입니다.

IVFPQ의 작동 방식

이 프로세스는 색인 및 검색 중에 두 가지 주요 단계로 이루어집니다:

• IVF 레이어: 벡터가 nlist 반전 목록(클러스터)으로 클러스터링됩니다. 쿼리 시에는 클러스터의 하위 집합(nprobe)만 방문하여 리콜과 지연 시간/처리량 간의 균형을 맞춥니다.

• PQ 계층: 방문한 각 클러스터 내에서 각 D 차원 벡터는 각각의 차원(D/m)인 m개의 서브벡터로 분할됩니다. 각 서브벡터는 해당 서브 코드북에서 가장 가까운 중심점에 할당하여 정량화됩니다. 하위 코드북에 256개의 중심이 있는 경우, 각 서브벡터는 uint8 코드([0, 255]의 ID)로 나타낼 수 있습니다.

그러면 거리 계산을 서브벡터에 대한 합으로 다시 작성할 수 있습니다:

D(q, X) = D(q, u0) + D(q, u1) + D(q, u2) + ... + D(q, un)

= L(q, id1) + L(q, id2) + L(q, id3) + ... + L(q, idn)

여기서 L은 조회 테이블을 나타냅니다. 쿼리 시점에 쿼리와 각 양자화된 서브벡터 사이의 거리를 기록하는 룩업 테이블이 구성됩니다. 이후의 모든 거리 계산은 테이블 조회로 변환된 후 합산됩니다.

예를 들어 128차원 벡터가 각각 4차원의 32개 하위 벡터로 분할된 경우, 각 하위 벡터가 uint8 ID로 인코딩되면 벡터당 스토리지 비용이 (128 x 4) 바이트에서 (32 x 1) 바이트로 1/16로 감소합니다.

IVFPQ에 기반한 ScaNN 최적화

요약하면, ScaNN은 두 가지 측면에서 IVFPQ를 개선합니다:

1. 양자화: ScaNN은 단순히 각 서브벡터를 가장 가까운 k-평균 중심값으로 대체하는 것(즉, 재구성 오류 최소화) 이상의 목표를 제시합니다.

2. 조회 효율성: ScaNN은 SIMD 친화적인 FastScan 경로를 통해 메모리 제약이 많은 LUT 기반 검색을 가속화합니다.

점수 인식 양자화 손실

분석은 IP 메트릭을 기반으로 하기 때문에 ScaNN이 양자화 오류를 병렬 및 수직 구성 요소로 분해한 후에는 병렬 구성 요소만 결과에 영향을 미치므로 더 큰 페널티 항을 적용해야 합니다. 따라서 손실 함수는 다음과 같이 다시 작성할 수 있습니다:

$$\begin{array}{r}{\displaystyle \mathrm{\ell }({\mathrm{xi}}_{},{\mathrm{x~i}}_{},w)}\end{array}$$$$∥2\begin{aligned} \ell\left(x_i, \tilde{x}_i, w\right) &=h_{\|}\left(w,\left\|x_i\right\|\right)\left\|r_{\|}\left(x_i, \tilde{x}_i\right)\right\|^2 +h_{\perp}\left(w,\left\|x_i\right\|\right)\left\|r_{\perp}\left(x_i,$$$$\tilde{x}_i\right)\right\|^2 \end{aligned}$$ ℓ$$\begin{array}{r}(x\end{array}$$i, x~i,w) =h∥ $$\begin{array}{l}(w.,\end{array}$$∥xi$$\begin{array}{l}\Vert )\end{array}$$ $$\begin{array}{l}r\end{array}$$∥ $$\begin{array}{l}(x\end{array}$$i, x~i) 2+h⊥ $$\begin{array}{l}(w,\Vert x\end{array}$$i$$\begin{array}{l}\Vert )\Vert r\end{array}$$⊥ $$\begin{array}{l}(x\end{array}$$i,

아래 그림은 병렬 구성 요소로 인한 오류가 더 크고 잘못된 최접 이웃 결과를 초래할 수 있으므로 더 심각한 페널티가 적용될 수 있음을 보여주는 2차원 예시입니다.

왼쪽 그림은 병렬 오프셋이 최종 결과에 영향을 미치기 때문에 양자화가 불량한 반면, 오른쪽 그림은 양자화가 개선된 것을 보여줍니다.

4비트 PQ 패스트스캔

먼저 PQ 계산 과정을 살펴보겠습니다. 쿼리하는 동안 쿼리와 서브벡터 클러스터 중심 사이의 거리를 미리 계산하여 룩업 테이블을 구성합니다. 그런 다음 테이블 조회를 통해 거리 계산을 수행하여 세그먼트 거리를 구하고 이를 합산합니다.

그러나 잦은 메모리 읽기는 여전히 성능 병목 현상이 발생합니다. 룩업 테이블을 레지스터에 맞을 만큼 작게 만들 수 있다면 메모리 읽기 연산을 효율적인 CPU SIMD 명령어로 변환할 수 있습니다.

먼저, 각 서브벡터는 16개의 클래스로 클러스터링되므로 4비트 값은 클러스터 중심을 나타낼 수 있으며, 이것이 "4비트 PQ"라는 이름의 기원입니다. 그런 다음 일반적으로 부동 소수점으로 표시되는 거리를 스칼라 양자화(SQ)를 사용하여 uint8로 변환합니다. 이렇게 하면 하나의 서브벡터에 대한 룩업 테이블을 16 × 8 = 128비트를 사용하여 레지스터에 저장할 수 있습니다.

마지막으로 레지스터 스토리지 레이아웃을 살펴봅시다(AVX2 명령어 세트를 예로 사용): 32개 벡터의 서브벡터가 128비트 레지스터에 배치되고 룩업 테이블과 결합됩니다. 그러면 단일 SIMD 셔플 CPU 명령어를 사용하여 "조회" 연산을 효율적으로 완료할 수 있습니다.

레지스터 레이아웃

룩업을 위한 SIMD 셔플

여기서 흥미로운 점은 ScaNN 논문이 전적으로 첫 번째 최적화에 초점을 맞추고 있다는 점인데, 이는 수학적 추론을 강조하는 알고리즘 논문으로 볼 수 있기 때문에 당연한 결과입니다. 그러나 이 논문에서 제시된 실험 결과는 매우 인상적입니다.

ScaNN 논문에 제시된 실험 결과.

직관적으로 손실 최적화만으로는 이렇게 극적인 효과가 나타나지 않을 것입니다. 다른 블로그에서도 이 점을 지적했는데, 실제로 차이를 만드는 것은 4비트 PQ FastScan 부분입니다.

실험 결과

벡터 데이터베이스 벤치마크 도구인 VectorDBBench를 사용하여 간단한 테스트를 수행했습니다. 기존 IVFFLAT 및 IVF_PQ에 비해 ScaNN의 성능 우위는 상당히 분명했습니다. Milvus에 통합된 후, 동일한 리콜률의 Cohere1M 데이터 세트에서 QPS는 IVFFLAT의 5배, IVF_PQ의 6배에 달할 수 있습니다.

그러나 QPS는 HNSW와 같은 그래프 기반 인덱스보다 약간 낮기 때문에 높은 QPS 사용 사례에 우선적으로 선택되지는 않습니다. 그러나 일부 추천 시스템과 같이 리콜이 낮은 시나리오에서는 원시 데이터를 로드하지 않고 ScaNN을 사용하면 매우 낮은 메모리 사용량(원본 데이터의 1/16)으로 인상적인 QPS를 달성할 수 있으므로 탁월한 인덱스 선택이 될 수 있습니다.

Index_Type	Case	QPS	지연 시간(p99)	recall	memory
IVFFLAT	성능1M	266	0.0173s	0.9544	3G
HNSW	성능1M	1885	0.0054s	0.9438	3.24G
IVF_PQ	성능1M	208	0.0292s	0.928	0.375G
ScaNN(with_raw_data: true)	Performance1M	1215	0.0069s	0.9389	3.186G
ScaNN(with_raw_data: false)	Performance1M	1265	0.0071s	0.7066	0.186G

결론

ScaNN은 익숙한 IVFPQ 프레임워크를 기반으로 하지만 양자화 및 로우레벨 룩업 가속 모두에서 심층 엔지니어링 작업을 통해 훨씬 더 발전시켰습니다. 양자화 목표를 랭킹 품질에 맞추고 내부 루프에서 메모리 병목 현상을 제거함으로써 ScaNN은 점수 인식 양자화를 4비트 PQ FastScan 경로와 결합하여 기존의 메모리 바운드 프로세스를 효율적이고 SIMD 친화적인 계산으로 전환합니다.

실제로 ScaNN은 명확하고 잘 정의된 틈새 시장을 제공합니다. 리콜률이 높은 설정에서 HNSW와 같은 그래프 기반 인덱스를 대체하기 위한 것이 아닙니다. 대신, 메모리 예산이 빠듯한 리콜에 민감하지 않은 워크로드의 경우, ScaNN은 매우 작은 설치 공간으로 높은 처리량을 제공합니다. 실험 결과, Milvus VectorDB에 통합된 후 ScaNN은 Cohere1M 데이터 세트에서 IVFFLAT의 약 5배에 달하는 QPS를 달성하여 완벽한 리콜보다 압축과 효율성이 더 중요한 고처리량, 저지연 ANN 검색을 위한 강력한 선택이 될 수 있었습니다.

ScaNN에 대해 더 자세히 알아보거나 실제 시스템에서의 인덱스 선택에 대해 논의하고 싶으신 경우, Slack 채널에 가입하여 커뮤니티의 엔지니어 및 다른 AI 엔지니어와 채팅하세요. 또한 20분 동안 진행되는 일대일 세션을 예약하여 Milvus 업무 시간을 통해 인사이트, 지침, 질문에 대한 답변을 얻을 수도 있습니다.