What is read-mostly graph safety?

Read-mostly graph safety is a concurrency approach for HNSW in which searches traverse the shared graph without taking a lock on every hop, while infrequent writers update neighbor lists under carefully published rules so readers never observe torn edges or freed memory still in use.

Why do query-heavy HNSW workloads want to avoid locking on the read path?

A single search may examine hundreds of nodes. If each hop acquired a shared reader/writer lock, acquire/release costs and cache-line bouncing on lock words would dominate even when no writer exists. Parallel query serving depends on many threads reading the same adjacency arrays concurrently with almost no synchronization. The graph is “read-mostly”: upserts and deletes happen, but far less often than searches. Read-mostly safety preserves that fast path — readers run as if the graph were immutable for the duration of their walk — while still allowing writers to make progress without stopping the world on every query.

The danger is clear if writers mutate lists in place with no protocol: readers can see half-written degrees, dangling IDs, or reuse of memory still visible to an in-flight search.

What invariants must hold so unlocked HNSW readers stay correct?

A reader must only follow neighbor IDs that point to fully initialized node storage. A writer must not free or reuse a neighbor array still reachable by any concurrent search. Publication order matters: initialize the new edge storage first, then swing a pointer or length field with release semantics so an acquire load on the reader side never sees a new pointer to old garbage. Alternatively, writers copy-on-write a neighbor list and atomically install the new version; old versions live until no search can still hold them. Generation counters and epoch-based reclaimers are common tools for delaying free until quiescent. Per-node exclusive locks among writers still prevent two inserters from corrupting the same list; they simply do not involve readers on every hop. Systems that serve live queries during upserts against HNSW, including deployments like Weaviate, rely on some variant of this publish-and-reclaim discipline so QPS stays high while the graph evolves.

Reader/writer locks are a heavier alternative that still counts as read-mostly in spirit when shared mode is the common case.

How do reader/writer locks compare with lock-free read publication?

A graph-wide or per-node reader/writer lock lets many searches hold shared mode while writers wait for exclusive mode. It is easier to implement correctly than full lock-free publication, but shared acquires on hot nodes — or a global reader/writer lock held across a long search — recreate latency spikes when writers arrive. Lock-free (or lock-aside) reads push complexity into memory ordering and safe memory reclaim. Many production designs mix both: no locks on the search hot path, exclusive per-node locks only for writer-versus-writer edge commits, and epochs for freeing obsolete arrays. Choosing among them is an engineering trade between team complexity and measured QPS under mixed load — not a purity contest.

Operationally, read-mostly safety fails in characteristic ways when reclaim or publication is wrong.

What symptoms suggest read-mostly HNSW safety is broken?

Rare crashes or nonsense neighbor IDs under concurrent upserts, recall that flickers only under write load, or sanitizer reports of use-after-free in search threads point at reclaim racing ahead of readers. Writers that block all queries for long stretches point at taking exclusive access too broadly — for example holding a global write lock during the entire construction search. Fixes tighten publication (release/acquire on installing lists), delay free until epochs drain, and shorten exclusive sections to the splice itself. Correct read-mostly safety is what lets parallel query serving and parallel insertion coexist on one HNSW index without turning every search into a locked critical section.

Read-mostly graph safety keeps HNSW searches lock-light on the hot path while writers publish edge updates so readers never see torn or reclaimed memory. From here, parallel query serving and parallel insertion are the workloads it enables, reader/writer locks and per-node locking are the heavier tools, atomics cover publication, and the chapter on concurrent HNSW construction and querying details full protocols.