What is global-state locking?

Global-state locking is a concurrency strategy that protects the entire HNSW index — or a single shared “graph lock” covering all neighbor lists and index-wide metadata — with one mutex or reader/writer lock, so any thread that needs to mutate (or, in coarse designs, read) the graph must take that same lock.

What counts as “global state” in an HNSW index?

Beyond any one node’s adjacency list, the index owns shared fields every insertion may touch: the next free node ID, the current entry point, the maximum layer observed so far, freelists for deleted slots, and sometimes a global generation counter for visited-set resets. Even with per-node locks on edges, those index-wide fields still need atomic updates or a small global lock. Full global-state locking goes further: one lock stands in for all of that plus every neighbor-list mutation, so the critical section is “the whole graph” rather than “this node” or “this counter.” The mental model is a single door into the index structure.

That single door is why global locking is easy to reason about and hard to scale under parallel insertion.

Why do implementations still use a global graph lock sometimes?

Correctness is straightforward: if only one thread can mutate the graph at a time, neighbor lists never tear, bidirectional links cannot interleave halfway, and lock ordering among nodes never arises. For prototypes, tests, small indexes, or mostly single-threaded ingest with parallel query serving on a frozen graph, a global write lock (or a global writer side of a reader/writer lock) is a legitimate choice. Parallel queries can still run lock-free or under shared mode if writers are rare and the protocol allows. Teams shipping concurrent HNSW under heavy upsert load — including production databases such as Weaviate — typically move past a lone global write lock for edge commits precisely because ingest QPS collapses when every splice queues behind one mutex; the global idea remains for a few true singleton fields.

The failure mode under load is not subtle: throughput flats out while cores wait.

What does global-state locking look like when it becomes the bottleneck?

Insert threads show high lock wait, CPU idle or spinning on the same futex, and inserts-per-second that barely move as you add workers. Query latency may stay fine if searches do not take the write lock — until a writer holds the global lock for an entire construction search rather than only the edge-commit phase, at which point QPS tanks whenever an upsert runs. Holding the global lock across efConstruction search is a common footgun: the search is long and memory-bound, and serializing it defeats multi-core hardware. Even brief global commits serialize all writers through one convoy, which may be acceptable at low ingest rates and unacceptable for bulk rebuilds.

Hybrid designs keep a global lock (or atomics) only where the state is truly singular, and use finer locks elsewhere.

How should global-state locking coexist with per-node locking in HNSW?

Use atomics or a tiny critical section for next-ID and entry-point publication; use per-node locks for adjacency mutations; never take the global lock while already holding arbitrary node locks without a documented order (global-before-nodes or nodes-only is safer than mixed ad hoc orders). Prefer reader/writer global locks only if you truly need to freeze the whole graph for a rare compaction; otherwise prefer read-mostly protocols so queries never queue behind writers on a graph-wide mutex. When profiling points at one lock dominating ingest, migrating edge commits from global to per-node locking is usually the highest-leverage concurrency fix available without changing M or efConstruction.

Global-state locking guards the whole HNSW index with one lock — simple and correct, but a scalability ceiling for parallel writes unless reserved for true singleton metadata. From here, per-node locking is the finer alternative, parallel insertion and multithreaded construction are the workloads that outgrow a global write lock, atomics cover single-field global updates, and the chapter on concurrent HNSW construction and querying shows hybrid protocols in context.