RIP, vectordatabase

We passen de opslagarchitectuur van turbopuffer aan. De nieuwe engine, informeel "turbopuffer v3" genoemd, verandert de manier waarop documenten en indexen worden gestructureerd, geschreven, gecompacteerd en bevraagd in turbopuffer. Dit stelt ons in staat om veel meer query-plannen te ondersteunen op een veel grotere schaal.

Turbopuffer werd gelanceerd als een serverloze vectordatabase, sterk gespecialiseerd in het uitvoeren van extreem goedkope en redelijk snelle vectorzoekopdrachten. Object storage als 'source of truth' zorgde voor de economische voordelen, terwijl gelaagde NVMe SSD/geheugencaches zorgden voor de prestaties. De waarde van deze specifieke afwegingen werd bevestigd door onze eerste klanten, waaronder Cursor en Notion.

In de loop van de tijd is turbopuffer geëvolueerd naar een algemene database voor zoekopdrachten (en andere zaken). De query-engine is meegegroeid om al deze query-plannen te ondersteunen, maar de opslagarchitectuur is grotendeels ongewijzigd gebleven: de ANN-vectorindex (Approximate Nearest Neighbor) was en is nog steeds de primaire index waar alle andere indexen en query-plannen omheen draaien.

We hebben de primaire ANN-index tot het uiterste gepusht, maar het is tijd om verder te gaan. We zijn bezig met de overstap naar een nieuwe primaire index, waardoor de ANN "gewoon een andere" secundaire index wordt. We dachten dat het leuk zou zijn om de deuren open te zetten en jullie dit proces te laten volgen.

In deze eerste update leggen we de basis door uit te leggen waarom we dit doen. Laten we een korte reis maken van tpuf v1 naar vandaag.

v1: een ID en een vector

In de eerste versie van turbopuffer bestonden documenten uit niets anders dan een ID en een vector. De heersende wisdom van dat moment wees naar grafiekgebaseerde vectorindexen, maar een hiërarchische clusteringindex werkt beter met object storage. We begonnen met SPANN en migreerden uiteindelijk naar SPFresh om incrementele indexering te ondersteunen.

Vectoren worden geclusterd in groepen, waarvan de centroïden op hun beurt weer worden geclusterd, wat herhaald wordt om een boomstructuur met één wortel (root) te vormen.

┌───────────────────┐
│   root centroid   │
└───────────────────┘
╱          │          ╲
╱           │           ╲
┌───────────────────┐ ┌───────────────────┐ ┌───────────────────┐
│   leaf centroid   │ │   leaf centroid   │ │   leaf centroid   │
└───────────────────┘ └───────────────────┘ └───────────────────┘
╱       ╲             ╱       ╲             ╱       ╲
╱         ╲           ╱         ╲           ╱         ╲
┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐
│ vector │ │ vector │ │ vector │ │ vector │ │ vector │ │ vector │
└────────┘ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘

We hebben dit geïmplementeerd bovenop een opslaglaag die functioneert als een key-value map met gesorteerde en unieke sleutels. Elk cluster krijgt een ClusterId, en vectoren binnen elk cluster krijgen een dense LocalId.

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

// cluster centroid voor C0 is zelf weer geclusterd op het volgende niveau van de boom
K::Vector(C1L4) = vec![0.64, -0.48, ...]
K::Id(C1L4) = C0

Zoals hierboven te zien is, wordt alles gesleuteld op ClusterId en LocalId (bijv. C0L1), wat we samen het ANN-adres noemen. Dit is wat we bedoelen als we zeggen dat de ANN-index de primaire index is.

v2: attribuutfiltering en full-text search

Twee nieuwe query-plannen markeerden de informele overgang van turbopuffer v1 naar v2: attribuutfiltering en full-text search.

Attribuutfiltering

Natuurlijk wilden klanten attribuutwaarden kunnen toevoegen en vectorzoekopdrachten daarop kunnen filteren. Om filtering snel en met een hoge recall te maken, hebben we dit gemodelleerd als een inverted index die een attribuutwaarde koppelt aan het ANN-adres van de documenten die deze bevatten.

K::AttrIndex("family", "Alcidae") -> vec![C0L3, C1L2, C1L3, ...]
K::AttrIndex("genus", "Fratercula") -> vec![C0L3, C1L2, C1L9, ...]

Voor projecties (include_attributes) hebben we de documentattributen ook opgeslagen naast het ID en de vector.

K::Vector(C0L0) = vec![0.45, 0.32, ...]
K::Id(C0L0) = 7
K::Attr(C0L0, "family") = "Alcidae"
K::Attr(C0L0, "genus") = "Fratercula"

Full-text search

BM25 full-text search was een andere evidente en veelgevraagde query-functie. Vergelijkbaar met attribuutzoekopdrachten werkt full-text search door eerst de documenten te vinden waarin de zoekterm voorkomt (meestal "postings" genoemd). Voor een FTS-index voegen we ook de (term count, document length) metadata toe die nodig is voor BM25-scoring:

