Skip to main content

Design a Friend Recommendation System

Friend recommendation systems suggest new connections—people a user might know or want to connect with. Facebook’s “People You May Know”, LinkedIn’s “People You May Know”, Instagram’s Suggested Accounts, Snapchat’s Quick Add, and X’s Suggested Users all rely on sophisticated graph traversal and ranking algorithms. Unlike content recommendations that predict user preferences for items, friend recommendation is fundamentally a graph problem: you must explore the social graph around a user, generate plausible candidates, and rank them by relevance, all while operating at the scale of billions of nodes and edges.

This article presents a comprehensive architecture for building a friend recommendation system from scratch, covering graph modeling, candidate generation, ranking, serving, and scaling.

Step 1: Requirements Clarification​

Functional Requirements​

  • Recommend people to connect with – Show a list of potential friends/connections.
  • Mutual friend recommendations – Candidates with many mutual friends should rank highly.
  • Colleague recommendations – Suggest people who work at the same company.
  • School recommendations – Suggest alumni from the same educational institution.
  • Nearby people (optional) – Geographically close users who may know each other.
  • Contact-based recommendations (optional) – Use uploaded address books to find matches.
  • Hide existing friends – Do not recommend users who are already connected.
  • Ignore blocked users – Respect block lists and hidden profiles.
  • Refresh recommendations – Users should see fresh candidates periodically.
  • Personalized ranking – The most relevant people should appear first.

Non-Functional Requirements​

  • Low latency – Recommendations must load within a few hundred milliseconds.
  • High availability – The service should be 99.95%+ available.
  • Horizontal scalability – Must support billions of users and trillions of edges.
  • Personalized results – Recommendations should reflect individual user context.
  • Fresh recommendations – New connections and profile updates should influence results quickly.
  • Fault tolerance – Partial failures should not break the entire recommendation list.
  • High graph query performance – Graph traversals (e.g., friends of friends) must be fast.

Step 2: Capacity Estimation​

Assume a large social network:

  • Registered users: 2 billion
  • Daily active users: 500 million
  • Average friends per user: 300 (undirected edges)
  • Total graph edges: 2B * 300 / 2 = 300 billion edges (considering undirected friendship)
  • Recommendation requests per second: 50,000 average, 200,000 peak.
  • Candidate pool per request: Up to 1,000 candidates derived from the graph.
  • Ranked results per request: 20-30 displayed.
  • Storage: Graph edges alone require ~300B edges * (source_id + dest_id + metadata) ~ 300B * 50 bytes ≈ 15 TB of raw edge data. With indexing and replication, several times that.
  • Cache: Hot recommendation lists and user profiles require terabytes of in-memory data.

Graph traversal becomes expensive at this scale because a single “friends of friends” query can touch hundreds of nodes and thousands of edges.

Step 3: API Design​

The system exposes REST APIs for fetching recommendations and providing feedback.

  • Get Friend Recommendations
    GET /api/v1/recommendations/friends?limit=30
    Returns { recommendations: [UserObject, ...], next_cursor }

  • Ignore Recommendation (dismiss)
    POST /api/v1/recommendations/friends/{user_id}/ignore

  • Connect with User (send friend request)
    POST /api/v1/friends/requests/{user_id}

  • Refresh Recommendations
    GET /api/v1/recommendations/friends?refresh=true

  • Record Feedback (internal)
    POST /internal/feedback – logs impressions, clicks, connects to improve model.

Pagination is cursor-based for the list of recommendations. Each recommendation item includes a user_id, display name, mutual friend count, and optionally shared context (e.g., “You both worked at Acme”).

Step 4: High-Level Architecture​

