어제 마침내 Vector Sets를 Redis에 병합했습니다. 무엇이 제공되는지 자세히 설명하는 README는 여기에서 확인할 수 있습니다:

https://github.com/redis/redis/blob/unstable/modules/vector-sets/README.md

새로운 자료구조의 목표는 간단히 말해 Sorted Sets와 유사한, 일종의 ‘Set 같은’ 새로운 데이터 타입을 만드는 것입니다. 점수(score)로 스칼라 값 대신 벡터를 가지고, Redis의 추상 자료구조가 구현하는 속성 외에는 아무것도 신경 쓰지 않고 Redis 방식대로 요소를 추가하고 제거할 수 있으며, 주어진 질의 벡터(또는 이미 셋 안에 있는 요소에 연결된 벡터)와 유사한 요소를 요청할 수 있는 식입니다. 자세한 내용은 뒤에서 다루고, 먼저 배경부터 짚어보겠습니다:

README의 경로만 봐도 구현이 “modules” 아래에 있는 것을 알 수 있지만, 사실 Vector Sets는 모듈이 아니라 Redis 코어의 일부입니다. 처음에는 모듈로 개발을 시작했는데, 이후에도 모듈 API를 그대로 사용하도록 제안했습니다. Redis 내부의 모듈성을 높이기 위해서였죠. 이렇게 하면 두 가지 장점을 모두 얻을 수 있습니다. Redis 8부터 모든 Redis 인스턴스가 Vector Sets를 네이티브 데이터 타입으로 갖게 되면서도, 코어와 구현 사이에는 명확한 경계가 유지됩니다.

오랜만에 등장한 Redis의 새로운 주요 데이터 타입

내가 알기로 Redis의 마지막 대형 자료구조는 역시 제가 개발한 Streams였습니다. 그 사이에 저는 사임했고, 복귀했으며, 포크도 일어났는데도 Redis에 새로운 데이터 타입을 도입하는 부담은 여전히 제 몫인 것 같습니다 :D 그래도 괜찮다고 말씀드리고 싶습니다. 프로그래밍을 좋아하는 만큼 디자인도 정말 좋아하고, 벡터와 벡터 유사도라는 개념 자체가 매우 단순하다고 느꼈기 때문에, 그에 걸맞게 아주 단순한 API가 어울린다고 생각했습니다. 그래서 그렇게 만들려고 노력했습니다. Vector Sets는 아직 베타 기능이지만, 한 가지는 장담할 수 있습니다. API는 3분이면 익힐 수 있습니다.

벡터 유사도를 구현할 때 근본적인 전제로 삼은 것은 HNSW를 처음부터 다시 구현하는 것이었습니다(제 구현은 hnsw.c에서 볼 수 있습니다). HNSW가 핵심 자료구조가 될 예정이었기 때문에, GitHub에서 아무 코드나 가져와 만족하고 싶지 않았습니다. 그런데 논문을 읽기 시작하면서 몇 가지 빠진 부분이 있다는 걸 알게 되었습니다.

