turbopuffer가 벡터 인덱스를 기본 인덱스에서 보조 인덱스로 전환함

TL;DR

• turbopuffer가 벡터 중심 저장 구조의 한계를 넘어 더 많은 쿼리 계획을 더 큰 규모로 처리하기 위해, ANN(근사 최근접 이웃) 주소를 기본 키로 삼지 않는 새 저장 엔진 turbopuffer v3로 전환함.
• v1은 문서를 ID와 벡터로 구성하고 객체 스토리지에 적합한 계층적 클러스터링을 적용했으며, SPANN에서 SPFresh로 이전해 증분 인덱싱을 지원함.
• 속성 필터링과 BM25 전문 검색을 비롯한 기능이 추가됐지만, ANN 인덱스가 기본 인덱스인 구조는 다중 벡터 문서의 저장 증폭, 인덱싱 과정의 쓰기 증폭, 쿼리별 블록 크기 제약을 낳음.
• 기존 구조는 단일 인덱스에서 1,000억 개 이상 벡터, 1k+ QPS, 200ms p99 읽기를 지원했으며, 이를 바꾸면 ANN 성능이 저하될 위험이 있음.
• turbopuffer v3는 CI 테스트 100% 통과를 달성했지만 현재 프로덕션보다 성능이 크게 낮으며, 설계와 정확성 작업을 마친 뒤 성능 최적화를 시작한 상태임.

v1: ID와 벡터

• turbopuffer 초기 버전의 문서는 ID와 벡터만 포함했으며, 당시 널리 쓰이던 그래프 기반 벡터 인덱스 대신 객체 스토리지에 더 잘 맞는 계층적 클러스터링 인덱스를 선택함.
• 처음에는 SPANN을 사용했고, 이후 증분 인덱싱을 지원하기 위해 SPFresh로 이전함. 벡터를 클러스터로 묶고 각 클러스터의 중심점을 다시 묶는 과정을 반복해 단일 루트를 가진 트리를 구성함.
• 저장 계층은 정렬되고 고유한 키를 제공하는 키-값 맵 형태임. 각 클러스터에는 ClusterId를, 클러스터 안의 각 벡터에는 조밀한 LocalId를 부여함.
• 벡터와 ID 등 문서 데이터는 ClusterId와 LocalId를 결합한 ANN 주소를 키로 저장함. ANN 주소가 모든 데이터의 기준이 되므로 ANN 인덱스가 기본 인덱스임.

v2: 속성 필터링과 전문 검색

• 속성 필터링과 전문 검색이라는 두 쿼리 계획이 turbopuffer v1에서 v2로의 비공식 전환을 이끔.

속성 필터링

• 고객이 문서에 속성 값을 추가하고 해당 값으로 벡터 검색 결과를 필터링하려는 수요가 생김. 빠르고 재현율 높은 필터링을 위해 속성 값에서 해당 값을 포함하는 문서의 ANN 주소로 연결되는 역인덱스를 구성함.
• 속성 투영(include_attributes)을 위해 ID와 벡터에 더해 문서 속성도 함께 저장함.

전문 검색

• BM25 전문 검색은 수요가 큰 쿼리 계획으로 추가됨. 전문 검색은 먼저 질의어가 포함된 문서를 찾으며, 이 문서 목록을 포스팅(postings)이라고 부름.
• BM25 점수 계산에 필요한 용어 빈도와 문서 길이 메타데이터도 전문 검색 인덱스에 포함함.
• 이후 집계, 정규식 검색, 퍼지 매칭, 희소 벡터 검색, 속성 정렬 등 여러 인덱스 구조와 쿼리 엔진을 추가했지만, 모두 벡터 중심 저장 구조를 기반으로 함.

벡터 기본 인덱스의 문제

• ANN 기본 인덱스는 객체 스토리지에서 ANN 검색을 매우 잘 처리하므로 지금까지 대체되지 않음. 이 구조로 단일 인덱스에서 1,000억 개 이상 벡터를 처리하고 1k+ QPS에서 200ms p99 읽기를 제공했으며, 큰 변경은 ANN 성능 회귀 위험을 동반함.
• 반면 비벡터 쿼리 형태에서는 저장 증폭, 쓰기 증폭, 제한적인 벡터화라는 세 가지 제약이 발생함.

