Design a Social Graph

• 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.

• 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.

• 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.

• 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.

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.
   2. B accepts; one local transaction on B’s shard flips the invitation and inserts B’s connection row with an outbox entry.
   3. The connection service writes A’s side directly, as an idempotent upsert, and returns.
   4. Both shards’ changes flow through the event stream into every graph cache replica, which inserts each id into the other’s sorted list.
   5. Both members’ next reads carry the token, so “1st” shows immediately even on a replica that is a moment behind.
   6. Downstream consumers react to the same events: PYMK incremental adds B’s strongest ties as candidates for A, and A’s for B.
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.
   2. The query service looks up both connection counts in memory, then reads both lists and block sets in parallel.
   3. Blocks are checked first: if either has blocked the other, the answer is “not visible” and nothing else is computed.
   4. First degree: is B in A’s list, or A in B’s?
   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.
   6. Third degree, only if the first two missed: probe B’s ids against A’s cached second-degree set, or answer “3rd+”.
   7. A taps “23 mutual connections”; each page is recomputed from the two lists and continues after a cursor.
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.
   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.
   3. R views another recruiter with 25 k connections: the smaller list, 200 KB, is shipped to R’s shard and merged there.
   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.
   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.
   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.
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.
   2. The service returns success to B anyway: the outbox entry is the promise that A’s side will be written.
   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.
   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”.
   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.
   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.
   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.
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.
   2. The PYMK batch loads a capped graph into memory on each worker: every member’s 100 strongest ties, as 32-bit ids.
   3. For each of 300 M active members, the job counts friends of friends through those ties and adds company, school and contact candidates.
   4. A cheap score keeps the top 500 per member; a ranker trained on accepted invitations orders them and keeps 200.
   5. The job bulk-loads the lists as a new version of the PYMK store, validates it, and flips the current-version pointer.
   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.
   7. A new member signs up and connects to three colleagues; the incremental job writes a first list within minutes.

Ask: Why store every connection twice, sharded by member, instead of once, or in a graph database?

Good answers name: Two typed rows per relationship, sharded by member id, One row per connection keyed (lower id, higher id), plus a secondary index, A graph database (Neo4j, Neptune) for storage and traversal, Partition by community so neighbours share a shard.

Our pick: Every relationship is a pair of typed rows (src, type, dst) → (state, created_at, version), one on each member’s shard: CONNECTED both ways, INVITE_IN on the recipient and INVITE_OUT on the sender, FOLLOWS and FOLLOWED_BY, BLOCKS and BLOCKED_BY. Rows are clustered by (src, type, dst), so “A’s connections” is one range scan and “is B connected to A” is a point read. Members hash to 4 096 logical slots on ~128 MySQL primaries with two replicas each, and slots move between hosts without rehashing anyone. The only lists that outgrow a partition are big creators’ FOLLOWED_BY rows, bucketed as (member, bucket); connections are capped at 30 k, so a connection list never needs it. This is the shape of Facebook’s TAO (USENIX ATC 2013): typed associations stored on the shard of their source object in sharded MySQL, with inverse associations written from both ends.

1. Why MySQL rather than Cassandra?
   Either works for this layout; what decides it is per-shard transactions and conditional updates. Accepting flips one row and inserts another on the same shard, and the state = pending guard is what settles accept against withdraw. That is an ordinary local transaction in MySQL and a lightweight transaction, a Paxos round, in Cassandra. At ~5 k row writes a second neither is stretched, so I would pick whichever the company already runs well.
2. What exactly is in a row, and how big is it?
   Two 8-byte ids and a 1-byte type in the key; state (pending, accepted, ignored, withdrawn, removed), created_at and a version in the value. With InnoDB row and index overhead that is ~60 B on disk, so 500 B connection rows are ~30 TB a copy. The version belongs to the pair, and both rows carry the same one, which is what lets the two sides be reconciled.
3. How do you rebalance when a host fills up?
   Members hash to 4 096 slots and a small table maps slots to hosts, so moving load means moving whole slots, never rehashing members. A slot is copied to its new host from a snapshot plus the binlog, writes to it pause for about a second at cutover, and the map is updated. The graph cache uses the same slots, so its shard map moves in step.