K::FTS("description", "Atlantic") -> vec![(C0L0, 2, 37), (C9L4, 1, 42), ...]
K::Attr(C0L0, "description") -> "A sharply dressed black-and-white seabird with a \
huge, multicolored bill, the Atlantic Puffin is often \
called the clown of the sea. It breeds in burrows on \
islands in the North Atlantic, and winters at sea."

In de loop van de tijd hebben we diverse andere indexstructuren en query-engines uitgebracht: aggregaties, regex-search, fuzzy matching, sparse vector search en attribuut-sortering — allemaal gebouwd rond dezelfde vector-primaire opslaglayout.

Het probleem met een primaire vectorindex

De ANN-primaire index is tot op heden grotendeels intact gebleven om één simpele reden: het werkt echt heel goed voor ANN-zoekopdrachten op object storage. Met deze architectuur hebben we vector search gepusht naar enkele indexen van 100 miljard+ vectoren, met p99 reads van 200 ms bij 1k+ QPS.

Elke significante wijziging hierin brengt het risico met zich mee dat de ANN-prestaties verslechteren. Echter, deze layout houdt ons tegen om state-of-the-art te zijn voor de non-vector query-vormen die we ondersteunen, op drie belangrijke manieren: opslagamplificatie, schrijfamplificatie en beperkte vectorisatie.

Opslagamplificatie

Zoals hierboven beschreven, plaatst turbopuffer momenteel de volledige inhoud van elk document onder het ANN-adres. Wanneer er slechts één vector is, worden de non-vector data slechts één keer naast de vector opgeslagen.

Bij multi-vector representaties van een document, zoals document-nesting of late interaction, betekent dit echter dat we de inhoud voor elke vector moeten dupliceren. Dit is de reden voor sommige van onze minder ideale limieten.

Schrijfamplificatie

Telkens wanneer een document wordt ingevoegd, bijgewerkt of verwijderd, kan SPFresh de vectoren herbalanceren om ervoor te zorgen dat ze goed geclusterd blijven (anders kan de recall lijden).

Omdat alles in een document is opgeslagen met de sleutel van het ANN-adres van de vector van het document, cascadeert deze herbalancering naar het verplaatsen van de volledige documentinhoud, evenals alle inverted indexen (attribuut en FTS) die hiernaar verwijzen. Het bijwerken van slechts één vector kan honderden attributen en hun indexen verplaatsen. Deze schrijfamplificatie is zo groot dat onze pogingen om de indexeringsdoorvoer te optimaliseren, tekenen van afnemende meeropbrengst vertonen.

Beperkte vectorisatie

Moderne query-engines zijn gevectoriseerd: ze voeren strakke loops uit over blokken waarden, wat vaste kosten per blok amortiseert, beter comprimeert, de CPU-pipeline vol houdt en SIMD ontsluit. DuckDB werkt bijvoorbeeld in batches van 2.048 rijen, ClickHouse tot circa 65k, de posting-blocks van Lucene zijn 256 documenten, en onze ANN-index werkt het best met clusters van ongeveer 100–200 documenten.

Elk query-plan heeft een optimale blokgrootte, maar vandaag worden ze allemaal beperkt door de ANN-primaire index. Een plan dat blokken van duizenden documenten wil om de CPU verzadigd te houden, zit nog steeds vast aan 100–200.

We hebben al gedocumenteerd hoe belangrijk dit is in turbopuffer. Onze eerste versie van full-text search partitioneerde posting-lijsten langs ANN-clustergrenzen, en het mediane blok bevatte slechts ~1,5 postings. FTS v2 herstructureerde postings in vaste blokken van ~256, waardoor de index 10x kleiner werd en queries tot 20x sneller. Posting-lijsten konden dit omdat ze apart worden opgeslagen en naar documenten wijzen, waardoor hun layout niet de clusters hoeft te volgen. Aggregaties en andere scans lezen de documenten zelf, en die zijn opgeslagen als één blok per cluster. Zolang het ANN-adres de primaire sleutel is, is hun blokgrootte beperkt tot de clustergrootte, zelfs als ze een grotere grootte zouden prefereren.

RIP, primaire vectorindex

De oplossing voor deze problemen is simpel: gebruik het ANN-adres niet als sleutel. Dat is precies de wijziging die turbopuffer v3 doorvoert. Zoals je je kunt voorstellen, is dit geen triviale aanpassing.

We hebben onlangs een belangrijke mijlpaal bereikt: sinds begin deze maand slaagt 100% van de CI op turbopuffer v3. Echter, dit betekende een aanzienlijke prestatie-regressie ten opzichte van de productieversie van turbopuffer. Dat is geen verrassing! Tot nu toe hebben we ons primair gericht op het fundamentele ontwerp en de correctheid, en we zijn pas net begonnen met het tunen.

Het is erg leuk om de cijfers te zien dalen, dus we wilden jullie vanaf dag nul betrekken bij dit optimalisatieproces. We zullen resultaten toevoegen aan de benchmarks terwijl we opschrijven wat er is veranderd. Onderweg zullen we dieper ingaan op de nieuwe architectuur en de optimalisaties die turbopuffer uiteindelijk sneller zullen maken voor meer query-plannen in productie.