Don't block The Rock — relationship-chain locks and dense-node grouping for supernodes

Adding an edge to a celebrity used to take a lock on the entire node, so every concurrent writer serialized and throughput collapsed — until relationship-chain locks let writers lock only the part of the chain they touch, and dense-node grouping (≥50 relationships get a grouped layout by type/direction) made it scale.

Previously

Expanding through a supernode was a read disaster; writing to one was a concurrency disaster — a whole-node lock turned every concurrent edge-add into a queue. Relationship-chain locks and dense-node grouping let writers work on different parts of the chain in parallel. Locks, of course, only matter because the database promises something about correctness — and we haven't yet said what.

Scene 09a

Don't block The Rock

Watch
Try it
Predict
Capture

What to watch for

The Rock has tens of millions of followers. Right now, eight users tap 'Follow' in the same instant — each is one tiny write: add a FOLLOWS edge to The Rock's relationship chain. Watch the lock overlay. The first writer grabs a lock on the WHOLE node, and every other writer — even though it only wants to add its own separate edge — has to wait in line behind it. Eight independent edge-adds, executed strictly one at a time.

The same social graph.
The Rock (id 11) is the supernode — a fan of FOLLOWS edges, ×10M in the real world.
Several writers each want to add ONE new FOLLOWS edge to The Rock at the same time.
Watch the lock overlay on the supernode.
Relationship-chain lock — a writer locks only the segment of the relationship chain it is splicing into, not the whole node, so writers touching different segments don't block each other.
Dense-node grouping — once a node has ≥50 relationships it gets a 'dense' layout that buckets its edges by type and direction (a FOLLOWS-inbound group, a RATED-outbound group, …) and relaxes locking for groups of ≥10, so concurrent adders to the same group spread out instead of colliding.

Implementation

Highlighted lines are the ones running in the diagram right now.

Writer.addFollowsEdge

adding one FOLLOWS edge = splice a record into the chain — but you must hold a lock to do it safely

1def add_follows(writer, target):        # target = The Rock
2    new_rel = RelRecord(writer, target, FOLLOWS)
3    # to splice into the chain you must lock what you touch
4    lock = acquire(target, new_rel)     # ← the contended step
5    splice_into_chain(target, new_rel)  # re-point 2 pointers, O(1)
6    commit_and_release(lock)
7 
8# the splice itself is tiny; the WAIT for the lock is the cost.
9# 8 writers, each wanting its own edge, all call acquire() here.

Lock.acquire

the region a writer must lock decides who blocks whom

1def acquire(node, new_rel):
2    if not CHAIN_LOCKS:
3        # historical: the protected region is the WHOLE node
4        return lock_whole_node(node)        # 1 holder at a time
5    # chain locks: protect only the segment being spliced
6    segment = chain_segment_for(node, new_rel)
7    if DENSE_GROUPING and group_size(segment) >= 10:
8        segment = relax_to_group(segment)   # many adders share it
9    return lock_segment(segment)            # disjoint → no wait

Sources

Where this sits in Build a graph database (Neo4j / Dgraph-style)

Scene 09a of 16, in the It breaks act — The supernode shatters the O(1)-per-hop promise.. Concurrent edge-adds to a supernode historically serialized on a whole-node lock; relationship-chain locks plus dense-node grouping let writers touch different parts of the chain at once, turning a serialized hotspot into parallel throughput.

Up next. We just leaned on 'a lock' to make concurrent writes correct. But locks are one piece of a bigger promise: that a multi-step write either fully happens or doesn't, survives a crash, and is isolated from other writers. On a single machine a graph store can give you that fully — ACID — and it's worth seeing exactly how before we try to spread the graph across machines.

All 16 scenes in Build a graph database (Neo4j / Dgraph-style) · Every curriculum

Built with Arqly

Every scene in Build a graph database (Neo4j / Dgraph-style) builds on the one before it.All 16 Build a graph database (Neo4j / Dgraph-style) scenes