You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by iv...@apache.org on 2026/09/04 08:58:14 UTC
(lucene) branch main updated: Make HNSW merges abortable during graph initialization and repair (#16620)
This is an automated email from the ASF dual-hosted git repository.
iverase pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/lucene.git
The following commit(s) were added to refs/heads/main by this push:
new 553fb33c0ef Make HNSW merges abortable during graph initialization and repair (#16620)
553fb33c0ef is described below
commit 553fb33c0ef7c5e6d54ed4f35b966d95cb6535a9
Author: Tanguy Leroux <tl...@gmail.com>
AuthorDate: Fri Sep 4 10:58:06 2026 +0200
Make HNSW merges abortable during graph initialization and repair (#16620)
---
lucene/CHANGES.txt | 4 ++
.../codecs/lucene99/Lucene99HnswVectorsWriter.java | 2 +
.../lucene/util/hnsw/ConcurrentHnswMerger.java | 7 ++-
.../apache/lucene/util/hnsw/HnswGraphBuilder.java | 10 +++
.../util/hnsw/IncrementalHnswGraphMerger.java | 3 +-
.../util/hnsw/InitializedHnswGraphBuilder.java | 63 ++++++++++++++++++-
.../lucene/util/hnsw/MergingHnswGraphBuilder.java | 38 +++++++++++-
.../lucene/util/hnsw/TestHnswFloatVectorGraph.java | 71 ++++++++++++++++++++++
8 files changed, 191 insertions(+), 7 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index e77c3057b65..16f79b3dc3d 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -490,6 +490,10 @@ Optimizations
Bug Fixes
---------------------
+* GITHUB#16620: Make HNSW merges abortable during graph initialization and repair, so that the
+ copy, repair and rebalance phases of an initialized graph build can be promptly aborted when the
+ surrounding merge is cancelled. (Tanguy Leroux)
+
* GITHUB#16565: IndexWriter#updateBinaryDocValue now rejects updating a field that is part of the
index sort, matching IndexWriter#updateNumericDocValue. (Jim Ferenczi)
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/lucene99/Lucene99HnswVectorsWriter.java b/lucene/core/src/java/org/apache/lucene/codecs/lucene99/Lucene99HnswVectorsWriter.java
index e643596cd3b..6868682aa22 100644
--- a/lucene/core/src/java/org/apache/lucene/codecs/lucene99/Lucene99HnswVectorsWriter.java
+++ b/lucene/core/src/java/org/apache/lucene/codecs/lucene99/Lucene99HnswVectorsWriter.java
@@ -419,6 +419,8 @@ public final class Lucene99HnswVectorsWriter extends KnnVectorsWriter {
public IORunnable mergeOneField(FieldInfo fieldInfo, MergeState mergeState) throws IOException {
flatVectorWriter.mergeOneFlatVectorField(fieldInfo, mergeState);
return () -> {
+ // Bail out before the potentially heavy graph build if the merge was already aborted
+ mergeState.checkAborted();
// Lazily finish flat writer and open a reader for the written segment
ensureFlatReaderOpen();
// Get the vector values and scorer supplier from the written segment
diff --git a/lucene/core/src/java/org/apache/lucene/util/hnsw/ConcurrentHnswMerger.java b/lucene/core/src/java/org/apache/lucene/util/hnsw/ConcurrentHnswMerger.java
index ea306fec0ce..9fe52794322 100644
--- a/lucene/core/src/java/org/apache/lucene/util/hnsw/ConcurrentHnswMerger.java
+++ b/lucene/core/src/java/org/apache/lucene/util/hnsw/ConcurrentHnswMerger.java
@@ -97,7 +97,12 @@ public class ConcurrentHnswMerger extends IncrementalHnswGraphMerger {
initializedNodes);
graph =
InitializedHnswGraphBuilder.initGraph(
- initializerGraph, oldToNewOrdinalMap, maxOrd, beamWidth, scorerSupplier);
+ initializerGraph,
+ oldToNewOrdinalMap,
+ maxOrd,
+ beamWidth,
+ scorerSupplier,
+ abortCheck);
}
}
return new HnswConcurrentMergeBuilder(
diff --git a/lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java b/lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java
index dbd92163f8d..d37d980537b 100644
--- a/lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java
+++ b/lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java
@@ -220,6 +220,16 @@ public class HnswGraphBuilder implements HnswBuilder {
this.abortCheck = abortCheck;
}
+ /**
+ * Runs the abort check if one has been set, otherwise does nothing. Subclasses should call this
+ * from any long-running merge operation so that a cancelled merge can be aborted promptly.
+ */
+ protected final void maybeAbort() throws IOException {
+ if (abortCheck != null) {
+ abortCheck.run();
+ }
+ }
+
@Override
public OnHeapHnswGraph getCompletedGraph() throws IOException {
if (!frozen) {
diff --git a/lucene/core/src/java/org/apache/lucene/util/hnsw/IncrementalHnswGraphMerger.java b/lucene/core/src/java/org/apache/lucene/util/hnsw/IncrementalHnswGraphMerger.java
index 014e801924a..94a2baaf7e9 100644
--- a/lucene/core/src/java/org/apache/lucene/util/hnsw/IncrementalHnswGraphMerger.java
+++ b/lucene/core/src/java/org/apache/lucene/util/hnsw/IncrementalHnswGraphMerger.java
@@ -177,7 +177,8 @@ public class IncrementalHnswGraphMerger implements HnswGraphMerger {
graphs,
ordMaps,
maxOrd,
- initializedNodes);
+ initializedNodes,
+ abortCheck);
}
protected final int[][] getNewOrdMapping(
diff --git a/lucene/core/src/java/org/apache/lucene/util/hnsw/InitializedHnswGraphBuilder.java b/lucene/core/src/java/org/apache/lucene/util/hnsw/InitializedHnswGraphBuilder.java
index d9ce25dd69a..ac8d4906592 100644
--- a/lucene/core/src/java/org/apache/lucene/util/hnsw/InitializedHnswGraphBuilder.java
+++ b/lucene/core/src/java/org/apache/lucene/util/hnsw/InitializedHnswGraphBuilder.java
@@ -30,6 +30,7 @@ import org.apache.lucene.internal.hppc.IntArrayList;
import org.apache.lucene.internal.hppc.IntCursor;
import org.apache.lucene.util.ArrayUtil;
import org.apache.lucene.util.BitSet;
+import org.apache.lucene.util.IORunnable;
/**
* This creates a graph builder that is initialized with the provided HnswGraph. This is useful for
@@ -108,6 +109,10 @@ public final class InitializedHnswGraphBuilder extends HnswGraphBuilder {
* tracking)
* @param totalNumberOfVectors the total number of vectors in the merged graph (used for
* pre-allocation)
+ * @param abortCheck optional check polled during graph construction, i.e. while copying,
+ * repairing and rebalancing the initializer graph and before each node insertion; may throw
+ * {@link org.apache.lucene.index.MergePolicy.MergeAbortedException} to abort the build when
+ * the surrounding merge has been aborted, or null
* @return a new builder initialized with the provided graph structure
* @throws IOException if an I/O error occurs during graph initialization
*/
@@ -118,7 +123,8 @@ public final class InitializedHnswGraphBuilder extends HnswGraphBuilder {
HnswGraph initializerGraph,
int[] newOrdMap,
BitSet initializedNodes,
- int totalNumberOfVectors)
+ int totalNumberOfVectors,
+ IORunnable abortCheck)
throws IOException {
InitializedHnswGraphBuilder builder =
@@ -129,10 +135,37 @@ public final class InitializedHnswGraphBuilder extends HnswGraphBuilder {
new OnHeapHnswGraph(initializerGraph.maxConn(), totalNumberOfVectors),
initializedNodes);
+ if (abortCheck != null) {
+ builder.setAbortCheck(abortCheck);
+ }
builder.initializeFromGraph(initializerGraph, newOrdMap);
return builder;
}
+ /**
+ * Same as {@link #fromGraph(RandomVectorScorerSupplier, int, long, HnswGraph, int[], BitSet, int,
+ * IORunnable)} but without an abort check.
+ */
+ public static InitializedHnswGraphBuilder fromGraph(
+ RandomVectorScorerSupplier scorerSupplier,
+ int beamWidth,
+ long seed,
+ HnswGraph initializerGraph,
+ int[] newOrdMap,
+ BitSet initializedNodes,
+ int totalNumberOfVectors)
+ throws IOException {
+ return fromGraph(
+ scorerSupplier,
+ beamWidth,
+ seed,
+ initializerGraph,
+ newOrdMap,
+ initializedNodes,
+ totalNumberOfVectors,
+ null);
+ }
+
/**
* Convenience method to create a fully initialized on-heap HNSW graph without tracking
* initialized nodes. This is useful when you just need the resulting graph structure without
@@ -143,6 +176,10 @@ public final class InitializedHnswGraphBuilder extends HnswGraphBuilder {
* @param totalNumberOfVectors the total number of vectors in the merged graph
* @param beamWidth the search beam width for graph construction
* @param scorerSupplier provides vector similarity scoring
+ * @param abortCheck optional check polled during graph construction, i.e. while copying,
+ * repairing and rebalancing the initializer graph and before each node insertion; may throw
+ * {@link org.apache.lucene.index.MergePolicy.MergeAbortedException} to abort the build when
+ * the surrounding merge has been aborted, or null
* @return a fully initialized on-heap HNSW graph
* @throws IOException if an I/O error occurs during graph initialization
*/
@@ -151,7 +188,8 @@ public final class InitializedHnswGraphBuilder extends HnswGraphBuilder {
int[] newOrdMap,
int totalNumberOfVectors,
int beamWidth,
- RandomVectorScorerSupplier scorerSupplier)
+ RandomVectorScorerSupplier scorerSupplier,
+ IORunnable abortCheck)
throws IOException {
InitializedHnswGraphBuilder builder =
@@ -162,10 +200,26 @@ public final class InitializedHnswGraphBuilder extends HnswGraphBuilder {
initializerGraph,
newOrdMap,
null,
- totalNumberOfVectors);
+ totalNumberOfVectors,
+ abortCheck);
return builder.getGraph();
}
+ /**
+ * Same as {@link #initGraph(HnswGraph, int[], int, int, RandomVectorScorerSupplier, IORunnable)}
+ * but without an abort check.
+ */
+ public static OnHeapHnswGraph initGraph(
+ HnswGraph initializerGraph,
+ int[] newOrdMap,
+ int totalNumberOfVectors,
+ int beamWidth,
+ RandomVectorScorerSupplier scorerSupplier)
+ throws IOException {
+ return initGraph(
+ initializerGraph, newOrdMap, totalNumberOfVectors, beamWidth, scorerSupplier, null);
+ }
+
private InitializedHnswGraphBuilder(
RandomVectorScorerSupplier scorerSupplier,
int beamWidth,
@@ -239,6 +293,7 @@ public final class InitializedHnswGraphBuilder extends HnswGraphBuilder {
HnswGraph.NodesIterator it = initializerGraph.getNodesOnLevel(level);
while (it.hasNext()) {
+ maybeAbort();
int oldOrd = it.nextInt();
int newOrd = newOrdMap[oldOrd];
@@ -327,6 +382,7 @@ public final class InitializedHnswGraphBuilder extends HnswGraphBuilder {
NeighborArray scratchArray = new NeighborArray(beamWidth, false);
for (int node : disconnectedNodes) {
+ maybeAbort();
scorer.setScoringOrdinal(node);
NeighborArray existingNeighbors = hnsw.getNeighbors(level, node);
@@ -402,6 +458,7 @@ public final class InitializedHnswGraphBuilder extends HnswGraphBuilder {
// Promote with probability 1/M, matching HNSW's level assignment distribution
if (random.nextDouble() < invMaxConn && !hnsw.nodeExistAtLevel(level, node)) {
+ maybeAbort();
scorer.setScoringOrdinal(node);
hnsw.addNode(level, node);
diff --git a/lucene/core/src/java/org/apache/lucene/util/hnsw/MergingHnswGraphBuilder.java b/lucene/core/src/java/org/apache/lucene/util/hnsw/MergingHnswGraphBuilder.java
index e41979b1acd..77be973ba46 100644
--- a/lucene/core/src/java/org/apache/lucene/util/hnsw/MergingHnswGraphBuilder.java
+++ b/lucene/core/src/java/org/apache/lucene/util/hnsw/MergingHnswGraphBuilder.java
@@ -24,6 +24,7 @@ import java.util.Arrays;
import java.util.Locale;
import org.apache.lucene.internal.hppc.IntHashSet;
import org.apache.lucene.util.BitSet;
+import org.apache.lucene.util.IORunnable;
/**
* A graph builder that is used during segments' merging.
@@ -87,6 +88,9 @@ public final class MergingHnswGraphBuilder extends HnswGraphBuilder {
* all vectors expected to be added to the graph in the future
* @param initializedNodes the nodes will be initialized through the merging, if null, all nodes
* should be already initialized after {@link #updateGraph(HnswGraph, int[])} being called
+ * @param abortCheck optional check invoked during the graph-join initialization/repair of the
+ * base graph; may throw {@link org.apache.lucene.index.MergePolicy.MergeAbortedException} to
+ * abort a cancelled merge promptly rather than only during subsequent node insertion, or null
* @return a new HnswGraphBuilder that is initialized with the provided HnswGraph
* @throws IOException when reading the graph fails
*/
@@ -97,15 +101,45 @@ public final class MergingHnswGraphBuilder extends HnswGraphBuilder {
HnswGraph[] graphs,
int[][] ordMaps,
int totalNumberOfVectors,
- BitSet initializedNodes)
+ BitSet initializedNodes,
+ IORunnable abortCheck)
throws IOException {
OnHeapHnswGraph graph =
InitializedHnswGraphBuilder.initGraph(
- graphs[0], ordMaps[0], totalNumberOfVectors, beamWidth, scorerSupplier);
+ graphs[0], ordMaps[0], totalNumberOfVectors, beamWidth, scorerSupplier, abortCheck);
return new MergingHnswGraphBuilder(
scorerSupplier, beamWidth, seed, graph, graphs, ordMaps, initializedNodes);
}
+ /**
+ * Same as {@link #fromGraphs(RandomVectorScorerSupplier, int, long, HnswGraph[], int[][], int,
+ * BitSet, IORunnable)} but without an abort check.
+ *
+ * <p>This parameter-less overload is kept deliberately so the abort-check change stays purely
+ * additive: existing call sites keep compiling unchanged, which keeps the backport to 10.5
+ * minimal. New callers should prefer the {@code abortCheck} overload so a cancelled merge can be
+ * aborted during the graph-join initialization/repair phase.
+ */
+ public static MergingHnswGraphBuilder fromGraphs(
+ RandomVectorScorerSupplier scorerSupplier,
+ int beamWidth,
+ long seed,
+ HnswGraph[] graphs,
+ int[][] ordMaps,
+ int totalNumberOfVectors,
+ BitSet initializedNodes)
+ throws IOException {
+ return fromGraphs(
+ scorerSupplier,
+ beamWidth,
+ seed,
+ graphs,
+ ordMaps,
+ totalNumberOfVectors,
+ initializedNodes,
+ null);
+ }
+
@Override
public OnHeapHnswGraph build(int maxOrd) throws IOException {
if (frozen) {
diff --git a/lucene/core/src/test/org/apache/lucene/util/hnsw/TestHnswFloatVectorGraph.java b/lucene/core/src/test/org/apache/lucene/util/hnsw/TestHnswFloatVectorGraph.java
index 6822511fa10..329da3a0275 100644
--- a/lucene/core/src/test/org/apache/lucene/util/hnsw/TestHnswFloatVectorGraph.java
+++ b/lucene/core/src/test/org/apache/lucene/util/hnsw/TestHnswFloatVectorGraph.java
@@ -20,11 +20,13 @@ package org.apache.lucene.util.hnsw;
import com.carrotsearch.randomizedtesting.RandomizedTest;
import java.io.IOException;
import java.util.Random;
+import java.util.concurrent.atomic.AtomicInteger;
import org.apache.lucene.document.Field;
import org.apache.lucene.document.KnnFloatVectorField;
import org.apache.lucene.index.FloatVectorValues;
import org.apache.lucene.index.KnnVectorValues;
import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.index.MergePolicy;
import org.apache.lucene.index.VectorEncoding;
import org.apache.lucene.index.VectorSimilarityFunction;
import org.apache.lucene.search.KnnCollector;
@@ -34,6 +36,7 @@ import org.apache.lucene.search.ScoreDoc;
import org.apache.lucene.search.TopDocs;
import org.apache.lucene.util.ArrayUtil;
import org.apache.lucene.util.FixedBitSet;
+import org.apache.lucene.util.IORunnable;
import org.junit.Before;
/** Tests HNSW KNN graphs */
@@ -117,6 +120,74 @@ public class TestHnswFloatVectorGraph extends HnswGraphTestCase<float[]> {
}
}
+ /**
+ * A cancelled merge must be able to abort HNSW graph construction during the graph-join
+ * initialization and disconnected-node repair phases, not only during the subsequent incremental
+ * node insertion.
+ */
+ public void testAbortCheckInterruptsGraphInitAndRepair() throws IOException {
+ // Pin vectors, both graph seeds, and similarity so the merged graph is identical every run.
+ long savedRandSeed = HnswGraphBuilder.randSeed;
+ try {
+ HnswGraphBuilder.randSeed = 42;
+ similarityFunction = VectorSimilarityFunction.EUCLIDEAN;
+ int M = 16;
+ int beamWidth = 100;
+ int size = 256;
+ int dim = 16;
+ MockVectorValues vectors =
+ MockVectorValues.fromValues(createRandomFloatVectors(size, dim, new Random(42)));
+ RandomVectorScorerSupplier supplier = buildScorerSupplier(vectors);
+ OnHeapHnswGraph graph = HnswGraphBuilder.create(supplier, M, beamWidth, 42).build(size);
+
+ // Delete every other document (never the entry node) so the merge takes the graph-join path
+ // with deletes: many survivors lose neighbors and get repaired by fixDisconnectedNodes.
+ int entry = graph.entryNode();
+ int[] newOrdMap = new int[size];
+ for (int i = 0; i < size; i++) {
+ newOrdMap[i] = (i == entry || (i & 1) == 0) ? i : -1;
+ }
+
+ // copyGraphStructure polls the abort check exactly once per source node across every level.
+ int copyLoopChecks = 0;
+ for (int level = 0; level < graph.numLevels(); level++) {
+ copyLoopChecks += graph.getNodesOnLevel(level).size();
+ }
+
+ // Test that aborting on the very first check stops the graph initialization immediately
+ IORunnable abortImmediately =
+ () -> {
+ throw new MergePolicy.MergeAbortedException("aborted before init");
+ };
+ expectThrows(
+ MergePolicy.MergeAbortedException.class,
+ () ->
+ InitializedHnswGraphBuilder.initGraph(
+ graph, newOrdMap, size, beamWidth, supplier, abortImmediately));
+
+ // Test that aborting during repair stops the graph initialization immediately
+ AtomicInteger checksUntilAbort = new AtomicInteger(copyLoopChecks + 1);
+ IORunnable abortDuringRepair =
+ () -> {
+ if (checksUntilAbort.decrementAndGet() == 0) {
+ throw new MergePolicy.MergeAbortedException("aborted mid-repair");
+ }
+ };
+ expectThrows(
+ MergePolicy.MergeAbortedException.class,
+ () ->
+ InitializedHnswGraphBuilder.initGraph(
+ graph, newOrdMap, size, beamWidth, supplier, abortDuringRepair));
+
+ // Test that the graph can be correctly initialized
+ OnHeapHnswGraph merged =
+ InitializedHnswGraphBuilder.initGraph(graph, newOrdMap, size, beamWidth, supplier, null);
+ assertNotNull(merged);
+ } finally {
+ HnswGraphBuilder.randSeed = savedRandSeed;
+ }
+ }
+
@Override
MockVectorValues vectorValues(LeafReader reader, String fieldName) throws IOException {
FloatVectorValues vectorValues = reader.getFloatVectorValues(fieldName);