[RFC] Add Random Access Write Support to IndexOutput

[sam-herman]

[RFC] Add Random Access Write Support to IndexOutput

Summary

This RFC proposes adding random access write capabilities to Lucene's IndexOutput interface to enable use cases that require non-sequential writes while maintaining compatibility with Lucene's existing architecture.

Motivation

Currently, Lucene's IndexOutput interface is designed exclusively for sequential, append-only writes. This design provides important benefits:

• Immutability: Index files are written once and never modified
• Efficient checksumming: Checksums can be computed incrementally during writes without re-reading data
• Atomic commits: Files are finalized atomically, ensuring index consistency
• Simplicity: Sequential writes are easier to reason about and optimize

However, there are emerging use cases where random access write capabilities would provide significant benefits:

Use Case 1: Modern Storage Optimization

Modern storage devices (SSDs, NVMe) can handle random writes efficiently and support concurrent writes to different file regions. Random access writes could enable parallel construction of index structures, significantly reducing total write time.

Reference: JVector PR #542 demonstrates performance improvements from parallel writes during vector index construction.

Use Case 2: Mutable Index Structures

Some applications require the ability to update index structures in-place without full rewrites:

• Dynamic graph updates for vector search indices
• In-place modifications during index optimization
• Incremental updates to reduce I/O overhead

References:

• OpenSearch JVector Issue #169 discusses mutable index requirements
• OpenSearch k-NN Issue #2715 discusses reducing I/O during frequent merges

Use Case 3: Graph Index Construction Optimization

When building graph-based indices (HNSW, Vamana) with inlined vectors:

• Currently requires maintaining separate flat vector files during construction for scoring
• Random access writes would allow reusing the partially-written graph index file
• Eliminates redundant storage and I/O operations

Reference: [To be added]

Proposed Solution

Option 1: New Interface Extending IndexOutput

Introduce a new RandomAccessIndexOutput interface that extends IndexOutput:

/**
 * An IndexOutput that supports random access writes in addition to sequential writes.
 *
 * <p>This interface allows seeking to arbitrary positions within the file and writing
 * data at those positions. Implementations must handle checksum computation appropriately
 * when random access writes are performed.
 *
 * <p>Instances of this class are <b>not</b> thread-safe.
 *
 * @lucene.experimental
 */
public abstract class RandomAccessIndexOutput extends IndexOutput {

  protected RandomAccessIndexOutput(String resourceDescription, String name) {
    super(resourceDescription, name);
  }

  /**
   * Sets the file pointer to the specified position for the next write.
   *
   * @param pos the position in bytes from the beginning of the file
   * @throws IOException if an I/O error occurs
   * @throws IllegalArgumentException if pos is negative or beyond the current file length
   */
  public abstract void seek(long pos) throws IOException;

  /**
   * Forces any buffered output to be written to the underlying storage.
   *
   * @throws IOException if an I/O error occurs
   */
  public abstract void flush() throws IOException;

  /**
   * Returns the checksum of bytes in the specified range.
   * This allows computing checksums for specific regions when random access writes are used.
   *
   * @param startOffset the starting position (inclusive)
   * @param endOffset the ending position (exclusive)
   * @return the checksum value for the specified range
   * @throws IOException if an I/O error occurs
   * @throws IllegalArgumentException if the range is invalid
   */
  public abstract long getChecksum(long startOffset, long endOffset) throws IOException;
}

Option 2: Capability-Based Approach

Alternatively, add optional methods to IndexOutput with default implementations that throw UnsupportedOperationException, similar to how IndexInput handles RandomAccessInput:

// In IndexOutput class
public void seek(long pos) throws IOException {
  throw new UnsupportedOperationException(
    "This IndexOutput implementation does not support random access writes");
}

Design Considerations

Checksum Handling

Random access writes complicate incremental checksum computation. Proposed approaches:

1. Range-based checksums: The getChecksum(startOffset, endOffset) method allows computing checksums for specific regions
2. Invalidation on seek: Seeking invalidates the current checksum; callers must explicitly recompute
3. Implementation-specific: Leave checksum strategy to implementations (e.g., in-memory implementations could maintain full checksums)

Safety Guarantees

• Random access writes should only be used during index construction, not for modifying committed segments
• Implementations should validate that seeks don't extend beyond current file length
• Thread-safety remains the caller's responsibility (consistent with existing IndexOutput contract)

Alternatives Considered

