What is a mutex?

A mutex, short for mutual exclusion lock, is a synchronization primitive that lets only one thread at a time enter a protected critical section — so concurrent updates to shared data do not interleave and leave that data half-modified.

How does a mutex actually enforce “only one thread at a time”?

Before a thread touches the protected state, it locks the mutex. If no other thread holds it, the lock succeeds and the thread proceeds through the critical section, then unlocks when finished. If another thread already holds the lock, the newcomer waits — spinning briefly, sleeping in the operating system, or some hybrid — until the holder unlocks. While the mutex is held, the holder’s sequence of reads and writes to the guarded structures appears atomic to other threads as a whole block, even though each individual instruction is not an atomic operation. That is the key distinction: atomics protect one memory word; a mutex protects an arbitrary region of code and as many memory locations as that code touches. The cost is serialization: every thread that needs the same mutex must take turns, so a hot lock becomes a throughput ceiling.

Concurrent HNSW uses mutexes wherever an update is bigger than a single word — especially neighbor-list rewrites during insertion.

Where do mutexes show up in concurrent HNSW construction and querying?

Inserting a node means searching for neighbors, then writing bidirectional edges into multiple nodes’ adjacency lists. Those list updates are multi-step: changing counts, writing IDs, sometimes reallocating storage. Two insertions that both connect to the same existing node would corrupt that node’s list if they interleaved freely, so implementations often take a per-node mutex before mutating that node’s edges, or a finer lock around the list structure itself. A single global mutex around the entire graph works correctly but destroys parallel insert scalability. On the query side, pure read-only search against a frozen graph may need no mutexes at all on the hot path — each thread uses private heaps and visited sets. When inserts and queries run together, writers still take mutexes (or upgrade to reader/writer locks) on nodes they mutate, while readers either lock shared for traversal or follow a protocol that publishes updates only after the writer releases. Production in-memory indexes such as Weaviate’s HNSW path depend on this kind of disciplined locking so CRUD against the graph stays safe under concurrent load.

How finely you carve the locks decides whether the mutex is a scalpel or a bottleneck.

Why does lock granularity matter so much for HNSW throughput?

One mutex for the whole index means every insert and every locked read queues behind every other — simple, and disastrous once many threads build or upsert. Per-node mutexes allow insertions that touch disjoint regions of the graph to proceed in parallel, which matches how HNSW edges fan out across many nodes. The trade-off is bookkeeping: more locks use more memory, acquiring several node locks for a bidirectional link risks deadlock unless a lock order is defined, and the hottest hub nodes still serialize traffic because every insertion wants their mutex. Intermediate designs lock shards of the ID space or use striped locks. Choosing granularity is therefore an empirical systems decision: measure insert throughput and lock wait time as thread count grows, and tighten or loosen protection until correctness holds without a single global convoy.

Mutexes also interact with the memory hierarchy — a heavily contended lock is not only a scheduling problem but a cache-line ping-pong problem.

What goes wrong when HNSW mutexes are contended or misused?

Under contention, threads spend their time waiting rather than computing distances, so CPU utilization looks high or oddly low while QPS stalls and latency percentiles spike. Holding a mutex across an entire neighbor search (not just the final edge splice) keeps the lock for far too long and amplifies contention. Forgetting to unlock on an error path deadlocks the graph for every later thread that needs that node. Locking nodes in inconsistent orders across insertion paths invites classic deadlock. Putting unrelated counters on the same cache line as a mutex flag can add false sharing on top of true lock contention. The usual hygiene is short critical sections, lock only what you mutate, prefer private per-query state over shared mutable state, and reserve mutexes for true multi-location updates while using atomics for single-word publication. When profiles show threads blocked on HNSW locks, the algorithm’s M and efConstruction are not the first knobs to turn — the locking protocol is.

A mutex gives one thread exclusive ownership of a critical section so shared HNSW structures can be updated without races. From here, the reader/writer lock page covers sharing read access among many searchers, lock ordering and deadlock explain multi-lock hazards, atomics cover single-word alternatives, contention names the performance failure mode, and the chapter on concurrent HNSW construction and querying puts these tools into a full design.