HLDintermediatePremium

LinkedIn HLD: Degrees of Separation on a Billion-Edge Graph

A LinkedIn system design: the connection graph, degrees of separation via BFS, People You May Know ranked by mutual connections, why deep traversal is precomputed, and scaling the graph.

By fiveyearsdevJune 14, 202614 min read

"Design LinkedIn." Profiles and a feed are the visible surface, but the thing that makes it a network is the connection graph — and one number decides the whole design. You have ~500 connections; each of them has ~500; each of theirs has ~500. So the ring one hop out is ~500 people, two hops is ~250,000, three hops is ~125 million. Every LinkedIn question — the 1st / 2nd / 3rd-degree badge on a profile, People You May Know, "who can introduce me" — is a walk across those exploding rings. The engineering isn’t the walk; a graph traversal is a first-week algorithm. It’s stopping the walk before …

What’s inside

Let’s start nowhere near a computer

Where this exact shape shows up

Step 1 — Functional requirements (sentences first)

Step 2 — Non-functional requirements

Step 3 — Nouns and the data model

Step 4 — The graph and degrees of separation

Step 5 — Bidirectional BFS: searching from both ends

Step 6 — People You May Know

Step 7 — Trade-offs (each one keeping an NFR)

The complete implementation

Step 8 — Only now, the boxes

Step 9 — Scaling the design, one bottleneck at a time

Step 10 — When a piece fails: designing for failure

The interview corner

Where to go from here

Read this one free

HLD