Skip to content

[IS] checkpoint Phase B searches global graph — duration is O(N_total) instead of O(N_live_shards) #614

Closed

Description

@eolivelli

Summary

doCheckpointFusedPQPhaseB builds HNSW graph connections for each new live-shard
vector by searching the entire global on-disk graph (all existing segments).
This violates the checkpoint contract: checkpoint's only job is to durably persist
the in-memory (live) shards so the service can recover after a crash. The cost of
Phase B should be proportional to the size of the live shards alone, not the
total index size. Merging on-disk segments and maintaining global graph connectivity
is the responsibility of the background compaction threads, not the checkpoint.

Observed behaviour

Workload: BIGANN 50M, gRPC push mode, k3s-local cluster, IS pod 26 GiB / -Xmx5g.

Every regular checkpoint during ingestion flushed 3–6 live shards (~270K–400K
vectors) quickly:

Phase A: snapshotted 4 live shards (340,603 vectors) + 431,974 on-disk, 5 mergeable
Phase B: completed in 6,712 ms   (4 shard segments, 310,382 total vectors, 506 MB)

Phase A: snapshotted 4 live shards (389,556 vectors) + 46,392,090 on-disk, 513 mergeable
Phase B: completed in 9,861 ms   (4 shard segments, 389,556 total vectors, 635 MB)

These are all consistent at ~20–25 ms per live-shard vector regardless of how
many on-disk vectors exist — up to a point.

The final back-pressure checkpoint (triggered at 46.8M on-disk vectors, 517
mergeable segments) had identical live-shard input:

Phase A: snapshotted 6 live shards (472,730 vectors) + 46,781,646 on-disk vectors,
         0 sealed + 517 mergeable segments
Phase B: completed in 2,139,268 ms (6 shard segments, 472,730 total vectors, 771 MB)

2,139 seconds (35.7 minutes) for the same ~470K live-shard vectors that would
normally take ~10 seconds. The output size (771 MB / 472K vectors ≈ 1,630 bytes/vector)
is identical to earlier Phase Bs — confirming only the live shards were written to
disk. Yet the work done was ~200× more expensive.

During this Phase B the IS JVM ran at 99.5% heap for ~45 minutes. A jstack
taken mid-run showed all threads idle between bursts, confirming the JVM was
spending almost all cycles in GC rather than useful work. The compaction progress
log showed bursts of ~10–50 batches/minute:

Compaction I/O progress: 4190/30424 batches written to disk
Compaction I/O progress: 4200/30424 batches written to disk
...

30,424 batches for 472,730 vectors = 64 batches/vector, versus earlier Phase Bs
that completed with no visible batch logging at all (too fast to log).

Root cause

doCheckpointFusedPQPhaseB calls
OnDiskGraphIndexCompactor.runBatchesWithBackpressure, which builds HNSW graph
edges for each new live-shard vector by searching the global graph context
(all 46.8M on-disk nodes). The cost of each vector insertion is:

O(ef_construction × log(N_total))

where N_total = 46,781,646 at the time of the final checkpoint vs N_total = 0
for the very first checkpoint. This makes Phase B latency proportional to the
total index size rather than the live shard size.

What checkpoint Phase B should do

Checkpoint exists to enable crash recovery: if the IS restarts it must be able
to replay only the entries since the last durable LSN. Phase B just needs to write
the raw live-shard vectors (and their intra-shard graph edges) to a new on-disk
segment file. It does not need to integrate them into the global HNSW graph —
that is the job of background compaction.

What it actually does

Phase B calls the full graph-merge compactor, which:

  1. Reads all vectors from the global on-disk graph as the "background" context
  2. Inserts each new live-shard vector into this global context via HNSW search
  3. Writes the new segment with inter-segment edges to all 46.8M existing neighbors

This is O(N_live × log(N_total)) instead of O(N_live × log(N_live)).

Why background compaction did not help

The two dedicated compaction threads (persistent-vector-store-compaction-vidx,
persistent-vector-store-vidxcompaction-vidx) consumed only 33 s and 72 s of
CPU
respectively over the entire 110-minute run (confirmed via jstack). They were
in Object.wait() for essentially the whole ingestion. With no incremental
compaction happening, every new Phase B flush added 3–6 more "mergeable" segments,
growing the global graph that the next Phase B must search through.

Evidence

Checkpoint Live shards On-disk vectors Phase B duration
#1 91,371 0 15,144 ms
#5 310,382 431,974 6,712 ms
#130 389,556 46,392,090 9,861 ms
#131 472,730 46,781,646 2,139,268 ms
#132 1,629,075 ~47M 39,837 ms
#133 461,658 ~47M 10,522 ms

Note: checkpoints #130 and #133 have similar on-disk counts but wildly different
durations. The #131 outlier is explained by JVM heap at 99.5% from accumulated
GC pressure after the ingestion back-pressure blocked entry processing for ~35 min.

