Design a Social Graph

LinkedIn’s connections for 1 B members: invitations, follows, a 1st/2nd/3rd badge on 200 k profile views a second, and daily People You May Know.

Last updated 2026-10-26. Difficulty: hard. Patterns: graph, sharding, in-memory, consistency, batch. Reported at LinkedIn, Meta, X, Snap, Pinterest, Microsoft.

Functional requirements

• Send, accept, ignore and withdraw connection invitations. A connection is mutual and needs consent, so it starts as a pending invitation that the recipient owns. Accepting makes both people 1st-degree. Caps: 30 k connections per member (LinkedIn’s own limit) and a weekly invitation quota against spam.
• Follow and unfollow. One-way and without consent, for creators and companies. Connecting implies following both ways. Follows feed the news feed but never change anyone’s degree.
• Degree badge on every profile view. 1st, 2nd or 3rd relative to the viewer, from current connections. 1st and 2nd are exact on every view. Beyond two hops we show an exact 3rd where the viewer’s second-degree set is cached and “3rd+” otherwise, which is how LinkedIn’s own search filters group everything past two hops.
• Mutual connections. A count and three faces on the profile, and the full list paginated behind it. It is the intersection of two connection lists, computed at read time.
• Connection lists and counts. Browse a member’s connections, newest first, if they allow it. Your own count is exact; other people see “500+” past 500. Follower counts may lag by seconds.
• People You May Know (PYMK). Ranked suggestions with a reason (“12 mutual connections”, “also at Acme”), recomputed daily. A new member gets suggestions within minutes of signing up, before any daily run has seen them.
• Privacy: hidden connection lists and blocking. A member can hide their list; shared connections still show, because the viewer already knows those people. A block removes any connection and invitation and hides each member from the other everywhere: profile, mutual lists, PYMK, search badges.
• Out of scope. The feed itself (fan-out over the follow graph is Design a News Feed), search, messaging, spam and fake-account detection beyond quotas, and recruiter products. We say where each plugs in.

Non-functional requirements

• Scale (1 B members · 250 B connections). Average 500 connections with a heavy tail to the 30 k cap. Reads dominate: about 100 degree checks for every connection written.
• Degree check latency (p99 < 20 ms at 200 k/s). On every profile view, inside a ~200 ms page budget. This drives the hardest tradeoff in the design: a check may read at most two lists over the network, so 2nd degree must be an intersection, never a two-hop expansion, and an exact 3rd degree is only affordable where it is precomputed.
• Bounded work per check (≤ 2 list reads · ≤ 30 k ids). Whatever the degrees involved. A supernode must cost the size of the smaller list in a check, not the larger.
• Read-your-writes for the two people (immediate for A and B · < 1 s for others). A connection you just made must show as 1st on your next screen. Counts, second-degree caches and PYMK may lag by seconds to a day.
• Edges converge (half-written pair healed < 1 min · proven daily). A connection is two rows on two shards. A pair with only one side written must heal on its own, and a daily scan must show that it did.
• Privacy on every read (block effective < 1 s, on every surface). Blocks and hidden lists are checked at read time against the live graph. Precomputed lists (PYMK, second-degree sets) are copies and are never trusted for privacy.
• Availability (99.99 % for degree checks). A profile renders without the badge rather than failing: a timeout returns no badge, never a guessed one. Invitations can live with 99.9 %.
• PYMK freshness (daily · new members < 10 min). Never suggest someone you are connected to, have invited, dismissed or blocked, even if yesterday’s list says so.

Back-of-envelope estimates