The architecture separates graph storage, candidate generation, and ranking into distinct services.

  • Recommendation Service orchestrates the request, combining candidate generation and ranking.
  • Candidate Generation Service performs graph traversal and rule-based candidate selection.
  • Social Graph Service provides an API to query relationships: friends, friends-of-friends, mutuals.
  • Ranking Service scores and orders candidates using features from the Feature Store.
  • Feature Store aggregates user profile attributes, graph counts, and interaction history.
  • Graph Storage persistently stores the massive social graph.
  • Recommendation Cache stores pre-computed recommendation lists for fast retrieval.
  • Event Collection captures user actions (clicks, connects, ignores) for feedback and model updates.

Step 5: Social Graph Modeling​

The social graph consists of nodes (users) and edges (relationships). For a friendship graph, edges are undirected; for a follow model, they are directed.

Storage Options

ApproachDescriptionProsCons
Relational DBStore edges as (user_id, friend_id) with indexes.Simple, familiar.Joins for “mutual friends” are expensive at billions of edges.
Graph Database (Neo4j, JanusGraph)Native graph storage with traversal-optimized queries.Efficient for deep traversals.Scaling to internet-scale is challenging; often requires partitioning.
Key‑Value Store (Redis, DynamoDB)Store adjacency lists: key = user_id, value = set of friend IDs.Very fast reads; horizontally scalable.Custom traversal logic needed; memory-intensive.
Distributed Graph Processing (Giraph, Spark GraphX)Batch processing on giant graphs.Handles massive scale for offline computation.Not suitable for low-latency online queries.

In practice, large platforms often use a sharded adjacency list stored in a wide-column database or Redis cluster. For online queries, the friend list is retrieved and “friends of friends” intersections are computed on the fly using memory-efficient algorithms (e.g., HyperLogLog for counts, Bloom filters for candidate deduplication). For heavy offline computations (e.g., updating recommendations for all users), distributed graph processing frameworks are used.

Step 6: Candidate Generation​

Candidate generation narrows the universe of billions of users down to a few hundred plausible recommendations. Common signals:

  • Mutual friends: The most powerful signal. If A and B are not friends, but share many friends, they likely know each other.
  • Friends of friends (FoF): For each friend of the user, collect their friends, then aggregate and count occurrences. The users with the highest FoF counts become candidates.
  • Common schools / employers: Use profile attributes to find people from the same institution or company.
  • Shared groups / communities: Membership in the same online groups.
  • Geographic proximity: People in the same city or who recently checked in nearby.
  • Imported contacts: Match uploaded contact lists against existing users.
  • Popular nearby users: In dense areas, recommend local people even without mutual connections.
  • Random exploration: A small percentage of candidates are non-obvious to allow serendipitous connections.

The candidate generation service must execute these queries efficiently. For example, “friends of friends” can be computed by fetching the user’s friend list (say 300 IDs), then for each friend, fetching their friend list (or a sampled subset) and aggregating counts in a hash map. With caching and optimized data structures, this can be done in under 10ms for typical users. For celebrities with millions of followers, graph sampling or pre-computed summaries are used.

Step 7: Ranking Pipeline​

Once candidates are generated, they are scored to determine the final order. Features used in ranking include:

  • Number of mutual friends – The strongest predictor.
  • Interaction intensity – How often do they like/comment on mutual friends’ content? (if available)
  • Profile similarity – Same company, school, city, interests.
  • Recent profile views – If a user recently searched for or viewed this person’s profile.
  • Account quality / trust score – To avoid recommending fake or spam accounts.
  • User activity – Active users are more likely to accept friend requests.
  • Recency – Freshness of the candidate in the pool; avoid stale suggestions.

Ranking often proceeds in two stages:

  1. Lightweight rule-based scoring using fast-to-compute features (mutual friends count, shared attributes) to prune the list to the top 100 candidates.
  2. Machine learning model (e.g., logistic regression, gradient boosted trees, or a neural network) trained on historical acceptance data to produce a final engagement probability. This model is served via a low-latency model serving platform.

The ranked list is then filtered: remove already existing friends, blocked users, and users who recently dismissed the recommendation.

