RIP, 벡터 데이터베이스

┌───────────────┐
│ root centroid │
└───────────────┘
...

K::Vector(C0L0) = vec![0.45, 0.32, ...]
K::Id(C0L0) = 7
K::Vector(C0L1) = vec![-0.28, 0.96, ...]
...

K::AttrIndex(

BM25 전체 텍스트 검색(full-text search)은 또 다른 명확하고 수요가 많은 쿼리 플랜이었습니다. 속성 검색과 유사하게, 전체 텍스트 검색은 먼저 쿼리 용어가 존재하는 문서를 찾는 방식으로 작동합니다 (일반적으로 'postings'라고 불림). FTS 인덱스의 경우, BM25 점수 계산에 필요한 `(용어 카운트, 문서 길이)` 메타데이터도 포함합니다:

시간이 지나면서 저희는 몇 가지 다른 인덱스 구조와 쿼리 엔진을 출시했습니다: 집계(aggregations), 정규식 검색(regex search), 유사 매칭(fuzzy matching), 희소 벡터 검색(sparse vector search), 그리고 속성 순서 지정(attribute ordering) — 이 모든 것이 동일한 벡터 중심 저장 레이아웃을 기반으로 구축되었습니다.

**벡터 우선 인덱스의 문제점**

ANN 기본 인덱스는 오늘날까지 거의 변하지 않았는데, 그 이유는 간단합니다. 객체 스토리지에서 ANN 검색에 매우 잘 작동하기 때문입니다. 이 아키텍처를 바탕으로, 저희는 100B개 이상의 벡터를 가진 단일 인덱스에 대해 1k+ QPS(초당 쿼리 수)에서 p99 읽기 지연 시간 200ms로 벡터 검색을 확장했습니다. 여기서 어떤 중대한 변경도 ANN 성능의 회귀(regressions)를 초래할 위험이 있습니다.

하지만 이 레이아웃은 저희가 지원하는 비-벡터 쿼리 형태에 대해 최첨단(state-of-the-art) 기술을 구현하는 데 세 가지 주요 방식으로 걸림돌이 됩니다: 저장 증폭(storage amplification), 쓰기 증폭(write amplification), 그리고 제한적인 벡터화(limited vectorization).

**저장 증폭 (Storage amplification)**

앞서 설명했듯이, turbopuffer는 현재 각 문서의 전체 내용을 해당 ANN 주소 아래에 배치합니다. 벡터가 하나만 있는 경우, 비-벡터 데이터는 벡터와 함께 한 번만 저장됩니다.

하지만, 문서 중첩(document nesting)이나 후기 상호작용(late interaction)과 같은 다중 벡터 표현의 경우, 이는 각 벡터마다 내용을 복제해야 함을 의미합니다. 이것이 저희가 겪고 있는 몇 가지 불운한 제한 사항의 이유입니다.

**쓰기 증폭 (Write amplification)**

문서가 삽입되거나 업데이트되거나 삭제될 때마다 SPFresh는 벡터들이 잘 클러스터링된 상태를 유지하도록 리밸런싱(rebalance)을 수행할 수 있습니다 (그렇지 않으면 재현율(recall)이 떨어질 수 있기 때문입니다). 문서의 모든 내용은 해당 문서 벡터의 ANN 주소로 키가 지정되어 저장되기 때문에, 이 리밸런싱은 전체 문서 내용과 이를 참조하는 모든 역색인(inverted index) (속성 및 FTS)을 이동시키는 연쇄 작용을 일으킵니다. 단지 하나의 벡터만 업데이트해도 수백 개의 속성과 그 인덱스가 이동할 수 있습니다.

이러한 쓰기 증폭(write amplification)은 너무 커서, 저희가 색인 처리량(indexing throughput)을 조정하려는 노력이 점차적인 수익 감소(diminishing returns)에 부딪히기 시작했습니다.

**제한된 벡터화 (Limited vectorization)**

최신 쿼리 엔진들은 벡터화되어 있습니다. 이들은 값 블록(blocks of values) 위로 긴 루프를 실행하여, 고정적인 블록당 비용을 상각하고, 압축률을 높이며, CPU 파이프라인을 가득 채우고, SIMD를 활용할 수 있게 합니다. 예를 들어 DuckDB는 2,048개 행 단위로 작동하고, ClickHouse는 최대 약 65k까지 하며, Lucene의 포스팅 블록(posting blocks)은 256개의 문서이고, 저희 ANN 인덱스는 약 100~200개의 클러스터에서 가장 잘 작동합니다. 모든 쿼리 계획에는 최적의 블록 크기가 있지만, 오늘날 이들은 모두 ANN 기본 인덱스에 의해 제약을 받습니다. CPU를 포화 상태로 유지하기 위해 수천 개의 문서를 담는 블록을 원하는 계획이라도 여전히 100~200개에 머물러 있습니다.

저희는 turbopuffer에서 이것이 얼마나 중요한지 이미 문서화했습니다. 저희의 첫 번째 버전은 전체 텍스트 검색(full-text search) 포스팅 리스트를 ANN 클러스터 경계를 따라 분할했는데, 중앙값 블록에는 겨우 약 1.5개의 포스팅만 담겨 있었습니다. FTS v2는 포스팅을 약 256개 단위의 고정된 블록으로 재작업하여, 인덱스는 10배 작아지고 쿼리는 최대 20배 빨라졌습니다. 포스팅 리스트가 그렇게 할 수 있었던 이유는 별도로 저장되고 문서들을 가리키기 때문에 그 레이아웃이 클러스터를 따를 필요가 없었기 때문입니다. 집계(Aggregations) 및 기타 스캔은 문서 자체를 읽으며, 이들은 클러스터당 하나의 블록으로 저장됩니다. ANN 주소가 기본 키인 한, 더 큰 것을 선호하더라도 블록 크기는 클러스터 크기에 의해 제한됩니다.

RIP, 기본 벡터 인덱스

이러한 문제들의 해결책은 간단합니다. ANN 주소에 키를 설정하지 않는 것입니다. 이것이 바로 turbopuffer v3가 변경하는 핵심입니다. 상상하실 수 있듯이, 이는 사소한 변화가 아닙니다.

v3는 모든 쿼리 플랜에서 상당한 성능 향상을 가져올 새로운 기반이며, 우리는 이달 초에 주요 이정표를 달성했습니다. 바로 turbopuffer v3의 CI(지속적 통합) 통과율이 100%라는 것입니다. 저희는 정확성에 중점을 두는 것부터 시작했습니다. 이제 그것을 *그리고* 빠르게 만들 것입니다. 벤치마크 수치가 떨어지는 것을 지켜보는 것은 큰 즐거움이라, 성능 최적화 작업의 첫날부터 여러분께 경험하게 해드리고 싶었습니다. v3를 프로덕션에 배포하기 전에 (그리고 그 이상으로) 성능 동등성을 목표로 하는 동안, 앞으로 몇 주에 걸쳐 벤치마크 결과를 공개할 예정입니다.

## turbopuffer

turbopuffer는 1조 개 이상의 문서를 호스팅하고, 초당 1,000만 건 이상의 쓰기(write)를 처리하며, 초당 25,000건 이상의 쿼리를 제공하는 빠른 검색 엔진입니다. 저희는 훨씬 더 많은 것을 감당할 준비가 되어 있습니다. 여러분의 쿼리를 저희에게 맡겨주시길 바랍니다.

시작하기