• Connections and edge rows: 250 B connections · 500 B rows. 1 B members × 500 average ÷ 2 (each connection has two ends) = 250 B connections. Stored as two rows each, one per member: 500 B rows. Every size below starts from this number.
• Connection writes: ~600/s avg · ~2 k/s peak. ~50 M invitations accepted a day (of ~150 M sent) ÷ 86 400 ≈ 580/s, about 3× that at the weekday peak. Each accept writes 2 connection rows on 2 shards plus an invitation update, ~5 k row writes/s at peak. Writes are not the hard part.
• Graph held in memory: ~4 TB raw · ~5 TB per copy. 500 B ids × 8 B = 4 TB of sorted connection lists; headers, block sets and allocator slack bring it to ~5 TB a copy. A typical list is 500 × 8 B = 4 KB, the largest (30 k) 240 KB. Small enough to hold the whole graph in RAM, so there is no miss path at all.
• Graph cache servers: ~25 per copy · ~75 per region. 5 TB ÷ ~200 GB usable on a 256 GB server = 25 servers per full copy. Three copies per region (one can be in maintenance, one can fail, one still serves): 75 a region, ~225 across three regions. Memory sizes this tier, not CPU: an intersection takes microseconds.
• Cost of one degree check: ~1 k comparisons · ~8 KB moved. Intersecting two sorted lists of 500 is a merge of ~1 000 comparisons, ~2 µs of CPU. The two list reads move ~8 KB; at 200 k/s that is ~1.6 GB/s across the fleet and under half a core of CPU. A check costs a network round trip, not arithmetic.
• Second-degree network: ~250 k ids · ~2 PB for everyone. 500 connections × 500 each = 250 k second-degree ids before overlap (fewer unique, since friends share friends). At 8 B that is 2 MB per member, and 1 B × 2 MB = 2 PB to store for everyone. So the second degree is never expanded per request nor stored for all: it is an intersection, cached only for heavy viewers.
• Edge store on disk: ~30 TB per copy. 500 B rows × ~60 B (two ids, type, state, version, timestamp, row overhead) = 30 TB for connections; follows, invitations and blocks add ~10 TB. Spread as 4 096 logical slots over ~128 MySQL primaries (~300 GB each), each with two replicas.
• PYMK daily batch: ~3 T paths → 150 B scored → ~1 TB served. Uncapped friends of friends is 1 B × 250 k = 250 T pairs. Capped to the 300 M members active in 30 days, walking their 100 strongest ties and 100 of each tie’s: 300 M × 100 × 100 = 3 T path increments. Keep the top 500 per member by a cheap score (150 B pairs) for the ranker and store the top 200 at ~16 B each: ~1 TB per daily version.

Components

