NHN Forward 22 - 벡터 검색 엔진에 ANN HNSW 알고리즘 도입기

https://youtu.be/hCqF4tDPNBw?si=wYvWqiYFzX5UDr6R

대충? 거의 정확하다! 벡터 검색 엔진에 ANN HNSW 알고리즘 도입기

NHN Cloud 로그플랫폼개발팀 권성재.

• 벡터 검색엔진 운영하면서 새로운 알고리즘 도입하기까지.
• 기존 방식의 문제점, 해결책, C++ 구현체 말고 Golang에 적용하기까지.

 

헷갈릴 수 있어서 용어 정리하자면

• ML 기술 결과물로 나온 Vector 값의 검색 관련 내용임.
• ML이나 AI 기술 자체에 관련된 건 아니다.

HNSW 도입 배경

기존 방식인 KNN: 점 두개의 L2 Distance 계산.

• 검색 대상으로 들어온 Vector가 있으면
• 기존 DB에 있던 모든 Vector 간 거리를 일일이 계산 -> 가장 거리가 가까운 K개 응답.

따라서, 데이터 많아질수록 계산성능이 떨어진다.

ANN: 검색 대상과 가까운 벡터를 '근사치로' 찾아내는 방법.

• 검색 성능 자체는 KNN보다 떨어지지만, 검색속도가 빠름. NHN의 경우 성능은 '정확도 95~97%' 정도를 생각한다고 함.
• Spotify의 Annoy가 대표적.
  • 수많은 Vector가 공간에 있을 때, 공간을 랜덤 분할한다. 같은 공간에 있는 Vector는 같은 색으로 칠해두었다.
  • 특정 Query Vector가 들어오면, 개별 vector가 아니라 해당 '공간'과의 근접도 확인.
    • 근접도 높은 공간에 있는 모든 vector들을 '유사도 높다'고 간주한다.

새로운 데이터가 공간에 추가될 때마다 '공간'을 다시 나누고, 트리 형태의 자료구조를 설정해야 한다.

• NHN에서는 2시간마다 데이터를 업데이트하는데, 자료구조 재설정에만 40분 ~ 1시간 소요되는 문제가 있었음.

HNSW 소개

Hierarchical Navigable Small World의 약자.

• Navigable Small World를 계층 구조화했다.
• 그럼 Navigable Small World는 뭘까?

6단계 법칙 -> 네트워크 이론 중 하나.

• 전 세계의 사람도 평균 6단계만 거치면, 모든 사람과 연결될 수 있다
• 즉, 전세계가 사실 수학적으로는 6단계만 거치면 연결되는 small world인 셈이다

edge가 고르게 연결되어 있는 Regular 상태에서

• 몇 개의 노드만 랜덤하게 추가로 연결하면
• 한 노드에서 다른 노드까지 평균적으로 도달하기 위한 hops가 크게 감소한다!

이 개념을 적용해보면

• 모든 Vector들을 삼각형이 되도록 서로 연결한다. (검은 선)
• 랜덤하게, 몇몇 Vector는 추가로 연결한다. (빨간 선)
• 검색 시작점 기준으로, 목적지에 가장 가까운 노드를 Greedy하게 찾아가는 방식.
  • 예컨대 entrypoint 기준, 초록색과 가장 가까운 vector (노드)를 찾아내려면 3 hops로 충분해진다.
• 그러나 데이터 차원이 올라가면, local minimum에 빠질 수 있다는 문제점이 있음.

차원이 올라갔을 때 local minimum에 빠지지 않기 위해, 계층 구조로 쌓는 방식이 추가로 도입됨.

 

제시된 자료구조는 Linked List.

• Linked list의 최대 단점은 '검색 시, 반드시 순차적으로 접근'

Skip List: 단점을 줄이기 위해서, 노드를 겹쌓은 뒤 중간 단계는 건너뛰는 형태의 구조.

• 9번 노드까지 도달하려면 기존 방식으로는 8 hops. 겹쌓은 구조에서는 3 hops로 가능.

그러면, 새로운 노드가 추가되었을 때 '이 노드는 몇 층짜리 노드인가?' 를 결정해야 함.

• 이걸 확률 기반으로 결정한다.

