PaperlayerView exact revision on arXiv

Source-linked AI summary

PrairieFire: Igniting High-Throughput Updates in Large-Scale Approximate Nearest Neighbor Search

Yuchen Huang, Baiteng Ma, Yiping Sun, Xiao Chen, Rui Ma, Yue Chen, Jinwei Zhang, Xiaocheng Zhong, Zhiyong Wang, Yao Hu, Erci Xu, Chuliang Weng

arXiv:2610.23232v1cs.DB

TL;DR

SSD-based ANNS indexes must keep pace with continuous changes to data and embedding models, but existing systems have limited update throughput. PrairieFire uses buffered updates, batched local rebuilds, cascaded adjustments, concurrency control, and CPU-GPU-SSD cooperation. It reports higher update and search throughput than state-of-the-art systems, alongside improved hardware efficiency and production results.

  • Problem

    Existing SSD-based ANNS systems cannot keep pace with continuous data and embedding-model changes at the update throughput required for fresh large-scale indexes.

    Source: §1 · p. 1, §3.1 · p. 3

  • Method

    PrairieFire combines buffered updates and batched local rebuilds with cascaded centroid adjustments, fine-grained concurrency control, and CPU-GPU-SSD cooperation.

    Source: §1 · pp. 1–2

  • Results

    PrairieFire sustains approximately 3–35× update throughput while maintaining approximately 3–5× search throughput, with comparable or higher search accuracy than baselines.

    Source: §1 · p. 2

  • Takeaways & Limitations

    In RedNote services, PrairieFire ran for two months, reduced index rebuild frequency by over 95% across dozens of indexes, and improved all reported business metrics.

    Source: §1 · p. 2

Abstract

from arXiv · show

Arrays of modern NVMe SSDs are approaching memory in terms of bandwidth while offering much lower cost per gigabyte. Hence, approximate nearest neighbor search (ANNS) for billion-scale vectors in applications such as recommendation, search, and retrieval-augmented generation increasingly runs on SSD-based systems. Unfortunately, due to the limited update throughput of existing SSD-based solutions, the indexed corpus cannot keep pace with continuous modifications to data and embedding models, thus hindering broader deployment across more scenarios and larger scales. The bottleneck lies in CPU-intensive update paths, where foreground insertions incur frequent SSD accesses and background reassignments repeatedly relocate each vector, making high update throughput difficult to achieve even by exhausting available hardware. In this paper, using buffered updates and batched local rebuilds, we develop PrairieFire with cascaded adjustments, concurrency control, and CPU-GPU-SSD cooperation. These co-designs avoid frequent SSD accesses in foreground updates and heavy background reassignments, achieving high update throughput while maintaining excellent search performance. Evaluations show that, compared with state-of-the-art systems, PrairieFire can sustain approximately 3-35x update throughput while maintaining approximately 3-5x search throughput simultaneously. It also achieves approximately 1.5-8.7x cost efficiency. PrairieFire has been deployed in RedNote's production environments for two months, improving business metrics by higher freshness without frequent index rebuilds.

1 INTRODUCTION

SSD-based ANNS must absorb continuous changes to items and embedding models, but existing systems fall short of production update demands. PrairieFire combines buffered updates, batched local rebuilds, cascaded adjustments, concurrency control, and CPU-GPU-SSD cooperation to improve update and search throughput.

1 INTRODUCTION

  • Existing systems achieve only about 6% to 40% of the up-to-30K QPS update target for a 0.1B-scale recommendation index, even with an SSD array and all 64 CPU cores.OdinANN reaches only 2–3 KQPS, while SPFresh reaches approximately 12 KQPS with 64 update-only cores.Source: §1 · p. 1
  • Buffered updates amortize foreground SSD round trips, while batched local reclustering replaces repeated per-vector background reassignments.Updates to a cluster accumulate in memory and flush as a batch; an imbalanced region is reclustered in one local rebuild.Source: §1 · p. 1
  • Fine-grained partitions and replicated placement leave little room for buffers and can trigger repeated SSD accesses even with buffering.SPFresh can create up to 16% as many partitions as vectors, and a new vector can trigger up to 8× insertions.Source: §1 · p. 2
  • Normal-scale partitions and single-copy placement create challenges for PrairieFire: centroid drift can hurt search, while reclustering can consume at least as many cores as reassignment.Dynamic centroid adjustment, high concurrency, and improved pipelines are needed to support search performance.Source: §1 · p. 2
  • PrairieFire uses a three-level partition index with cascaded centroid adjustments, fine-grained concurrency control, and a GPU-CPU-SSD workflow.The workflow accelerates centroid routing, partition scanning, and clustering-based rebuilds.Source: §1 · p. 2
  • PrairieFire sustains approximately 3–35× update throughput while maintaining approximately 3–5× search throughput, with comparable or higher search accuracy than baselines.It also achieves up to 1.5–8.7× hardware efficiency; in RedNote services, it reduced index rebuild frequency by over 95% across dozens of indexes.Source: §1 · p. 2