Step 8: Recommendation Pipeline​

The following sequence diagram illustrates the end-to-end flow when a user requests recommendations.

  1. The client requests recommendations.
  2. If a fresh cached list exists, return it immediately.
  3. Otherwise, candidate generation runs graph traversals (friends of friends, shared attributes) to produce a candidate pool.
  4. The ranking service enriches candidates with features, scores them, and returns the top 30.
  5. The result is cached for a period (e.g., 1 hour) to serve subsequent requests quickly.
  6. The user sees the list; their actions (connect, dismiss, ignore) are fed back via events to update future recommendations.

Step 9: Caching Strategy​

Caching is essential to avoid expensive graph traversals on every request.

  • Recommendation cache: A Redis cache keyed by user_id, storing the precomputed list of recommended user IDs with scores. This list is refreshed asynchronously every few hours or when the user takes a significant action (e.g., adding many new friends).
  • Graph cache: The user’s friend list and frequently accessed adjacency lists are cached in a distributed cache to speed up candidate generation.
  • User profile cache: Basic profile data (name, photo, employer) is cached to avoid hitting the profile database for every rendered recommendation.
  • Feature cache: Aggregated features (mutual friend count, shared groups) for candidate pairs are pre-computed and cached to accelerate ranking.
  • Cache invalidation: When a user adds or removes a friend, their recommendation list and affected mutual friend counts are invalidated. This is handled by an event-driven invalidation worker.

Step 10: Scalability Strategies​

  • Horizontal scaling: All online services (Recommendation, Candidate Gen, Ranking) are stateless and scale out behind load balancers.
  • Graph partitioning: The social graph is partitioned by user ID. A user’s adjacency list (friends) resides on a single shard, allowing fast retrieval. For “friends of friends”, only the IDs are needed, which can be fetched from multiple shards in parallel and aggregated in-memory.
  • Distributed graph queries: For users with massive friend lists, pre-computed aggregations (e.g., top 100 mutual friends with each candidate) are stored and served instead of real-time computation.
  • Candidate cache: Besides per-user recommendation caches, popular candidate sets (e.g., trending new users in a region) can be cached globally.
  • Read replicas: For relational databases storing profile data, read replicas absorb the heavy read load.
  • Event-driven updates: When a user’s friend network changes, a message is published to Kafka. Asynchronous workers recompute the affected recommendation lists, decoupling user actions from online serving.
  • Regional deployment: For global latency, the entire stack is deployed in multiple regions, with graph data sharded such that a user’s data is co-located in their primary region.

Step 11: Reliability and Failure Recovery​

  • Retry strategies: Transient failures in graph queries or feature fetching are retried with exponential backoff.
  • Partial graph failures: If a shard of the graph database is temporarily unavailable, the system can fall back to a cached adjacency list or return a partial candidate set with a note.
  • Cache failures: On cache miss or failure, the system falls back to direct computation (though slower). Redis clusters are deployed with replication and auto-failover.
  • Ranking service degradation: If the ML ranking model is slow or down, a rule-based fallback (e.g., order by mutual friend count) ensures recommendations are still served.
  • Queue buffering: Event streams (Kafka) ensure that no feedback or update events are lost during traffic spikes.
  • Graceful fallback: In the worst case, a static list of popular or regional users can be served instead of personalized recommendations.

Step 12: Security and Privacy​

  • Authentication & Authorization: Only authenticated users can access recommendations, and a user can only see recommendations for their own account.
  • Privacy settings: Users who have opted out of being recommended (e.g., “Do not suggest my profile”) are excluded from candidate generation. Their setting is stored in the user profile and enforced at query time.
  • Block lists: If user A has blocked user B, B will never be recommended to A, and vice versa.
  • Hidden profiles: Users who limit visibility to friends will not appear in recommendations to non-friends.
  • Abuse prevention: Rate limiting on API requests; detection of automated account creation. New or low-quality accounts are deprioritized in ranking.
  • GDPR / Data deletion: When a user deletes their account, their node and all edges are removed from the graph, and their data is expunged from recommendation caches and training sets.
  • Bias and fairness: Monitoring the demographics of recommendations to ensure certain groups are not systematically excluded. The ranking model is audited for fairness.