Navigable Small World + 확률 기반 skip list 구조를 합친 게 HNSW.

• layer 2의 빨간 점이 entrypoint라고 하자. 검색의 시작점.
• layer 0의 초록 점이 검색 대상 Vector.

Greedy 방식으로 탐색을 시작하면 가장 가까운 노드로 이동 -> hierarchy 이동 을 반복한다.

• 계층이 생겼기 때문에, hops 수는 유지하면서 local minimum으로 수렴하는 문제점을 해결할 수 있다.

장점: 데이터 추가가 쉽다.

• 새 노드가 추가된다? -> 그래프에 노드 몇 개 연결해주면 됨.

단점: 파라미터 튜닝을 세심하게 해줘야 한다.

• 그래프를 만들기 위한 파라미터 설정을 잘해줘야 검색 성능이 향상된다.

장점이자 단점이 될 수 있는 특징: 데이터 경향에 영향을 많이 받는다.

• 데이터의 sparsity... 결국 그래프를 그려야 하기 때문에, 데이터 간 밀집도가 작으면 그래프 그리기가 까다로워진다.

잘 쓰기 위한 성능 튜닝

용어 정의.

• 응답시간 (response time): 검색 요청 후 응답 오기까지의 시간. 수치가 작을수록 좋다.
• 재현율 (recall): 검색 결과가 실제 정답과 얼마나 일치하는지. 수치가 클수록 좋다.
  • 알고리즘 자체가 재현율을 일정 부분 포기하면서 응답시간을 향상한 것이기에, 적정 수준의 재현율은 유지할 수 있어야 함.
• 검색 개수 (K)
• 인덱스: 검색하기 위해 만든 자료구조/파일. 예시의 경우 그래프.
• 빌드: Vector 데이터에 index 만드는 과정. 예시의 경우 그래프 만드는 과정.

그래프 빌드에 쓰이는 파라미터

성능 튜닝 - M

• 하나의 노드에 연결된 이웃 노드의 개수.
• M 값이 클수록 그래프 품질이 올라감. (빽빽한 그래프를 만들 수 있다) 단, 그래프를 저장하는 자료구조 (메모리 크기), 빌드 시간이 커진다.
• 추천 범위는 5 ~ 48.

다른 변수 고정하고 M만 변화시켜본 벤치마크 결과, M이 커질수록

• 응답시간이 길어지고, 빌드시간이 늘어남. (Bad)
• 재현율 증가 (Good)

성능 튜닝 - ef_construction

• ef 파라미터 종류 중 하나로, 빌드에 관여하는 설정값.
• index 구성할 때(빌드할 때), 이웃 노드를 찾을 때 사용하는 (저장해두는) dynamic queue의 크기.

값이 클수록, 기존 노드에서 더 멀리까지 탐색한다. 한 노드가 더 멀리 있는 노드에까지 연결될 수 있음.

• 더 멀리까지 연결할 수 있다 = 노드 탐색이 더 오래 걸린다. 따라서 빌드 시간이 선형적으로 늘어난다 (Bad)
• 응답시간이 줄어들고, 재현율이 증가한다. (Good)
  • 즉, 그래프의 빽빽한 정도가 같더라도 유의미한 결과를 더 빨리 가져올 수 있다.

검색에 쓰이는 파라미터

성능 튜닝 - ef

• 특정 vector와 가장 유사도 높은 vector 1000개 / 10000개 찾아달라고 할 때... 어디까지 탐색할 것인가? 를 결정하는 값.

벤치마크 표는 K=1000 일 때가 기준임. (특정 vector와 가장 유사한 vector 1000개를 검색해달라)

• ef가 1000이면 1000개까지 찾고 바로 응답, 3000이면 3000개까지 찾아보고 응답...
  • greedy 방식이라서, 가장 빨리 나온 1000개 != 가장 유사도 높은 1000개

따라서 ef 수치가 크면

• 응답시간이 길어진다 (Bad)
• 재현율이 높아진다 (Good)

성능 튜닝 - 데이터 경향성

