HNSW의 모든 것: Redis Vector Sets 구현기

게시일: 2025년 11월 13일 | 원문 작성일: 2025년 11월 12일

작성일: 2025년 1월 | 원저자: antirez (Salvatore Sanfilippo) | 원문 보기

왜 이 글을 쓰나

HNSW 개발을 잠시 멈추고 (지금은 다른 데이터 구조 작업 중), 지난 1년간 배운 걸 정리할 타이밍이라고 생각했어요. AI 시대 이전에 흔했던 그런 “브레인 덤프” 스타일의 글이죠. 이건 HNSW 입문서가 아니에요 - 그건 이미 많으니까요. 대신 HNSW를 이미 아는 사람들을 위한 “extra mile”, 특히 Redis처럼 저지연·고성능이 필요한 환경에서 HNSW를 추상 데이터 구조로 노출하는 과정에서의 도전과 해법을 다룹니다.

HNSW의 현재 상태

원논문은 훌륭한 컴퓨터 과학 문헌이고 HNSW는 놀라운 데이터 구조지만, 제 생각에 벡터 근접 검색의 마지막 단어는 아니에요. 논문을 읽다 보면 뭔가 “빠진 조각”이 있는 느낌이 들어요 - 연구자들에게 6개월만 더 주어졌다면 더 많이 탐구하고 말할 게 있었을 것 같아요.

예를 들어, 저는 논문을 확장해서 실제 삭제(tombstone 방식이 아닌)를 구현했는데, 논문엔 삭제 얘기가 아예 없거든요. 비슷하게, 지금 “H”(Hierarchical, 계층 구조)가 정말 필요한지, 단일 레이어로도 비슷한 성능이 나오는지 연구하는 사람들도 있어요.

결론: 데이터 구조 연구에 관심 있다면, HNSW의 진화와 개선이 좋은 연구 분야라고 봐요. “디스크용으로 만들어보자”(Microsoft 같은) 방향만이 아니라요.

메모리 확장: 공간 전쟁

Redis는 인메모리 시스템이고, HNSW와 벡터 둘 다 메모리를 엄청 많이 먹어요. 이유는 세 가지:

실제로 효과 있는 최적화: 벡터 양자화

여러 최적화를 시도했는데, 진짜 low-hanging fruit는 벡터 양자화였어요:

8-bit quantization 결과:

• 거의 4배 속도 향상
• 벡터 크기 4배 감소 (전체 노드는 4배까진 아님 - 포인터는 그대로)
• 실제 사용 사례에서 recall은 거의 동일

그래서 Redis Vector Sets는 기본적으로 8-bit quantization을 사용해요. VADD 옵션으로 full precision이나 binary quantization도 선택 가능하지만, binary는 원본 정보가 이미 이진(yes/no 속성 같은)일 때만 쓰길 권장해요.

양자화 구현 디테일

min/max 둘 다 저장하는 것보다는 덜 정확하지만, cosine similarity 계산이 더 빨라요. 간단한 연산으로 양자화 도메인과 원본 도메인을 오갈 수 있죠.

속도 확장: 스레딩과 지역성

저는 사실 스레드 시스템을 별로 안 좋아해요 - 싱글 코어로 많이 할 수 있고, 그 다음엔 shared-nothing 아키텍처로 여러 코어를 쓰는 게 선호하는 방식이거든요. 하지만 HNSW는 달라요. 느리고, 대부분 읽기 전용으로 접근되니까요. 그래서 제 Vector Sets 구현은 완전히 스레드화되어 있어요 - 읽기뿐 아니라 쓰기도 부분적으로 스레드화했죠.

읽기 스레딩: epoch 배열 트릭

방문한 노드를 추적하기 위해 해시테이블 같은 별도 구조 대신 각 노드에 “epoch” 정수를 저장해요. 글로벌 데이터 구조가 검색마다 epoch를 증가시키고, 현재 epoch로 방문한 노드를 마킹하죠.

문제: 스레드가 여러 개면 동시에 여러 검색이 일어나요!

해법: epoch 배열 사용

또 다른 공간-시간 트레이드오프인데, 여기서도 시간이 승리했어요.

쓰기 스레딩: split-phase 기법

HNSW 삽입에서 시간의 대부분은 이웃 후보를 찾는 데 쓰여요. 그래서 쓰기를 두 단계로 나눴어요:

첫 번째 단계는 읽기만 하고, 두 번째 단계만 쓰기 락이 필요해요. 첫 단계 동안 HNSW가 변경되면 수집한 후보를 폐기하는 트릭이 있어요.