Real-World Example: LinkedIn “People You May Know”​

LinkedIn’s “People You May Know” (PYMK) is a classic friend recommendation system. It heavily leverages the professional graph: connections, companies, schools.

  1. Alice opens LinkedIn; the recommendation service requests candidates.
  2. Candidate generation finds all 2nd-degree connections (friends of Alice’s connections) plus people who share her current or past company or school.
  3. Ranking scores each candidate using a model trained on historical connection acceptance data. Features: mutual connections count, shared employer/school, industry match, profile completeness.
  4. The top 30 are returned.
  5. When Alice sends a connection request to a recommended user, that positive signal is fed back into the system to improve Alice’s future recommendations and also influence the candidate’s ranking for others.

Trade-offs​

  • Recommendation quality vs latency: Deeper graph traversal (e.g., 3rd-degree connections) improves candidate diversity but increases query time. Staged candidate generation (quick FoF, then augment with slower signals) balances this.
  • Graph database vs relational database: Graph DBs offer natural traversal but are harder to scale horizontally. Sharded adjacency lists on key-value stores scale better but require custom traversal logic.
  • Freshness vs cache efficiency: Pre-caching recommendations reduces latency but may serve slightly outdated suggestions. A refresh interval of a few hours is acceptable for most social platforms.
  • Rule-based ranking vs ML ranking: ML models improve personalization but add complexity and serving latency. A hybrid approach uses rules for fast pruning and ML for final scoring.
  • Online computation vs precomputation: Real-time candidate generation provides the most up-to-date results but is resource-intensive. Precomputed recommendations (batch jobs at night) reduce load but are less responsive. Many systems use a combination: precomputed candidates with online ranking.

Common Mistakes​

  • Recomputing recommendations on every request without caching leads to overwhelming the graph database.
  • Ignoring blocked/hidden users – Showing blocked users as recommendations violates privacy and degrades trust.
  • No graph caching – Repeatedly fetching friend lists from the database for millions of requests creates a bottleneck.
  • Overusing graph database joins – Real-time deep joins (e.g., 4th-degree connections) don’t scale; rely on pre-aggregated counts.
  • Not separating candidate generation from ranking – Trying to rank the entire user base is impossible; generation must dramatically reduce the candidate set first.
  • No feedback loop – Without tracking which recommendations are accepted or dismissed, the system cannot improve.
  • Ignoring recommendation diversity – Always showing the same top candidates (e.g., only from current company) leads to a poor experience.

Interview Perspective​

Interviewers use friend recommendation to test your understanding of graph problems at scale. Common questions:

  • Design Facebook “People You May Know.”
  • How do you model the social graph?
  • How do you find mutual friends efficiently?
  • How do you scale graph traversal to billions of users?
  • How do you rank recommendations?
  • How do you cache recommendations?

Demonstrate the ability to think in terms of graph operations, sharding, and asynchronous processing. Show that you understand the trade-off between real-time computation and precomputation, and the importance of caching.

Summary​

A friend recommendation system is a specialized recommendation engine that leverages the social graph to suggest new connections. It combines graph storage (often sharded adjacency lists), candidate generation via “friends of friends” and attribute matching, and a ranking pipeline that scores candidates using mutual friend counts, profile similarity, and user interactions. Caching precomputed recommendations and graph data is critical for low latency and scalability. Asynchronous event processing enables feedback loops that continuously improve recommendation quality. By carefully balancing real-time traversal with precomputation, and enforcing privacy and safety constraints, a well-designed system can deliver the familiar “People You May Know” experience to billions of users.

Further Reading​