• 그래프를 그렸을 때, '데이터가 얼마나 밀집해 있는가' 에 따라 검색 성능 (응답시간, 재현율)이 달라짐.
  • 초록색: 랜덤 추출 100만개
  • 보라색: 자체적으로 가지고 있는 옷(패션) 데이터 100만개. -> 클러스터링이 되어 있을 것.
• 어느 정도 데이터 경향성이 확고한 옷(패션) 데이터가 랜덤 데이터에 비해 응답시간이 더 짧고, 재현율이 높은 것을 확인할 수 있다.

파라미터 접근 전략

빌드 과정에서는 M과 ef_construction 값을 조정하면서 재현율 (recall) 을 높인다.

• M이 좀 더 중요함. 한 노드와 맺어질 수 있는 연결의 개수를 정의하므로, 높을수록 개별 노드가 차지하는 메모리 용량이 커진다.
  • 그래프 자체는 파일로 저장되고, 검색이 필요한 경우에 메모리에 올라가는 구조. (메모리에 상주해야 함)
• M을 정해서, 빌드 결과로 만들어지는 사이즈를 보고 serving 가능한지 아닌지 판단해야 함.
• 그 후 ef_construction 조정하면 된다.
  • 값이 커질수록 성능이 좋아지지만 빌드시간이 느려진다. 허용 가능한 최대 빌드시간까지 값을 올려가면 됨.

검색 과정에서는 ef값을 조정하면서 응답시간, 재현율 (recall) trade-off 에서 균형점을 찾는다.

• 가지고 있는 데이터 경향성에 따라 최적값이 다 다르므로, 시행착오를 거칠 수밖에 없다.
• ef는 ef_construction과 K 중 큰 값으로 시작, 조절해가면서 최적치를 찾아내면 된다.

Golang에서 C++ 라이브러리 쓰기 위한 SWIG 적용

SWIG: C++에서 쓰인 코드를 다른 언어와 연결하기 위한 코드.

• 인터페이스 파일 작성해서 빌드하면,
• 해당 라이브러리를 사용하기 위해 필요한 코드를 자동 생성해준다.

왼쪽의 interface.i 파일을 넣어주면, 오른쪽의 Go interface가 만들어지는 식.

• C++의 vector 자료구조를 변환해달라는 내용이고
• vector 자료구조를 사용하기 위해 필요한 go interface를 FloatVector 라는 이름으로 리턴.

단순 자료구조뿐만 아니라, vector 안에 pair<float, size_t> 처럼 정의된 것들이 있어도 매핑할 수 있는 인터페이스를 생성해준다.

유의점

• C++의 exception 을 정의해주지 않으면, go에서 실행하다 exception발생 시 sigkill 뜨면서 프로세스가 종료돼 버린다.
• 따라서 go panic으로 매핑해줘야 한다.

라이브러리를 뜯어보면, 사용할 수 있는 명령어가 여러 개 구현돼 있음.

• 예컨대 64bit 컴퓨터 -> cpu 레지스터 크기가 64bit. 한 번에 연산할 수 있는 비트 수가 최대 64라는 뜻.
• SSE가 64bit
• AVX가 128bit (실제 cpu 사양이 64bit여도, 128bit를 한번에 수행하는 것처럼 동작하도록 구현돼 있다)
• AVX512는 512bit.

해당 명령어가 동작하도록 컴파일해주면 속도가 향상된다.

• 그럼, 내 cpu 사양이 해당 명령어 지원되는지를 확인해야 함.
• 보통 cpu 버전을 v1 ~ v4로 구분하는데, 각 버전별로 지원되는 명령어가 있다.
  • 예컨대 인텔 제온은 AVX를 지원함.
• go에서도 GOAMD64, CGO_CXXFLAGS 옵션을 적용하고 컴파일하면, 실제로 저 AVX 명령어를 사용해서 vector 연산을 수행하기에 성능향상이 있음.
  • 내부적으로는 SSE보다 20% 의 향상이 있었다고 함.

정리

KNN 성능 한계로 ANN 알고리즘을 도입함.

• 데이터 삽입이 쉽고
• 데이터 경향에 따라 성능에 영향을 받으며
• 파라미터 튜닝을 적절히 한 뒤
• C++ 라이브러리를 Golang에 쓰기 위한 과정에서 CPU 명령어를 적절히 쓰면 성능 최적화가 된다.