4. Where do follows live, and why not in the graph cache?
   In the same store, as FOLLOWS and FOLLOWED_BY rows written through the same dual-write path. They are not part of degree, and the reads that need them, feed fan-out and follower pages, scan lists page by page rather than intersect them. Keeping them out holds the cache at ~5 TB a copy instead of roughly double, and keeps 30 M-entry follower lists out of a tier built for small lists.
5. A member deletes their account. What happens to their edges?
   Their own shard’s rows go in one pass; the rows on other members’ shards are removed through the mirror, one outbox entry per relationship, paced so a member with 30 k connections is not a burst on 128 shards at once. Until each lands, reads filter the member as deactivated, so nothing shows them in the meantime. The daily repair scan catches any pair left behind.

Ask: Accepting writes one row on B’s shard and one on A’s. Why not a distributed transaction, and what happens when the second write fails?

Good answers name: Local transaction plus outbox, idempotent write of the other side, mirror retries, daily repair, Two-phase commit across the two shards, A distributed SQL store (Spanner, CockroachDB class) doing it for you, Write one side only and derive the other from the stream.

Our pick: On accept, the connection service runs one local transaction on B’s shard: flip the invitation row (only if still pending), insert (B, CONNECTED, A) with a new pair version, and insert an outbox entry describing A’s side. It then writes A’s side directly as an upsert that applies only if the stored version is older, with a 200 ms budget, and returns success whether or not that write landed. The outbox entry reaches the mirror through the event stream, and the mirror applies the same upsert with backoff until it succeeds, usually within a minute, dead-lettering after an hour. Removes write tombstones with a higher version that are kept 30 days, so a late upsert can never resurrect a removed connection. A daily anti-join of the snapshot finds any pair still one-sided, re-checks it live and fixes it, and that count should be near zero. Facebook’s TAO paper describes the same decision for inverse associations: the two writes are not atomic, and an asynchronous job repairs the hanging ones.

1. Why write B’s side first and not A’s?
   Because B’s shard holds the invitation, and the invitation’s state is the decision. Flipping it to accepted and inserting B’s connection row in one local transaction makes the decision and the first side atomic, and the outbox entry for A’s side commits with them. If A’s side went first, a crash between the writes would leave A connected to someone whose invitation is still pending and could still be withdrawn.
2. A withdraws the invitation at the same moment B accepts it.
   Both are conditional updates on the same row, the INVITE_IN row on B’s shard: one sets accepted where state is pending, the other sets withdrawn where state is pending. The shard serialises them, so exactly one matches and the other updates zero rows and gets a 409. A losing withdraw is told “already accepted”, a losing accept “no longer available”. No other row is consulted.
3. A and B send each other invitations at the same moment.
   Each send writes INVITE_IN on the recipient’s shard, so both invitations can exist. The send path first checks for a pending invitation the other way, which sits on the sender’s own shard as an INVITE_IN row, and accepts it instead of creating a second. If the two sends race past each other, the first accept connects them, and accepting the second finds the pair already connected, closes it and does nothing else.
4. How do you know the dual write is not silently broken?
   Three numbers. Outbox age, the oldest unapplied entry per shard group, alerting past a few minutes. Dead letters, entries failing for an hour, which should be zero. And the repair scan’s daily count of pairs fixed after a live re-check: the end-to-end proof. A jump there means some code path writes one side without an outbox entry.
5. Could you drop the outbox and mirror and keep only the daily repair?
   Correctness would survive but the experience would not: a pair broken in a failover would stay one-sided for up to a day, so A’s list and count would be wrong until tomorrow. The outbox makes the common failure heal in seconds; the scan is the backstop for the rare one the outbox cannot cover, such as a bug that skips it. They catch different things and both are cheap.

Ask: 200 k profile views a second each need “what degree is B to me”, and a viewer’s second degree is 250 k people. How do you answer in 20 ms?

Good answers name: Bidirectional: membership probe for 1st, intersection of the two lists for 2nd, Cached second-degree bitmap per heavy viewer, for an exact 3rd, Breadth-first expansion from the viewer per request, Precompute everyone’s second-degree set or a distance table.

