Design People You May Know
Problem
Design the "People You May Know" (PYMK) module of a social network, which suggests other members a user might want to connect with. Suggestions are based mainly on mutual connections, and can also use shared schools, workplaces, and imported contacts. Each user sees a ranked list of suggestions that loads quickly on the home page and on a dedicated page. Users can dismiss a suggestion and never see it again, and suggestions should reflect new connections within a day. The network has 1 billion members, 300 million daily active users, and an average of 400 connections per member.
- What is the goal metric: accepted connection requests, requests sent, or long-term engagement after connecting?
- How fresh must suggestions be? Is a daily refresh acceptable, with faster updates only for brand new users?
- Which signals are allowed for privacy reasons? Can we use imported address books and profile views?
- Should suggestions be symmetric, or can A see B without B seeing A?
- How many suggestions does a page show, and is infinite scroll needed?
- Are there blocked users, private profiles, or minors who must never be suggested?
Items in bold are existing requirements. The rest are suggestions. Confirm with the interviewer whether they are relevant first.
- Generate connection suggestions for each user, driven by mutual connections.
- Return a ranked list of suggestions with the mutual connection count shown.
- Let users dismiss a suggestion permanently.
- Reflect new connections in suggestions within 24 hours.
- Use secondary signals such as shared employer, school, and imported contacts.
- Give brand new users useful suggestions within minutes of signing up.
- Never suggest blocked users, existing connections, or people with pending requests.
Items in bold are existing requirements. The rest are suggestions. Confirm with the interviewer whether they are relevant first.
- Serve 300 million daily active users; at 3 page views with the module each, that is about 10,000 reads per second on average and 30,000 at peak.
- Read latency under 100 ms at p99, since the module renders on the home page.
- The graph holds about 200 billion connections, or 400 billion adjacency entries when each is stored in both directions, roughly 2 TB as compressed adjacency lists.
- Friends of friends explode quickly: 400 times 400 is 160,000 two-hop paths per user before deduplication, so naive online computation is not an option.
- Precompute 200 candidates per active user: 300 million times 200 times 16 bytes is about 1 TB in the serving store.
- Availability over freshness: a stale suggestion list is fine, an empty module is not.
An offline pipeline computes friends of friends for every active user once a day on a distributed graph engine, joins in secondary signals, and writes about 200 scored candidates per user to a key-value serving store. At request time a PYMK service reads the candidates, removes anyone the user has since connected with, blocked, or dismissed, reranks the top few hundred with a lightweight model using fresh features, and returns a page. A near-real-time path recomputes candidates for new users and for users who just made several new connections.
Loading diagram...
Daily batch. Each night the social graph is snapshotted to the data lake. The batch pipeline computes, for every active user, the set of second-degree connections with their mutual counts, adds candidates from shared employers, schools, and address book matches, computes features for each pair, scores them with the offline ranking model, and writes the top 200 to the candidate store keyed by user ID.
Load suggestions. The client calls GET /pymk?limit=20. The PYMK service reads the user's candidate list, removes existing connections, pending requests, blocks, and dismissals using the exclusion store, fetches fresh features (for example, whether the candidate was active today), reranks with the online model, and returns the top 20 with mutual counts and a short reason such as "12 mutual connections".
New user or burst of connections. A connection event arrives on the event stream. If the user is new or has added several connections since the last batch, the realtime worker reads one and two hops from the live graph with a fan-out cap, scores the results, and overwrites that user's candidate list within minutes.
Feedback. Impressions, dismissals, and sent requests are logged to the event stream. Dismissals are written to the exclusion store immediately, and all events become training labels for the next model.
Offline job that turns the full social graph into scored candidate lists for every active user.
- Spark on a daily graph snapshot stored as Parquet adjacency lists.
- A gradient boosted tree model for offline scoring.
Diagram
Loading diagram...
Scalability
The friends-of-friends join is the expensive step. For each member M, every pair of M's connections becomes a candidate pair, which is quadratic in degree, so hub accounts with tens of thousands of connections are excluded as intermediaries (or sampled), since a shared hub says little about real affinity. The job runs only for users active in the last 30 days, and writes are bulk loaded as immutable files rather than individual puts.
Tradeoffs
Precomputing daily trades freshness for cost and latency: online two-hop traversal for 30,000 requests per second would touch billions of edges per second. The realtime worker covers the cases where staleness hurts most, new users and users actively growing their network.
Online service that assembles the final list for a request.
- Stateless Java or Go service with a local cache of model weights.
API
GET /pymk?limit=20&cursor=returns{ suggestions: [{ userId, mutualCount, reason }], nextCursor }.POST /pymk/:candidateId/dismisshides a candidate permanently.POST /pymk/impressionswith a batch of shown candidate IDs, used for ranking and fatigue.
Scalability
Each request is one key lookup for candidates, one batched lookup for exclusions, and one batched feature fetch, so the tier is CPU bound on reranking and scales horizontally. Results are cached per user for a few minutes to absorb page refreshes.
Tradeoffs
Reranking online with a small model lets fresh signals (a candidate who was just shown five times and ignored) change the order without waiting for the batch. A heavier model is kept offline where latency does not matter.
Key-value store that holds each user's precomputed candidate list.
- A read-optimized key-value store built for bulk-loaded derived data, such as Venice, or DynamoDB loaded through table imports.
Data Model
candidates:user_id(key), value is a compact list of{ candidate_id, score, mutual_count, reason_code }, pluscomputed_at.exclusions:user_id(partition key),excluded_id(sort key),reason(dismissed, blocked, connected, pending).
Scalability
About 1 TB of candidate data fits easily across a sharded cluster partitioned by user ID. Daily refresh writes a full new version and atomically switches readers to it, so readers never see half-updated data.
Tradeoffs
Keeping exclusions in a separate store, rather than rewriting candidate lists on every dismissal, keeps the write path tiny and makes dismissals take effect instantly. The cost is an extra lookup per request.
Source of truth for connections, used by the realtime worker and snapshotted for the batch pipeline.
- A sharded graph store built on MySQL or a purpose-built adjacency list service, with an in-memory cache of adjacency lists.
Data Model
edges:user_id(partition key),friend_id,created_at, stored in both directions.
Scalability
Shard by user ID so a user's adjacency list is one lookup. Two-hop traversal for the realtime path fetches up to 400 neighbor lists in parallel and caps each at the 200 most recent connections to bound the work.
Tradeoffs
A general-purpose graph database is tempting, but PYMK only needs one and two hop adjacency reads plus a bulk export, which a sharded adjacency list does more cheaply and predictably at a billion members.
Stream consumer that recomputes candidates for users whose network changed quickly.
- Kafka consumer group or a Flink job reading connection events.
Scalability
Only a small fraction of users qualify for a realtime refresh on a given day, and work per user is capped, so a modest consumer group keeps up. Updates for the same user within a few minutes are coalesced into one recomputation.
Tradeoffs
Recomputing everyone in real time would duplicate the batch at much higher cost. Limiting the path to new and fast-growing users captures most of the value, since these are the moments when good suggestions most increase connections.