2 BACKGROUND

Large-scale ANNS services need current results as items and embedding models change, motivating SSD-based indexes that support continuous updates. The background describes the dynamic operations and existing graph- and partition-based approaches.

2.1 Freshness Challenges of Large-Scale ANNS

  • Items and embedding models change continuously, so ANNS indexes must reflect updates promptly rather than rely only on static SSD-backed collections.Recommendation systems may retrain and deploy embedding models hourly or more frequently.Source: §2.1 · p. 2

2.2 Operations for Dynamic Workloads

  • Dynamic ANNS requires search, insert, and delete operations to take effect in the current valid collection and subsequent search results.Insertions should appear in later searches, while deleted vectors should no longer appear.Source: §2.2 · p. 2

2.3 Existing Solutions

  • OdinANN directly updates an SSD-resident graph, while SPFresh uses SSD posting lists and locally splits or merges partitions with vector reassignment.Figure 1 compares update-throughput scaling with CPUs and SSDs on SIFT100M and indicates that scaling both resources does not reach 30K QPS.Source: §2.3 · pp. 2–3, Figure 1 · p. 3

3 MOTIVATION

Existing update-capable ANNS systems miss the throughput required for fresh large-scale indexes, and adding SSD bandwidth does not resolve the dominant CPU costs. The section traces those limits to foreground insertion I/O and background rebuild reassignments.

3.1 Insufficient Performance

  • Existing OdinANN and SPFresh deliver only 2–12K QPS on up to 64 CPU cores, at most 40% of the approximately 30K QPS target.The target corresponds to refreshing a billion-vector index every 10 hours or a 100-million-vector index every hour.Source: §3.1 · p. 3
  • OdinANN’s graph insertion incurs 4–7 ms of multi-hop SSD access, while SPFresh’s faster in-memory routing still leaves throughput approximately 60% below target.SPFresh locates clusters in under 1 ms but updates their SSD pages; the cited comparison is for all threads allocated to updates.Source: §3.1 · p. 3

3.2 Does Bandwidth Scaling Work?

  • With 10 Gen5 SSDs providing approximately 120 GB/s, SPFresh’s update throughput improves by less than 10%.Its bandwidth usage remains below 1 GB/s, while the theoretical CPU requirement for target throughput is 128–256 cores, even without search requests.Source: §3.2 · p. 3

3.3 Where Does CPU Cost Come From?

  • SPFresh’s foreground inserts read and rewrite SSD lists, while background rebuilds split or merge clusters and reassign affected vectors.Foreground insertion uses most update threads; deletes only add a version value to an in-memory map.Source: §3.3 · p. 4
  • Foreground updates consume 59–62% of CPU cycles and background rebuilds 38–41%, with graph traversal and round-trip list I/O recurring across both paths.Graph traversal accounts for around 30–35% of cycles; read-modify-write operations dominate the remaining cycles.Source: §3.3 · p. 4

4 OPPORTUNITIES AND CHALLENGES

Buffered updates and local reclustering could reduce foreground I/O and background vector relocations, but SPFresh’s search-oriented design and hardware constraints complicate both. The section identifies memory, search, and computation trade-offs that the design must address.

4.1 Buffered Updates and Direct Rebuilds

  • Per-cluster buffers can reduce foreground read-modify-write I/O, and local reclustering can replace per-vector relocation after splits or merges.Reclustering nearby clusters jointly regenerates centroids and posting lists in a batch.Source: §4.1 · p. 4