Our pick: The graph query service answers relationship(viewer, target) with a fixed plan. Block sets first: if either side blocks the other, stop. Then 1st degree as two binary searches, the target in the viewer’s list or the viewer in the target’s, so a half-written pair still reads as connected. Then 2nd degree as one intersection: both lists read in parallel when both are under ~2 k ids, otherwise the smaller list shipped to the larger list’s shard and galloped into it. The intersection gives the mutual count and three preview ids, after removing anyone blocked or deactivated. Only if both miss does 3rd degree come in: for viewers with a network-cache bitmap the target’s ids are probed against it, and everyone else sees 3rd+. A typical check costs ~1 ms and 8 KB, the worst ~2 ms and 240 KB, against a 20 ms deadline. LinkedIn’s 30 k connection cap and its 3rd+ grouping are product choices that are exactly what keep this bounded.

1. Product wants an exact 3rd degree for everyone. What does it cost?
   A bitmap for every viewer who reaches a profile beyond two hops. Say 30 M members a day do: ~350 builds a second, each reading ~500 lists by scatter, is ~175 k extra list reads and ~0.7 GB a second, roughly doubling the graph cache’s read load. With a 30-minute lifetime about 1 M bitmaps are live at once, ~0.5 TB. Affordable, not free; I would ship it behind an experiment and keep it only if an exact 3rd changes what people do.
2. Why not a Bloom filter of the second degree instead of a bitmap?
   At 1 % false positives a Bloom filter of 250 k ids is ~300 KB, not much smaller than the ~0.5 MB compressed bitmap, and every false positive is a wrong badge on someone’s profile. The bitmap is exact and supports the unions needed to build it. A 1 % error on 3rd degree might be tolerable, but the exact structure already fits the budget.
3. A is blocked by one of the 23 mutual connections. What does A see?
   Twenty-two. Mutuals are filtered on the read: anyone who blocks A, whom A blocks, or who is deactivated is removed before the count and the preview are computed. If that blocker was the only mutual, A sees 3rd+ rather than a 2nd that the mutual list could not explain.
4. A search results page needs badges for 50 members at once.
   One batched call. The viewer’s list is read once, the 50 targets’ lists are read in parallel grouped by server, so a handful of calls moving ~200 KB, and 50 merges cost ~100 µs. For heavy searchers with a bitmap, 3rd degree is 50 sets of probes. A page of badges is a few milliseconds of graph work, which is why search can afford one on every result.
5. How would you know the badges are right?
   Shadow-check a sample: recompute 0.1 % of answers offline from the edge store and alert on any disagreement beyond the stream lag. Track the badge-missing rate (deadline misses), the token fallback rate, and the share of 3rd+ answers a bitmap would have resolved, which says whether the heavy-viewer threshold is right. A wrong 1st is the error people report, so it gets its own alert.

Ask: Why hold every connection list in RAM, how many machines is that, and how is it sharded and kept current?

Good answers name: Full in-memory replica: sorted id arrays, 4 096 slots, 3 copies per region, fed by CDC, LRU cache (Memcached, Redis) in front of the edge store, Write-through cache updated by the write path (TAO-style), Compressed or 32-bit ids.

Our pick: The graph cache holds every member’s CONNECTED list as a sorted array of 8-byte ids, plus their BLOCKS and BLOCKED_BY sets, ~5 TB per copy. Members hash to the same 4 096 slots as the edge store; ~164 slots per 256 GB server, ~200 GB of lists, gives ~25 servers per copy. Each region runs three copies, ~75 servers, each kept under 50 % so two copies can carry the whole load. Every replica consumes the change stream for its slots in commit order and records the applied position per shard group, which is what consistency tokens are compared with. A replacement server loads its ~200 GB from the latest snapshot in object storage in 3 to 4 minutes and replays the stream from the snapshot’s position before it takes traffic. The query service calls it through Get, MultiGet, Intersect and UnionNeighbours, so set operations run where the lists already are. LinkedIn has written about serving its graph from memory, most recently with its LIquid graph database.

