HarperFast / HarperFast/harper

HNSW: insertion degrades O(N) with graph size, blocks event loop, disrupts replication

Open
#895 0 comments 0 reactions 0 assignees View on GitHub
area:storage bug
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.