What is per-node locking?

Per-node locking gives each HNSW node (or its neighbor list) its own lock so concurrent insertions only block when they mutate the same node, allowing disjoint edge updates to proceed in parallel — unlike one global lock over the whole graph.
Created: Updated: 4 min read

Per-node locking is a concurrency design in which each HNSW graph node (or its neighbor-list storage) has its own mutex or reader/writer lock, so threads only serialize when they mutate or — depending on the protocol — read the same node’s adjacency data, while work on disjoint nodes proceeds in parallel.

How does per-node locking differ from locking the entire graph?

A global graph lock makes every insert or locked read take turns behind one mutex: correct, simple, and a throughput ceiling as soon as multiple threads build or upsert. Per-node locking shrinks the critical section to one node’s neighbor list (and related fields). Two insertions that connect into different regions of the graph can hold different locks and commit edges at the same time. Contention concentrates on hot hubs that many insertions touch — an inherent skew in proximity graphs — but the average case scales far better than a single lock. The cost is bookkeeping: N locks (or a striped subset), careful acquisition when one operation needs several nodes, and more opportunities for deadlock if order is ignored.

Bidirectional HNSW edges are exactly why one insertion often needs more than one node lock.

When does an HNSW insert take multiple per-node locks?

Writing a link between the new node and a neighbor updates both adjacency lists, so both endpoints must be protected for the commit. Linking to M neighbors can mean locking the new node plus each neighbor, or locking pairs sequentially if the protocol commits one edge at a time. Deletes and repair jobs similarly touch both ends of an edge. The safe pattern is to collect the set of node IDs that will be mutated, sort them (lock ordering), acquire in that sequence, splice all edges, then release. Searching for candidates under efConstruction usually does not need exclusive locks on every visited node if the implementation allows optimistic reads; holding exclusive locks for the whole search would destroy parallelism. Production concurrent HNSW paths, including those used in systems like Weaviate under upsert load, aim to keep exclusive sections short and local to the nodes being rewired.

Readers complicate the picture: exclusive-only per-node mutexes can block searches that only need to scan a list.

How do reader/writer per-node locks fit query-heavy HNSW workloads?

If searches take a shared lock on each node they inspect, many queries can proceed together, but lock acquire costs accumulate over hundreds of hops and can dominate. Many designs therefore avoid read locks on the hot path: writers take exclusive per-node locks only at commit, and readers rely on publish protocols, versioning, or quiescent epochs so they never see torn lists. Per-node exclusive locks then protect writers from each other and from any reader still using a pre-upgrade coordination mode. Choosing between “shared lock every hop” and “lock-free read, locked write” is a major fork; both can be correct, but only the latter usually hits high QPS under mixed load.

Hub nodes remain the scaling Achilles’ heel of fine-grained locking.

High-degree or frequently chosen neighbors become lock convoys: many inserters queue on the same node’s mutex even though the rest of the graph is idle. Symptoms match contention — rising insert latency, flat thread scaling — not deadlock, unless lock order bugs appear. Mitigations include shorter critical sections (build the new neighbor vector privately, then lock briefly to install), striping, or accepting that some hubs serialize. Padding lock words to avoid false sharing with adjacent node metadata keeps coherence traffic from amplifying the wait. Per-node locking is still usually the right default for parallel insertion; global locking is the fallback when simplicity matters more than ingest QPS.

Per-node locking serializes only threads that touch the same HNSW node’s edges, enabling parallel inserts elsewhere at the cost of multi-lock discipline and hub contention. From here, global-state locking is the coarse alternative, lock ordering and deadlock cover multi-lock hazards, parallel insertion and multithreaded construction are the workloads that need it, and the chapter on concurrent HNSW construction and querying shows full commit protocols.