Design LinkedIn-style connection degrees (1st, 2nd, 3rd)

Tell two members how far apart they are, in milliseconds, on a graph that does not fit in memory.

Problem 024 of 100Social and feedsL61 Nov 2026

Concepts this design leans on

Graph storage — Adjacency lists at scale and why hops get expensive.
Precompute or compute on the fly — Paying at write time or at read time, and how to tell which is cheaper.
Sharding and partitioning — Splitting data by key so each machine holds a slice it can handle.
Caching strategies — Read-through, write-through, write-back, TTLs and invalidation.
Batch versus streaming (MapReduce and friends) — Exact answers over everything at night, or approximate answers now.

01The design, in the six-step framework

1. Requirements

Functional

For a viewer and any other member, return their connection degree: 1st (directly connected), 2nd (share a connection), 3rd, or out of network.
Show the degree on every profile and in every search result and feed item, so the lookup is called in batches of tens.
Connections change constantly; a new connection should update degrees within seconds for the two members involved.
Out of scope: path display ("via Priya"), recommendations, groups.

Non-functional

1 billion members, 30 billion connections (average 60 per member, some with 30,000).
Batched degree lookups: 50 million a minute at peak, under 50 ms at p99 for a batch of 50 targets.
The graph does not fit in one machine's memory; the design must say what is precomputed and what is computed on the fly.
The interviewer rejected "use a graph database"; the traversal and its storage must be designed explicitly.

Back of the envelope

Adjacency: 3 × 10¹⁰ edges stored both ways = 6 × 10¹⁰ entries × 8 bytes ≈ 480 GB, plus structure ≈ 1 TB. It fits in memory across 20 to 40 machines, not one.

Second-degree size: 60 × 60 = 3,600 on average, but a member with 30,000 connections who are themselves well connected has millions; the 90th percentile is around 100,000. Materialising every member's 2nd-degree set is 10⁹ × 3,600 × 8 B ≈ 29 TB on average, far more in reality, and it changes constantly: do not precompute it.

Third degree is 60³ ≈ 216,000 on average and tens of millions for hubs: it can only be answered by intersection, never by enumeration.

2. Core entities

Member: id, connection count.
Adjacency list: member id → sorted array of connection ids (both directions, since connections are symmetric).
Viewer second-degree cache: viewer id → compact set (Bloom filter or sorted array) of 2nd-degree ids, with a build time.

3. API

POST /degrees body: viewer id, list of up to 100 target ids → degree per target (1, 2, 3, or none).
POST /connections, DELETE /connections → symmetric edge changes; emit an event.
Internal: graph.adjacency(ids[]) → batched adjacency lists from the in-memory graph tier.

4. High-level design

A batch lookup from a search page:

The degree service fetches the viewer's adjacency list (one call to the viewer's graph shard) and the targets' adjacency lists (batched calls to their shards). First degree is a membership test of each target in the viewer's list.
Second degree is a set intersection: does the target's adjacency list share any id with the viewer's? With sorted arrays this is a merge or, for a large list, a binary search of the smaller into the larger.
Third degree is answered using the viewer's second-degree set from the cache (built once per session and reused across pages): does the target's adjacency list intersect it?
Connection changes flow through an event stream to the graph shards (apply) and to the cache (invalidate the two members' entries).

5. Deep dives

What to precompute, what to compute per request

The interviewer's question is exactly this. The adjacency lists are precomputed and kept in memory, sorted, sharded by member id; they are the only structure. First degree is a lookup. Second degree per target is computed on the fly as an intersection of two sorted lists, which costs O(min(a, b) log max(a, b)) and for typical sizes (60 against 60) is microseconds. The viewer's full second-degree set is computed once and cached because a session asks about hundreds of targets; building it is the union of the viewer's connections' adjacency lists, 60 lists of 60 on average, done by fetching those lists in one batched call to the shards. For hub viewers (30,000 connections), the union is millions of ids: cap the build at a budget and store it as a Bloom filter of a few megabytes, accepting a tiny false-positive rate on "2nd" versus "3rd". Nothing is materialised for all members, because the arithmetic above shows it cannot be kept fresh or in memory.

Third degree without enumerating millions

Degree 3 means "the target is connected to someone in my second-degree set". With the viewer's second-degree set cached, the check is: for each id in the target's adjacency list, is it in the viewer's set? That is 60 probes of a hash set or Bloom filter per target, microseconds again. For a hub target with 30,000 connections, probe the smaller side instead: iterate the viewer's second-degree set and look up in the target's sorted list, or cap the work and return "3rd or more" when the budget is hit; the product shows "3rd+" for a reason. The symmetry of the relation lets the service always intersect the smaller set against the larger structure.

Memory and sharding of the graph tier

One terabyte of adjacency across 40 machines is 25 GB each, in RAM as sorted integer arrays with delta encoding (which halves it). Shard by member id hash; every lookup is a point read, and a batch of 50 targets touches up to 50 shards in parallel, which is fine at 50 ms. Replicate each shard three times for read capacity and availability; writes are rare relative to reads (a few thousand connection changes a second against millions of lookups) and are applied from the event stream in order per member. A shard restart rebuilds its lists from the connections database (a few minutes), so persistence in the graph tier is not needed.

Freshness: a new connection should show as 1st degree immediately

The connections database is the source of truth and is written synchronously; the graph shards apply the change within a second from the stream. The viewer cache is the stale part: the two members' second-degree sets are invalidated on the event, and a cheap patch (add the new connection's adjacency list to the set) can be applied instead of a rebuild. Other members' cached sets may be stale for up to their TTL (say 10 minutes), which affects only whether a stranger appears as 2nd or 3rd degree, a tolerable lag. The degree service also applies the viewer's own recent changes from a small per-session delta so the viewer always sees their own new connection as 1st.

The batch at 50 million lookups a minute

At peak the degree service handles about 800,000 batches a second, each with tens of targets. The viewer's adjacency list and second-degree set are fetched once per batch, so the per-target cost is the small intersection plus one batched adjacency read for the targets. The graph shards see roughly 40 million adjacency reads a second across 40 machines times 3 replicas, about 330,000 reads a second per replica, which is within reach of an in-memory service returning small arrays. Compressing the response (delta-encoded sorted ids) keeps the network under a few gigabits per shard. Say the numbers; they show the design is sized rather than assumed.

6. What a strong answer sounds like

Do the size arithmetic for the graph, for all second-degree sets, and for third degree; let it rule out materialisation and graph-database enumeration.
Name the single structure (sorted adjacency in RAM, sharded) and the three computations on top of it.
Introduce the per-viewer cached second-degree set and the Bloom-filter cap for hubs.
Explain freshness: truth in the database, shards from the stream, cache invalidation plus a session delta.
Expect follow-ups on showing the connecting path (a second lookup only when clicked), on blocked members, and on the cost of the batch at 50 million lookups a minute.
Common mistake: "a graph database with a 3-hop query", which the interviewer explicitly wants you to open up.

02Where this question was reported

Exponent · Detailed candidate report; interviewers pushed precomputation/caching over a graph-DB answer
Exponent / Aced · Low latency at very large scale; what to precompute if graph cannot fit in memory; do not rely on a graph-DB black box
Exponent / Aced · Recent candidate: interviewer rejected 'use a graph DB' and wanted precomputation, caching and the traversal built out.