graphshard lab

graph queries look local until the graph is split. a two-hop traversal that used to be a few hashmap lookups can suddenly require work from several shards, and the cost depends less on the query itself than on where the connected data ended up.

i built graphshard lab because i wanted to study that boundary as a system, not as a diagram. it is an in-process rust research prototype where i can change one design decision, replay the same deterministic workload, verify the result against an unsharded graph, and measure what changed.

the main question was simple: how should connected graph data be placed and queried when it no longer fits behind one local adjacency map?

starting with a graph small enough to understand

the base model is intentionally plain: users, directed follows edges, and one-hop or two-hop traversals. the reference graph stores everything together. the sharded version assigns each user to a logical shard and stores an edge with its source user, even when the target lives elsewhere.

user 12 on shard 0
  follows user 31 on shard 2
  follows user 44 on shard 0

query: everyone reachable from user 12 in two hops

this gives the project a correctness oracle. every optimization still has to return the same set of users as the unsharded graph. fewer messages do not matter if the answer changes.

placement is the first distributed query plan

the first experiments compared three ways to place users: hash placement, community placement, and balanced-community placement.

hash placement

hashing spreads users evenly and is easy to compute, but it ignores graph structure. two users that interact constantly are no more likely to share a shard than two unrelated users. balance is good; locality is mostly accidental.

community placement

community placement keeps densely connected users together. when the workload has real locality, this turns many remote traversals back into local reads. the cost is that community sizes are not guaranteed to be equal, so one shard can become much heavier than another.

balanced-community placement

balanced-community placement is the compromise: preserve as much locality as possible while preventing one community from dominating a shard. this made an important distinction visible:balance and locality are different objectives. optimizing one does not automatically optimize the other.

what the locality sweep showed

one main workload used 10,000 users, 10 communities, 8 outgoing edges per user, 4 shards, and a fixed seed. i changed how many of those eight edges remained inside the source user's community and measured logical cross-shard hops for two-hop queries.

the interesting result is not that community placement always wins. with zero local edges it was worse than hashing. placement only helps when its assumptions match the workload. under the strong-locality case, though, it reduced logical cross-shard hops by 86.19%.

batching changes communication without changing the query

a direct two-hop executor can issue one logical adjacency read for every first-hop user. if several of those users belong to the same shard, that creates repeated messages to the same destination.

direct
  shard 1 <- read user a
  shard 1 <- read user b
  shard 2 <- read user c

batched
  shard 1 <- read [user a, user b]
  shard 2 <- read [user c]

the batched executor groups adjacency reads by owning shard and dispatches one request per shard. the graph result remains identical; only the communication pattern changes. across the measured workloads, batching removed roughly 37.61% to 71.87% of logical shard requests.

turning logical shards into asynchronous workers

the first sharded implementation was still mostly a collection of data structures. i later made each shard a separate tokio task with its own local graph, a bounded request channel, and one-shot responses. a coordinator routes users, groups requests, and waits for independent shard work concurrently.

it is still one process, and transport delay is simulated, but that boundary was useful. once a query crosses an actual message channel, request count, queueing, concurrency, and tail latency stop being abstract counters.

skew and caching

even placement does not mean even traffic. i added a hub-heavy workload where 1% of users receive 25% of reads. in one measured run, those hubs were accessed about 33 times as often as a normal user.

that workload made shard-local adjacency caches meaningful. the project tracks cache hits and misses, supports multiple eviction policies, verifies invalidation after graph changes, and compares cold and warmed runs. the useful lesson was not simply that caching is faster. it was that cache value depends on skew, capacity, invalidation correctness, and where the hot data is placed.

what the project is actually for

graphshard lab is not a production graph database. the shard workers live inside one process, the workloads are synthetic, and the network is modeled rather than deployed across machines. that scope is intentional.

the project is a place to isolate systems questions that become hard to see inside a full database: when locality beats balance, when batching reduces real work, how hotspots distort an otherwise even layout, and why every benchmark needs a correctness check beside it.

the biggest thing i learned is that sharding is not just a storage decision. placement becomes part of query execution, communication becomes part of latency, and workload shape decides whether an optimization is useful at all.