LinkedIn looks like Twitter with a suit on. It has a feed, it has profiles, people follow each other. So candidates walk in ready to reuse the Twitter fan-out answer and get about four minutes in before the interviewer asks the question that breaks it: “This person is a 2nd-degree connection. How did you compute that?” Now you are not designing a feed. You are designing a graph query engine that answers “are these two of my billion users within three hops of each other” in under 100ms, on a graph with 500 billion edges.
That is the split that defines LinkedIn. Twitter’s edge is a directed follow - cheap, one-directional, and the whole product is a feed on top of it. LinkedIn’s edge is a symmetric connection that both parties accepted, and the product is built on distance in that graph: 1st degree (direct), 2nd degree (friend of a friend), 3rd degree (three hops). Every surface - who can message you, “people you may know,” search result ranking, the “2nd” badge next to a name - is a graph-distance query. The feed is real and I will design it, but the hard, LinkedIn-specific part is the graph. Let me do it properly.
Functional Requirements (FR)
In scope:
- Connections. A user sends a connection request; the target accepts or ignores. An accepted connection is a symmetric (undirected) edge - if A is connected to B, B is connected to A. This is the core object.
- Degree queries. Given the viewing user and any other user, compute the degree of separation (1st / 2nd / 3rd / “out of network”). This badge appears on every profile, search result, and feed item, so it must be cheap and ubiquitous.
- People You May Know (PYMK). Suggest people the user is likely to connect with - overwhelmingly 2nd-degree connections (friends of friends) ranked by number of shared connections and other signals.
- Feed. A home feed of posts from a user’s connections and followed companies/influencers, ranked (not pure chronological).
- Company pages. A company has a page, followers, employees (derived from profiles that list it), and posts. Following a company injects its posts into your feed.
- Search. Search people by structured attributes - job title, company, skill, location - with results ranked partly by the searcher’s network distance to each result.
Explicitly out of scope (say it so you own the scope):
- Messaging/InMail, notifications delivery, and the real-time presence system. Each is its own design.
- Jobs marketplace, recruiter product, ads auction, and the learning platform.
- Media storage/transcoding. Posts carry a media URL to a separate blob/CDN system.
- Endorsements, recommendations, and the full profile-editing surface beyond what search needs.
The one decision that drives everything: this system is dominated by graph-distance reads, not by content writes. Feed writes and post fan-out are a solved problem (it is Twitter, and I will reuse that). The novel, expensive, LinkedIn-specific cost is answering “what is the network distance between these two people” billions of times a day on a graph too large to traverse live. That asymmetry is the whole problem.
Non-Functional Requirements (NFR)
- Scale: ~1B total members, ~300M monthly active, ~150M daily active. Average ~500 connections/user, so the connection graph has roughly
1B * 500 / 2 ≈ 250B undirected edges(500B directed adjacency entries). Heavy tail: some users (influencers, open networkers) have 30K+ connections, and LinkedIn caps 1st-degree connections at 30K. - Latency: degree badge and PYMK panel must render inside the profile/search page budget - degree lookup p99 under 100ms, ideally served from a precomputed structure. Feed read p99 under 300ms. Search p99 under 500ms. Sending a connection request can be slower (async acceptance flow).
- Availability: 99.9%+ on read paths (feed, search, profile view). A profile that loads without the “2nd degree” badge is degraded but acceptable; a profile that will not load at all is not.
- Consistency: eventual almost everywhere. A newly accepted connection updating your 2nd-degree set a few minutes late is fine. The one place we want read-your-writes is the acceptance itself - once B accepts A, both should see “1st” quickly.
- Durability: connections and profiles must never be lost - they are the graph and the resume. Feed materializations and PYMK suggestions are derived and rebuildable.
- Freshness: posts should reach connections’ feeds within seconds. Degree data and PYMK can be minutes-to-hours stale; nobody notices that a friend-of-a-friend suggestion is an hour old.
Back-of-the-Envelope Estimation (BoE)
Real numbers with the arithmetic, because the graph size dictates the architecture.
The graph:
1B members * 500 avg connections = 500B directed adjacency entries
Undirected edges = 500B / 2 = 250B edges
Adjacency storage (from_id 8B + to_id 8B) = 500B * 16 bytes = 8 TB raw
With replication (x3) and indexing overhead: ~30-40 TB
8TB of raw edges is small enough to shard across a cluster but far too large to hold one user’s full 2nd/3rd-degree neighborhood in memory naively (see the PYMK explosion below).
Connection writes:
Assume each active user makes ~2 new connections/week.
300M MAU * 2 / 7 days ≈ 85M connections/day
= 85M / 86,400 ≈ 1,000 connection-accepts/sec average
Peak (3x) ≈ 3,000/sec
Each accept is a symmetric write (two adjacency rows) plus derived-data invalidation. Tiny volume. Connections are rare.
Degree/badge reads (the killer read):
Every profile view, every search result row, every feed item shows a degree badge.
150M DAU, each viewing profiles + scrolling feed + searching.
Assume ~40 badge lookups/user/day (profiles opened, search rows, feed authors).
150M * 40 = 6B degree lookups/day
= 6B / 86,400 ≈ 70,000 degree lookups/sec average
Peak (3x) ≈ 200,000/sec
200K degree queries/sec, each of which naively means a breadth-first search across an 8TB graph. That is the number that forces a precomputed design. You cannot BFS the live graph 200,000 times a second.
The 2nd-degree explosion (why BFS is hopeless live):
1st degree: ~500 people
2nd degree: each of my 500 connections has ~500 -> up to 500 * 500 = 250,000
(minus overlap; realistically 20K-100K distinct 2nd-degree people)
3rd degree: 500^3 = 125,000,000 in the worst case
A single user’s 3rd-degree neighborhood can be a hundred million people. This is why “are we within 3 hops” cannot be answered by expanding the full neighborhood - you expand from both ends and check for intersection instead (deep dive).
Feed:
Assume ~1M posts/day authored (LinkedIn is far less write-heavy than Twitter).
1M / 86,400 ≈ 12 posts/sec average, peak ~35/sec.
Fan-out: avg 500 connections + company followers.
12 * 500 ≈ 6,000 feed-inserts/sec average. Trivial versus Twitter.
Feed reads: 150M DAU * ~5 feed loads = 750M/day ≈ 8,700/sec, peak ~26K/sec.
The feed is an order of magnitude smaller than Twitter’s. It is not the hard part here.
Post/content storage:
1M posts/day * ~1KB (text + metadata, media external) ≈ 1 GB/day ≈ 365 GB/year.
Profiles: 1B * ~5KB structured (titles, companies, skills, education) ≈ 5 TB.
Modest. The graph dwarfs the content. This is the inversion from Twitter, where content storage dominated.
Precomputed 2nd-degree cache:
Store each active user's DISTINCT 2nd-degree set as a compact structure for PYMK + degree.
~50K entries/user * 8 bytes = 400 KB/user (naive). For 150M DAU = 60 TB. Too big to keep raw.
Fix (deep dive): store a Bloom/compressed sketch (~10-50 KB/user) instead -> ~1.5-7 TB. Tractable.
High-Level Design (HLD)
Three subsystems with very different cost profiles: the Graph subsystem (the hard part - connections, degree, PYMK), the Feed subsystem (Twitter-lite fan-out), and the Search subsystem (structured search over profiles, distance-aware). They share the profile store and are stitched together at read time.
┌──────────────────────────┐
│ Clients │
│ (mobile, web, API) │
└────────────┬─────────────┘
│
┌────────────▼─────────────┐
│ API Gateway / LB │
└───┬──────────┬────────┬───┘
│ │ │
GRAPH path │ FEED │ SEARCH│ path
┌───────────────────▼──┐ ┌────▼─────┐ ┌▼──────────────────┐
│ Graph Service │ │ Feed │ │ Search Service │
│ (connect, degree, │ │ Service │ │ (title/company/ │
│ PYMK) │ │ │ │ skill query) │
└───┬───────────┬───────┘ └────┬─────┘ └───┬────────────────┘
│ │ │ │
symmetric │ │ degree / │ fan-out │ query
edge write│ │ PYMK cache │ + read │
┌─────▼──────┐ ┌──▼───────────┐ ┌─▼──────────┐ ┌▼───────────────┐
│ Graph Store │ │ 2nd-Degree │ │ Feed Cache │ │ Search Index │
│ (sharded │ │ Sketch Cache │ │ (Redis: │ │ (Elasticsearch: │
│ adjacency, │ │ (Redis/RocksDB│ │ user -> │ │ profiles by │
│ by user_id)│ │ per user) │ │ [post_id]) │ │ attribute) │
└─────┬──────┘ └──────┬────────┘ └─────┬──────┘ └────────┬───────┘
│ │ │ │
│ CDC stream │ rebuild │ post fan-out │ index updates
┌────▼───────────────▼────────────────▼─────────────────▼────────┐
│ Kafka (connection events, post events, profile CDC) │
└────┬──────────────────────┬───────────────────────┬─────────────┘
│ │ │
┌───────▼────────┐ ┌────────▼─────────┐ ┌────────▼──────────┐
│ PYMK / Degree │ │ Feed Fan-out │ │ Profile Store │
│ Batch Builders │ │ Workers │ │ (source of truth │
│ (Spark/graph │ │ (push post_id │ │ for members, │
│ batch jobs) │ │ to feeds) │ │ companies) │
└─────────────────┘ └──────────────────┘ └────────────────────┘
Connection flow (write):
- A sends
POST /connections {target: B}. Graph Service writes a pending request row and notifies B. - B accepts. Graph Service writes the symmetric edge: two directed adjacency rows
(A -> B)and(B -> A), in one transaction on the graph store. This is the only place we need atomicity - both rows or neither. - A connection event is published to Kafka. This invalidates A’s and B’s 2nd-degree sketches and feeds the PYMK/degree batch builders. The actual sketch rebuild is async - a few minutes of staleness is fine.
Degree query flow (the hot read):
- Client renders a profile/search row for user X while logged in as user U. It needs the U-to-X degree badge.
- Degree Service checks: is X in U’s 1st-degree adjacency list? -> 1st. Is X in U’s precomputed 2nd-degree sketch? -> 2nd. Otherwise run a bidirectional bounded BFS to check for a 3rd-degree path; if none within 3 hops -> “out of network.”
- The 1st/2nd checks are O(1) cache hits and cover the overwhelming majority of rendered badges. Only the rarer 3rd-degree / out-of-network case pays for a bounded traversal.
Feed flow (read): identical shape to Twitter - read the precomputed user -> [post_id] list from Feed Cache, hydrate post bodies, rank, return. Company posts and influencers (the high-follower tail) are merged at read time; normal connections are fanned out on write. I lean on the Twitter design here and spend the deep dive on the graph.
Component Deep Dive
The hard parts, naive-first then evolved: (1) storing the symmetric connection graph, (2) degree-of-separation queries at 200K QPS, (3) People You May Know, (4) distance-aware search. The feed reuses fan-out and I keep it short.
1. The connection graph store
Naive approach: a graph database holding everything
“It’s a graph, use a graph database (Neo4j).” Model members as nodes, connections as edges, and let the graph engine answer degree queries with native traversal.
Where it breaks: a single-instance native graph database does not hold 250B edges, and graph databases are notoriously hard to shard because traversals cross partition boundaries - a 2nd-degree query starting on shard 1 fetches neighbors living on shards 2 through N, turning one query into a scatter of network hops. At 200K degree QPS, cross-shard traversal latency is uncontrollable. Native graph engines shine for deep, complex traversals on graphs that fit a box; they do not shine as a billion-user sharded OLTP store.
Evolved approach: sharded adjacency lists in a wide-column store
Store the graph as adjacency lists in a horizontally sharded key-value / wide-column store (think LinkedIn’s own Espresso, or Cassandra/DynamoDB). The edge is symmetric, so we store it in both directions:
Table: connections
user_id BIGINT PARTITION KEY
peer_id BIGINT CLUSTERING KEY
created_at TIMESTAMP
status ENUM(connected) -- pending lives in a separate table
"who is U connected to" -> connections[U] = single-partition scan, U's 1st degree
Shard by: user_id
Writing a connection A-B inserts (A, B) and (B, A). Reading A’s 1st-degree list is a single-partition scan - fast, and it lands entirely on one shard. This is the key win over a native graph DB: the 1st-degree lookup, which is the building block of every degree query, is a single-partition read. We give up cheap deep traversal (which we will not do live anyway) in exchange for a horizontally scalable, single-partition adjacency read.
Because we store both directions, the write cost of a connection is two rows in one transaction. Connections are ~3K/sec at peak, so double writes are free. The 30K connection cap bounds any single adjacency list, so no partition is unboundedly large - the heaviest open-networker still fits comfortably in one partition read.
The graph store also emits a change-data-capture (CDC) stream to Kafka on every edge write. Everything derived - 2nd-degree sketches, PYMK candidates, search-index distance features - subscribes to this stream and updates asynchronously. The source-of-truth graph is small and transactional; the expensive derived structures are eventually consistent off the CDC stream.
2. Degree-of-separation queries (the core problem)
Every profile and search row shows a “1st / 2nd / 3rd” badge, at 200K QPS. This is the query that makes LinkedIn LinkedIn.
Naive approach: BFS on read
For each (U, X) badge, run a breadth-first search from U outward until you reach X or exhaust 3 hops.
Where it breaks, brutally:
- U’s 2nd-degree neighborhood is 20K-100K people; the 3rd-degree is up to ~125M. A single BFS to 3 hops can touch tens of millions of nodes across every shard in the cluster.
- You do this 200,000 times per second. Each query is a multi-shard scatter-gather with unbounded fan-out. p99 would be seconds, not 100ms, and the cluster would collapse under its own traversal traffic.
Live full-neighborhood BFS is a non-starter. Two independent ideas fix it: bidirectional search (for the rare deep check) and precomputed 2nd-degree sets (for the common case).
Fix part A: bidirectional BFS for the 3rd-degree check
To check whether U and X are within 3 hops, do not expand U’s entire 3rd-degree set. Expand from both ends toward the middle and look for an intersection:
degree(U, X, max=3):
if X in adj(U): return 1 # direct edge
frontier_U = adj(U) # ~500 people (U's 1st degree)
frontier_X = adj(X) # ~500 people (X's 1st degree)
if frontier_U ∩ frontier_X: return 2 # shared connection
# expand one more hop from the SMALLER frontier only
twoU = neighbors_of(frontier_U) # U's 2nd degree
if X in twoU or (twoU ∩ frontier_X): return 3
return "out of network"
Why bidirectional wins: a one-directional 3-hop expansion touches ~500^3 ≈ 125M nodes. Meeting in the middle means each side expands at most ~1.5 hops, so you compare a ~500-set against a ~250K-set - a set intersection over hundreds of thousands of entries, not a traversal over a hundred million. That is the classic square-root reduction: O(b^{d/2}) instead of O(b^d). It turns an impossible query into a bounded one.
But even bidirectional BFS is too expensive to run 200K times/sec. So we only reach it for the rare 3rd-degree/out-of-network case. The common cases (1st and 2nd, which are the vast majority of rendered badges, since you mostly view people near you) are served from a precomputed structure.
Fix part B: precomputed 2nd-degree sets
The 1st-degree check is already O(1) - it is a single-partition adjacency read (and for active users, that list is cached). The 2nd-degree check is the one worth precomputing, because it is the most common “interesting” badge and because PYMK needs the same data.
Naive precompute: for each user, materialize the explicit set of all distinct 2nd-degree user IDs. At ~50K IDs * 8 bytes = 400KB/user, times 150M DAU = 60TB. Too big, and it churns on every connection change.
Evolved: store a compact membership sketch, not the explicit set. For each active user, maintain a Bloom filter (or a compressed roaring bitmap) over their 2nd-degree member IDs:
2nd-degree sketch for user U:
bloom_filter( { all distinct IDs reachable in exactly 2 hops from U } )
sized for ~50K-100K members at 1% false-positive rate -> ~10-50 KB/user
150M DAU * ~30 KB ≈ 4.5 TB (fits a sharded Redis/RocksDB tier)
Degree check becomes:
degree(U, X):
if X in adj(U): return 1 # single-partition adjacency read
if bloom_U.contains(X): return 2 # ~1% false positives, verified below
# not 1st or 2nd -> rare path: bidirectional BFS for 3rd / out-of-network
return bidirectional_bfs(U, X, max=3)
The Bloom filter’s false positives are acceptable because a “2nd” badge is a soft signal, and for the small number of surfaces that must be exact (e.g. messaging permission), we verify a positive with one real 2nd-degree confirmation: intersect adj(X) with adj(U) (both single-partition reads, ~500 entries each) to confirm a shared connection actually exists. A false positive costs one cheap verification, not a wrong permission.
The sketches are rebuilt asynchronously off the connection CDC stream by batch/graph builders (Spark or a dedicated graph-processing job). A few minutes of staleness after a new connection is invisible to users. This is the whole trick: move the expensive neighborhood computation off the read path into an async batch that produces a tiny O(1)-queryable sketch.
| Approach | Read cost | Storage | Breaks on | Verdict |
|---|---|---|---|---|
| Live BFS on read | O(b^3) multi-shard scatter | none | 200K QPS, deep fan-out | Impossible |
| Bidirectional BFS | O(b^1.5) set intersection | none | still too heavy for every read | Use only for rare 3rd-degree |
| Explicit 2nd-degree set | O(1) lookup | 60 TB, churns | storage + rebuild cost | Too big |
| Bloom sketch + adjacency | O(1) with rare verify | ~4.5 TB | nothing at scale | The answer |
3. People You May Know (PYMK)
PYMK is “show me people I am likely to connect with.” Empirically, the strongest signal is number of shared 1st-degree connections - a 2nd-degree person you share 30 connections with is a near-certain “yes.”
Naive approach: compute friends-of-friends on request
When the user opens PYMK, expand all their connections’ connections, count occurrences, subtract people already connected, sort by count, return top 20.
Where it breaks: this is exactly the 2nd-degree explosion - expanding 500 connections’ ~500 connections each is a 250K-entry gather with counting, per request, multi-shard. Doing it live per page load at DAU scale melts the graph store. And PYMK does not need to be live; an hour-old suggestion is fine.
Evolved approach: offline friend-of-friend intersection, ranked
Compute PYMK candidates in an offline batch pipeline off the connection graph, and serve precomputed results:
Candidate generation (batch, graph-parallel). For each user U, compute the multiset of 2nd-degree members with their shared-connection count: for every pair of U’s connections, the people they both know are candidates, and the count of distinct paths is the shared-connection score. This is a classic triangle/common-neighbor computation done in Spark/graph frameworks over the full edge list, run daily or continuously off the CDC stream. Output:
U -> [(candidate_id, shared_count)], capped to the top few hundred.Feature enrichment. Join candidates against profile data to add signals beyond shared connections: same company (current or past), same school, same location, overlapping skills, whether they recently viewed each other’s profile. Each is a cheap join in the batch job.
Ranking. A model scores each candidate from these features (shared connections dominate, but “same employer + 3 shared connections” outranks “8 shared connections at random”). Output the ranked top-K per user into a serving store.
Serving.
GET /pymkis a single read of the precomputed ranked list from a key-value store, then filter out anyone the user has since connected to or dismissed (a small real-time exclusion set kept in Redis). O(1) at read time.
Batch (daily / streaming):
edges --> common-neighbor count --> enrich(company, school, skills, location)
--> rank(model) --> pymk_store[U] = [candidate, candidate, ...]
Serve:
GET /pymk(U) = pymk_store[U] minus already_connected(U) minus dismissed(U)
The dismissed/already-connected exclusion is the only real-time piece; everything expensive is precomputed. This is the same philosophy as the degree sketch: the graph-heavy computation is an async batch, the read is a list fetch. PYMK and the 2nd-degree sketch even share the candidate-generation stage - both need “distinct 2nd-degree members of U,” so we compute it once.
4. Distance-aware search
Search people by job title, company, skill, or location. The LinkedIn twist: results are ranked partly by network distance - a matching 2nd-degree person outranks an identical-on-paper stranger.
Naive approach: SQL LIKE over the profile table
SELECT * FROM profiles WHERE title LIKE '%engineer%' AND company = 'Acme'.
Where it breaks: LIKE '%...%' cannot use a B-tree index, so it is a full table scan over 1B rows per query. No relevance ranking, no fuzzy matching (“SWE” vs “Software Engineer”), no multi-attribute scoring. Structured text search is not what a relational WHERE clause is for.
Evolved approach: inverted index + distance re-ranking
Index profiles in a search engine (Elasticsearch/Lucene) with an inverted index over the structured fields:
Profile document (indexed):
user_id, name, current_title, current_company, past_companies[],
skills[], location, seniority, industry
Query "software engineer at Acme in Bangalore":
1. Retrieve: inverted-index lookup on title + company + location
-> candidate set of matching user_ids (thousands), ranked by text relevance (BM25)
2. Re-rank by network distance: for the top candidates, fetch the searcher's
degree to each (1st/2nd via the same adjacency + Bloom sketch as above),
and boost closer connections up the ranking.
3. Return the page with the degree badge already attached (reusing step 2).
The two-stage split matters: retrieval is content-only (the search index knows nothing about who is searching), and re-ranking injects the per-searcher network signal by calling the exact same degree service built in deep dive 2. We do not bake the graph into the search index (it would need re-indexing on every connection change for every user); we compute distance at query time on the ~100 candidates that survive retrieval, which is cheap because degree lookup is O(1) from the sketch.
Profile updates flow to the search index asynchronously off the profile-store CDC stream, so a title change is searchable within seconds without blocking the profile write. Company pages reuse the same machinery: a company document is indexed, and “employees” is a saved search (current_company = X) rather than a materialized list, which stays correct as people change jobs.
5. Feed (kept short - it is Twitter-lite)
The feed reuses the Twitter design, so I state it and move on. Normal connections and followed companies are fanned out on write: when someone posts, a worker pushes the post_id into each connection’s cached feed list (user -> [post_id], IDs only, capped). High-follower influencers and companies with millions of followers are the celebrity case - not fanned out, merged at read time from their own cached author feed. Reads fetch the precomputed list, hydrate bodies from a shared post cache (dedup: one post body, referenced by ID everywhere), rank at read time, and return with a reverse-chronological fallback if the ranker is slow. Fan-out volume here is ~6K inserts/sec versus Twitter’s millions, so it is genuinely the easy part of this system.
API Design & Data Schema
API
POST /api/v1/connections
Body: { "target_id": "999" }
Resp 202: { "request_id": "...", "status": "pending" } # async accept flow
POST /api/v1/connections/{request_id}/accept
Resp 200: { "status": "connected", "since": "2026-07-26T09:00:00Z" }
GET /api/v1/degree?target_id=999
Resp 200: { "target_id": "999", "degree": 2, "shared_connections": 14 }
# degree in {1,2,3,"out_of_network"}; p99 < 100ms
GET /api/v1/pymk?limit=20
Resp 200: { "suggestions": [ { "user_id":"...", "shared_connections":9,
"reason":"3 shared + same company" }, ... ] }
GET /api/v1/feed?limit=25&cursor=<opaque>
Resp 200: { "posts": [ { "post_id":"...", "author":{...}, "text":"...",
"author_degree":1, "created_at":"..." } ], "next_cursor":"..." }
GET /api/v1/search/people?title=engineer&company=Acme&location=Bangalore&cursor=..
Resp 200: { "results": [ { "user_id":"...", "name":"...", "title":"...",
"company":"...", "degree":2 } ], "next_cursor":"..." }
POST /api/v1/companies/{id}/follow -> 202
GET /api/v1/companies/{id} -> company page + recent posts
Pagination is cursor-based everywhere. Offset pagination on a feed or search result set breaks when the underlying set shifts between page loads; the cursor encodes a stable position (last-seen sortable ID / search score).
Data store choices
1. Graph Store - sharded wide-column (Espresso / Cassandra), NOT a native graph DB. Access is single-partition adjacency reads and symmetric edge writes; that is a KV/wide-column sweet spot and it shards cleanly by user_id. A native graph database cannot shard 250B edges without cross-partition traversals killing latency at 200K QPS.
Table: connections
user_id BIGINT PARTITION KEY
peer_id BIGINT CLUSTERING KEY
created_at TIMESTAMP
Shard by: user_id. Symmetric: A-B stored as (A,B) and (B,A).
Table: pending_requests
target_id BIGINT PARTITION KEY -- the person who must accept
requester BIGINT CLUSTERING KEY
created_at TIMESTAMP
Shard by: target_id ("my pending requests" = single partition)
2. Profile Store - relational or document, source of truth for members and companies. ~5TB, updated far more than the graph, needs rich structured fields. A sharded relational store (sharded by user_id) or a document store works; this is the canonical record that feeds the search index via CDC.
Table: members
user_id BIGINT PK, name, current_title, current_company_id,
location, industry, seniority
Table: member_positions (past + present jobs; feeds "past_companies")
user_id, company_id, title, start, end -- indexed by (company_id) for employee lookup
Table: member_skills
user_id, skill_id -- indexed by (skill_id) for search
Table: companies
company_id BIGINT PK, name, industry, size, description
3. Derived serving stores - Redis / RocksDB. The 2nd-degree Bloom sketches (user -> bloom), the PYMK ranked lists (user -> [candidate]), the feed lists (user -> [post_id]), and the shared post-body cache (post_id -> body). All rebuildable from source; all keyed and sharded by their read key.
4. Search Index - Elasticsearch/Lucene. Inverted index over profile attributes for retrieval; network distance is applied as a query-time re-rank, not indexed.
Why NoSQL/specialized over one big SQL box: the workload is billions of partition-scoped graph reads, structured full-text search, and cache serving - three access patterns, none of which is “cross-entity ACID transaction.” The single place we need atomicity (writing the symmetric edge as both-or-neither) is a single-partition two-row write, which the wide-column store handles with a lightweight transaction. SQL’s joins and global transactions are exactly what we do not need at this scale.
Bottlenecks & Scaling
Where it breaks first, in order, and the fix:
1. Degree queries at 200K QPS (breaks first and hardest). Live BFS is impossible. Fix: 1st degree = single-partition adjacency read; 2nd degree = O(1) Bloom sketch lookup; 3rd/out-of-network = bounded bidirectional BFS run only on the rare miss. The expensive neighborhood math is precomputed async into a tiny sketch. This is the decision that makes the system possible.
2. The 2nd-degree neighborhood explosion. A user’s 2nd degree is 50K-100K people, 3rd is up to 125M.
Fix: never materialize the explicit neighborhood on the read path. Store a ~30KB Bloom sketch per active user (async-built off the CDC stream), and for exact-required surfaces verify a sketch hit with a cheap adj(U) ∩ adj(X) shared-connection check. Bidirectional search meets in the middle so no query expands the full 3rd-degree set.
3. Sharding the graph and hot partitions. Shard key = user_id on the adjacency table, so every 1st-degree read and every symmetric write is single-partition. The 30K connection cap bounds any partition, so even open-networkers do not create an unbounded hot partition. Replication factor 3 for durability. Choosing anything time-based as a shard key would concentrate all current writes on one shard - the classic mistake.
4. PYMK compute cost. Friend-of-friend intersection is a 250K-entry gather per user. Fix: compute candidates in an offline graph-parallel batch (shared with the 2nd-degree sketch stage), enrich and rank offline, serve a precomputed ranked list with only the small dismissed/already-connected exclusion applied in real time.
5. Search over 1B profiles. LIKE is a full scan; per-searcher distance cannot be indexed.
Fix: inverted-index retrieval (content-only) then query-time re-rank by network distance over the ~100 surviving candidates, reusing the degree service. Profiles reach the index async via CDC so writes never block on indexing.
6. Connection-write consistency. The symmetric edge must be both rows or neither.
Fix: both (A,B) and (B,A) written in one single-partition-coordinated transaction; if we cannot co-locate them, use a saga that retries the second row idempotently and reconciles. Accepting a request gives read-your-writes for the two parties; everyone else’s derived view (sketches, PYMK) updates eventually off the CDC stream.
7. Sketch/feed staleness after a new connection. A fresh connection is not instantly in your 2nd-degree sketch. Fix: accept it. Degree/PYMK are explicitly eventual; the 1st-degree adjacency (which reflects the new connection immediately) covers the case the two parties actually care about. Sketches catch up within minutes off the stream.
8. Single points of failure. Graph, Feed, Search, and Degree services are stateless behind load balancers - scale horizontally, any instance serves any request. Kafka, the stores, and the caches are replicated. Batch builders are restartable and idempotent. No single box whose loss stops badges or feeds from rendering; a degraded badge (missing degree) still lets the page load.
9. Multi-region for a global membership. Deploy read services and caches per region, route via GeoDNS. The graph store replicates across regions; because degree/PYMK/feed are eventually consistent, cross-region lag is forgiving. The two parties to a new connection read their own just-accepted edge from their home region (read-your-writes on the adjacency only).
Wrap-Up
The trade-offs that define this design:
- Adjacency lists in a sharded KV store over a native graph database. We give up cheap deep traversal (which we refuse to do live anyway) to get a single-partition 1st-degree read that scales horizontally to 250B edges. This is the opposite of the instinctive “it’s a graph, use a graph DB” answer, and it is the right call at a billion users.
- Precompute the neighborhood into a tiny sketch; answer degree O(1). The expensive 2nd-degree math moves off the 200K-QPS read path into an async batch that emits a ~30KB Bloom filter per user. We accept ~1% false positives (verified cheaply where exactness matters) in exchange for making the ubiquitous badge nearly free.
- Bidirectional BFS for the rare deep check. Meet in the middle to turn
O(b^3)intoO(b^1.5), and only pay it on the uncommon 3rd/out-of-network case. - Everything graph-heavy is offline, everything on the read path is a list fetch. Degree sketches, PYMK, feed materialization, and search indexing are all async off CDC streams; reads are O(1) cache hits stitched together at query time.
- Distance as a re-rank, not an index. Search retrieval is content-only; the per-searcher network signal is applied at query time on the surviving candidates, so a connection change never triggers a global re-index.
One-line summary: LinkedIn is a graph-distance system before it is a feed - a symmetric connection graph stored as sharded adjacency lists, degree answered O(1) from precomputed per-user Bloom sketches with bidirectional BFS for the rare deep case, PYMK and search built offline off the same friend-of-friend computation, and a Twitter-lite fan-out feed bolted on top, all serving 200K degree queries a second on a quarter-trillion-edge graph.
Comments