추가 문제: 백그라운드 스레드가 작업 중일 때 사용자가 키를 삭제하면?
해법: 객체를 실제로 해제하기 전에 백그라운드 작업이 끝날 때까지 기다리는 함수

결과: 실제 벡터 워크로드에서 redis-benchmark로 50k ops/sec (순수 HNSW 라이브러리는 훨씬 높음)

메모리 회수: 제대로 삭제하기

대부분의 HNSW 구현은 노드 삭제 시 메모리를 직접 회수하지 못해요. 두 가지 이유가 있어요:

문제 1: 단방향 링크의 함정

많은 사람들이 HNSW 링크가 양방향일 필요가 없다고 생각해요. 새 노드를 삽입할 때 좋은 이웃들이 이미 최대 링크 수에 도달한 경우가 많은데, 이때 단방향으로만 링크하는 거죠.

문제는: 노드를 삭제할 때 들어오는 링크를 모두 찾을 수 없어서 메모리를 회수할 수 없어요. 그래서 tombstone flag로 “삭제됨”으로만 마킹하고, 나중에 재구성하거나 아예 메모리가 leak되기도 해요.

제 해법: 강제 양방향 링크

Redis 구현에선 링크를 강제로 양방향으로 만들어요. A가 B를 링크하면 B도 A를 링크해야 해요.

”근데 A가 이미 꽉 차 있으면?” 복잡한 휴리스틱을 써서 기존 노드의 링크를 드롭하고, 새 노드가 더 나은 후보면 강제로 최소한의 링크를 만들어요. small world 속성을 유지하면서요.

노드 삭제 후 재연결

삭제된 노드의 이웃들이 링크를 잃으면 어떻게 할까요? 거리 행렬을 만들어서 서로 연결하려고 해요:

• 각 (i, j) 쌍의 연결이 얼마나 좋은지 (벡터 유사도)
• 그 연결이 남은 쌍들에게 얼마나 나쁜 영향을 주는지

점수 행렬을 만든 후 탐욕적으로 페어링해요. 이게 너무 잘 작동해서 수백만 개 노드의 HNSW를 만들고 95%를 삭제해도 남은 그래프가 여전히 좋은 recall을 유지하고 고립 노드도 없어요.

이게 제가 “HNSW에 대한 새 논문의 여지가 있다”고 말하는 이유예요.

여러 프로세스로 확장하기

Redis Vector Sets 작업을 시작할 때 이미 RediSearch의 인덱스 타입으로 벡터 유사도 구현이 있었어요. 대부분 사람들이 HNSW를 생각하는 방식이 “기존 데이터의 인덱싱”이죠.

하지만 저는 완전히 다른 방식으로 HNSW를 제공하고 싶었어요 - 데이터 구조로서요.

왜 데이터 구조로?

벡터는 Redis Sorted Sets의 score 같은 거예요. 전체 순서가 없는 거만 빼고요. VADD, VREM으로 요소를 추가/제거하고, ZRANGE 대신 VSIM으로 유사한 요소를 가져와요.

VADD my_vector_set VALUES [… components …] my_element_string

Redis는 컴포넌트가 뭔지 신경 안 써요. VSIM을 호출하면 유사한 요소를 반환하죠.

확장성의 마법

핵심 철학

많은 프로그래머들이 똑똑해요. 접근할 수 없는 마법 시스템 대신 데이터 구조와 트레이드오프를 보여주면, 더 많은 걸 만들고 자기 use case를 특정 방식으로 모델링할 수 있어요. 그리고 시스템도 더 단순해지고요.

로딩 시간 확장하기

스레딩 없이 제 HNSW 라이브러리는 word2vec(300 컴포넌트)을 싱글 스레드로 5000 요소/초로 추가할 수 있고, 결과 HNSW를 90k 쿼리/초로 검색할 수 있어요. 큰 격차죠.

이건 수백만 요소의 HNSW를 Redis dump 파일에서 메모리로 다시 로딩하는 데 오래 걸린다는 뜻이에요. 복제에도 영향을 주고요.

해법: 그래프 구조 자체를 직렬화

Naive 방법: 디스크에 “요소, 벡터” 저장 → 메모리에서 HNSW 재구성
똑똑한 방법: 노드와 이웃들을 있는 그대로 직렬화 → 메모리에서 할당하고 이웃 ID를 포인터로 변환

결과: 100배 속도 향상

보너스: 보안 검증

최근 Redis는 보안 기능이 강화되어서 RDB 파일이 공격자에 의해 손상되어도 나쁜 일이 안 일어나도록 해요. 그래서 로딩 후 HNSW가 유효한지 확인해야 했어요.

특히 멋진 트릭 하나가 reciprocal check예요:

사용 사례 확장: JSON 필터

