[RFC] In-Place Updating Segments with jVector Graphs

[sam-herman]

RFC: In-Place Updating Segments with jVector Graphs

Author: Sam Herman (@sam-herman)
Contributors: Akash Shankaran (@akash-shankaran)
Status: Review

---

1. Overview

This RFC proposes a new approach for updates in jVector indices to enable in-place updating of jVector graph segments in OpenSearch and Cassandra (C*). The goal is to eliminate costly segment merges during vector index construction, enabling faster ingestion, lower disk I/O, and improved query performance.

Currently, OpenSearch and C* rely on the Log-Structured Merge Tree (LSM) model, creating new immutable segments for each write. Merges and compactions are required later, which introduces significant overhead, especially for large vector datasets.

By leveraging the mutable nature of the jVector graph, we propose maintaining a fixed number of jVector graphs per index, shared across segments. These graphs grow or shrink with insertions and deletions—no full merges required.

This change would make OpenSearch and C* a leader in vector index construction speed and real-time graph updates.

---

2. Background

Both OpenSearch and Cassandra depend on Lucene’s LSM architecture. Every write results in a new immutable segment. Over time, multiple small segments must be merged—a process that is both CPU- and I/O-intensive.

Vector indices, such as those powered by jVector, exacerbate this issue because merges require complete re-indexing of vector data (O(n log n) cost), effectively duplicating prior work.

This results in a tradeoff:

• Frequent merges → better query latency, worse indexing throughput.
• Infrequent merges → efficient indexing, but slow queries (multi-segment scans).

---

3. Problem Statement

1. High Cost of Merges: Each merge re-indexes the entire graph, leading to O(n log n) reconstruction cost.
2. Redundant Work: Previous indexing work is discarded during merges.
3. Disk I/O Overhead: Large vector indices (e.g., 4GB) can trigger >35GB of file rewrites.
4. Backup & Restore Inefficiency: Segment-based snapshotting amplifies storage usage.
5. Latency-Throughput Tradeoff: Merge policies force an undesirable compromise between ingestion performance and query latency.

---

4. Proposal Summary

We propose a three-stage, incremental path toward mergeless, in-place vector updates:

1. Improvement 1: Leading Segment Merge Policy
   • Maintain a single “leading” segment that accumulates new data incrementally.
   • Avoid full graph reconstructions by appending new nodes in-place.
   • Expected performance for a single merge is O(log n) instead of O(n log n).
   • Yields commutative cost of O(N log N) instead of O(r^N) while minimizing query latency.

2. Improvement 2: Per-Field Segments

   • Decouple vector field segmentation from the rest of Lucene’s index.
   • Each vector field maintains its own segment lifecycle and merge policy.
   • Reduces the blast radius of Disk I/O and enables more aggressive optimization.

3. Improvement 3: Mergeless In-Place Updates

   • Allow jVector graphs to mutate directly on disk—no new segments created.
   • Support insertions, deletions, and updates without full rebuilds.
   • Moves OpenSearch vector indexing from LSM-style to mutable-graph-based indexing.

---

5. Design Details

The design will be focused on the final goal of mergeless in-place updates, the first two improvements can be implemented independently.

5.1 Mapping And Indirection

Introduce indirection mapping layers:
DocID → NodeID → Vector Ordinal

For the design to work properly at any of the improvements, we need to maintain a mapping from the Lucene document ID to the jVector ordinal. This mapping is necessary because the jVector ordinals can be different from the Lucene document IDs and when lucene documentIDs change after a merge, we need to update this mapping to reflect the new document IDs. This requires us to know the previous mapping from the previous merge and the new mapping from the current merge.
Moreover, the nodeIds need to be disjoint from the ordinals of the actual vectors store. This is essential because the set of vectors constantly changes upon updates, before the graph does.
Therefore, even for inline vectors, we can't assume that all the vectors are in the same graph. This is even more crucial when we introduce external vector store such as NVQ.

5.2 Vector Index Engine Goes Into Its Own Process