저장 증폭

• 현재는 문서의 전체 내용을 해당 문서 벡터의 ANN 주소에 저장함. 벡터가 하나인 문서는 비벡터 데이터가 한 번만 저장됨.
• 문서 중첩이나 지연 상호작용(late interaction)처럼 문서 하나에 벡터가 여러 개 있으면 각 벡터마다 문서 내용을 복제해야 하며, 이 때문에 일부 제한이 발생함.

쓰기 증폭

• 문서를 삽입·갱신·삭제할 때 SPFresh는 벡터가 적절히 군집화되도록 재균형을 수행할 수 있음. 군집화가 나빠지면 재현율이 낮아질 수 있음.
• 문서 데이터 전체가 벡터의 ANN 주소를 키로 삼으므로 재균형 과정에서 문서 내용 전체와 이를 참조하는 속성·전문 검색 역인덱스까지 이동함. 벡터 하나를 갱신해도 수백 개의 속성과 해당 인덱스가 함께 이동할 수 있음.
• 쓰기 증폭 규모가 커 인덱싱 처리량을 높이려는 최적화가 수확 체감에 이르기 시작함.

제한적인 벡터화

• 최신 쿼리 엔진은 값 블록을 반복 처리하는 벡터화 방식을 사용함. 블록 단위 처리는 블록별 고정 비용을 분산하고 압축률을 높이며 CPU 파이프라인을 채우고 SIMD를 활용하게 함.
• DuckDB는 2,048행 배치, ClickHouse는 최대 약 6만 5,000행, Lucene 포스팅 블록은 문서 256개 단위로 처리함. ANN 인덱스는 문서 약 100~200개 규모의 클러스터에서 가장 잘 작동함.
• 쿼리 계획마다 최적 블록 크기가 다르지만 현재는 모두 ANN 기본 인덱스에 묶여 있음. CPU를 포화시키기 위해 문서 수천 개 단위의 블록을 원하는 쿼리도 100~200개 규모에 제한됨.
• turbopuffer의 첫 전문 검색 버전은 ANN 클러스터 경계를 따라 포스팅 목록을 나눴고, 블록당 포스팅 중앙값은 약 1.5개였음. 전문 검색 v2는 포스팅을 약 256개 단위의 고정 블록으로 재구성해 인덱스 크기를 10배 줄이고 쿼리를 최대 20배 빠르게 처리함.
• 포스팅 목록은 별도 저장되며 문서를 가리키므로 클러스터 구조를 따를 필요가 없었음. 반면 집계와 기타 스캔은 문서 자체를 읽고 문서는 클러스터당 한 블록으로 저장되므로, ANN 주소가 기본 키인 한 원하는 블록 크기가 더 커도 클러스터 크기에 제한됨.

기본 벡터 인덱스와의 작별

• 해결책은 ANN 주소를 키로 사용하지 않는 것임. turbopuffer v3는 바로 이 변경을 적용하며, 이는 간단한 변경이 아님.
• 이달 초 turbopuffer v3에서 CI 테스트 100% 통과라는 주요 이정표를 달성함. 그러나 프로덕션 turbopuffer보다 성능이 크게 낮았으며, 설계 기반과 정확성에 우선 집중한 뒤 성능 최적화를 막 시작한 단계임.
• 변경 사항을 정리하면서 벤치마크 결과를 추가할 예정이며, 새 아키텍처와 프로덕션에서 더 많은 쿼리 계획을 빠르게 처리할 최적화 방법을 차례로 설명할 예정임.
• turbopuffer는 문서 1조 개 이상을 호스팅하고 초당 1,000만 건 이상의 쓰기를 처리하며 초당 2만 5,000건 이상의 쿼리를 제공함. 더 큰 규모의 작업을 처리할 준비가 돼 있다는 설명과 함께 서비스 시작 안내를 제공함.