1. A graph cache server dies at peak. What happens?
   Its slots are still served by the other two copies; health checks route around it within a second, and the servers holding those slots go from under 50 % to ~75 % for a few minutes. A replacement loads the snapshot for its slots, replays the stream, and joins once its applied position is within a second of the head, about four minutes. Nothing touches the edge store, which is exactly why the tier has no miss path.
2. A bad deploy corrupts the graph cache in a whole region.
   Deploys go one copy at a time per region, canary server first, precisely so all three copies cannot break together. If it happened anyway, the region’s query service fails over to another region’s tier at ~100 ms more latency, most badges in that region miss their deadline and render empty, and the tier is rebuilt from snapshots in parallel in about ten minutes. The profile page never depends on the badge, so this is degraded, not down.
3. Why sorted arrays rather than hash sets or bitmaps?
   A sorted array is the most compact exact form for a sparse set, 8 B per id, and it supports everything needed: binary search for membership, merge or galloping for intersection, and an ordered scan for paging by id. A hash set costs two to three times the memory. Compressed bitmaps shine on dense sets, but 500 ids scattered over a billion are so sparse that per-container overhead makes them bigger than the array; I use bitmaps only for second-degree sets, which are dense enough to compress.
4. The graph grows 20 % a year. How do you add capacity?
   Move slots, not members: add servers to a copy, give them a share of the 4 096 slots, load those slots from snapshot plus stream, then flip the slot map, one copy at a time so two copies are always serving. A slot is ~1.2 GB, so each moves in seconds. Past ~40 servers a copy I would split every slot in two once, which needs no data movement, only a new map.
5. Why three copies per region and not two?
   With two, a server failure during a deploy or a slot move leaves one copy carrying every read for those slots with no margin. Three lets one copy be in maintenance and one fail while the third serves, and it spreads hot members’ reads over three servers. The third copy is ~25 servers a region, a small fraction of what the services calling the graph cost.

Ask: B accepts A’s invitation, and a minute later C blocks A. Who must see each change immediately, and how do you guarantee it without making every read strongly consistent?

Good answers name: Tokens for the people involved, blocks checked on every read, derived data allowed to lag, Strongly consistent reads from edge-store primaries, Optimistic UI: the app shows what it just did, Update every cache replica synchronously before the write returns.

Our pick: Every relationship write returns a token: the shard group and commit position it wrote. The actor’s client keeps it for 60 s, and the other member gets it in the notification about the change. Reads carry it, and if the graph cache replica has not yet applied that position, the query service answers for the pair from the edge store with one primary-key read instead of the list. The 1st-degree probe checks both members’ lists, so a pair half-written by the dual write still reads as connected. Blocks are checked first on every relationship, mutual-list and PYMK read, from the viewer’s own BLOCKS and BLOCKED_BY sets, so a block applies on every surface within the stream lag, including for the member who was blocked. Precomputed artefacts are never trusted for privacy: PYMK lists, second-degree bitmaps and search caches are filtered at read time, the same rule the news feed and post search apply to their copies. What may lag, and by how much, is written down: other viewers by the stream lag, counts by seconds, bitmaps by hours, PYMK by a day.

1. A and B are homed in different regions. Does the token still work?
   Yes, because it names the shard group and position, not a region. If A’s local replica of B’s shard group has applied the position, the fallback reads it there; if not, it reads the primary across the ocean, ~100 ms. That happens once, in the first seconds after the change, for the two people involved.
2. What does a block actually do, step by step?
   One local transaction on the blocker’s shard writes (C, BLOCKS, A), marks any connection, invitation and follow between them removed, and queues the other side; the mirror writes (A, BLOCKED_BY, C) and A’s side of the removals. From the moment either side reaches the graph cache, reads treat them as blocked, because each check reads both of the viewer’s sets. C gets a token, so C’s own next screen is right immediately, PYMK drops them on read, and tomorrow’s batch excludes them as candidates.
3. C has hidden their connection list. What can A still see?
   A cannot browse C’s connections, and C’s count shows only to C. Shared connections still show on C’s profile, because A already knows those people: hiding protects who C knows that A does not. C still counts for degree badges and as a path in PYMK. Those rules live in one filter in the graph query service, so every surface applies them the same way.