The vector index engine is moving into it's own dedicated process with inter-process communication via gRPC.
This allows for a number of advantages:

1. Easier support for native code operation - no longer requires JNI, makes profiling and instrumentation easier. Since we don't have to deal with additional layer of the JVM to detect resource allocations (memory, threads, etc.)
2. Easier support for multiple vector index engines - Codecs can be more easily replaced on the fly as long as the gRPC interface is compatible.
3. Easier support for in-place updates - Vector index engine process can be located on a separate machine from the main OpenSearch process with dedicated specialized hardware.(e.g. NVMe, SSD, etc.)
4. Separate Tunning And Optimization - Process isolation enables running indexing and updates optimally, and not be subject to merges etc. that impact the main opensearch process. The indexing process can be tuned to customer needs independently from the rest of OpenSearch.
5. Composable System Design - Enables the design of a composable data system, providing a clean separation of query engine functionality from core OpenSearch.
6. Dedicated Process For Query Capabilities - Sets precedence for separating query capabilities to a dedicated process in the future.

5.3 In-Place Disk Updates

jVector will leverage it's RandomAccessWriter capabilities to perform in-place updates to the graph index on disk.
This becomes easier to do since jVector has a format that easily enable in-place updates especially for inline vectors.

5.4 Lucene Integration

Another important aspect is keeping the interface behaving the same way for the Lucene hook methods in the FieldWriter.
addDocuments - This method is called when new documents are added to the index. This method will be responsible for adding the new documents to the jVector graph.
merge - This method is called when segments are merged. This method will be responsible for merging the jVector graphs from the different segments.
flush - This method is called when a segment is flushed to disk and making it visible to queries.
commit - This method is called when a segment is fsynced to disk and making it persistent and also commits it into the segmentInfos to become recoverable after a crash.

Even though we are changing to in-place updates, this should not fundamentally change the expected behavior of the above methods.
While addDocuments and flush are trivial, the merge method will still be called when segments are merged, but instead of creating a new segment, it will simply update the docID to nodeID mapping and update the graph in-place for any deletes.
For commit, we will fsync the graph changes to disk.

5.5 Snapshots And Backups

For backups, OpenSearch at the moment doesn't have a way to do block level diffs, instead it's doing a segment level diff.
This works well with the LSM model, but with in-place updates, this actually becoming more expensive since it will force a full copy of the segment.

There are however some solutions around this:

1. Flat Vectors - Flat vectors are not affected by this change since they can be kept separate from the graph index. Therefore they can still benefit from the segment diffs. The graphs on the other hand are a lot less expensive to copy since they are a lot smaller.
2. Block Diffs - For in-place segments, to only copy the changed blocks. This is a lot more expensive to implement, but it's a lot more efficient.

---

6. References

• Lucene Merge Policy Documentation
• Incremental Graph Index Updates Paper
• Elastic Merge Efficiency Improvements

---

[chishui]

Thank you @sam-herman for bringing up this "segment free" design. I really like the idea of decoupling vector engine into a independent process which give us new flexibilities and capabilities. I have some questions:

1. You mentioned "indirection mapping layers: DocID → NodeID → Vector Ordinal" is this jVector graph per node? I think multiple shards of an index could exist on the same node.
2. Should you also include segment id into id mapping layer? As ids in segments could be the same.
3. Your RFC is mainly focusing on building index, could you also add how you plan to support query? Is there any challenges plumbing this segment-free structure into segment aware query framework?

Thanks

[yuye-aws]

Great issue from @sam-herman !

My major concern is concurrency when the OpenSearch supports query and update at the same time. Different from the conventional segment level approach, now updating a document need to update the whole JVector graph. This would definitely require a wider-range lock. I'm wondering to what extent does adding lock degrade the concurrency?

In addition to that, it's quite good that you provide time for incremental graph merge. What's the expected behavior when we scale the graph to million-scale?

Have a good day.

[sam-herman]

Hi @yuye-aws thank you for the feedback, see my answers below regarding each point.

