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);