• Member app (web · iOS · Android): Shows the degree badge and mutual connections on profiles, invitations, connection lists and PYMK cards. Keeps the consistency token returned by a relationship change, or carried in the notification about one, for 60 s and sends it with graph reads, so the two people in a new connection see “1st” on their very next screen.
• API gateway (auth · quotas · deadlines): Authenticates, enforces invitation quotas (a weekly cap per member, stricter for new accounts) and composes pages. The profile page calls the graph query service with a 20 ms deadline and renders without the badge if it misses: a missing badge is acceptable, a wrong one is not.
• Connection service (invites · accept · block): Owns every relationship change. Each change commits the deciding member’s rows and an outbox entry in one local transaction on one shard, then writes the other member’s rows directly as an idempotent upsert. For invitations the recipient’s shard is the authority, so an accept and a withdraw racing each other are settled by one conditional update on one row.
• Edge store (sharded MySQL · by member id): Typed edge rows keyed (src, type, dst) with state, created_at and a per-pair version: CONNECTED, INVITE_IN, INVITE_OUT, FOLLOWS, FOLLOWED_BY, BLOCKS, BLOCKED_BY. Every relationship is two rows, one on each member’s shard, so any one-hop question about a member reads one shard. 4 096 logical slots on ~128 primaries, ~40 TB a copy, with an outbox table on every shard.
• Graph query service (degree · mutuals · lists): Stateless. Answers relationship(viewer, targets) with degree, mutual count and a preview, plus mutual and connection lists behind cursors. Keeps a 2 GB table of every member’s connection count from last night’s snapshot, used only to plan which list to move, and applies blocks and hidden-list rules to every answer before it leaves.
• Graph cache (all lists in RAM · 3×/region): Every member’s connections as a sorted array of 8-byte ids, plus both block sets: ~5 TB a copy on ~25 servers, the same 4 096 slots as the edge store, three copies per region. It is a full replica, not a cache with misses: it boots from a snapshot and applies the change stream in commit order, so a cold key can never stampede the edge store. Intersections and unions run next to the data, so a 30 k list never has to cross the network.
• Event stream (Kafka · binlog CDC + outbox): Row changes from every edge-store shard, keyed by src member so one member’s changes stay in order, plus the outbox entries for the mirror. Consumers: the graph cache, the mirror, PYMK incremental, the snapshot builder, and outside this design the feed, search and notifications. Its lag, p99 under a second, is the staleness of every read that does not carry a token.
• Mirror & repair (outbox consumer · daily scan): Applies the other side of every relationship change from the outbox, as an upsert guarded by the pair version, retrying with backoff until it lands, so a failed second write heals in seconds. A daily scan anti-joins the edge snapshot with itself to find pairs with one side, re-checks each against the live rows and fixes it. Pairs repaired per day is how you know the dual write is healthy.
• Network cache (2nd-degree bitmaps): Second-degree sets as compressed bitmaps for the ~2 M heaviest viewers (recruiter and sales seats, anyone past 20 profile views today): ~0.5 MB typical, up to ~20 MB for a 30 k-connection recruiter, ~2 TB in all. Built on demand by a scatter to the graph cache shards and kept 6 hours. It makes an exact 3rd-degree check a probe of the target’s ~500 ids; hours of staleness are fine because 1st and 2nd are always computed live.
• PYMK service (serve · filter · explain): Reads the member’s daily list and incremental overlay, drops anyone now connected, invited, dismissed, blocked or deactivated, and asks the graph query service for exact mutual counts on the visible cards. Logs every impression with list version, position and reason, which becomes the ranker’s training data.
• PYMK store (KV · versioned daily lists): Member id → top 200 candidates with score and reason code, ~3 KB each, ~1 TB per daily version. Each run is bulk-loaded as a new version and switched on by flipping one pointer after validation, with yesterday’s kept for rollback. A small overlay keyspace holds same-day suggestions from the stream until the next version supersedes them.
• PYMK batch (daily · capped FoF + ranker): Loads a capped graph (each member’s 100 strongest ties, 32-bit ids, ~400 GB) and member features into memory on each of ~20 workers, and partitions members, not the graph, across them. Counts friends of friends with paths through high-degree members discounted, adds company, school and contact candidates, and ranks with a model trained on accepted invitations. Writes the top 200 per member as a new version.
• PYMK incremental (stream · cold start): Consumes sign-ups and new connections. For a new member it builds a first list within minutes from their first connections’ connections, same-company and same-school cohorts and contact matches; for an existing member’s new connection it adds that person’s strongest ties as candidates. Writes the overlay, which the next daily version replaces.
• Graph snapshots (daily edges · profiles · logs): A daily edge snapshot cut at a known stream position, compacted from the change stream so the live store is never scanned. Beside it: profile attributes (companies with dates, schools with years, region, industry), contact-import matches, and PYMK impressions with their outcomes. The PYMK batch and the repair scan both read it, so neither touches production MySQL.

User flows

1. Send and accept an invitation. The write path. One relationship becomes rows on two shards; the design makes the second write certain rather than atomic, and makes the result visible to both people on their next screen.
   1. A invites B; the connection service writes the pending invitation on B’s shard, which owns it. B’s shard is the authority because only B can accept or ignore, and a withdraw by A is a conditional update on the same row, so one row settles every race. The same transaction checks the 30 k cap and that neither has blocked the other (B’s shard holds both BLOCKS and BLOCKED_BY for B), and adds an outbox entry for A’s INVITE_OUT row.
   2. B accepts; one local transaction on B’s shard flips the invitation and inserts B’s connection row with an outbox entry. The state = "pending" guard makes accept, ignore and withdraw mutually exclusive: zero rows updated means someone else got there first, and an accept retried after a timeout finds its own row already accepted and returns success. The new pair version v2 goes on both rows so later changes to the pair can be ordered.
   3. The connection service writes A’s side directly, as an idempotent upsert, and returns. Normally both sides land inside the request, about 10 ms in all. If this write fails the request still succeeds, because the outbox entry from the previous step guarantees the mirror will apply it (see the failure flow). The version guard makes the direct write and the mirror’s write the same operation, so doing it twice is harmless.
   4. Both shards’ changes flow through the event stream into every graph cache replica, which inserts each id into the other’s sorted list. Each replica applies a shard group’s changes in commit order and records the last position applied, which is what tokens are compared with. Inserting into a sorted array of 500 ids moves at most 4 KB; the largest lists are kept in chunks of ~1 k ids so an insert never moves more than 8 KB. Lag is tens of milliseconds normally, p99 under a second.
   5. Both members’ next reads carry the token, so “1st” shows immediately even on a replica that is a moment behind. The query service compares the token with the replica’s applied position for that shard group; almost always the replica is already past it. The token expires after 60 s, by which time every replica has applied the change anyway. Everyone else sees the connection after the stream lag, which nobody can notice.
   6. Downstream consumers react to the same events: PYMK incremental adds B’s strongest ties as candidates for A, and A’s for B. These may lag. Counts need no consumer at all: a member’s connection count is the length of their list in the graph cache, so it can never disagree with the list they can open. Feed, search and notifications consume the same stream outside this design.