My major concern is concurrency when the OpenSearch supports query and update at the same time. Different from the conventional segment level approach, now updating a document need to update the whole JVector graph. This would definitely require a wider-range lock. I'm wondering to what extent does adding lock degrade the concurrency?

in jVector concurrency is already built in to graph insertions. There is a recent blog published about it:
https://opensearch.org/blog/breaking-the-single-thread-bottleneck-concurrent-vector-graph-construction-in-opensearch/

In addition to that, it's quite good that you provide time for incremental graph merge. What's the expected behavior when we scale the graph to million-scale?

Based on the benchmarks we ran, and as the graph indicates the increase in graph insertion is a logarithmic scale. So the expectation is for this to still apply for millions as well as billions of nodes graphs. I'll try to publish a benchmark for it as well.

[sam-herman]

Thank you for the feedback @chishui see my answers below (would also make sure to include those in the description above).

1. You mentioned "indirection mapping layers: DocID → NodeID → Vector Ordinal" is this jVector graph per node? I think multiple shards of an index could exist on the same node.

This refers to the mapping that exists for each shard. If for example you would have 3 shards then for each shard there could be 1 in-place segment for vector index, which means means 3 vector index segments in total.

2. Should you also include segment id into id mapping layer? As ids in segments could be the same.
   This is a good question, and I think I need to add the details about it in the design as well.

The DocID → NodeID mapping is a global mapping, so the docID already takes into account all the readers in the segments and their base docId offset. For each one of those it creates a mapping to the graph node ID in the in-place segment.
At the moment we have started to introduce it here but only for merges.

3. Your RFC is mainly focusing on building index, could you also add how you plan to support query? Is there any challenges plumbing this segment-free structure into segment aware query framework?

Good question, I'll add that in the description as well! Query will be supported in a similar way to construction, except that for query we will have to apply the DocID -> NodeID mapping to the results of any pre-filtering before passing over the bitmap to the graph index for query.

Let me know if those answer your questions

[yuye-aws]

Thanks for the timely response @sam-herman .

in jVector concurrency is already built in to graph insertions. There is a recent blog published about it:
https://opensearch.org/blog/breaking-the-single-thread-bottleneck-concurrent-vector-graph-construction-in-opensearch/

I've read the blog. I'm still curious about the benchmark results when insertion and query happens at the same time.

Based on the benchmarks we ran, and as the graph indicates the increase in graph insertion is a logarithmic scale. So the expectation is for this to still apply for millions as well as billions of nodes graphs. I'll try to publish a benchmark for it as well.

That's definitely a good news! Expect to see it scaling to millions and billions scale vector search applications

[navneet1v]

Hi @sam-herman

This is similar to what I was also thinking in k-NN plugin RFC: opensearch-project/k-NN#2538. One question I have on this is why we choose to move vector engine in a separate process rather than not keeping it within Opensearch process?

Also do you have some performance numbers in terms of improvements in indexing time? Would be very interested to see how much we can gain here.

[sam-herman]

Hi @sam-herman

This is similar to what I was also thinking in k-NN plugin RFC: opensearch-project/k-NN#2538. One question I have on this is why we choose to move vector engine in a separate process rather than not keeping it within Opensearch process?

Also do you have some performance numbers in terms of improvements in indexing time? Would be very interested to see how much we can gain here.

Hi @navneet1v, the main difficulty we've had with Faiss (Native library which is holding resources outside of JVM) is embedded within OpenSearch is that it was hard to instrument, profile and debug in production.
This is the reason why we went with pure Java library that only delegates to native code for the SIMD instructions, but is doing so without holding state within the native code part.
Going forward we would like to be able to better support in production Native libraries, such as Faiss, and newer version of jVector that will hold state in native code.
We believe that within a dedicated process those would be easier to operate in production for instrumentation/debugging purposes.
Another aspect is that we may want to have the vector index running on a different storage medium then the rest of the indices. This is also another important consideration in cloud native versions.