What is lock ordering?
Lock ordering is a concurrency discipline that requires every thread to acquire multiple locks in the same global sequence — for example always lower node ID before higher — so two threads can never each hold a lock the other is waiting for and stall forever.
Why does acquiring the same locks in different orders cause trouble?
Suppose thread A locks node X then tries to lock node Y, while thread B locks Y then tries to lock X. Each holds what the other needs next. Neither can proceed, unlock, or make progress: that circular wait is a deadlock. The individual critical sections may be correct in isolation; the bug is in the relative order of acquisition across threads. Lock ordering prevents that cycle by imposing one agreed total order on the lockable objects. If every path that needs both X and Y always locks the earlier one in that order first, the situation above cannot arise: the second thread will block on the first lock before taking the second, rather than holding the second while waiting for the first. The rule is simple to state and easy to violate when different code paths — insert, delete, repair, background compaction — each “naturally” lock in the order they discover nodes.
HNSW insertion is exactly the kind of algorithm that wants two or more node locks at once, which is why ordering shows up as soon as per-node mutexes replace one global lock.
Where does lock ordering matter inside concurrent HNSW?
Adding a bidirectional edge means mutating the new node’s neighbor list and the neighbor’s list — two nodes, two locks if you protect lists per node. A single insertion may connect to M neighbors and thus touch many endpoints. Without a rule, one insert might lock the new node then neighbor 7, while another locks neighbor 7 then tries to lock a node the first thread still holds, and a third path might lock in discovery order during a reverse-edge update. Deletes, graph repair, and tombstone reclaim add more multi-node critical sections. Reader/writer locks obey the same ordering rule when a thread upgrades or holds exclusive locks on several nodes. Systems that accept concurrent upserts against a live HNSW graph, including deployments like Weaviate, need this discipline (or an equivalent avoidance strategy) so rare timing windows under load do not freeze ingest threads while queries appear healthy on already-held read paths.
The usual HNSW-friendly order is by stable node identifier, but the important part is consistency, not which direction you pick.
How do you pick and enforce an order for HNSW node locks?
Node IDs assigned at allocation are a natural total order: before mutating an edge between a and b, lock min(a,b) then max(a,b), regardless of which endpoint the algorithm “thought of” first. When more than two nodes must be held, sort the ID set and acquire in sorted order, then perform the rewiring. Avoid locking while traversing in greedy-search order — that order is data-dependent and will not match another thread’s sequence. Prefer collecting the set of nodes you will mutate after the search phase, sorting, locking, committing edges, then unlocking. Document the rule next to the lock helpers so future features do not invent a second convention. Static checkers and debug-mode assertions that verify ascending acquire order catch mistakes long before production deadlock.
Ordering is not the only way to stay safe, and sometimes restructuring the critical section is cleaner than holding many locks.
What alternatives reduce how often HNSW needs multi-lock ordering?
Some designs lock only one node at a time and publish the other side of an edge through a retry-friendly protocol, accepting brief asymmetry until the second half lands. Others build the new neighbor list in private memory and swing a pointer with a single atomic publish, shrinking the exclusive window to one structure. A global or sharded lock avoids ordering among nodes at the cost of throughput. Fine-grained per-node locks with a documented ID order remain the common middle path: good parallelism when insertions touch disjoint regions, predictable deadlock avoidance when they overlap. Whatever you choose, treat lock ordering as part of the HNSW concurrency contract — as binding as the neighbor-selection heuristic — not as an afterthought when the first deadlock appears under an overnight soak test.
Lock ordering is the shared acquire sequence that keeps multi-lock HNSW updates free of circular waits. From here, the deadlock page names the failure mode this rule prevents, mutexes and reader/writer locks are the primitives being ordered, contention covers the performance side of locking, and the chapter on concurrent HNSW construction and querying shows how insertion paths collect, sort, and commit under that discipline.