4.2 Conflicts and Challenges Arising

  • On a roughly 13GB SIFT100M dataset, buffers of 16 vectors per list raise total memory use toward 3× dataset size.SPFresh already uses about 1.5× the raw dataset size; adding buffers of 2 to 16 vectors adds 5–22 GB.Source: §4.2 · p. 4
  • Reducing centroid count without adjusting centroids increases scan overhead by up to approximately 3× after 100M updates to maintain recall.With about 2% as many centroids as vectors, each cluster has roughly 50–100 members.Source: §4.2 · p. 5
  • With replicated placement, buffering 2 vectors still triggers SSD access with nearly 100% probability, and buffering 16 leaves the probability around 40%.SPFresh’s vectors may be placed in up to 8 clusters, undermining the expected I/O reduction from buffering.Source: §4.2 · p. 5
  • Removing replicas raises search latency, while local reclustering 64 nearby clusters can require more background CPU cores than reassignment.The comparison uses 10–15 Lloyd iterations for clustering and measures cores needed to match insertion throughput.Source: §4.2 · p. 5

5 PRAIRIEFIRE

PrairieFire makes buffered updates and batched local rebuilds practical through choices in index structure, concurrency control, and CPU-GPU-SSD cooperation. Its design combines these components in the update-search workflow.

5.1 Considerations

  • PrairieFire pairs normal-granularity partitioning, centroid adaptation, and non-redundant placement to support buffering while tracking cluster changes and avoiding duplicate vector insertion.The design targets affordable buffering, representative centroids, and fewer SSD accesses.Source: §5.1 · p. 5
  • The design calls for efficient concurrency control and coordinated GPU, CPU, and SSD pipelines to support concurrent operations and clustering-based rebuilds.GPUs provide extra computation for heavier search overhead and rebuilds without overwhelming CPUs.Source: §5.1 · p. 5

5.2 Design Overview

  • PrairieFire's overview combines its index structure, concurrency control, and software-hardware co-design in one update-search workflow.The index uses three levels with buffering and cascaded centroid adaptation; the locking design decouples hierarchical levels, while the hardware workflow uses CPUs, GPUs, and SSDs.Source: §5.2 · pp. 5–6, Figure 7 · p. 6

5.3 Index Structure

PrairieFire organizes vectors in a three-level partition-based index across storage and compute tiers, with buffered foreground operations and batched flushes or local rebuilds. Cascaded centroid adjustments propagate changes upward to maintain index quality.

5.3 Index Structure

  • PrairieFire uses a bottom-up, three-level clustering layout across GPUs, host memory, and NVMe SSDs to support buffered updates and cascaded adjustments.Level-2 holds vector partitions; level-1 holds their partition centroids, and level-0 holds routing centroids.Source: §5.3 · p. 6, §5.3.1 · p. 6

5.3.2 Operation paths.

  • Search scans buffered and on-SSD vectors in candidate partitions; inserts append to a target partition's buffer, while deletes remove buffered vectors or mark on-SSD IDs for lazy collection.Search proceeds through level-0 and level-1 to identify candidate level-2 partitions before scanning their vectors.Source: §5.3.2 · p. 6

5.3.3 Flush, local rebuild, and cascaded adjustment.

  • A full buffer or excess invalid IDs triggers a flush that rewrites buffered and remaining valid vectors to the same SSD region; imbalance triggers reclustering nearby partitions into balanced partitions.PrairieFire's local rebuild reclusters directly rather than using SPFresh's per-vector conditional reassignments.Source: §5.3.3 · p. 6, Figure 9 · p. 7
  • Flushes summarize bounded level-2 changes into centroid updates, while rebuilds insert or delete level-1 centroids and propagate routing-centroid changes to the host shadow for lazy GPU synchronization.Upper-level changes use in-place update, append, and swap-last-pop primitives to keep centroid arrays dense and contiguous.Source: §5.3.3 · p. 7

5.4 Concurrency Control

PrairieFire decouples locks across hierarchical index levels and uses version validation and ordered acquisition to support concurrent searches, updates, and rebuilds. Its locking mechanisms protect only the objects each operation needs at each stage.

5.4.1 Decoupled locks.

  • Independent control components govern partition-centroid clusters, vector partitions, and vectors, while each centroid is bound atomically to the lower-level member set it represents.Slot-based locks protect vector-to-partition mappings without requiring a lock per vector.Source: §5.4.1 · p. 7, Table 1 · p. 7

5.4.2 Basic principles.

  • PrairieFire provides immediate record-level visibility, releases locks when switching granularities and validates versions, and acquires multiple locks in a deterministic order to prevent deadlocks.Level-2 partitions have version records for consistency validation during online rebuilds.Source: §5.4.2 · p. 7, §5.4.1 · p. 7

