HNSW 스케일링
원문은 Salvatore Sanfilippo님이 에 게재했습니다. 이 블로그 구독하기
잠시 HNSW 개발을 멈추고 몇 주간 다른 자료구조를 만들고 있다(조만간 소식 전하겠다). 지금 시점에서 Redis에 새로 추가한 타입은 충분히 안정적이고 완성도도 높아졌다. 그래서 지금까지 HNSW에 대해 배운 것들을 정리해 블로그 글로 풀어내기에 딱 좋은 타이밍이다. AI 시대 이전에는 흔했던, 머릿속에 있는 걸 그대로 쏟아내는 그런 글 말이다. 요즘은 어쩌면 조금 드물어진. 어쨌든 거의 1년 동안 HNSW와 벡터 유사도 관련 작업을 고민하고 구현해 왔으니, 이제는 글을 쓸 때가 됐다. 다만 이 글은 HNSW 입문서가 아니다. 그런 글은 이미 차고 넘친다. 대신 ‘한 걸음 더 나아간’ 이야기를 하려 한다. HNSW를 이미 알고 있다면, 특히 ‘Redis다운’ 경험을 가능할 만큼 빠르게 만드는 맥락에서 얻은 좀 더 ‘심화된’ 발견들을 공유하고 싶다. 알다시피 Redis는 낮은 지연 시간과 높은 성능을 위해 설계됐고, HNSW는 그런 특성에 다소 저항하는 면이 있다. 그래서 HNSW를 추상적인 자료구조로 노출시키는 데 여러 난관이 있었다.
이 블로그 글은 여러 섹션으로 나뉜다. 같은 책의 여러 페이지, 같은 경험의 다른 챕터라고 생각하면 된다. 아, 참고로 이 글은 이미 한 번 쓰고 날려버렸다 :D [MacOS와 나쁜 습관에 얽힌 길고 슬픈 이야기다 – 90년대 정전 때 이후로 이런 식으로 글을 날린 건 처음이다]. 그래서 이번에는 며칠 전에 썼던 내용을 떠올리는 것이 가장 큰 과제이고, 그러면서 별로 마음에 들지 않았던 부분을 좀 더 잘 다듬어 보려 한다.
HNSW의 현 상태에 대해 잠깐
HNSW 내부와 최적화에 대해 깊게 들어가기 전에, HNSW에 대해 몇 가지 하고 싶은 말이 있다. HNSW를 처음 소개한 원 논문은 훌륭한 컴퓨터 과학 문헌이며, HNSW 자체도 놀라운 자료구조다. 하지만 거리 함수에 따라 가까운 벡터를 탐욕적으로 탐색하는 문제에 있어 HNSW가 최종 정답이라고는 생각하지 않는다. 논문을 읽으면 어딘가 빠진 ‘조각’이 있다는 느낌이 든다. 연구자들이 6개월만 더 있었다면 훨씬 더 탐구하고 할 말이 많았을 것 같은 느낌이다. 예를 들어 나는 논문을 직접 확장해 항목 삭제 기능을 지원하도록 했다. 단순히 삭제된 것으로 표시해두고 나중에 수거하는 tombstone 방식이 아니라, 실제로 제거하는 방식이다. 항목 삭제는 논문에서 완전히 빠져 있다. 마찬가지로 지금은 HNSW의 ‘H’(계층)가 정말 필요한지, 오히려 단일 레이어의 평면 자료구조가 거의 비슷한 성능을 내는지 검증하려는 시도들도 있다(이에 대해서는 나중에 더 다룰 수 있길 바란다. 내 생각에는 진실이 중간 어딘가에 있고, 레벨 선택 함수를 수정해 특정 임계값 이상의 레벨만 갖도록 하는 것이 타당하다).
이 말을 하는 이유는, 자료구조 연구에 관심이 있다면 HNSW의 진화와 개선을 상상하는 것이 훌륭한 분야라고 믿기 때문이다. 진화란 ‘디스크용으로 만들어 보자’(Microsoft의 시도 등을 보라) 같은 식으로만 해야 한다는 생각에 갇히지 말고 말이다. 자, 서론은 이쯤 하고, 이제 진짜 로우레벨 이야기로 들어가 보자 :)
메모리 스케일링
Redis는 인메모리 시스템이고, HNSW와 벡터 모두 안타깝게도 공간을 매우 많이 차지한다는 특징이 있다. 이유는 세 가지다. 1. HNSW는 이웃 노드를 가리키는 포인터가 많다. 16개, 32개 혹은 그 이상인데, 이는 HNSW에서 튜닝 가능한 파라미터다. 2. HNSW는 스킵 리스트와 유사한 자료구조라 레벨이 많다. 이는 첫 번째 문제를 더 악화시킨다. 3. HNSW의 위성 데이터는 부동소수점 수로 이루어진 벡터다. 기본적인 경우 컴포넌트당 4바이트를 쓰고, 보통 300~3000개의 컴포넌트를 갖는다. 이게 일반적인 범위다.
그래서 여기서 얻은 교훈은 무엇인가? 포인터를 압축하는 사람들도 있다. 64비트 시스템에서 포인터(8바이트)의 상위 4바이트가 대부분 동일할 가능성이 높기 때문이다. 똑똑한 방법이다. 나는 아직 구현하지 않았다. Redis에서는 빨라야 하기 때문이고, 이는 공간과 시간 사이의 트레이드오프이기 때문이다. 하지만 해볼 만할 수도, 아닐 수도 있다. 더 파고들어 볼 예정이다.
하지만 계산을 해보면, 레이어가 많다는 사실이 보기만큼 그렇게 끔찍하지는 않다. 평균적으로 노드당 여러 레이어가 상황을 약 1.3배 정도만 악화시킨다(레벨 선택 함수에서 레벨 증가 확률이 0.25인 경우). 많은 노드가 레벨 0에만 존재하기 때문이다. 그래도 1.3은 1보다는 크고, 만약 HNSW의 ‘H’가 정말 그렇게 유용하지 않다면… [스포일러하자면, 내가 발견한 바로는 모든 걸 레벨 0에만 두면 탐색 시간이 더 길어진다. 탐욕 탐색의 메인 루프가 덜 최적화된 곳에서 시작해 결국 올바른 클러스터에 도달하긴 하지만 더 많은 연산 시간이 든다. 다만 이는 아직 초기 결과다.]
그래서 여기서 진짜 쉽게 얻을 수 있는 성과는 벡터 양자화다. 내가 발견한 바로는 8비트 양자화를 사용하면 거의 4배의 속도 향상, 벡터 크기의 4배 감소(하지만 전체 노드가 4배 줄어드는 건 아니다. 포인터는 그대로 있고 공간을 많이 차지한다), 그리고 실제 사용 사례에서는 사실상 동일한 리콜을 얻을 수 있다. Redis Vector Sets가 기본적으로 8비트 양자화를 사용하는 이유가 바로 이것이다. VADD 옵션으로 전체 정밀도 벡터나 부호만 취하는 이진 양자화 벡터를 사용하겠다고 지정할 수도 있지만, 나는 전체 크기 벡터와 이진 양자화 벡터를 쓰는 것 모두에 대해 회의적이다. 그 이야기를 하기 전에, 내가 8비트에 어떤 양자화를 사용했는지 보자.
내가 하는 방식은 각 벡터의 컴포넌트 중 절댓값이 가장 큰 값을 계산하는 것이다(즉 양자화는 벡터별로 이루어진다). 그런 다음 부호 있는 8비트 값으로 -127부터 127까지의 양자화 값을 표현한다. 최소값과 최대값을 모두 저장하는 것만큼 좋지는 않지만, 코사인 유사도를 계산할 때는 더 빠르다. 이렇게 할 수 있기 때문이다.
/* Each vector is quantized from [-max_abs, +max_abs] to [-127, 127]
* where range = 2*max_abs. */
const float scale_product = (range_a/127) * (range_b/127);그런 다음 정수 영역에서 이렇게 곱한다(실제 코드에서는 메인 루프가 언롤링되어 있고 여러 개의 누산기를 사용해 현대 CPU를 더 바쁘게 만든다)
for (; i < dim; i++) dot0 += ((int32_t)x[i]) * ((int32_t)y[i]);그리고 마지막으로 부동소수점 거리로 다시 돌아온다.
float dotf = dot0 * scale_product;자세한 내용은 vectors_distance_q8()을 확인하면 되지만, 아이디어는 이해했을 것이다. 정수 양자화 영역에서 양자화되지 않은 내적으로 돌아가는 것은 아주 간단한 연산으로 가능하다.
결국 8비트 양자화는 아주 훌륭한 선택이고, 전체 정밀도 역시 *필요한* 기능이었다. 미세한 차이가 중요하도록 생성된 벡터로 작업하는 사람들이 있을 것이기 때문이다(물론 학습된 벡터에서는 그런 경우가 아니다…). 그런데 왜 이진 양자화인가? 원래 정보 자체가 이미 이진인 경우 사용자가 공간을 낭비하지 않는 간단한 방법을 갖게 하고 싶었기 때문이다. 예를 들어 사용자 집합이 있고 각 사용자가 yes/no 속성을 갖는다고 하자. 그리고 비슷한 사용자, 아이템 등을 찾고 싶다. 바로 이런 경우에 이진 양자화를 써야 한다. 이 역시 VADD 명령의 옵션일 뿐이다.
속도 스케일링: 스레딩과 지역성
아, 나에 대해 한 가지 말해야겠다. 나는 단일 코어로 많은 일을 할 수 있고, 그 다음에 공유하지 않는(shared-nothing) 아키텍처로 여러 코어를 사용하는 것이 가능할 때는 스레드 기반 시스템을 별로 좋아하지 않는다. 하지만 HNSW는 다르다. HNSW는 *느리고*, 적어도 대부분의 사용 사례에서는 거의 항상 읽기 전용으로 접근된다. 그래서 내 Vector Sets 구현은 완전히 스레드 기반으로 동작한다. 읽기뿐 아니라 쓰기도 부분적으로 스레딩되며, 특히 백그라운드 저장 프로세스나 클라이언트 등 다양한 주체가 키에 접근할 수 있는 Redis 같은 시스템에서 어떻게 이게 엉망이 되지 않고 가능한지 궁금할 것이다.
일단 읽기부터 살펴보자. 자료구조에 쓰는 사람이 아무도 없는 동안에는, 가까운 벡터들을 탐욕적으로 수집하는 스레드를 생성해 그 결과를 블로킹된 클라이언트에게 돌려줄 수 있다. 다만 내 HNSW 구현은 완전히 처음부터 작성됐다. 말 그대로 vim으로 빈 C 파일을 열어 시작한 것이고, 다른 시스템들이 주로 사용하는 두 구현과 공유하는 코드가 0%다. 그래서 몇 가지 ‘새로운 점’이 있다. 그중 하나는 이미 방문한 노드를 다시 방문하지 않기 위해, (해시 테이블 같은) 별도의 자료구조로 방문 여부를 표시하는 대신 각 노드에 저장된 ‘epoch’라는 정수를 사용한다는 것이다. 해시 테이블 방식은 꽤 느리다고 생각한다. 반면 epoch은 노드에 지역적으로 저장되고, 전역 자료구조는 탐색마다 epoch을 증가시킨다. 그래서 각 탐색의 맥락에서 현재 epoch 이하의 epoch만 존재한다고 확신할 수 있고, 현재 epoch을 방문 표시로 사용할 수 있다.
하지만 스레드를 사용하면 여러 탐색이 동시에 일어난다! 그래서 내가 필요했던 것은 epoch 배열이다.
typedef struct hnswNode {
uint32_t level; /* Node's maximum level */
… many other stuff …
uint64_t visited_epoch[HNSW_MAX_THREADS];
}이것이 hnsw.h에서 볼 수 있는 내용이다. 이 역시 공간과 시간 사이의 트레이드오프이며, 이번에도 시간이 공간을 이겼다.
그렇다면 스레드 기반 쓰기는 어떻게 가능했을까? 핵심은 HNSW 삽입 시 많은 시간이 이웃 후보를 찾는 데 쓰인다는 점이다. 그래서 쓰기를 읽기 절반과 커밋 절반으로 나눈다. 두 번째 단계만 쓰기 락이 필요하고, 그 사이에 HNSW가 변경되어 일부 노드가 더 이상 유효하지 않게 되면 첫 번째 단계에서 모은 후보들을 버리도록 하는 몇 가지 트릭이 있다. 하지만 또 다른 문제가 있다. 백그라운드 스레드가 값에 대해 작업하는 동안 사용자가 키를 삭제하면 어떻게 되는가? 이 시나리오를 위해 실제로 객체를 회수하기 전에 백그라운드 작업이 반환될 때까지 기다리는 함수가 있다. 이런 트릭들을 통해 실제 벡터 워크로드에서 초당 5만 연산을 쉽게 달성할 수 있다. 이 수치는 모든 오버헤드를 포함한 redis-benchmark 자체에서 얻은 것이다. 순수한 HNSW 라이브러리 자체의 수치는 훨씬 더 높다.
메모리 스케일링: 제대로 회수하기
여러 인스턴스가 관련된 큰 사용 사례로 HNSW를 어떻게 확장하는지, 그리고 왜 Redis Vector Sets가 실제 자료구조를 사용자에게 직접 노출하는지에 대해 이야기하기 전에(나는 프로그래머가 똑똑하고 보살핌이 필요 없다고 믿지만, 그것만이 이유는 아니다), 메모리 이야기로 다시 돌아가고 싶다. 이 부분에 대해 들려줄 흥미로운 이야기가 있기 때문이다.
대부분의 HNSW 구현은 그래프에서 노드를 삭제할 때 메모리를 직접 회수하지 못한다. 그 이유는 크게 두 가지라고 생각한다.
1. 사람들이 원 논문을 특정한 방식으로 오해한다. 이웃 간의 링크가 상호적이지 않아도 된다고 믿는 것이다. 그들이 그렇게 생각하는 데는 특정한 이유가 있다.
2. 논문은 노드 삭제와, 노드가 사라진 뒤 연결 ‘망’에서 끊어진 링크를 어떻게 복구할지에 대해 아무것도 말하지 않는다.
첫 번째 문제는 (내 생각에) 논문의 명확성 부족과 HNSW를 구현하면서 사람들이 직면하는 특정 문제가 결합된 것이다. 새 노드를 삽입하면서 기존 노드들 중에서 좋은 이웃을 찾을 때, 후보 노드들이 이미 나가는 링크의 최대 개수에 도달해 있는 경우가 많다. 이 경우 어떻게 해야 하는가? 이 문제는 종종 삽입하려는 새 노드에서 이미 나가는 링크가 ‘가득 찬’ 후보들에게 단방향으로 링크를 거는 방식으로 해결된다. 하지만 노드를 삭제해야 할 때는 그 노드로 들어오는 모든 링크를 더 이상 해결할 수 없으므로 메모리를 실제로 회수할 수 없다. 플래그로 삭제 표시만 해두고, 나중에 그래프를 일부 재구축해 오래된 노드를 ‘가비지 컬렉션’하기도 하고, 때로는 메모리가 그냥 누수되기도 한다.
그래서 내 Redis 구현은 링크를 양방향으로 강제함으로써 다르게 동작한다. A가 B를 가리키면 B도 A를 가리킨다. 하지만 A가 이미 바쁜 상태라면 어떻게 그렇게 할 수 있는가? 여기서부터는 복잡한 영역이지만, 일어나는 일은 기존 노드의 링크를 잘 연결된 다른 이웃과의 연결을 끊는 휴리스틱을 사용하는 것이다. 우리 노드가 대상 노드에게조차 더 나은 후보라면 그렇게 하고, 그렇지 않다면 새 노드가 최소 개수의 링크를 갖도록 강제하는 다른 방법들이 있으며, 항상 그래프의 스몰 월드 속성을 만족시키려 한다.
이렇게 하면 Redis가 Vector Set에서 노드를 삭제할 때 항상 그 노드를 가리키는 모든 포인터를 제거할 방법이 있다. 하지만 이제 링크가 하나 사라진 채 남은 노드들은 어떻게 해야 하는가? 내가 하는 방식은 그 노드들 사이에 거리 행렬을 만들어, 평균 거리를 최소화하도록 기존 노드의 이웃들끼리 연결을 시도하는 것이다. 기본적으로 행렬 안의 각 i,j 노드 쌍에 대해, 그 연결이 얼마나 좋은지(벡터가 얼마나 유사한지)와 그들을 연결하는 것이 *남은* 가능한 쌍들에 얼마나 나쁜 영향을 미치는지(두 특정 노드를 연결하면 좋은 짝을 찾지 못한 채 남는 요소가 생길 수 있기 때문이다)를 계산한다. 이 점수 행렬을 만든 뒤 탐욕적인 페어링 단계를 진행한다.
이 방식은 매우 잘 동작해서, 수백만 개 요소로 큰 HNSW를 구축한 뒤 나중에 95%를 삭제해도 남은 그래프가 여전히 좋은 리콜을 유지하고 고립된 노드가 생기지 않는다.
HNSW에는 새로운 논문이 계속해서 연구를 이어갈 여지가 있다고 말할 때 내가 의미하는 바가 바로 이것이다.
HNSW를 다중 프로세스로 스케일링하기
내가 Redis Vector Sets 작업을 시작했을 때, Redis 생태계에는 이미 벡터 유사도 구현이 존재했다. 특히 RediSearch의 인덱스 타입으로서였다. 그리고 이것이 대부분의 사람들이 HNSW를 생각하는 방식이다. 기존 데이터에 대한 인덱싱의 한 형태로 말이다.
하지만 나는 Redis에 완전히 다른 방식으로 노출되는 새로운 HNSW 구현을 제공하고 싶었다. 어떻게 할까? 물론 자료구조로서다. 이는 오랜 세월이 지나 내 머리가 얼마나 Redis처럼 되었는지를 보여주는 이야기이기도 하고, 어쩌면 처음부터 Redis처럼 생겨먹었고 Redis가 내 머리를 닮은 것일지도 모른다. 나는 HNSW를 사용자에게 직접 노출하는 Redis 자료구조를 어떻게 설계할지 즉시 그려냈고, Redis에서 벡터 작업이 정확히 그런 방식으로 이루어지지 않았다는 사실에 당황했기 때문이다.
동시에 내가 설계 문서를 Redis 동료들에게 건넸을 때, 그들이 즉시 그것을 당연한 것으로 ‘이해’했다고는 말할 수 없다. 내 논리는 이러했다. 벡터는 Redis Sorted Sets의 스코어와 같지만, 전체 순서를 갖는 스칼라 스코어가 아니라는 점만 다르다. 그럼에도 VADD, VREM으로 요소를 추가·삭제하고, ZRANGE 대신 VSIM을 호출하면 *유사한* 요소들을 얻을 수 있다. 이는 API로서만 타당한 것이 아니라, 나는 HNSW를 강하게 조합 가능하고 특정 사용 사례에 묶이지 않은 것으로 생각했다(텍스트 임베딩이나 이미지 임베딩, 심지어 *학습된* 임베딩에만 국한되지 않는다). 이렇게 하면 된다.
VADD my_vector_set VALUES [… components …] my_element_string따라서 컴포넌트에 무엇이 들어 있든 Redis는 신경 쓰지 않는다. VSIM을 호출하면 유사한 요소들을 반환할 뿐이다.
하지만 이는 또한 같은 사용 사례에 대한 서로 다른 벡터들이 여러 인스턴스/키에 나뉘어 있다면, 모든 인스턴스에 대해 동일한 질의 벡터로 VSIM을 요청하고 WITHSCORES 옵션(코사인 거리를 반환한다)을 추가한 뒤 결과를 클라이언트 측에서 병합하면, 데이터셋을 N배로 나누어 수억 개의 벡터를 여러 인스턴스로 마법처럼 확장할 수 있다는 의미이기도 하다[이런 사용 사례의 흥미로운 점 중 하나는 클라이언트 라이브러리가 충분히 똑똑하다면 멀티플렉싱을 이용해 N개의 인스턴스를 병렬로 조회할 수 있다는 것이다].
HNSW를 이런 날것 그대로의 방식으로 노출했을 때 또 하나 매우 주목할 만한 점은, 마침내 쓰기를 아주 쉽게 확장할 수 있다는 것이다. 요소를 N으로 모듈러 해시해서 나온 Redis 키/인스턴스를 대상으로 하면 된다. 여러 인스턴스가 (느리지만 HNSW 기준으로는 여전히 빠른) 쓰기를 동시에 흡수할 수 있어, 원래라면 매우 느린 과정을 병렬화할 수 있다.
이렇게 HNSW를 노출하는 방식은 아래쪽으로도 매우 유의미하게 확장된다. 때로는 작업 중인 각 사용자/아이템/제품 등마다 HNSW 하나씩을 원할 때가 있다. 무언가 위에 인덱스가 있는 형태라면 이를 모델링하기가 매우 어렵지만, HNSW가 자료구조라면 간단하다. 각 아이템마다 소수의 요소만 가진 Vector Set 키를 하나씩 두면 된다. 그리고 물론 다른 Redis 키와 마찬가지로 키에 만료 시간을 설정해 나중에 자동으로 삭제되도록 할 수 있다.
이 모든 것은 우리 업계에 더 많이 존재해야 한다고 믿는 하나의 규칙으로 압축할 수 있다. 많은 프로그래머는 똑똑하며, 접근할 수 없는 마법 같은 시스템을 만드는 대신 자료구조와 트레이드오프를 보여주면, 그들은 더 많은 것을 만들고 자신의 사용 사례를 구체적인 방식으로 모델링할 수 있다. 그리고 시스템도 더 단순해진다.
로딩 시간 스케일링
스레딩을 사용하지 않으면, 내 HNSW 라이브러리는 단일 스레드로 word2vec(벡터당 300개 컴포넌트)을 HNSW에 초당 5,000개 요소 속도로 추가할 수 있고, 결과 HNSW에 대해 초당 9만 쿼리를 수행할 수 있다. 보시다시피 큰 격차가 있다.
이는 수백만 개 요소를 가진 HNSW를 Redis 덤프 파일에서 메모리로 다시 로딩하는 데 많은 시간이 걸린다는 의미다. 그리고 이 시간은 리플리케이션에도 영향을 미친다. 좋지 않다. 하지만 이는 디스크에서 메모리로 요소를 가장 단순한 방식으로 추가할 때만 해당한다. 즉 디스크에 ‘요소, 벡터’를 저장해두고 메모리에서 HNSW를 다시 구축하려는 경우다. 여기서 배울 또 다른 교훈이 있다. HNSW를 사용할 때는 노드와 이웃을 있는 그대로 직렬화해야 한다. 그래야 메모리에 모든 것을 그저 할당하고 이웃 ID를 포인터로 바꾸는 것만으로 재구축할 수 있다. 이를 통해 100배의 속도 향상을 얻었다.
하지만 이야기가 여기서 끝난다고 정말 믿는가? 헤헤. 최근 Redis는 더 강력한 보안 기능을 갖추고 있어 RDB 파일이 공격자에 의해 손상되더라도 나쁜 일이 일어나지 않도록 한다. 그래서 내가 해야 했던 일은 직렬화된 자료구조의 오류나 손상 여부와 관계없이 로딩 후 HNSW가 유효함을 보장하는 것이었다. 여기에는 많은 트릭이 동원됐지만, 그중 상호성 검사가 특히 멋지다고 생각해 내가 작성한 주석 하나를 그냥 그대로 옮겨 보려 한다.
/* Second pass: fix pointers of all the neighbors links.
* As we scan and fix the links, we also compute the accumulator
* register "reciprocal", that is used in order to guarantee that all
* the links are reciprocal.
*
* This is how it works, we hash (using a strong hash function) the
* following key for each link that we see from A to B (or vice versa):
*
* hash(salt || A || B || link-level)
*
* We always sort A and B, so the same link from A to B and from B to A
* will hash the same. Then we xor the result into the 128 bit accumulator.
* If each link has its own backlink, the accumulator is guaranteed to
* be zero at the end.
*
* Collisions are extremely unlikely to happen, and an external attacker
* can't easily control the hash function output, since the salt is
* unknown, and also there would be to control the pointers.
*
* This algorithm is O(1) for each node so it is basically free for
* us, as we scan the list of nodes, and runs on constant and very
* small memory. */사용 사례 스케일링: JSON 필터
Vector Sets의 첫 번째 동작하는 구현이 완성됐다고 느꼈던 날을 기억한다. 모든 것이 예상대로 동작했고, 개선과 추가 기능을 시작하기 위한 출발점이었다.
하지만 지난 몇 주, 몇 달 동안 내부적으로 대부분의 사용 사례가 어떤 형태의 혼합 검색을 필요로 한다는 피드백을 받았다. 주어진 질의 벡터에 가까운 벡터를 원하면서(예: 어떤 영화와 가장 유사한 영화) 동시에 어떤 필터링(2000년에서 2010년 사이에 개봉된 것만)도 원하는 것이다. 내 생각에는 제품 쪽 사람들이 믿는 것보다 서로 다른 파라미터로 조회할 필요가 그리 자주 있지 않으며, 대부분의 경우 더 효율적으로 얻을 수 있다. 이 특정 사례에서는 각 연도를 서로 다른 Vector Set 키에 추가함으로써 말이다(이 역시 HNSW를 인덱스가 아닌 자료구조로 표현했을 때의 조합 가능성의 또 다른 예다).
하지만 나는 HNSW 탐욕 탐색의 메인 루프에 대해 생각하고 있었다. 대략 이런 형태다.
// Simplified HNSW greedy search algorithm. Don’t trust it too much.
while(candidates.len() > 0) {
c = candidates.pop_nearest(query);
worst_distance = results.get_worst_dist(query);
if (distance(query,c) > worst_distance) break;
foreach (neighbor from c) {
if (neighbor.already_visited()) continue;
neighbor.mark_as_visited();
if (results.has_space() OR neighbor.distance(query) < worst_distance) {
candidates.add(neighbor);
results.add(neighbor);
}
}
}
return results;그래서 각 노드에 JSON 형태의 메타데이터 집합을 추가하는 아이디어를 가지고 놀기 시작했다. {"year": 1999} 같은 것이 있다면, 탐욕 탐색을 수행하면서 필터링하기에 충분하지 않을까? 물론 탐색은 제한되어야 하지만, 여기서 핵심 통찰이 있다. 나는 우선 질의 벡터에 *가까운* 요소들을 원하므로, JSON 속성에 대한 조건을 많은 노드가 만족하지 못한다면 전체 그래프를 탐색할 필요가 별로 없다. 노력(effort)은 사용자가 지정하도록 하고, 어차피 필터와 일치하더라도 아주 멀리 떨어진 결과는 쓸모가 없다.
그래서 이것이 내 HNSW가 다른 또 하나의 방식이다. 프로그래밍 언어의 ‘if’ 문 안에 쓸 법한 표현식으로 필터링을 지원한다. 그리고 Vector Set의 요소들은 그 속성을 표현하는 JSON 블롭과 연결될 수 있다. 그러면 다음과 같은 일을 할 수 있다.
VSIM movies VALUES … your vector components here… FILTER '.year >= 1980 and .year < 1990'메모리 사용량에 대한 몇 마디
HNSW의 치명적인 문제는 — 이론적으로 — 보통 메모리에서 서비스된다는 점이다. 사실 HNSW를 디스크에 구현할 수도 있지만, 디스크 접근 지연 시간 관점에서는 더 나은 자료구조들이 있다. 하지만 Redis와 Vector Sets의 특정 사례에서는 매우 빠르고 다루기 쉬운 무언가를 제공하려는 것이 아이디어다. 인메모리 자료구조의 유연성이 이에 도움이 된다. 그래서 문제는 결국 이것으로 귀결된다. 메모리 사용량이 정말 그렇게 나쁜가?
기본 int8 양자화로 300만 개의 Word2Vec 항목을 Redis에 로드하는 데 3GB의 RAM이 들고, 항목당 1KB다. 많은 사용 사례에서는 수천만 개, 혹은 그보다 훨씬 적은 수의 항목만 갖는다. 그리고 잘 구현되고 메모리에 있는 HNSW로부터 얻는 것은 매우 좋은 성능이며, 이는 정의상 느린 자료구조이자 워크로드에서는 매우 중요하다. 내 MacBook에서는 이 키(word2vec 데이터셋을 담고 있는)에 대해 redis-benchmark와 VSIM으로 초당 4만 8천 연산을 얻는다. 내 생각에는 인메모리 HNSW의 메모리 사용량은 많은 사용 사례에서 매우 수용 가능하다. 그리고 벡터의 대부분을 디스크에 두고 싶어 느린 성능이라는 대가를 치러야 하는 사용 사례에서도, 핫셋은 아마도 RAM에서 서비스되어야 할 것이다.
이것이 내가 HNSW 연구에 적극적으로 참여하는 것이 좋은 생각이라고 믿는 이유 중 하나다. 대부분의 사용 사례에서 HNSW가 조만간 대체될 것이라고 생각하지 않는다. 사용 사례와 데이터 크기에 따라 RAM과 디스크에 각각 이상적인 서로 다른 자료구조를 계속 갖게 될 가능성이 더 높아 보인다. 게다가 최근 Hacker News 첫 페이지만 훑어봐도, 수백만 개 아이템을 가진 사람들이 필요 이상으로 느리거나 복잡한 시스템과 씨름하는 것을 봤다. HNSW를 올바른 방식으로 신중하게 노출하면 그런 일을 모두 피할 수 있다.
결론
나는 HNSW를 좋아하고, 이를 작업하고 구현하는 것은 정말 즐거웠다. 벡터는 AI가 없는 세상에서도 Redis에 아주 잘 맞는다고 믿는다(예를 들어 몇 달 전에는 과거 HN에 게시된 오래된 작업을 재현해 Hacker News 사용자를 지문화하는 데 벡터를 사용했다). HNSW는 여러 사용 사례에 있어 단순히 너무 멋지고 강력하며, AI와 학습된 임베딩과 함께라면 이 모든 것이 무수한 잠재적 사용 사례로 확장된다. 하지만 Redis의 대부분 기능과 마찬가지로, 사람들이 그것이 유용하고 강력하며 어떻게 사용하는지 깨닫기까지는 많은 시간이 걸릴 것으로 예상한다(아니, 단순히 RAG의 문제가 아니다). Streams도 마찬가지였다. 마침내 수년이 지나 대중적으로 채택됐다.
대신 HNSW와 내가 작성한 구현에 더 관심이 있다면, 코드가 꽤 접근하기 쉽고 주석도 풍부하다고 생각한다.
https://github.com/redis/redis/blob/unstable/modules/vector-sets/hnsw.c
Redis Vector Sets에 대해 더 알고 싶다면, 내가 직접 작성한 README 파일을 읽어 보길 바란다. 공식 Redis 문서도 있지만, 여기서부터 시작하는 것을 추천한다.
https://github.com/redis/redis/tree/unstable/modules/vector-sets
이렇게 긴 블로그 글을 읽어줘서 고맙다! 그리고 좋은 하루 보내길 바란다.
참고 문헌. HNSW의 ‘H’와 그것이 얼마나 유용한지에 대한 논문이다 -> https://arxiv.org/abs/2412.01940
댓글
로그인하고 댓글 남기기