What is a reader/writer lock?
A reader/writer lock is a synchronization primitive that allows many threads to hold shared read access at the same time, but requires exclusive access for any thread that needs to write — so readers proceed in parallel until a writer needs the data alone.
How does a reader/writer lock differ from an ordinary mutex?
A mutex treats every critical-section entrant the same: only one thread may hold the lock, whether that thread will merely read or will modify the guarded state. A reader/writer lock distinguishes the two intents. Any number of readers may hold the lock in shared mode concurrently, because read-only observers do not interfere with each other. A writer must acquire the lock in exclusive mode, which waits until no readers (and no other writer) remain, then blocks new readers until the write completes. The payoff appears on read-heavy workloads: instead of serializing every search behind a single mutex, many searches can traverse the same structure at once, and only the relatively rare update pays the exclusive-access cost. The complexity appears at the policy edges — whether waiting writers block new readers (write-preferring) or new readers can starve writers (read-preferring) — which different implementations resolve differently.
HNSW query serving is almost the textbook read-heavy case, which is why reader/writer locks (or equivalent read-mostly protocols) show up around concurrent graphs.
Why does concurrent HNSW map so naturally onto reader/writer locking?
In steady state, a vector index answers far more searches than it applies inserts or deletes. Each search walks neighbor lists and scores vectors without needing to mutate the graph; those threads are readers. An insertion rewires adjacency lists and updates metadata; that thread is a writer for the nodes it changes. Using a single global mutex around the whole graph would force searches to take turns even though they only read. A reader/writer scheme — global or per-node — lets many query threads hold shared access while an inserter waits for exclusive access on the regions it will modify. Per-node reader/writer locks keep the critical section small: searches take shared locks only on nodes they currently inspect (or avoid explicit read locks entirely under a quieter epoch/RCU-style protocol), and inserters take exclusive locks only on the endpoints of edges they splice. In-memory systems that expose concurrent query and upsert traffic against HNSW, including deployments like Weaviate, depend on some variant of this read-mostly idea so QPS stays high while the graph still accepts writes.
Read-mostly is not the same as lock-free, and the distinction matters when writers arrive in bursts.
What goes wrong when writers compete with a crowd of HNSW readers?
If the lock prefers readers, a continuous stream of searches can delay an insert indefinitely — writer starvation — so the graph lags behind the ingest pipeline even though CPUs look busy serving queries. If the lock prefers writers, a single insert can pause admission of new readers until in-flight readers drain, creating latency spikes on the query path every time a batch of upserts lands. Holding a write lock across an entire construction search (not just the final neighbor-list mutation) stretches exclusive time and turns every insert into a broad hiccup. Holding per-node write locks in an inconsistent order across threads reintroduces deadlock risk just as with plain mutexes. The practical discipline is short exclusive sections, prefer writer-friendly policies when ingest SLOs matter, and consider separating “search for candidates” (no exclusive lock) from “commit edges” (exclusive only on touched nodes).
Some HNSW designs reduce read-side locking further, which is the next step beyond a classic reader/writer lock.
When might you avoid read locks entirely on the HNSW search path?
If writers publish updates through atomic pointer swings or versioned neighbor arrays, and readers follow a quiescent or epoch-based rule that never frees memory still visible to in-flight searches, queries can traverse without taking a shared lock on every hop. That approach still embodies the reader/writer idea — many concurrent readers, exclusive logical writers — but moves coordination into memory reclamation and publication order instead of a lock acquire per node. It is harder to implement correctly, yet it removes shared-lock cache-line traffic from the hottest path. Choosing between explicit reader/writer locks and lock-free read-mostly publication is an engineering trade against team complexity, delete/reclaim requirements, and measured contention. For many codebases, per-node or striped reader/writer locks remain the clear, maintainable fit until profiles prove the shared-acquire cost dominates.
A reader/writer lock lets many HNSW searches share the graph while still giving inserts an exclusive window to rewire edges safely. From here, the mutex page covers exclusive-only locking, read-mostly graph safety deepens the query-side model, lock ordering and deadlock address multi-lock hazards, contention explains scaling limits, and the chapter on concurrent HNSW construction and querying shows full protocols that mix these tools.