2. View a profile: degree and mutual connections. The read path, 200 k times a second. Two list reads in parallel, a block check, a membership probe and one intersection: bounded work, about a millisecond, whatever the degrees involved.
   1. A opens B’s profile; the page asks the graph query service for the relationship with a 20 ms deadline. One internal call returns the badge, the mutual count and three preview faces. Search results and comment threads use the same call with up to 50 targets at once. If it misses the deadline the page renders without a badge rather than guessing.
   2. The query service looks up both connection counts in memory, then reads both lists and block sets in parallel. The counts table decides the plan before any network call. Both lists are under ~2 k ids, the common case, so it reads both from any replica in the region: ~8 KB in one parallel round trip of ~0.5 ms. If either side were large it would ship the smaller list to the larger list’s shard instead (the supernode flow).
   3. Blocks are checked first: if either has blocked the other, the answer is “not visible” and nothing else is computed. Each member’s shard holds both BLOCKS and BLOCKED_BY, so one read answers both directions. Deciding privacy before computing anything means a blocked member can never leak through a count or a preview face. Mutuals who block A, or whom A has blocked, are removed before the count in the intersection step.
   4. First degree: is B in A’s list, or A in B’s? Two binary searches, about 10 comparisons each. Checking both directions makes the badge right as soon as either side of a new connection has been written, which hides the seconds, or in a failure the minute, when the second write is still in flight.
   5. Second degree: intersect the two sorted lists; a non-empty result means 2nd degree, and it is also the mutual count and the preview. A linear merge of 480 and 650 ids is ~1 100 comparisons, about 2 µs. When one list is ten times longer, galloping (binary-searching ahead in the long one) makes it O(small × log large). The two hops are never expanded: “is B within two hops of A” is answered as “do their neighbourhoods touch”.
   6. Third degree, only if the first two missed: probe B’s ids against A’s cached second-degree set, or answer “3rd+”. If A is a heavy viewer, the network cache holds A’s second-degree bitmap and 650 probes decide 3rd degree exactly. Otherwise the badge reads 3rd+, because computing it would mean reading the lists of all 480 of A’s connections, ~2 MB, for one profile view.
   7. A taps “23 mutual connections”; each page is recomputed from the two lists and continues after a cursor. Recomputing is cheaper than caching: two 4 KB reads and a 2 µs merge. The merge emits members in id order, so the cursor is the last id returned and a connection made mid-scroll cannot cause a duplicate. B hiding their list does not apply, since only shared connections are shown; blocked and deactivated members are filtered on every page.
3. A recruiter with 30 k connections. The case that breaks naive designs. A 30 k list is 240 KB and a recruiter’s second degree is ~15 M ids, so every operation must cost the size of the smaller side, and expensive state must be built once and reused.
   1. Recruiter R, with 30 k connections, opens B’s profile; the counts table says R’s list is the big one. Fetching R’s list for every view would move 240 KB per check, and R views hundreds of profiles a day. So the plan flips: move the small list to the big one.
   2. The query service reads B’s 4 KB list and sends it to R’s shard, which intersects it next to R’s list. R’s shard gallops 650 ids into its 30 k sorted array: ~650 × 15 ≈ 10 k comparisons, ~10 µs. What comes back is a count and three ids, not R’s list. Two sequential round trips instead of one parallel pair, ~1 ms, bounded by the smaller list.
   3. R views another recruiter with 25 k connections: the smaller list, 200 KB, is shipped to R’s shard and merged there. About 55 k comparisons, ~50 µs, and a 200 KB transfer: the most expensive single check in the system, and the 30 k cap is what bounds it. The mutual count can run to thousands; it is exact, and the preview takes three.
   4. R passes 20 profile views today, so the query service builds R’s second-degree set once and stores it in the network cache. Pulling the lists of R’s 30 k connections to one place would move 120 MB. Instead R’s list goes to every server of one graph cache copy (25 × 240 KB) and each ORs its local lists into a partial bitmap; merged, ~15 M ids (~10 M unique) become a ~20 MB compressed bitmap in a few hundred milliseconds. Built at most once per 6 hours per viewer.
   5. From now on each of R’s views is bounded by the target: a probe for 1st, an intersection on R’s shard for 2nd, B’s ids against the bitmap for 3rd. 650 bitmap probes take ~10 µs. The bitmap can be hours old, which only affects 3rd degree: a connection made since is still found by the live intersection. A search page of 50 badges for R is 50 intersections on R’s shard and one bitmap fetch.
   6. A hot target: a CEO with 30 k connections gets 5 k profile views a second, each intersecting the viewer’s small list on the CEO’s shard. The three replicas of that slot in the region share it, ~1.7 k intersections a second each at ~10 µs: trivial CPU. The query service also keeps the lists of the few thousand hottest members in process for 10 s, so their shard sees one fetch per host per 10 s rather than one per view.
4. The second write fails halfway. B accepts while A’s shard is failing over. B’s side commits and A’s does not. The pair has to heal on its own, neither person should notice, and something has to prove afterwards that nothing stayed one-sided.
   1. B accepts; the transaction on B’s shard commits with its outbox entry, but the write to A’s shard times out during a primary failover. A primary failover takes ~10–30 s. The connection service gives the second write a 200 ms budget and does not retry inline: its outcome is unknown (it may have committed just before the old primary died), and retrying is the mirror’s job.
   2. The service returns success to B anyway: the outbox entry is the promise that A’s side will be written. Failing the request would be wrong, because B’s side is durable and “accepted” is already true. B’s token names B’s shard, so B sees 1st immediately. A’s “accepted” notification is sent from the stream after the commit and carries the same token.
   3. The outbox entry reaches the mirror through the event stream; it retries the upsert on A’s shard with backoff until the new primary accepts it. The upsert is guarded by the pair version, so it is safe whether or not the timed-out write actually committed. Backoff runs from 100 ms to 30 s, and the pair usually heals within a minute. An entry still failing after an hour goes to a dead-letter topic and pages someone.
   4. Meanwhile A opens B’s profile: B’s list already contains A, and the 1st-degree probe checks both directions, so A sees “1st”. The one-sided window never shows on the badge. What is off for that minute: A’s own connection count is one short and B is missing from A’s connection list, both acceptable for a minute.
   5. B opens A’s profile with a token the local replica has not applied yet; the query service reads that one pair row from the edge store. The fallback is one primary-key read, not a list, and happens only when a token is newer than the replica, so it is a tiny fraction of reads, all in the seconds after writes. It has a 10 ms budget; past that the answer comes from the replica.
   6. If an outbox entry is ever lost to a bug, the daily repair scan finds the one-sided pair in the snapshot, re-checks the live rows and writes the missing side. An anti-join of the 500 B-row snapshot with itself runs in the batch cluster, not against production MySQL. Pairs that were mid-write when the snapshot was cut show up too, so every finding is re-read live before it is fixed. Pairs fixed per day should be near zero; a rise is the alarm that some code path writes one side without an outbox entry.
   7. A removes B a minute later while an old retry is still in flight; the version check stops the retry from resurrecting the connection. Remove writes tombstones with version v3 on both shards, through the same outbox path. The stale upsert carries v2, so its version guard matches nothing. Tombstones are kept 30 days, longer than any retry or repair can be late; without them a late upsert would find no row and recreate the connection.
