HarperFast / HarperFast/harper
HNSW: insertion degrades O(N) with graph size, blocks event loop, disrupts replication
- Dominant language
- JavaScript
- Stars
- 89
- Forks
- 10
- Avg merge
- 2d 6h
- Merged PRs (30d)
- 200
Description
## Summary
HNSW insertion throughput degrades roughly O(N) as the graph grows — the opposite of the expected O(log N). On a free-tier cluster with a 10k-vector table, ingest slows from **~178 vectors/s** to **~19 vectors/s** as the graph fills, and each insert takes **~53 ms** (should be sub-millisecond). The event loop produces 11 "JavaScript execution too long" warnings per run. On single-CPU machines this causes write-queue stalls (HTTP 503) and nodes going offline.
The slowdown also disrupts replication: the event-loop blockage during bulk inserts triggers TCP keepalive timeouts, killing in-flight clone connections and forcing clone restarts from zero. On large tables the cluster never converges.
## Root cause
HNSW graph traversal visits O(N) nodes per operation (during layer-0 search). On every node visit, Harper decodes the stored vector from msgpackr format — a full round-trip over a boxed `Array` of 768 floats. Profiling shows this decode accounts for **54.5% of search CPU** and **70.8% of insert CPU**; the actual `computeDistance` call is only 3–4%. The per-vector decode cost makes traversal O(N·decode) even when the graph's structural complexity is O(log N).
## Reproduction
1. Create a table with an HNSW index on a 768-dim vector attribute.
2. Bulk-insert 10k vectors while monitoring throughput.
3. Observe: throughput decays from ~180/s at the start to <20/s by 10k; Harper logs "JavaScript execution too long".
Repro script and detailed findings from @chris-nelson attached to [#development Slack thread](https://harperdb.slack.com/archives/C3Z2T1QAZ/p1779806565475909).
## Fix in progress
- **[harper#894](https://github.com/HarperFast/harper/pull/894)** — int8 scalar quantization for HNSW navigational graph. Eliminates per-element float32 decode by storing graph nodes as compact int8 bin + per-vector scale. Benchmarked: **~4.9× search throughput**, p99 latency **9s → 0.5s**, ~3.6× update, ~3× smaller index, recall@10 within noise of float. CI ✅ all passing.
- **[harper-pro#248](https://github.com/HarperFast/harper-pro/pull/248)** — replication keepalive by byte activity + decode-loop yield budget. Makes replication resilient to event-loop bursts from large HNSW inserts.
- **[harper-pro#255](https://github.com/HarperFast/harper-pro/pull/255)** — resumable bulk clone on reconnect. Prevents clone restarts from zero when a connection is lost mid-copy due to the above event-loop blockage.
## Impact
Clusters with HNSW-indexed tables containing more than a few thousand vectors will see progressively degraded write performance and intermittent replication disruption on single-CPU or resource-constrained nodes.
Contributor guide
Assessment
This issue has not been assessed yet.