Edge-cut, vertex-cut, predicate sharding

On power-law graphs edge-cut (one vertex per machine) dumps a hub's edges onto one machine as a hotspot, so vertex-cut splits the high-degree vertex across machines to balance edges; predicate-sharding (Dgraph) sidesteps the choice by keeping every edge of one TYPE together so 'all of X's friends' stays local — but no cut has zero crossing edges.

Previously

Cutting is unavoidable; the question was which cut crosses fewest edges. Edge-cut hotspots on hubs; vertex-cut splits the hub to balance edges; predicate-sharding keeps each edge type together so common expands stay local. The supernode broke naive partitioning, just as it broke reads and writes. But all of this is about TRAVERSAL by edges — what about finding a start node by its VALUE across a distributed store?

Scene 11a

Edge-cut, vertex-cut, predicate sharding

Watch
Try it
Predict
Capture

What to watch for

Same social graph, but it no longer fits on one machine — we have to cut it across two. Watch the simplest cut first: give every PERSON to one machine and cut whatever edges span the two. Step 1, the cut line drops. Step 2, look what happens to The Rock — it's a hub, so when its vertex lands on machine 1, ALL of its edges land there too. One machine ends up carrying half the graph's edges: a hotspot.

The same social graph, now split across two machines with a cut line down the middle.
EDGE-CUT assigns each vertex to one machine and cuts the edges that span machines — so The Rock and all its edges land on machine 1 as a red hotspot.
VERTEX-CUT assigns each EDGE to a machine and slices a high-degree vertex into mirrors across machines, balancing edges instead of vertices.
PREDICATE SHARDING keeps all edges of one TYPE on one machine (all :FRIEND together, all :FOLLOWS together) so a 'give me all of X's friends' expand reads exactly one machine.
Crossing edges render as dashed RPC hops with a latency stamp — a cut hop is a network round trip, not a pointer follow.

Implementation

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

Partitioner.place

where does each vertex / edge live? (the slider picks the branch)

1def place(graph, mode, M):              # M machines
2    if mode == 'edge-cut':
3        for v in graph.vertices:        # vertex → one machine
4            home[v] = hash(v) % M       # a hub's edges all follow v
5    elif mode == 'vertex-cut':
6        for e in graph.edges:           # edge → one machine
7            home[e] = hash(e) % M       # split hubs: mirror across M
8    elif mode == 'predicate':
9        for e in graph.edges:           # edge TYPE → one shard
10            home[e] = shard_of[e.type]  # all of one type together
11    return home

Query.expand_friends

'all of X's friends' — how many machines does it touch?

1def expand_friends(X, mode):
2    if mode == 'predicate':
3        return read(shard_of['FRIEND'])  # ONE machine, local
4    # otherwise X's :FRIEND edges may live on several machines
5    machines = {home[e] for e in edges(X, 'FRIEND')}
6    return rpc_fanout(machines)          # cross-cut network hops

StreamingPartitioner.assign

no cut crosses zero edges — min-cut is NP-hard, so we greedily place and accept some crossings

1def assign(graph, M):                    # one pass, heuristic
2    for v in stream(graph.vertices):
3        # score each machine: keep neighbors together, stay balanced
4        best = argmax(m in machines,
5                      neighbors_on(v, m) - lambda * load[m])
6        home[v] = best                       # greedy, not optimal
7        load[best] += 1
8    # whatever's left spanning machines is the unavoidable cut:
9    crossings = count(e for e in edges
10                      if home[e.from] != home[e.to])
11    return home, crossings                   # crossings > 0 always

Sources

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

Scene 11a of 16, in the Scale & ACID act — ACID on one box; the partition cut turns hops to RPCs.. Edge-cut assigns each vertex to a machine and chokes on power-law hubs; vertex-cut splits the hub across machines to balance edges; predicate-sharding keeps all edges of one TYPE together so a common expand stays on one machine.

Up next. Sharding decided where edges live, but every query still has to find its ANCHOR — by name, by text, by range. That SEEK was never part of adjacency (scene 5), and it isn't part of sharding either. In distributed graph stores, finding start nodes by value is served by classic indexes — full-text, B-tree, vector — bolted on the side, not woven into the native pointer-chase.

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