jstack CPU summary at peak GC pressure:

"persistent-vector-store-compaction-vidx"       cpu=33,367ms   SLEEPING
"persistent-vector-store-vidxcompaction-vidx"   cpu=72,501ms   SLEEPING
"indexing-checkpoint"                           cpu=270,151ms  WAITING (between bursts)
"indexing-apply-worker-0..7"                    cpu=3,033–3,043s each (all from ingestion phase, now idle)

Expected behaviour

Phase B duration should be O(N_live_shards) regardless of total index size.
The live shards should be written as self-contained segment files (with intra-shard
graph edges only). Background compaction then merges them into the global graph
incrementally and asynchronously, without blocking the checkpoint path.

Impact

  • With a large index (≥10M vectors) and an active background compaction that keeps
    up, Phase B duration grows slowly but manageably as O(N_live × log(N_total)).
  • When background compaction stalls (as here), all segments accumulate as
    "mergeable" and the next Phase B's global graph grows without bound —
    exponentially increasing Phase B cost until it either times out or GC-thrashes
    the JVM to near-OOM.
  • This is a latent reliability issue: any condition that delays background
    compaction (S3 throttling, GC pressure, resource contention) compounds into
    catastrophic checkpoint latency at the next back-pressure trigger.

Environment

Activity

  1. added
    k3s-benchAutomated reports from the k3s vector-bench agent
    on May 20, 2026
  2. eolivelli commented on May 20, 2026

    @eolivelli
    OwnerAuthor

    Closing as not-a-bug after code inspection of master @ b7855a2f.

    Phase B does not search the global on-disk graph

    The issue claims doCheckpointFusedPQPhaseB calls OnDiskGraphIndexCompactor.runBatchesWithBackpressure against the global graph. That call does not exist in the codebase. What Phase B actually does today (herddb-indexing-service/src/main/java/herddb/indexing/vector/PersistentVectorStore.java):

    1. doCheckpointFusedPQPhaseB (line 6017) iterates the frozen LiveGraphShards and calls writeShardAsFusedPQSegment (line 6580) for each one — optionally in parallel.
    2. writeShardAsFusedPQSegment takes the shard's already-built OnHeapGraphIndex via shard.builder.getGraph() (line 6597), PQ-encodes the shard's vectors using a per-shard view (VectorStorageShardView, line 6614), and serializes both via OnDiskGraphIndexWriter. No OnDiskGraphIndexCompactor, no global graph reader, no inter-segment edges.
    3. The per-shard GraphIndexBuilder is created at createEmptyLiveShard (line 8204) with BuildScoreProvider.randomAccessScoreProvider(ravv, similarityFunction) over the shard's own VectorStorage. The graph is built incrementally during addVector → active.builder.addGraphNode(localOrd, vec) (line 4429). The score provider can only see the per-shard vectors, by construction.

    Phase B is provably O(N_live_shards × log(per_shard_cap)) with per_shard_cap bounded by computeEffectiveMaxLiveGraphSize(). It does not consult segments or any on-disk graph.

    What the 35-minute outlier actually was

    The issue itself states it in passing:

    The #131 outlier is explained by JVM heap at 99.5% from accumulated GC pressure after the ingestion back-pressure blocked entry processing for ~35 min.

    That is the real root cause. The IS pod was GC-thrashing at 99.5% heap during checkpoint #131; per-vector wall-clock time inflated by ~200× because almost every cycle went to GC, not because the algorithm changed shape. The output size (771 MB / 472K vectors ≈ 1,630 bytes/vector) being identical to earlier Phase Bs is direct confirmation — the same amount of work, just executed under GC starvation.

    On the cited log lines

    The strings Compaction I/O progress, batches written to disk, and runBatchesWithBackpressure do not appear anywhere in the herddb codebase. They are jvector-library output emitted by OnDiskGraphIndexCompactor, which is only reachable from RemoteSegmentGraphMerger.merge() — i.e. the background compactor (runCompactionCycle) and the index-optimizer service. Those threads ran concurrently with the Phase B at issue, so their progress lines appear interleaved in the log, but they are not Phase B work.

    Where to dig next, if needed

    The real symptom worth tracking is the GC-pressure compounding when ingestion back-pressure stalls. Existing work touching that area:

    If a future run reproduces a multi-minute Phase B without 99%+ heap, please reopen with the heap-utilisation timeline alongside the Phase B logs — that would distinguish a genuine algorithmic regression from another GC-pressure event.

  3. eolivelli commented on May 20, 2026

    @eolivelli
    OwnerAuthor

    Reopening to implement defensive observability and regression assertions (Option 2 from analysis above): per-shard Phase B timing breakdown, free-heap logging at Phase B boundaries, and two new tests locking the local-scope invariant and the delete+recall invariant.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    k3s-benchAutomated reports from the k3s vector-bench agent

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions