Design LinkedIn MutualConnection Search

Given two members A and B, return how many first-degree connections they share and, on request, who those people are, ordered so the most relevant ones come first. The same answer is needed in several places, each with its own shape of traffic.

Assume 900 million members with a heavily skewed degree distribution: a median of about 60 connections, a mean near 100, and a long tail capped by the product at 30,000. Edges are undirected, so each one is stored twice.

The source of truth for connections is an ordinary sharded database owned by the connections service, which handles invitations, acceptance and removal. It is never queried for intersections. Its change log feeds a graph serving tier: a fleet of in-memory shards, each holding the full adjacency lists for a slice of members, partitioned by a hash of member ID and replicated three times.

The mutual service is the only entry point for reads. For a batch, it first fetches the viewer's own list, from cache or from the viewer's shard, then groups targets by the shard that owns them and sends one request per shard carrying the viewer's list and the targets on that shard. Each shard intersects locally against its own lists and returns counts. The service merges the replies and applies privacy filtering for any preview faces.

This is the key layout choice: ship the smaller side, the viewer's list, to where the many target lists already live. Shipping 25 target lists to one place would move far more bytes.

When the lists are similar in size, a linear merge is hard to beat: two pointers, advance the smaller value, count matches. It reads both lists once in order, which suits CPU caches and can be vectorised with SIMD to compare several values per instruction.

When one list is far larger, merging wastes time stepping through entries that cannot match. Instead, take each element of the small list and search for it in the large one. Plain binary search costs log of the large size per element. Galloping search is better: because both lists are sorted, each search starts where the last one ended and doubles its step until it overshoots, then binary searches inside that window. The cost grows with the small list times the log of the gap between matches.

A simple rule works well in practice: if the larger list is more than about 30 times the smaller, gallop; otherwise merge. For the rare pair where both sides are huge, say two recruiters with 25,000 connections each, use a bitmap representation of the larger list (compressed bitmaps such as Roaring) and test membership in constant time.

Sorted, delta-encoded arrays are perfect for reading and awkward for writing, because inserting one ID in the middle means re-encoding the block it lands in. The fix is the same one log-structured stores use. Each member's list is split into blocks of about 128 IDs, each block encoded on its own, so an insert rewrites one small block rather than the whole list. Very recent changes go first into a tiny delta buffer per member: a sorted set of additions and a set of removals. Intersections read the main blocks and the buffer together, and a background task folds the buffer into the blocks once it passes a few dozen entries.

Removals deserve care. If a removal arrives before the matching addition, because events were replayed out of order, a naive shard would resurrect the edge. Each edge event carries a version from the source database, and the shard keeps the latest version per pair long enough to ignore anything older.

On a typical search page, many results are strangers with no shared connections at all. Each shard keeps a Bloom filter per member over that member's connection IDs. Before intersecting, probe the target's filter with a handful of the viewer's entries, or for a short viewer list, all of them. If every probe says "definitely not present", the count is zero and the shard skips the intersection. A Bloom filter never gives a false negative, so a "no" is always correct; a "maybe" falls through to the real intersection.

Sizing is a trade between memory and how often the shortcut works. At about 10 bits per entry with seven hash functions, the false positive rate is under 1 percent. For 90 billion entries that is roughly 110 GB across the fleet, so it is worth applying only to members above a minimum degree, where intersections are expensive enough to justify it.

Recruiters and public figures with tens of thousands of connections show up in many searches. Three measures keep them from hurting tail latency. Cap reported counts at 1,000, so intersections can stop early once they pass the cap. Store their lists as bitmaps as well as arrays, so membership tests are constant time. And spread their shards' load by placing extra replicas of their lists, since the hottest members are known in advance.

A count is cheap, but the list view needs order. Once the intersection is computed (and it is materialised only for this endpoint, not for counts), score each shared member by the viewer's interaction signals with them: recent messages, profile views, same company. Those signals come from a feature store keyed by viewer, fetched once per request. Then filter out anyone whose privacy setting hides their connections and return the top page.