1. External libraries: Projects could implement random access writes outside Lucene, but this creates fragmentation and prevents sharing optimizations
2. Custom Directory implementations: Possible but requires duplicating significant infrastructure

Open Questions

1. Should random access writes be restricted to specific Directory implementations?
2. What are the implications for index verification and corruption detection?
3. Should there be explicit markers in the index format to indicate random-access-written files?
4. How should this interact with encryption or compression layers?

Backward Compatibility

This proposal is fully backward compatible:

• No changes to existing IndexOutput contract
• New functionality is opt-in via new class or optional methods
• Existing IndexOutput implementations remain unchanged
• Codecs that don't need random access continue using standard IndexOutput
• Existing codecs and applications continue working unchanged

[uschindler]

Hi,
I strongly disagree with this. We had random access in the eraly times of Apache Lucene and luckily removed it in Lucene 4.0 for good reasons, most of the details about why were already discussed here.

The seconds use case is an anti-pattern in Lucene and breaks the whole transactional behaviour, write once is a must and not uncommon.

Sorry, Uwe

[rmuir]

Modern storage devices (SSDs, NVMe) can handle random writes efficiently and support concurrent writes to different file regions. Random access writes could enable parallel construction of index structures, significantly reducing total write time.

Lucene already has parallel construction: just index with multiple threads.

I agree with Uwe here, I think these datastructures are just not very efficient and not integrated well. With a quick search, you can find alternatives for ANN that are more sympathetic to the hardware and use sequential access.

[sam-herman]

Hi, I strongly disagree with this. We had random access in the eraly times of Apache Lucene and luckily removed it in Lucene 4.0 for good reasons, most of the details about why were already discussed here.

@uschindler in the use case 1 above: datastax/jvector#542, shows a clear quantitative horizontal improvement in bandwidth for parallel writes on NVMe and SSDs.
Can you share the reasoning why it was removed from earlier versions? Where these benefits been considered back then? Would be great to have data driven discussion around those aspects to weigh cons/pros outside of idiomatic/syntactic preferences.

The seconds use case is an anti-pattern in Lucene and breaks the whole transactional behaviour, write once is a must and not uncommon.

