hardDesignScenarioSeniorStaff
A graph of two billion edges will not fit on one machine and the algorithm needs neighbours. How do you partition it?
Check the premise first, because two billion edges as vertex id pairs is about 32GB and that fits in one large machine. If it genuinely must be distributed, partition edges rather than vertices, since real graphs are power-law and a single high-degree vertex under an edge cut makes its machine the straggler that every synchronous superstep waits for.
6 min readUpdated 2026-08-15
Answer
Short answer
Before distributing a two-billion-edge graph, calculate the raw size because edge pairs may fit on one large machine. If it must be distributed, partition edges and replicate vertices rather than assigning all edges of a high-degree vertex to one machine. Power-law hubs make vertex partitioning skewed, and in bulk-synchronous graph jobs the slowest partition controls every superstep.
Was this answer helpful?
Likely follow-ups
- One vertex holds 50 million of the two billion edges. What happens to a hash partitioner, and what do you do instead?
- Which of your algorithms can be answered on a sample, and how would you decide whether the sampled answer is usable?
- Locality-aware partitioning gives the best message reduction and needs a graph algorithm to compute. How do you break that circularity?
- What changes if the graph is being updated continuously rather than loaded once per job?
Related questions
- A transform has been writing wrong revenue figures for three days and six downstream tables have consumed it. How do you backfill the corrected data without double-counting anything?hardAlso on partitioning4 min
- Consumer lag on your orders topic climbs every morning and never clears before the next peak. Work through it.hardAlso on partitioning6 min
- Every message must survive the phone being wiped, and a user has 40,000 of them. Where do they live and how are they paged?hardAlso on partitioning6 min
- How do you choose a datastore, and then how do you choose its shard key?hardAlso on partitioning6 min