첫 작동하는 Vector Sets 구현이 완성된 날을 기억해요. 모든 게 예상대로 작동하고 개선과 추가 기능의 시작점이었죠.

하지만 지난 몇 주/달 동안 대부분 사용 사례가 혼합 검색이 필요하다는 피드백을 받았어요. 주어진 쿼리 벡터에 가까운 벡터를 원하지만(가장 유사한 영화 같은), 뭔가 필터링도 하고 싶다는 거죠(2000~2010년 사이 개봉만).

제 생각

다른 파라미터로 쿼리할 필요는 제품 사람들이 생각하는 것보다 덜 자주 있어요. 이 경우엔 각 연도를 다른 벡터 셋 키에 넣는 게 더 효율적일 수 있어요(데이터 구조로서의 HNSW 조합 가능성의 또 다른 예).

하지만 HNSW의 탐욕적 검색 메인 루프를 생각하다가 아이디어가 떠올랐어요:

JSON 메타데이터 필터링

각 노드에 JSON 메타데이터 셋을 추가하면 어떨까요? { “year”: 1999 } 같은 게 있으면 탐욕적 검색 수행 중에 필터링할 수 있잖아요?

핵심 인사이트: 쿼리 벡터에 가까운 요소를 먼저 원하니까, JSON 속성 조건을 만족하는 노드가 많지 않아도 전체 그래프를 탐색할 필요가 없어요. 사용자가 노력(effort)을 지정하게 하고, 어차피 필터에 맞는 아주 먼 결과는 쓸모없으니까요.

또 다른 차별점: 제 HNSW는 프로그래밍 언어의 “if” 문 안에 쓸 수 있는 것 같은 표현식으로 필터링을 지원해요. Vector Set의 요소를 JSON blob과 연결해서 속성을 표현할 수 있죠:

메모리 사용량에 대한 몇 마디

HNSW의 치명적인 문제는 - 이론적으로는 - 보통 메모리에서 서빙된다는 거예요. 물론 디스크에도 HNSW를 구현할 수 있지만, 디스크 접근 지연 관점에선 더 나은 데이터 구조가 있어요.

하지만 Redis와 Vector Sets의 경우엔 빠르고 다루기 쉬운 걸 제공하는 게 아이디어예요. 인메모리 데이터 구조의 유연성이 도움이 되고요.

질문: 메모리 사용량이 정말 그렇게 나쁜가요?

많은 사용 사례가 수천만 엔트리 정도거나 훨씬 적어요. 그리고 잘 구현되고 메모리에 있는 HNSW에서 얻는 건 매우 좋은 성능이에요. 정의상 느린 데이터 구조와 워크로드에서 이건 중요하죠.

제 MacBook에서: word2vec 데이터셋에 대한 VSIM으로 redis-benchmark가 48k ops/sec

제 느낌엔 많은 사용 사례에서 인메모리 HNSW의 메모리 사용량이 매우 수용 가능해요. 벡터 대부분을 디스크에 원하는 사용 사례에서도 느린 성능을 감수해야 하지만, hot set은 RAM에서 서빙되어야 할 거예요.

이게 HNSW 연구가 여전히 좋은 아이디어라고 믿는 이유 중 하나예요 - 대부분 사용 사례에서 금방 대체되진 않을 거예요. RAM과 디스크에 각각 이상적인 다른 데이터 구조들이 계속 있을 것 같아요.

결론

저는 HNSW가 좋고, 작업하고 구현하는 게 진짜 즐거웠어요. 벡터가 Redis에 잘 맞는다고 생각하는데, AI 없는 세상에서도 그래요(예를 들어 몇 달 전에 Hacker News 유저를 fingerprinting하는 데 썼어요 - HN에 과거 올라온 작업을 복제한 거죠).

HNSW는 많은 사용 사례에 너무 멋지고 강력해요. AI와 학습된 임베딩이 있으면 잠재적 사용 사례가 무수히 많아지고요. 하지만 Redis의 대부분 기능처럼, 사람들이 유용하고 강력하다는 걸 깨닫고 사용법을 배우기까지는 시간이 좀 걸릴 거예요(아뇨, RAG만이 아니에요). Streams도 그랬거든요 - 여러 해가 지나서야 마침내 mass adoption이 일어났죠.

HNSW와 제가 작성한 구현에 관심 있으시면, 코드가 꽤 접근 가능하고 주석도 많이 달려 있어요:

• Redis HNSW 구현 (hnsw.c)
• Redis Vector Sets README - 여기서 시작하길 추천해요

이렇게 긴 블로그 포스트를 읽어주셔서 감사해요! 좋은 하루 되세요.