HNSW 스케일링
HNSW 개발을 잠시 몇 주간 멈추고 있습니다. 지금은 다른 자료구조를 작업 중인데, 곧 소식을 전하겠습니다. 현시점에서 제가 Redis에 추가한 새로운 타입은 충분히 안정적이고 완성도도 갖춰, 그동안 HNSW에 대해 배운 것들을 정리해 블로그 글로 풀어내기에 더없이 좋은 타이밍입니다. AI 시대 이전에는 흔했던, 일종의 브레인 덤프 같은 글이죠. 요즘은 어쩌면 조금 드물어진 그런 글 말입니다. 어쨌든 거의 1년 동안 HNSW와 벡터 유사도에 대해 고민하고 구현해 온 만큼 이제 글을 쓸 때가 되었다고 느꼈습니다. 다만 이 글은 HNSW 입문서가 아닙니다. 그런 글은 이미 차고 넘칩니다. 대신 ‘한 걸음 더 나아가는’ 글입니다. HNSW를 이미 알고 계신 분들을 위해, 특히 HNSW를 ‘Redis다운’ 경험을 제공할 만큼 빠르게 만든다는 관점에서 얻은 좀 더 심화된 발견들을 공유하려 합니다. 아시다시피 Redis는 낮은 지연 시간과 높은 성능을 위해 설계되었는데, HNSW는 그와는 다소 맞지 않는 구석이 있어 HNSW를 추상 자료구조로 노출시키는 데 적지 않은 과제가 있었습니다.
이 글은 여러 섹션으로 나누어 진행됩니다. 같은 책의 여러 페이지, 같은 경험의 여러 장이라고 생각해 주시면 됩니다. 아, 그리고 참고로 이 글은 이미 한 번 썼다가 날려버렸습니다 :D [macOS와 나쁜 습관에 얽힌 길고 슬픈 이야기입니다. 90년대 정전 때 이후로 이런 식으로 무언가를 날려본 적이 없었는데 말이죠] 그래서 이번 글의 가장 큰 과제는 며칠 전에 썼던 내용을 기억해 내는 동시에, 마음에 들지 않았던 부분을 좀 더 잘 다듬는 일이 될 것 같습니다.
HNSW의 현주소에 대한 몇 마디
HNSW의 내부 구조와 최적화를 본격적으로 파고들기 전에 HNSW 자체에 대해 몇 가지 짚고 넘어가고 싶습니다. HNSW를 처음 소개한 논문은 훌륭한 컴퓨터 과학 문헌이며, HNSW 자체도 놀라운 자료구조입니다. 하지만 거리 함수에 따라 가까운 벡터를 탐욕적으로 탐색하는 문제에 대해 HNSW가 마지막 정답이라고는 생각하지 않습니다. 논문은 어딘가 ‘빠진 조각’이 있는 듯한 느낌을 줍니다. 연구진이 6개월만 더 시간을 가졌다면 훨씬 더 많은 것을 탐구하고 이야기할 수 있었을 것 같은 느낌 말입니다. 예를 들어 저는 논문 내용을 직접 확장해 원소 삭제를 지원하도록 만들었습니다. 단순히 삭제된 것으로 표시해 두고 나중에 수거하는 툼스톤 방식이 아니라 실제 삭제를 말합니다. 논문에는 원소 삭제에 대한 내용이 전혀 없습니다. 마찬가지로 지금은 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 Set이 기본적으로 8비트 양자화를 사용하는 이유가 바로 여기에 있습니다. VADD 옵션으로 완전 정밀도 벡터나 부호만 취하는 이진 양자화 벡터를 쓰겠다고 지정할 수도 있지만, 저는 완전 정밀도 벡터와 이진 양자화 벡터를 쓰는 것 모두에 대해서는 회의적입니다. 그 이야기를 하기 전에 8비트에 대해 제가 사용한 양자화 방식을 먼저 보겠습니다.
제가 하는 방식은 각 벡터의 컴포넌트 중 절댓값이 가장 큰 값을 계산하는 것입니다(즉 벡터별 양자화입니다). 그리고 -127부터 127까지를 표현하는 부호 있는 8비트 값으로 양자화합니다. 최소값과 최대값을 모두 저장하는 것만큼 정확하지는 않지만, 코사인 유사도를 계산할 때는 더 빠릅니다. 다음과 같이 할 수 있기 때문입니다.
/* 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 Set 구현은 완전 스레드 기반입니다. 읽기뿐 아니라 쓰기도 부분적으로 스레딩됩니다. 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가 변경되어 일부 노드가 더 이상 유효하지 않게 되었을 경우 첫 번째 단계에서 수집한 후보들을 버리도록 하는 몇 가지 트릭이 있습니다. 하지만 또 다른 문제가 있습니다. 백그라운드 스레드가 값을 처리하고 있는 동안 사용자가 키를 삭제하면 어떻게 될까요? 이런 시나리오를 위해 실제로 객체를 회수하기 전에 백그라운드 작업이 반환될 때까지 기다리는 함수가 있습니다. 이런 트릭들 덕분에 실제 벡터 워크로드에서 50k ops/sec를 쉽게 달성할 수 있으며, 이 수치는 모든 오버헤드를 포함한 redis-benchmark 자체에서 얻은 것입니다. 순수한 HNSW 라이브러리 자체의 수치는 훨씬 더 높습니다.
메모리 스케일링: 제대로 회수하기
여러 인스턴스가 관련된 큰 사용 사례로 HNSW를 스케일링하는 방법과, 왜 Redis Vector Set이 실제 자료구조를 사용자 앞에 그대로 노출하는지에 대해 이야기하기 전에(저는 프로그래머가 똑똑하며 과잉 보호가 필요 없다고 믿지만, 이유가 *그것뿐*은 아닙니다), 메모리 이야기로 다시 돌아가고 싶습니다. 이 부분에 대해 들려줄 흥미로운 이야기가 있기 때문입니다.
대부분의 HNSW 구현은 그래프에서 노드를 삭제할 때 메모리를 직접 회수하지 못합니다. 두 가지 이유 때문이라고 봅니다.
1. 사람들이 원래 HNSW 논문을 특정한 방식으로 오해하기 때문입니다. 이웃 간의 링크가 상호적이지 않아도 된다고 믿는 것이죠. 그리고 그들이 그렇게 생각하는 데에는 특정한 이유가 있습니다.
2. 논문이 노드 삭제와 노드가 사라진 뒤 그래프에서 빠진 링크를 어떻게 복구할지에 대해 아무것도 말하지 않기 때문입니다.
첫 번째 문제는 (제 생각에) 논문의 명확성 부족과 HNSW를 구현하면서 마주치는 특정 문제가 결합된 결과입니다. 새 노드를 삽입할 때 기존 노드 중에서 좋은 이웃을 찾다 보면, 후보 노드들이 이미 나가는 링크의 최대 개수에 도달해 있는 경우가 많습니다. 이 경우 어떻게 해야 할까요? 이 문제는 종종 새로 삽입하는 노드에서 이미 나가는 링크가 ‘포화 상태’인 후보들로 단방향으로 링크를 거는 방식으로 해결됩니다. 하지만 노드를 삭제해야 할 때 들어오는 모든 링크를 추적할 수 없게 되므로 메모리를 제대로 회수할 수 없습니다. 플래그로 삭제 표시만 해두고 나중에 그래프를 재구축해 오래된 노드를 가비지 컬렉션하거나, 때로는 그냥 메모리를 누수시키기도 합니다.
그래서 우선 Redis의 제 구현은 링크를 양방향으로 강제하는 방식으로 다르게 동작합니다. A가 B를 가리키면 B도 A를 가리킵니다. 하지만 A가 바쁜 상태라면 어떻게 그렇게 할 수 있을까요? 이 부분은 복잡한 영역으로 들어가지만, 핵심은 기존 노드에서 잘 연결된 다른 이웃과의 링크를 끊는 휴리스틱을 사용하고, 우리 노드가 대상 노드에게도 더 나은 후보라면 교체하며, 그렇지 않더라도 새로운 노드가 최소 개수의 링크를 확보하도록 강제하는 다른 방법들이 존재한다는 점입니다. 항상 그래프의 스몰 월드 속성을 만족시키려 노력하면서 말입니다.
이렇게 하면 Redis가 Vector Set에서 노드를 삭제할 때 그 노드를 가리키는 모든 포인터를 제거할 방법이 항상 존재합니다. 하지만 이제 링크 하나가 빠진 채 남게 된 노드들은 어떻게 해야 할까요? 제가 하는 방식은 그 노드들 사이에 거리 행렬을 만들어, 평균 거리를 최소화하도록 예전 노드의 이웃들을 서로 연결하려 시도하는 것입니다. 기본적으로 행렬 안의 i, j 노드 쌍마다 연결이 얼마나 좋은지(벡터가 얼마나 유사한지)와 그들을 연결하는 것이 *남은* 가능한 쌍들에 얼마나 나쁜 영향을 미치는지(특정 두 노드를 연결하면 좋은 짝을 찾지 못한 채 남는 원소가 생길 수 있기 때문입니다)를 계산합니다. 점수 행렬을 만든 뒤에는 탐욕적인 페어링 단계를 진행합니다.
이 방식은 매우 잘 동작해서, 수백만 개 원소로 큰 HNSW를 구축한 뒤 전체 원소의 95%를 삭제하더라도 남은 그래프는 여전히 좋은 리콜을 유지하고 고립된 노드도 생기지 않습니다.
제가 HNSW에는 새로운 논문들이 계속해서 이어갈 여지가 있다고 말할 때 의미하는 바가 바로 이것입니다.
여러 프로세스로 HNSW 스케일링하기
제가 Redis Vector Set 작업을 시작했을 때 Redis 진영에는 이미 벡터 유사도 구현이 존재했습니다. 구체적으로는 RediSearch의 인덱스 타입 중 하나로 말입니다. 그리고 대부분의 사람들이 HNSW를 생각하는 방식도 바로 그와 같습니다. 기존 데이터에 대한 일종의 인덱싱 형태라는 것이죠.
하지만 저는 Redis에 완전히 다른 방식으로 노출되는 새로운 HNSW 구현을 제공하고 싶었습니다. 어떻게요? 물론 자료구조로서 말입니다. 이는 오랜 세월 동안 제 머리가 얼마나 Redis스럽게 되었는지를 보여주는 이야기이기도 하고, 어쩌면 처음부터 제 머리가 Redis스러웠고 Redis가 제 머리를 닮은 것일 수도 있습니다. HNSW를 사용자에게 직접 노출하는 Redis 자료구조를 어떻게 설계할지 즉시 그려졌고, Redis에서 벡터 작업이 왜 정확히 그런 방식으로 수행되지 않았는지 의아했기 때문입니다.
동시에 제가 설계 문서를 Redis 동료들에게 건넸을 때, 그들이 곧바로 그것을 당연한 일이라고 “이해”했다고는 말할 수 없습니다. 제 논리는 이랬습니다. 벡터는 Redis Sorted Set의 스코어와 같지만, 전체 순서가 존재하는 스칼라 스코어가 아니라는 점만 다릅니다. 그럼에도 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개 컴포넌트)을 초당 5000개 원소 속도로 HNSW에 추가할 수 있으며, 결과 HNSW에 대해서는 초당 90k건의 질의를 처리할 수 있습니다. 보시다시피 큰 격차가 있습니다.
이는 수백만 개 원소를 가진 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 Set의 첫 번째 동작하는 구현이 완성되었다고 느껴진 날을 기억합니다. 모든 것이 예상대로 동작했고, 세부 개선과 추가 기능들을 시작하기 위한 출발점이었습니다.
하지만 지난 몇 주, 몇 달 동안 내부적으로 대부분의 사용 사례가 일종의 혼합 검색을 필요로 한다는 피드백을 받았습니다. 주어진 질의 벡터와 가까운 벡터를 찾으면서(예: 어떤 작품과 가장 유사한 영화) 동시에 일종의 필터링(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 Set의 경우 아이디어는 매우 빠르고 다루기 쉬운 무언가를 제공하는 것입니다. 인메모리 자료구조의 유연성이 여기에 도움이 됩니다. 그렇다면 문제는 결국 이것으로 귀결됩니다. 메모리 사용량이 정말 그렇게 나쁠까요?
기본 int8 양자화로 300만 개의 Word2Vec 항목을 Redis에 로딩하면 3GB의 RAM을 사용합니다. 항목 하나당 1KB인 셈입니다. 많은 사용 사례는 단지 수천만 개, 혹은 그보다 훨씬 적은 수의 항목을 가집니다. 그리고 HNSW로부터, 잘 구현되고 메모리에 올라가 있다면 얻을 수 있는 것은 매우 뛰어난 성능이며, 이는 그 자체로 느릴 수밖에 없는 자료구조이자 워크로드에서는 결정적으로 중요합니다. 제 MacBook에서는 이 키(word2vec 데이터셋을 담고 있는)를 대상으로 redis-benchmark와 VSIM으로 초당 48k ops를 얻습니다. 인메모리 HNSW의 메모리 사용량은 많은 사용 사례에서 충분히 감당 가능하다는 것이 제 느낌입니다. 그리고 벡터의 대부분을 디스크에 두고 싶은 사용 사례에서도, 성능 저하를 감수해야 하더라도 핫셋은 아마도 RAM에서 서비스되어야 할 것입니다.
이것이 제가 HNSW 연구를 계속하는 것이 좋은 생각이라고 믿는 이유 중 하나입니다. 대부분의 사용 사례에서 HNSW가 머지않아 대체될 것이라고 생각하지 않습니다. 사용 사례와 데이터 크기에 따라 RAM과 디스크에 각각 이상적인 서로 다른 자료구조들을 계속 갖게 될 가능성이 더 높아 보입니다. 게다가 최근 Hacker News 프론트 페이지를 훑어보면서도 본 것은, 수백만 개 아이템을 가진 사람들이 필요 이상으로 느리거나 복잡한 시스템과 씨름하고 있다는 점입니다. HNSW를 올바른 방식으로 잘 노출하면 그런 수고를 모두 피할 수 있습니다.
결론
HNSW가 좋고, 이를 작업하고 구현하는 과정은 정말 즐거웠습니다. 저는 벡터가 AI가 없는 세상에서도 Redis에 잘 어울린다고 믿습니다(예를 들어 몇 달 전 Hacker News 사용자를 지문화하는 데 벡터를 사용한 적이 있습니다. 과거 HN에 게시된 오래된 작업을 재현한 것이었습니다). HNSW는 수많은 사용 사례에 대해 그저 너무 멋지고 강력하며, AI와 학습된 임베딩이 더해지면 잠재적인 사용 사례는 무수히 많아집니다. 하지만 Redis의 대부분 기능처럼, 사람들이 그 유용함과 강력함, 그리고 활용 방법을 깨닫기까지는 많은 시간이 걸릴 것이라고 예상합니다(단순한 RAG만의 문제가 아닙니다). Streams도 그랬습니다. 마침내 수년이 지나 대중적으로 채택되었습니다.
대신 HNSW와 제가 작성한 구현에 더 관심이 있으시다면, 코드가 꽤 접근하기 쉽고 주석도 충실하다고 생각합니다.
https://github.com/redis/redis/blob/unstable/modules/vector-sets/hnsw.c
Redis Vector Set에 대해 더 알고 싶으시다면 제가 직접 작성한 README 파일을 읽어보셔도 좋습니다. 공식 Redis 문서도 있지만, 여기부터 시작하시길 권합니다.
https://github.com/redis/redis/tree/unstable/modules/vector-sets
이렇게 긴 블로그 글을 읽어주셔서 감사합니다! 좋은 하루 보내세요.
참고 문헌. HNSW의 ‘H’가 얼마나 유용한지에 대한 논문입니다 -> https://arxiv.org/abs/2412.01940