벡터 인덱스를 기본 키에서 내리는 turbopuffer v3, 저장 구조를 다시 짜는 이유

TL;DR

• turbopuffer는 v3에서 저장 구조의 중심을 ANN 벡터 인덱스에서 새 기본 인덱스로 옮기고, ANN을 여러 보조 인덱스 중 하나로 내린다. 목표는 텍스트, 정규식, 벡터 검색을 모두 빠르게 하고 더 많은 SQL 질의를 처리하는 것이다.
• 지금까지는 문서의 모든 내용이 벡터의 ANN 주소(클러스터 ID와 로컬 ID) 밑에 저장됐다. 이 설계는 벡터 검색에는 잘 맞았지만 GROUP BY와 집계 같은 질의 계획을 제약했다.
• 병목은 셋이다. 다중 벡터 문서에서 내용이 벡터 수만큼 중복되는 저장 증폭, 재균형 때 문서와 역색인이 통째로 움직이는 쓰기 증폭, 질의 계획이 원하는 블록 크기를 쓰지 못하는 제한된 벡터화다.
• v3는 CI 전체 통과라는 정확성 이정표를 넘었지만 성능은 아직 입증 단계다. 벤치마크는 앞으로 몇 주에 걸쳐 공개하고, 성능이 기존 수준과 같아지는 지점을 넘긴 뒤에 운영에 투입한다.

벡터 전용 데이터베이스에서 출발한 설계

turbopuffer는 서버리스 벡터 데이터베이스로 시작했다. 오브젝트 스토리지를 원본 저장소로 삼아 비용을 낮추고 NVMe SSD와 메모리로 이뤄진 계층 캐시로 속도를 맞췄다. 글은 이 절충이 Cursor와 Notion 같은 초기 고객에게 검증됐다고 적는다. 이후 텍스트와 정규식 검색이 강해졌고(v2), Linear의 동기화 엔진처럼 검색이 아닌 용도에도 쓰이게 됐다.

질의 엔진은 이런 변화를 따라 진화했지만 저장 구조는 거의 그대로였다. 모든 인덱스와 질의 계획이 ANN 벡터 인덱스를 중심으로 돌았다는 뜻이다. 저자는 이 벡터 중심 구조를 더는 밀어붙일 수 없는 지점까지 끌고 왔다고 말한다.

모든 것이 ANN 주소에 매달려 있던 구조

v1의 문서는 ID와 벡터가 전부였다. 당시 통념은 그래프 기반 벡터 인덱스였지만 오브젝트 스토리지에는 계층적 클러스터링이 더 잘 맞아 SPANN으로 시작했고 증분 색인을 위해 SPFresh로 옮겼다. 벡터를 묶어 클러스터로 만들고 그 중심점을 다시 묶어 하나의 루트까지 트리를 쌓는 방식이다. 저장소는 정렬된 유일 키를 가진 키-값 맵이었고 각 클러스터에 ClusterId를, 클러스터 안의 벡터에 조밀한 LocalId를 붙였다. 두 값을 합친 것이 글이 말하는 ANN 주소이고 이 주소로 모든 것을 색인하는 것이 ANN 인덱스가 기본 인덱스라는 말의 의미다.

v2에서는 속성 필터링과 전문 검색이 들어왔다. 필터는 속성 값에서 그 값을 가진 문서의 ANN 주소 목록으로 가는 역색인으로 만들어 빠르고 재현율 높게 유지했다. BM25 전문 검색도 같은 방식으로, 용어가 들어 있는 문서의 목록에 BM25 점수에 필요한 용어 빈도와 문서 길이를 함께 담았다. 이후 집계, 정규식, 퍼지 매칭, 희소 벡터 검색, 속성 정렬도 같은 벡터 중심 배치 위에 얹혔다.

벡터 중심 구조가 발목을 잡는 세 지점

이 구조가 오래 유지된 이유는 ANN 검색에 정말 잘 맞았기 때문이다. 글에 따르면 단일 인덱스에 1,000억 개 이상의 벡터를 두고 초당 1,000건 이상의 질의에서 p99 읽기 지연 200ms를 냈다. 그래서 어떤 큰 변경이든 ANN 성능의 퇴행 위험을 안는다. 그럼에도 벡터가 아닌 질의 형태에서는 세 가지가 최고 수준에 이르는 것을 막는다.