5. Daily PYMK, then a page of it. The background path. A daily batch turns a capped snapshot into a ranked list per member; serving filters that list against the live graph, and a stream job covers members the batch has not seen yet.
   1. At midnight UTC the snapshot builder cuts the edges at a known stream position, alongside profiles and yesterday’s PYMK outcomes. The snapshot is built by compacting the day’s changes into yesterday’s snapshot, so the live store is never scanned. Recording the position per shard group means the batch knows exactly which edges it saw; the serving filter handles everything after.
   2. The PYMK batch loads a capped graph into memory on each worker: every member’s 100 strongest ties, as 32-bit ids. 1 B × 100 × 4 B = 400 GB, plus ~200 GB of member features, fits on 1 TB-RAM machines, so ~20 workers each hold the whole capped graph and split the members instead of the graph. Strength is recency plus interaction (messages, profile views, endorsements). The cap is why a 30 k-connection member adds 100 paths to each neighbour’s count, not 30 k.
   3. For each of 300 M active members, the job counts friends of friends through those ties and adds company, school and contact candidates. Each path through a middle member adds 1 / log(that member’s degree) (Adamic–Adar), so knowing someone through a 30 k-connection recruiter counts for less than through a 50-connection colleague. 300 M × 100 × 100 = 3 T increments into per-member hash maps, ~5 k unique candidates each, minutes of work because it is all in memory. Cohorts: same company with overlapping dates, same school within two years.
   4. A cheap score keeps the top 500 per member; a ranker trained on accepted invitations orders them and keeps 200. This is the candidate-then-rank funnel of the recommendation system, run offline: 150 B pairs scored by gradient-boosted trees at ~10 µs is ~420 core-hours, about 20 minutes on the workers. Features: weighted mutuals, cohort overlap, region, industry, seniority gap, profile views either way, and how often the candidate accepts. The label is an accepted invitation, not a click, so the model is not rewarded for suggestions people ignore.
   5. The job bulk-loads the lists as a new version of the PYMK store, validates it, and flips the current-version pointer. Bulk files rather than 300 M individual writes. Checks before the flip: coverage of active members, score distribution against yesterday’s, and a sample proving no suggestion is an existing connection. Yesterday’s version stays for rollback. LinkedIn has written about serving batch-computed data such as PYMK from a key-value store built for bulk loads (Voldemort’s read-only stores).
   6. A opens My Network; the PYMK service reads A’s list and overlay, filters them against the live graph, and gets exact mutual counts for the visible cards. The list is up to a day old, so anyone A has since connected with, invited or dismissed, anyone blocked either way, and anyone who opted out is dropped here. The batch counted mutuals over capped ties; the card shows the exact count from the live intersection. Impressions go to the event stream with version and position, as tomorrow’s training data.
   7. A new member signs up and connects to three colleagues; the incremental job writes a first list within minutes. Three colleagues with ~500 connections each give ~1 500 candidates, counted and scored by a lighter model in milliseconds; same-company cohorts and contact matches fill the list before the first connection exists. The PYMK service reads the overlay alongside the daily list, and tomorrow’s version supersedes it.

Deep dives

The theory behind it

• Storing and querying graphs: Social graphs and other graph data in system design: adjacency lists in a key-value store, graph databases, friends-of-friends and mutual friends, celebrity nodes, sharding a graph, and what Facebook's TAO does.
• Large-scale graph processing: Running algorithms over graphs with billions of edges: the Pregel vertex-centric model, PageRank, connected components, friend-of-friend recommendations, partitioning graphs, offline batch versus online queries, incremental updates, and where graph processing appears in system design.
• Sharding and partitioning: Horizontal partitioning strategies (range, hash, directory), consistent hashing, choosing a shard key, hot shards, cross-shard queries, and resharding without downtime.

Related

• Design a Payment System
• Design a Real-Time Leaderboard
• Design AWS Step Functions
• Design Venmo
• All 83 system design interview questions
• Run this question for a friend: the interviewer kit