Social graph sharding
Your task
Design the storage and sharding for a social graph database backing a 'people you may know' / friends-of-friends feature, with 1 billion users averaging 300 connections (some celebrities have 50M), serving 80k graph traversals/sec that walk 2–3 hops. How do you store the adjacency data, shard the graph, and keep 2-hop traversals fast despite supernodes that span many shards?
It covers
- Adjacency partitioning
- Edge cut
- Supernode