어제 마침내 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 코어의 일부입니다. 저는 처음에 모듈로 개발을 시작했고, 나중에는 구현이 그대로 modules 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 구현들과 비교해 몇 가지 차이가 생겼습니다. 저는 툼스톤(tombstone) 삭제를 사용하지 않고, 노드가 삭제되는 순간 실제로 링크를 끊고 다른 적절한 이웃 후보들과 다시 연결합니다. 이를 위해 제 구현은 링크가 반드시 상호적(reciprocal)이어야 하도록 강제합니다. 더 이상 최선을 다하는(best effort) 수준의 속성이 아닙니다. 이는 다시 삽입 과정에서 해야 할 일들을 꽤 많이 바꾸게 됩니다.

HNSW에서 제가 또 하나 수정한 부분은 predicate 함수로 그래프를 스캔할 수 있도록 한 것입니다. 그래서 주어진 식에 부합하는 노드를 요청할 수 있습니다. 이를 위해서는 탐욕적 그래프 탐색 알고리즘을 어느 정도 수정해야 합니다. 방문할 후보 노드를 수집하고 결과 집합을 모으는 과정은 물론, 질의의 선택도(selectivity)가 너무 높을 경우를 대비한 조기 종료 조건도 필요합니다. 당연히 전체 그래프 스캔을 유발하고 싶지는 않으니까요.

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

1. 모든 벡터 유사도 요청을 스레드로 처리하는 것입니다. 네, Redis에서는 새로운 시도입니다. 저는 일반적으로 단일 스레드와 shared nothing 설계가 좋은 설계라고 믿지만, 벡터는 특별하다고 생각합니다. Redis가 다루는 다른 자료구조들보다 훨씬 느리니까요. 보너스로, 스레드 기반 VSIM(벡터 유사도 질의를 수행하는 명령)을 구현하면서 몇 가지 트릭을 쓰면 쓰기 연산의 읽기 절반과 쓰기 절반을 두 부분으로 나눌 수 있다는 것도 알게 되었습니다. 그래서 이웃 후보를 수집하는 과정은 백그라운드에서 일어나고, 실제 삽입은 포그라운드에서 수행됩니다. 다만 이 분리는 기본값이 아니며, VADD의 CAS 옵션으로 강제해야 합니다.
2. 양자화(quantization)를 지원하고, 심지어 이를 기본값으로 만들고 싶었습니다. 그래서 Vector Sets는 8비트 양자화와 이진 양자화를 모두 제공합니다. 차원 축소를 위한 랜덤 프로젝션(random projection)도 지원합니다. 하지만 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 set을 가질 수도 있습니다. 그리고 여기서 중요한 점은 벡터를 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은 더 말할 것도 없겠죠! 하지만 이번에 처음으로 JSON을 Redis API에 사용자 측면으로 직접 노출할 만한 좋은 이유를 찾았습니다:

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를 즐겨 주시길 바랍니다. 정말(정말!) 기대하고 있습니다. 버그를 발견하시면 꼭 알려주세요 :)