그래서 예전에 HyperLogLog를 만들 때 몇 가지 빈틈을 메워야 했던 것처럼(여기 참고: https://antirez.com/news/75), 이번에도 새로운 알고리즘적 과제가 있었습니다. 특히 두 가지를 원했습니다:

1. 노드를 진정으로 삭제할 수 있을 것. Vector Sets에서는 VADD로 새 요소를 추가하고 VREM으로 요소를 제거할 수 있습니다. 그리고 메모리가 가능한 한 빨리 회수되길 원했습니다.
2. 요소를 삭제하더라도 HNSW 그래프의 연결 속성이 유지되도록 할 것.

그래서 제 구현은 다른 HNSW 구현들과 몇 가지 차이가 생겼습니다. 툼스톤 삭제를 사용하지 않고, 삭제되는 순간 노드의 연결을 실제로 끊고 다른 적합한 이웃들과 다시 연결합니다. 이를 위해 제 구현은 링크가 반드시 상호적이어야 하도록 강제합니다. 더 이상 최선 노력(best effort) 수준의 속성이 아닙니다. 이는 결국 삽입 과정에서 해야 할 일도 꽤 많이 바꾸게 됩니다.

HNSW에 가한 또 다른 수정은 프레디케이트 함수로 그래프를 스캔할 수 있도록 한 것입니다. 이를 통해 주어진 표현식과 일치하는 노드를 요청할 수 있습니다. 그러려면 탐욕적 그래프 스캔 알고리즘을 어느 정도 수정해야 합니다. 방문할 후보 노드를 수집하고 결과 집합을 모으는 방식은 물론, 쿼리의 선택도가 너무 높을 경우를 대비한 조기 종료 조건도 필요합니다. 물론 전체 그래프 스캔을 유발하고 싶지는 않습니다.

HNSW 수정 외에도, 좀 더 실용적이고 당연한 것들을 몇 가지 더 원했습니다:

1. 모든 벡터 유사도 요청의 스레딩입니다. 네, Redis 세계에서는 새로운 일이지만, 일반적으로 단일 스레드와 shared nothing이 좋은 설계라고 믿는 저조차도 벡터는 특별하다고 생각합니다. Redis가 다루는 다른 자료구조보다 훨씬 느리기 때문입니다. 덤으로, 벡터 유사도 쿼리를 수행하는 명령인 VSIM을 스레드로 구현하면서 몇 가지 트릭을 쓰면 쓰기 작업의 읽기 절반과 쓰기 절반을 두 부분으로 나눌 수 있다는 것도 알게 되었습니다. 이웃 후보 수집은 백그라운드에서 일어나고, 실제 삽입은 포그라운드에서 수행되는 방식입니다. 다만 이 분할은 기본값이 아니며, VADD의 CAS 옵션을 사용해야 강제할 수 있습니다.
2. 양자화를 지원하고, 심지어 기본값으로 만들고 싶었습니다. 그래서 Vector Sets는 8비트 양자화와 이진 양자화를 모두 제공합니다. 차원 축소를 위한 랜덤 프로젝션도 지원합니다. 하지만 RP와 이진 양자화를 좋아하긴 해도, 제게 진짜 ‘킬러’는 int8 양자화입니다. 엄청나게 빠르고 FP32 대비 25%의 메모리만 사용하면서도, 임베딩 AI 모델로 생성된 대부분의 벡터에서는 전체 벡터와 거의 동일한 결과를 냅니다.

여담이지만 최종 결과물은, 제 생각에, 매우 빠른 구현입니다. 예를 들어 제 노트북에서 300차원 벡터 300만 개로 구성된 Vector Set으로 초당 5만~6만 건의 VSIM(상위 10개 항목) 처리를 달성했습니다. 물론 직접 벤치마크해보시길 권장합니다.

또 Vector Sets는 디스크에 그래프 형태로 직렬화되므로, Redis를 재시작한 뒤 메모리에 다시 로드할 때 삽입 비용을 다시 치를 필요가 없습니다. 백만 개 요소를 로드하는 데 몇 초면 충분하고, 인메모리 HNSW에 다시 추가할 때 필요한 수 분이 걸리지 않습니다.

인덱스가 아닌 자료구조

지금까지는 모두 저수준 이야기에 관한 것이었습니다. 하지만 제게 Vector Sets에서 가장 흥미로운 부분은 데이터 모델과 이를 뒷받침하는 API입니다. 많은 데이터베이스가 벡터 유사도를 일종의 인덱스로 제공하지만, 여기는 Redis이고 Redis에서는 모든 것이 자료구조입니다. 이번에도 예외는 아닙니다. 요소를 추가하는 방식은 이런 식입니다:

VADD mykey FP32 …blob of data… item1

이런 식으로 이어집니다. 원한다면 키마다 하나씩, 여러 개의 작은 Vector Sets를 가질 수 있습니다. 여기서 중요한 점은 벡터를 N개의 서로 다른 키로 나누면(삽입하는 항목을 해싱하는 등의 방식으로 어떤 키를 선택할지 정하면), 서로 다른 키에 대한 여러 VSIM 호출을 하나의 응답으로 병합할 수 있다는 것입니다:

VSIM word_embeddings_int8 ele "banana" WITHSCORES COUNT 4
1) "banana"
2) "0.9997616112232208"
3) "bananas"
4) "0.8758847117424011"
5) "pineapple"
6) "0.8288004100322723"
7) "mango"
8) "0.8179697692394257"

서로 다른 키와 인스턴스에서 이런 결과를 몇 개 얻으면, 점수(1은 동일, 0은 정반대 벡터를 의미)를 기준으로 정렬하기만 하면 끝입니다.

그래서 제 느낌으로는 Vector Sets를 다양한 패턴으로 조합해 많은 벡터(상당히 많은 RAM을 소비합니다)를 여러 인스턴스에 나누어 처리할 수 있습니다. 또한 분할하면 쓰기가 선형적으로 확장된다는 점도 흥미롭습니다. 각 서브셋이 특정 키에 매핑되고, 여러 삽입을 병렬로 수행할 수 있기 때문입니다.

늘 그렇듯, 지금은 당연해 보이지 않는 많은 활용 패턴을 Redis 커뮤니티가 찾아낼 것입니다.

필터링은 어떻게 동작하는가

필터링에 대해 말하자면, 스레딩도 Redis에서는 흔치 않았는데 JSON은 오죽하겠습니까! 하지만 이번에는 처음으로 Redis API에서, 사용자에게 직접 드러나는 방식으로 JSON을 노출할 만한 좋은 이유를 찾았습니다:

VGETATTR word_embeddings_int8 banana
{"len": 6}

기본적으로 VSETATTR / VGETATTR(그리고 VADD로 항목을 추가할 때 JSON 속성을 직접 설정하는 동등한 옵션)를 사용해 원하는 항목에 문자열을 연결할 수 있습니다.

그러면 다음과 같은 일을 할 수 있습니다:

VSIM word_embeddings_int8 ele "banana" FILTER ".len == 3"
 1) "yam"
 2) "pea"
 3) "fig"
 4) "rum"
 5) "ube"
 6) "oat"
 7) "nut"
 8) "gum"
 9) "soy"
10) "pua"

필터 표현식은 프로그래밍 언어가 아니라, 고급 프로그래밍 언어의 if() 문 안에 쓸 수 있는 것과 같은 것입니다. &&, ||, 그리고 당연한 모든 연산자 등을 사용할 수 있습니다(하지만 앞으로 몇 가지를 더 추가하게 될 것 같습니다).

자세한 내용은 문서에 있고, 메모리 사용 예제나 특정 기능에 대한 심층 논의 등도 담겨 있습니다. 곧 문서를 더 보강할 수 있기를 바랍니다. 지금은 정말(정말!) Vector Sets를 마음에 들어하시길 바랍니다. 버그를 발견하면 꼭 알려주세요 :)