벡터 검색 엔진 도입기
처음 만든 벡터 검색 엔진이 어떤 한계가 있었고, 새로운 알고리즘을 찾다 HNSW를 도입한 건에 대해 공유하는 발표다. 구현체가 C++로 되어 있어 이를 Golang에서 사용한 방법까지 다루며, 머신러닝 기술로 나온 벡터에 대한 검색 이야기임을 전제로 한다.
기존에는 두 점의 L2 거리를 기준으로 쿼리 벡터와 전체 벡터 데이터를 전부 비교하는 KNN을 썼다. 가진 벡터가 천 개면 천 번을 다 계산하는 방식이라, 256차원 벡터 약 150만 개 규모에서는 필연적으로 느려질 수밖에 없어 이를 해결하는 것이 주요 주제가 된다.
정확도를 조금(95~97%) 줄이는 대신 속도를 얻는 근사(ANN) 방식으로 방향을 잡는다. 스포티파이가 쓰는 Annoy는 벡터 공간을 랜덤으로 나눠 같은 공간의 벡터끼리 묶고, 쿼리가 들어오면 같은 영역 벡터를 이웃으로 퉁치는 방식이다. 성능은 좋았지만 자료구조를 만드는 데, 즉 데이터 추가 때마다 공간을 다시 나눠야 하는 한계가 있었다.
Annoy의 색인이 길게는 1시간 넘게 걸리는 문제로 새 알고리즘을 찾다 HNSW(Hierarchical Navigable Small World)에 도달한다. 계층을 어떻게 쌓는지는 '케빈 베이컨의 6단계' 같은 스몰 월드 개념에서 왔는데, 엣지가 고르게 연결된 그래프에 몇 개의 랜덤 연결(빨간 엣지)만 더해도 노드 간 평균 도달 거리가 확 줄어든다는 성질을 활용한다.
그리디 탐색이 로컬 미니멈에 빠지는 문제를, 스킵 리스트에서 착안한 계층 구조로 해결한다. 링크드 리스트 맨 끝 노드까지 순회하려면 오래 걸리듯, 위 층을 듬성듬성 쌓아 급행처럼 이동한 뒤 아래 층으로 내려가면 순회 수는 유지하면서 훨씬 빠르게 목표 노드에 도달한다. 이 확률 기반 계층 구조가 HNSW의 핵심이며 데이터 추가도 쉽다.
HNSW 파라미터를 튜닝한다. M은 각 노드의 최대 연결 수로, 높이면 그래프가 촘촘해져 재현율은 오르지만 메모리·빌드 시간이 커진다. ef_construction은 빌드 시 탐색 범위로, 크면 연결 신뢰성이 높아져 응답시간이 줄고 재현율이 오르지만 빌드 시간이 선형으로 증가한다. ef_search는 검색 시 탐색 범위로, 크면 재현율이 오르는 대신 응답시간이 늘어난다.
HNSW의 C++ 라이브러리를 Golang에서 쓰기 위해 SWIG를 사용한다. SWIG는 C++ 코드를 다른 언어와 붙여주는 프로그램으로, 인터페이스 파일을 넘기면 바인딩 코드를 자동 생성한다. C++ 예외가 발생하면 프로세스가 죽는지 알 수 없는 문제가 있어, C++ exception을 Golang의 panic과 연결하도록 처리해 안정성을 확보했다.
AVX 같은 SIMD 명령어셋으로 벡터 연산을 가속한다. 일반 64비트 레지스터는 한 번에 64비트만 계산하지만, AVX는 128비트 이상을 한 번에 연산해 여러 값을 동시에 처리한다. CPU가 어떤 명령어셋(v1~v4)을 지원하는지 확인해 적용하며, AVX를 써서 벡터 연산 속도를 약 20% 향상시켰다. KNN→HNSW 전환과 SIMD 활용으로 성능을 크게 끌어올린 사례로 마무리한다.