5.4.3 Locking mechanisms.

  • Search releases shared level-0 locks before acquiring shared level-1 locks, then validates partition versions and skips invalid partitions rather than retrying.The passage reports that skipping invalid partitions keeps recall stable in evaluations.Source: §5.4.3 · pp. 7–8, Figure 10 · p. 8
  • Insertions lock and validate the target partition before adding a vector, while deletions verify the vector's current partition; both retry when rebuilds invalidate their target.Vector-to-partition mappings are protected with exclusive slot locks.Source: §5.4.3 · p. 8
  • Background rebuilds lock nearby vector partitions for reclustering and remap member IDs, then use upper-level locks to propagate centroid changes.The locking workflow also updates partition-centroid clusters and routing-centroid parent IDs.Source: §5.4.3 · p. 8, Figure 11 · p. 8

5.5 Software-Hardware Workflow

PrairieFire co-designs search and rebuild operations for a CPU-GPU-SSD system with high-bandwidth interconnects. It batches level-0 distance computation, overlaps buffered and SSD searches, and fuses kernels for micro-scale clustering.

5.5 Software-Hardware Workflow

  • PrairieFire's CPU-GPU-SSD platform provides direct GPU-SSD I/O of approximately 50 GB/s between each GPU and five NVMe SSDs, and targets three stages for optimization.Those stages are level-0 search on GPUs, level-2 search across CPUs, GPUs, and SSDs, and GPU-based rebuilds.Source: §5.5 · p. 8

5.5.1 Batched Distance Computation for Level-0.

  • For 1B-scale SIFT, PrairieFire packs concurrent level-0 requests into batched GPU operations, using GEMM to reuse routing-centroid reads and reduce per-request bandwidth demand.The naive GEMV and ranking path can demand approximately 1.8-3.8 TB/s at the target throughput.Source: §5.5.1 · p. 8

5.5.2 Parallelizing in-buffer and on-SSD parts during level-2 search.

  • PrairieFire scans in-memory buffers on CPUs while transferring on-SSD vectors to GPUs for distance computation, then merges candidates on CPUs to reduce search latency.This overlaps the two partition components instead of scanning them sequentially.Source: §5.5.2 · pp. 8–9, Figure 12 · p. 9

5.5.3 Fusing kernels for micro-scale clustering.

  • PrairieFire fuses assignment with cluster-statistics accumulation for micro-scale rebuilds, avoiding intermediate assignment materialization and several kernel launches to achieve clustering under 5 ms.The local rebuilds recluster at most 64 nearby partitions, usually involving thousands of vectors; standard GPU KMeans backends can take 10-30 ms at this scale.Source: §5.5.3 · p. 9, Figure 12 · p. 9

6 EVALUATION

PrairieFire is evaluated on dynamic workloads from 0.1B to 1B vectors, sensitivity and hardware configurations, and production-oriented comparisons. Across these settings, it improves update and search throughput while maintaining comparable or better recall, with reported cost-efficiency gains.

6.1 Experimental Setup

  • The evaluation uses an EPYC 64-core Genoa CPU, 10 PCIe-Gen5 NVMe SSDs, two GPUs, and three dynamic workloads spanning SIFT1B and SPACEV1B at 0.1B and 1B scales.Comparisons include Greator, OdinANN, SPFresh, and GPU-CPU system SVFusion; FreshDiskANN is excluded for prohibitive memory use and weaker reported throughput.Source: §6.1 · p. 9

6.2.1 0.1B-scale evaluation.

  • On uniform SIFT and skewed SPACEV workloads, PrairieFire delivers ∼3-35× update and ∼3-5× search throughput, with lower tail latency, comparable or better recall@10, and the same memory-footprint level.Figure 13 covers update and search throughput, tail latency, accuracy, and memory usage.Source: Figure 13 · p. 10, §6.2.1 · p. 10

6.2.2 1B-scale evaluation.

  • At 1B vectors, PrairieFire achieves ∼3× higher search throughput and up to ∼27× higher update throughput than baselines, with 36-39K QPS for both and higher recall.Packing level-0 distance computation with batched GEMM saves global-memory traffic despite about 10× more level-0 centroids than at 0.1B scale.Source: §6.2.2 · p. 10

