Don't block The Rock

Build a graph database (Neo4j / Dgraph-style) (16 scenes)

Scene 9.5 · Don't block The Rock

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.

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 9.5

Don't block The Rock

Watch

Diagram

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.

Sources

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.

Implementation

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

Not sure what to ask? Tap a question — the staff engineer answers in the chat panel.

PreviousThe supernode breaks the promise NextACID on a single primary