graph shard lab started with a simple question: what actually changes when a graph is split across multiple shards?
i did not want to build a full graph database. i wanted a small rust project where i could change the placement strategy, run the same queries, and see how much work crossed shard boundaries.
the problem
graphs are awkward to shard because the data is connected. placing users evenly across machines is easy, but their edges do not necessarily stay local. a two hop query can begin on one shard and quickly spread across several others.
that means a placement strategy can look balanced while still making every useful query expensive. the question is not only where each node lives, but how often a query has to leave that shard.
what i built
i built an in memory graph in rust with logical shard workers and a few placement strategies. hash placement spreads users evenly without caring about their relationships. community placement tries to keep strongly connected users together.
the lab runs one hop and two hop queries, counts cross shard work, and compares direct requests with batched execution. the shard workers use bounded tokio channels, but everything still runs inside one process and network delay is simulated.
the locality experiment
the main experiment used 10,000 users, 10 communities, 8 edges per user, and 4 shards. i gradually changed how many of each user's edges stayed inside their own community.
hash placement stayed almost unchanged because it ignores the graph's structure. community placement improved as the workload became more local. with seven of eight edges staying inside the community, it reduced cross shard hops by about 86 percent compared with hash placement.
when all eight edges stayed local, the community strategy could answer the tested queries without crossing a shard boundary at all. that is an intentionally clean synthetic case, but it made the relationship between graph structure and placement easy to see.
batching helped too
placement was not the only thing that mattered. a direct two hop query can send several separate requests to the same shard. batching those reads together reduced the number of logical shard requests, depending on the workload.
this did not change the graph result. it changed how much coordination was needed to produce it. that was a useful distinction for me: better placement reduces how often a query becomes distributed, while batching reduces the cost once it already has.
the part that surprised me
even placement is not the same as even load. in the hub heavy workload, a small group of users received a large share of the reads. roughly one percent of users received twenty five percent of the accesses, and the busiest users were read far more often than ordinary ones.
the nodes were still distributed across shards, but the traffic was not. that showed me why a system can have balanced storage and still develop a hot shard or hot key problem.
so what does this mean
graph shard lab is not a distributed graph database. the shards run inside one process, the data is stored in memory, and the workloads are synthetic.
what it gave me was a controlled way to see three different problems separately: where graph data is placed, how distributed queries are executed, and how skew changes the load even when storage looks balanced.
the main takeaway is simple: graph sharding is not only about dividing nodes evenly. the shape of the graph and the shape of the workload decide whether that division is actually useful.