6.3 Sensitivity and Ablation Study

  • Buffering 8 vectors per cluster balances throughput and memory use on Workload C; higher budgets yield only marginal further improvements.Figure 14 presents throughput-memory trade-offs across buffering budgets.Source: §6.3 · p. 10, Figure 14 · p. 11
  • Across update-to-search thread allocations, PrairieFire sustains high throughput on both tasks; ablations report up to 2.3× update and 3.2× search gains from decoupled locks, with further gains from batched and parallel search and fused background clustering.Without cascaded adjustment, recall can drop by up to 3%; level-1 and level-0 adjustment improve recall by up to 1.5% and 2.9%, respectively.Source: §6.3 · p. 11, Figure 15 · p. 11
  • Additional GPUs and SSDs support higher throughput: GPUs bring up to 3.4× update and 4.1× search improvement, while more SSDs mainly improve search and support linear search scaling during concurrent updates.Figure 16 compares CPU-only, +1GPU, and +2GPU configurations and illustrates the SSD contribution.Source: §6.3 · p. 11, Figure 16 · p. 11

6.4 Hardware Efficiency

  • On Workload C, PrairieFire achieves 2.2–3.4× device cost efficiency and ∼1.5–2.4× power cost efficiency despite higher device cost and power than OdinANN and SPFresh.Its storage cost is ∼1.65K$, yielding 4.9–8.7× storage-cost efficiency of baselines; Figure 17 covers device price, energy, and storage.Source: §6.4 · pp. 11–12, Figure 17 · p. 11

6.5 GPU-based comparison, high-dimensional datasets, and production evaluation

  • PrairieFire achieves approximately 2× higher update and search throughput than SVFusion on Workload A, and over ∼10× update and ∼1.5× search throughput on higher-dimensional datasets, with recall gains of 3-5% in the first production refresh followed by stable recall.The reported high-dimensional datasets are 768-dimensional Wikipedia and 960-dimensional Gist.Source: §6.5 · p. 12

7 DEPLOYMENT

PrairieFire uses a Kafka-based write-ahead log for crash recovery, reusing existing infrastructure. In RedNote deployment, streaming rebuilds reduced full index rebuilds and improved reported business metrics.

7 DEPLOYMENT

  • The Kafka-based WAL reuses existing infrastructure, avoiding a separate WAL implementation in PrairieFire.The deployment combines it with unique incremental ID assignment.Source: §7 · p. 12, Figure 19 · p. 12
  • During recovery, PrairieFire sends persisted vector IDs to event-stream servers, which compare them with valid WAL IDs to identify inserts and deletes for replay.PrairieFire locally reconstructs routing centroids from persisted vector partitions, then dispatches the replay updates from Kafka to restore the index.Source: Figure 19 · p. 12, §7 · p. 12
  • In a recommendation index refreshed twice per hour, PrairieFire reduced full rebuilds from 48 per day to one, while business metrics rose by 0.5–2 percentage points.Streaming rebuilds handled embedding updates between full refreshes; reported metrics included exposure, click-through rate, and revenue yield.Source: §7 · p. 12

8 RELATED WORK

Related work spans graph- and cluster-based disk ANNS, update-capable systems, and hardware-accelerated approaches. The passage distinguishes these approaches by throughput, update support, and concurrent operation.

8 RELATED WORK

  • DiskANN and Starling represent graph-based disk ANNS, while PipeANN pipelines graph search; these systems use less I/O bandwidth and have higher throughput than cluster-based SPANN on a single SSD.Cluster-based approaches have regained attention as SSD arrays have become more capable.Source: §8 · p. 12
  • FreshDiskANN, Greator, OdinANN, SPFresh, and SVFusion support updates in large-scale scenarios, but the passage reports limited performance under high update rates.Quake supports CPU-only index maintenance but not concurrent update and search.Source: §8 · p. 12
  • GPU-, FPGA-, and CXL-based ANNS approaches address CPU limitations, but the passage says they do not support updates.Source: §8 · p. 12

9 CONCLUSION

The conclusion presents PrairieFire as a CPU-GPU-SSD ANNS system combining buffered updates with a cluster-based index. It reports support for high-throughput updates while preserving search throughput and maintaining several forms of efficiency.

9 CONCLUSION

  • PrairieFire combines buffered updates with a cluster-based index for large-scale updatable ANNS.Source: §9 · p. 12
  • The CPU-GPU-SSD system supports high-throughput updates while preserving high-throughput search.Source: §9 · p. 12
  • The evaluation reports high cost, energy, and storage efficiency alongside performance for high-freshness applications.Source: §9 · p. 12
Loading 2610.23232v1…