- turbopuffer가 벡터 검색 전용 DB에서 다양한 검색과 집계를 처리하는 엔진으로 확장하기 위해, v3에서 데이터 저장 구조를 개편 중임
- 기존에는 벡터가 저장된 위치를 기준으로 문서와 다른 인덱스까지 배치했지만, 이제 문서 저장을 벡터 인덱스에서 분리해 각 쿼리에 맞게 최적화함
- 기존 구조에서는 문서를 여러 벡터로 표현하면 내용이 중복되고, 벡터 위치를 조정할 때 문서와 관련 인덱스까지 옮겨야 해 저장 공간과 쓰기 비용이 커짐
- 문서를 한꺼번에 처리하는 크기도 벡터 클러스터에 묶여 집계 성능을 제한했음. 앞서 전문 검색의 배치를 바꿨을 때는 인덱스 크기가 10분의 1로 줄고 쿼리가 최대 20배 빨라졌음
- v3는 자동화 테스트를 모두 통과했으며, 앞으로 벤치마크를 공개하면서 기존 버전 이상의 성능을 확보한 뒤 운영 환경에 도입할 계획임
- turbopuffer는 매우 저렴하면서 적절히 빠른 벡터 검색에 특화한 서버리스 벡터 데이터베이스 v1으로 출발함
- 객체 스토리지를 원본 데이터 저장소로 삼아 비용 효율을 확보하고, 계층형 NVMe SSD/메모리 캐시로 성능을 확보함
- Cursor와 Notion 등 초기 고객을 통해 이 절충 방식의 가치를 확인함
- v2에서는 텍스트 검색과 정규식 검색을 강화했으며, Linear의 동기화 엔진처럼 검색 외 용도로도 사용되고 있음
- 쿼리 엔진은 확장됐지만 저장 구조는 대체로 그대로였음
- ANN 벡터 인덱스가 기본 인덱스로 남아 다른 인덱스와 쿼리 실행 계획의 중심 역할을 해 왔음
- 이 구조가 GROUP BY와 집계 등의 실행 계획을 제약함
- v3는 문서와 인덱스의 배치, 쓰기, 압축 병합, 조회 방식을 바꿈
- 벡터 검색을 포함한 검색 전반을 가속하고, 더 많은 SQL 쿼리를 turbopuffer로 옮겨 빠르게 실행할 기반을 마련하려 함
- 초기 문서는 ID와 벡터만으로 구성됐음
- 당시 널리 쓰이던 그래프 기반 벡터 인덱스보다 객체 스토리지에 잘 맞는 계층적 클러스터링 인덱스를 선택함
- SPANN으로 시작한 뒤 증분 인덱싱을 지원하기 위해 SPFresh로 전환함
- 벡터를 묶고, 각 클러스터의 중심점을 다시 묶는 작업을 반복해 하나의 루트를 가진 트리를 구성함
- 저장 계층은 정렬된 고유 키를 가진 키-값 맵이며, 각 클러스터에 ClusterId, 내부 벡터에 조밀한 LocalId를 부여함
- 두 식별자를 합친 C0L1 같은 값을 ANN 주소라고 부름
- 벡터와 ID 모두 ANN 주소를 키로 사용하며, 상위 계층에서는 클러스터 중심점의 ID가 하위 클러스터를 가리킴
- ANN 인덱스가 기본 인덱스라는 말은 이 주소가 저장 구조의 기준이라는 뜻임
- 속성 필터링과 전문 검색이라는 두 실행 계획의 추가가 비공식적인 v1에서 v2로의 전환점이 됐음
- 벡터 검색에 속성 조건을 적용하기 위해 역색인을 도입함
- 빠른 필터링과 높은 재현율을 위해 속성 값을 해당 문서들의 ANN 주소에 매핑함
- 예를 들어 family=Alcidae, genus=Fratercula 조건마다 일치하는 ANN 주소 목록을 저장함
- include_attributes로 속성을 반환할 수 있도록 문서 속성도 ID, 벡터와 함께 ANN 주소 아래에 저장함
- BM25 전문 검색도 검색어가 포함된 문서 목록인 포스팅을 먼저 찾는 방식으로 구현함
- 전문 검색 인덱스에는 문서의 ANN 주소와 함께 BM25 점수 계산에 필요한 검색어 출현 횟수와 문서 길이를 저장함
- 이후 추가한 실행 기능도 같은 벡터 우선 저장 구조를 기반으로 함
- 집계, 정규식 검색, 퍼지 매칭, 희소 벡터 검색, 속성 기준 정렬을 지원함
- 기존 구조는 객체 스토리지의 ANN 검색에서 매우 효과적이어서 오랫동안 유지됐음
- 벡터 1,000억 개 이상을 담은 단일 인덱스에서 1,000 QPS 이상, p99 읽기 지연 200ms를 달성함
- 이 구조를 크게 바꾸면 ANN 성능이 퇴보할 위험이 있음
- 반면 비벡터 쿼리에서 최고 수준의 성능을 내는 데는 저장 증폭, 쓰기 증폭, 제한된 벡터화라는 세 가지 장애물이 있음
- 저장 증폭은 문서 전체 내용을 ANN 주소 아래에 두는 방식에서 발생함
- 벡터가 하나라면 비벡터 데이터도 한 번만 저장함
- 문서 중첩이나 후기 상호작용(late interaction)처럼 문서를 여러 벡터로 표현하면 벡터마다 문서 내용을 복제해야 함
- 이 구조 때문에 네임스페이스당 벡터 열 수 등 일부 제한이 생김
- 문서를 삽입, 수정, 삭제할 때 SPFresh는 클러스터 품질을 유지하기 위해 벡터를 재균형할 수 있음
- 클러스터링 품질이 떨어지면 재현율도 낮아질 수 있음
- 모든 문서 데이터가 벡터의 ANN 주소를 키로 사용하므로 재균형의 영향이 문서 전체로 번짐
- 문서 내용뿐 아니라 이를 참조하는 속성 역색인과 전문 검색 역색인까지 이동해야 함
- 벡터 하나의 수정으로 수백 개의 속성과 관련 인덱스가 이동할 수 있음
- 이 쓰기 증폭이 커서 인덱싱 처리량을 추가로 튜닝해도 개선 효과가 점차 줄어들고 있음
- 현대 쿼리 엔진의 벡터화 실행은 값의 블록을 반복 처리해 블록별 고정 비용을 분산하고, 압축 효율과 CPU 파이프라인 활용도를 높이며 SIMD를 활용함
- 최적의 블록 크기는 실행 계획마다 다름
- DuckDB는 2,048행 단위, ClickHouse는 최대 약 65,000행 단위로 처리함
- Lucene의 포스팅 블록은 문서 256개이며, turbopuffer의 ANN 인덱스는 문서 약 100~200개로 구성한 클러스터에서 가장 잘 동작함
- 현재 문서 배치는 ANN 기본 인덱스에 묶여 있어, CPU를 충분히 활용하려면 수천 개 문서가 필요한 실행 계획도 100~200개 단위로 제한됨
- 전문 검색 v2는 저장 배치 변경의 효과를 이미 보여줌
- 첫 버전은 ANN 클러스터 경계에 맞춰 포스팅 목록을 나눴으며, 블록당 포스팅 수의 중앙값이 약 1.5개에 불과했음
- 포스팅을 약 256개씩 담는 고정 블록으로 개편한 뒤 인덱스 크기는 10분의 1로, 쿼리 시간은 최대 20분의 1로 줄었음
- 포스팅 목록은 문서와 별도로 저장하고 문서를 참조하므로 클러스터와 독립적인 배치가 가능했음
- 집계와 다른 스캔은 문서 자체를 읽는데, 문서는 클러스터당 한 블록으로 저장됨
- ANN 주소가 기본 키인 한, 이런 실행 계획은 더 큰 블록을 원해도 클러스터 크기에 묶임
- 해결책은 ANN 주소를 기본 키로 사용하지 않는 것이며, v3는 새 기본 인덱스로 옮기고 ANN을 다른 인덱스와 같은 보조 인덱스로 전환함
- 원리는 단순하지만 구현 변경은 간단하지 않음
- 새 구조를 모든 쿼리 실행 계획의 성능을 크게 개선할 토대로 삼음
- 먼저 정확성에 집중했으며, 9월 초 v3에서 CI가 100% 통과하는 이정표를 달성함
- 다음 단계는 성능 최적화임
- 향후 몇 주 동안 벤치마크를 공개할 예정임
- 프로덕션 배포에 앞서 기존 버전과 동등한 성능을 확보하고, 그 이상으로 개선하는 것을 목표로 함