4. Why is it fine for connection counts to lag?
   Your own count is the length of your own list, read with your token, so it is exact for you. Other people see “500+” past 500, so a second of lag changes nothing they can see, and follower counts for big creators are approximate anyway. What would not be fine is a count that disagrees with the list a person can open, and deriving the count from the list rules that out.
5. The stream falls 5 minutes behind during an incident. What breaks?
   Nothing is lost: changes are durable in the edge store and queued in the stream. People who just acted still see their changes, because their tokens force fallback reads, and the climbing fallback rate is itself the alert. Everyone else sees connections and blocks up to 5 minutes late, and blocks are the urgent part, so during heavy lag the query service also reads the viewer’s block rows from the edge store, a cheap single-partition read, until lag is back under a minute.

Ask: Friends of friends for a billion members is 250 trillion pairs. How do you produce fresh, good suggestions every day, and what does someone who joined an hour ago get?

Good answers name: Daily batch over a capped graph replicated in memory on each worker, ranked, versioned, filtered at read time, Spark self-join of the capped edge table, Pregel-style message passing over the full graph, Friends of friends computed on request.

Our pick: Each night the batch reads the snapshot, keeps each member’s 100 strongest ties (recency and interaction), remaps ids to 32 bits, and loads the ~400 GB capped graph plus ~200 GB of features into memory on ~20 workers, each owning 15 M of the 300 M members active in 30 days. For each member it walks ties of ties, adding 1 / log(the middle member’s degree) per path, then adds cohort candidates (same company with overlapping dates, same school within two years) and contact-import matches, ~5 k unique candidates each. A cheap score keeps 500; a gradient-boosted ranker trained on invitations sent and accepted keeps 200, which are bulk-loaded as a new version of the PYMK store and switched on after coverage and distribution checks. Serving reads the list plus the overlay, drops anyone now connected, invited, dismissed or blocked, and shows exact mutual counts from the live graph. The stream job writes the overlay within minutes for new members (their first connections’ ties, cohorts, contacts) and for every new connection. LinkedIn has described PYMK publicly in these terms: closing triangles, plus shared companies and schools, computed offline.

1. What do you train the ranker on, and what does it optimise?
   Impressions logged with list version, position and reason, labelled by what followed within a week: invited and accepted is positive, invited and ignored or reported as “I don’t know this person” is a strong negative, shown and skipped a weak one. Optimising accepted invitations rather than clicks or sends keeps the model from rewarding suggestions that become spam invitations. Position bias and exploration are handled the way any recommender handles them.
2. A member with 30 k connections: how do you stop them appearing in everyone’s list?
   Two caps and a weight. As a middle member they add at most their 100 strongest ties to anyone’s count, not 30 k, and each path through them counts 1 / ln(30 000) ≈ 0.1 against ~0.26 through a 50-connection colleague. As a candidate, the ranker sees their degree and how their invitations fare, so someone who accepts everyone but whom few people actually know ranks low. Members with unusually high inbound suggestion rates can also be rate-limited as candidates.
3. Tonight’s batch fails. What do members see?
   Yesterday’s version, because the pointer only flips after validation. Lists are two days old instead of one, the read-time filter still removes anyone connected since, and the overlay still adds suggestions from new connections. A second missed night is an incident; one is invisible.
4. At 10× the members the capped graph is ~4 TB even delta-encoded. Now what?
   Splitting members across workers does not help by itself, because the ties of any slice of members lead almost everywhere in the graph. Machines with several TB of RAM exist, so the first option is to keep the no-shuffle design on ~20 of them, with candidate generation growing from minutes to about an hour. The second is to shard the capped graph and run the walk as a distributed join, with the shuffle grown to ~480 TB. I would keep the big machines while they exist, because the job stays simple, and treat the join as the fallback; serving does not change either way.
5. How do you know PYMK got better, not just different?
   An A/B test randomised by member, with accepted invitations per member per week as the primary metric and guardrails on ignored invitations, “I don’t know this person” reports and members hitting their invitation quota, which catch a model that drives spam. Offline, replay yesterday’s lists against the connections people actually made today. And coverage, the share of active members with a non-empty list, is tracked per version, because a silent drop there can look like a quality win in averages.