I think we can still preserve the transactional contract, however the underlying implementation will be different. The idea is to be able to make changes in place within indices to reduce IO footprint.
In use case 2 (opensearch-project/opensearch-jvector#169) for example:

The performance boost from incremental insertion to a graph as opposed to merges is substantial:
https://github.com/opensearch-project/opensearch-jvector/blob/main/merge_times_comparison.png?raw=true

The issue however, is that even with choosing a leading segment and optimizing merges, there is still IO penalty for merge.
Imagine when you have a large segment of 1Billion vectors and you want to add 1 more? Force merge in that scenario will require you to persist about 6 TB of data back to disk.
Mutable indices can alleviate this problem by minimizing the IO signature for only the minimal delta required to add to the graph.

Lucene already has parallel construction: just index with multiple threads.

@rmuir see response above regarding the IO cost of merging large and small segment.
Multiple index threads doesn't achieve the same outcome as it forces you to create multiple segment, which means many small graphs. Mutable index allow you to keep a single most compact and efficient graph at all time without the need of merge which can become un-proportionally costly (see extreme example above of 1 Billion vector dataset when additional one is added).

I agree with Uwe here, I think these datastructures are just not very efficient and not integrated well. With a quick search, you can find alternatives for ANN that are more sympathetic to the hardware and use sequential access.

Can you share concrete example for an alternative backed by quantitative data?

[rmuir]

I'm not going to debate this endlessly. The problem with this HNSW crap, I've said it from day one, is that it was written by data scientists instead of computer scientists.

It sprays the OS with inefficient random accesses and thats why its many times slower than anything else in lucene. Other parts of the lucene index have supported efficient merge, including byte-copying when possible, for a long time and it scales perfectly fine.

Now we have the data scientists trying to justify their crappy slow random accesses and wanting to make the rest of lucene crappy-slow; NO!

[benwtrent]

I think if we want to make graph based indices (HNSW or others) build faster and merge faster, we should instead do something better with the algorithm.

There are many good ideas to explore around boot strapping graph building through clustering (and merging clusters between segments can be REALLY fast....)

Or taking advantage of bipartite ordering (and making that better) so that graph building has a head start due vectors that are similar being near each other on disk.

I would say lets do the "harder" thing (arguably, given how Lucene is built, I doubt its actually harder), and just make the graph based indices better in a segment based architecture.

[sam-herman]

I think if we want to make graph based indices (HNSW or others) build faster and merge faster, we should instead do something better with the algorithm.

There are many good ideas to explore around boot strapping graph building through clustering (and merging clusters between segments can be REALLY fast....)

Or taking advantage of bipartite ordering (and making that better) so that graph building has a head start due vectors that are similar being near each other on disk.

I would say lets do the "harder" thing (arguably, given how Lucene is built, I doubt its actually harder), and just make the graph based indices better in a segment based architecture.

@benwtrent all good ideas, which I'm actively exploring. Any thoughts on minimizing write IO to disk for frequent merges? Can take the previous extreme example of 1Billion vectors graph updated with a single vector and merging will cost writing back ~6TB of data to the disk.

EDIT: to add a bit more context, there is this one for example that I'm currently working on to improve merges with leading segment and utilizing existing quantized graphs. So definitely agreed there is a lot to be done on the merge algorithm as well.
However, when thinking forward, assume merges are now very computationally efficient, I am still thinking about the above extreme example (1Billion to 1) merge as something that we want to have a better story around. What do you think?

[benwtrent]

Can take the previous extreme example of 1Billion vectors graph updated with a single vector

This particular kind of segment merging is antithetical to Lucene's design and shouldn't be done.

Striking the right balance between write amplification and merging costs is key. While I think the typical tier-merging system might not work best for graph structures, it doesn't mean we should abandon it and attempt to merge in teeny segments into a single giant structure. Finding an appropriate balance is what you need.

Also, having a single 6TB Lucene Segment is likely to hit other scaling issues first.

Are you really concerned about frequent tiny merges or instead about improving multi-segment search over graph structures? There has been work there, but I would think there is more work to be done to make that better as well.

[sam-herman]

Striking the right balance between write amplification and merging costs is key. While I think the typical tier-merging system might not work best for graph structures, it doesn't mean we should abandon it and attempt to merge in teeny segments into a single giant structure. Finding an appropriate balance is what you need.

Thanks for the feedback — and to clarify, the goal of this RFC is not to encourage more frequent merges or to replace Lucene’s tiered merge policy. The motivation behind exposing a RandomAccessWriter-like primitive is to enable a path toward optional in-place updatable graph segments, which would significantly improve the ability to handle streaming inserts and deletes for vector/graph fields. This is motivated by real-world workloads similar to what we outline in the OpenSearch JVector proposal (opensearch-project/opensearch-jvector#169).

What we’re proposing is essentially a staged, opt-in evolution of the codec and segment APIs — not a change to Lucene’s core merge strategy:

Phase 1 — Leading-segment incremental merging

The initial step only enables the largest graph segment to incrementally append new nodes, reducing the cost of constantly rebuilding full graph structures on every merge. This doesn’t require changing merge frequency; it simply avoids unnecessary rewrite work in graph-heavy fields.

Phase 2 — Per-field segment policies

Similar to today’s per-field formats, this phase would allow a field (like a graph/vector field) to opt into a different segment-lifespan policy without affecting the rest of the index. This isolates the approach and keeps Lucene’s tiered merging intact for all other structures.

Phase 3 — Optional in-place updatable graph segments

This is the long-term goal: providing an interface that allows graph-based fields to apply small deltas in-place and persist them without requiring a full segment rewrite. Our own on-disk representations already support this pattern efficiently, and exposing these lower-level primitives in Lucene would allow experimentation — both within Lucene and by external codecs — without committing Lucene to a particular implementation.

[uschindler]

Hi,
thats all fine if it fitrs to your own ("we"?) search engine. But what you are propsing here is a complete change to the fundanmentals of how an Lucene index works. Especially the Phase 3 in your last comment is something which is a no-go for indexes, because the "write-once" is a basic design principle of the transactional system behind Lucene. Lucene supports snapshotting and also requires that an IndexReader which is already open does not change its contents unless it is reloaded/refreshed to last commit point. Therefore writing to existing files is a no-go. There is not much more to say.

If you are arguing: but we want updates to existing graphs: Yes, that's possible, look how it works with index deletes or doc-values, which are updateable. The pattern behind all those features is by using "delta files". So you don't start a new segment, but that changes to the current segment (e.g., deletes or updated docvalues) are written to a separate file. The separate files disappear during merging.

For phase 1 and phase 2, there are no random access writes neede, although this is a different dicussion point not fitting in that issue.

In general, if you want to use parallelism and therefor want to write graphs in parallel, there are multiple ways:

• As robert said: use multiple threads to write documents. Every thread produces a separate segment. This works well with documents, but this also allows to build the graph in parallel
• If you want to parallelize writing when building a single segment, a codec could simply write the parts to different files. Theres no need to seek within one file.

Can you share the reasoning why it was removed from earlier versions? Where these benefits been considered back then? Would be great to have data driven discussion around those aspects to weigh cons/pros outside of idiomatic/syntactic preferences.

In earlier versions of Lucene there was sometimes the need to write the header (with sizes) of a file at end. Because this does not work with checksums and because the general writing of index files was otherwise sequential, the IndexOutput's seek methods were removed. The Lucene 4+ codecs use the same pattern as said before: Split index files. E.g., for CFS theres now a CFE file with additional information which cannot be written without seeking. The same applies for many other index codecs: They have multiple files for the same piece of information. The same applies for graphs: you can split a file containing the graph, if it improves writing speed by working in parallel.

In summary: Theres no need to allow random access for writing.

Uwe

[sam-herman]

In general, if you want to use parallelism and therefor want to write graphs in parallel, there are multiple ways:

As robert said: use multiple threads to write documents. Every thread produces a separate segment. This works well with documents, but this also allows to build the graph in parallel
If you want to parallelize writing when building a single segment, a codec could simply write the parts to different files. Theres no need to seek within one file.

I want to clarify a few points where it seems we may be talking past each other, especially regarding graph-based structures and why segments themselves (not files) are the root of the challenge I'm trying to address.

1. The core issue is the multiplicity of segments, not multiplicity of files

For graph/vector indices, the dominant cost during query execution is not file I/O — it is the independent traversal of each segment-local graph. A HNSW-style query is typically log N over the graph in a single segment. But when the same document population is spread across K segments, we effectively incur: K × log(N/K)

This becomes linear in K and forces multi-segment search to become CPU-parallel rather than algorithmically efficient. Even when each segment is small, we pay the per-segment entry-point overhead and separate graph traversal cost.

So while parallelism can certainly be applied at the file level, or at the per-thread writer level, it does not address the fact that each segment is itself a standalone graph that must be searched in full. Ultimately, segment count — not file count — is the scalability bottleneck for graph query workloads. This is the main reason why I'm exploring ways to keep the number of graph-active segments small.

2. Why multi-file writes still cannot form a single logical graph

Even if we shard the graph across multiple files, Lucene still treats all files belonging to a segment as one isolated search universe. There is currently:
• no ability to share graph entry points across segments,
• no cross-segment edges,
• no global routing layer,
• no concept of a segment-spanning graph structure.

Advanced graph layouts (e.g., coarse-to-fine partitioned graphs like in https://dl.acm.org/doi/10.1145/3600006.3613166) fundamentally rely on a single logical graph with a global routing layer. Under Lucene’s model, the moment data is split into segments, those partitions cannot cooperate as one graph — even if they physically reside in multiple files.

So multi-file writing improves I/O performance, but it does not solve the architectural constraint.

In earlier versions of Lucene there was sometimes the need to write the header (with sizes) of a file at end. Because this does not work with checksums and because the general writing of index files was otherwise sequential, the IndexOutput's seek methods were removed. The Lucene 4+ codecs use the same pattern as said before: Split index files. E.g., for CFS theres now a CFE file with additional information which cannot be written without seeking. The same applies for many other index codecs: They have multiple files for the same piece of information. The same applies for graphs: you can split a file containing the graph, if it improves writing speed by working in parallel.

Thanks for the context, the motivation this time however is different, is not header rewriting; it’s to enable parallel construction of a single large graph segment to reduce the number of queried graphs, without paying the IO cost of full segment rebuild during merges.

[dweiss]

The immutability and independence of segments are so deeply hardcoded in how Lucene operates that I don't think you'll be able to change this. The way I see it, I think you'd be better off indexing your vectors in an external database system and use docvalues to store just an id of a vector in that external system...

[sam-herman]

The immutability and independence of segments are so deeply hardcoded in how Lucene operates that I don't think you'll be able to change this. The way I see it, I think you'd be better off indexing your vectors in an external database system and use docvalues to store just an id of a vector in that external system...

@dweiss Thanks, that makes sense. I’m currently exploring a similar hybrid approach, so it may indeed be the most practical path forward within Lucene’s existing abstractions. Appreciate the discussion.