첫째는 저장 증폭이다. 문서 전체 내용이 ANN 주소 밑에 저장되므로 벡터가 하나면 비벡터 데이터도 한 번만 저장된다. 그러나 문서를 중첩하거나 후기 상호작용(late interaction) 같은 다중 벡터 표현을 쓰면 벡터마다 내용이 복제된다. 글은 이것이 일부 불편한 제한의 이유라고 밝힌다.

둘째는 쓰기 증폭이다. 삽입, 갱신, 삭제가 일어나면 SPFresh가 벡터를 재균형해 클러스터 품질을 지킨다. 그런데 문서의 모든 것이 ANN 주소에 묶여 있어서 재균형은 문서 내용 전체와 그것을 가리키는 속성 및 전문 검색 역색인의 이동으로 번진다. 벡터 하나를 갱신해도 수백 개의 속성과 그 인덱스가 움직일 수 있다. 저자는 이 증폭이 커서 색인 처리량을 튜닝하는 노력이 수확 체감에 들어섰다고 말한다.

셋째는 제한된 벡터화다. 현대 질의 엔진은 값 묶음에 대해 촘촘한 반복문을 돌려 고정 비용을 분산하고 압축률과 SIMD 효율을 얻는다. 글은 DuckDB가 2,048행, ClickHouse가 최대 약 65,000행, Lucene의 포스팅 블록이 256문서 단위로 일한다고 비교한다. 반면 turbopuffer의 ANN 인덱스는 100~200개 문서의 클러스터에서 가장 잘 동작한다. 질의 계획마다 최적 블록 크기가 다른데 지금은 모두 ANN 클러스터 크기에 묶여 있다.

이 영향은 이미 측정됐다. 전문 검색 첫 버전은 포스팅 목록을 ANN 클러스터 경계에 따라 쪼개서 블록 하나에 든 포스팅이 중앙값 약 1.5개였다. FTS v2가 포스팅을 약 256개의 고정 블록으로 재구성하자 인덱스는 10배 작아지고 질의는 최대 20배 빨라졌다. 포스팅 목록은 문서를 가리키는 별도 저장 구조라서 클러스터 배치를 따를 필요가 없었기 때문에 가능했다. 반면 집계와 스캔은 문서 자체를 읽는데 문서가 클러스터당 한 블록으로 저장되어 있어, ANN 주소가 기본 키인 한 더 큰 블록을 쓸 수 없다.

ANN 주소를 기본 키로 쓰지 않는다

해법은 단순하게 요약된다. ANN 주소로 색인하지 않는다는 것이다. v3는 바로 이 변경이고 ANN은 여러 보조 인덱스 중 하나가 된다. 저자는 이것이 사소한 변경이 아니라고 덧붙인다.

진행 상황은 두 단계로 나뉜다. 정확성에 먼저 집중해 글이 게시된 달 초에 v3에서 CI가 100% 통과하는 이정표를 넘었다. 이제 빠르게 만드는 단계이고 성능 수치가 내려가는 과정을 공개적으로 따라오도록 벤치마크를 앞으로 몇 주 동안 공개한다. 성능이 기존과 같은 수준에 이르고 그 이상으로 넘어선 뒤에 운영 환경에 v3를 배포한다는 계획이다. 성능 개선 폭은 글에서 수치로 약속하지 않았으며 모두 앞으로 공개될 벤치마크로 확인해야 하는 주장이다.

글 끝의 소개에 따르면 turbopuffer는 1조 개 이상의 문서를 호스팅하고 초당 1,000만 건 이상의 쓰기와 2만 5천 건 이상의 질의를 처리한다. 이 수치는 회사의 자체 소개다.

참고 자료

Dan Harrison — RIP, vector database (turbopuffer blog)

SPANN (arXiv) · SPFresh (arXiv) — 글이 인용한 인덱스 논문이며 이 노트에서 본문은 읽지 않았다.