Designing a Social Graph and Friend Recommendations

A social graph stores relationships between users and answers queries such as who are my friends, do we share friends, and who might I know. Recommendations are then computed by traversing and scoring that graph.

Requirements

Functional

• Add and remove friendships (mutual) and follows (directed).
• List a user's friends or followers, paginated.
• Check whether two users are connected; count mutual friends.
• Suggest people you may know.

Non-functional

• 1B users, average 200 connections, so roughly 200B edge entries (each mutual friendship is stored twice).
• Edge lookup under 10 ms at p99; friend list page under 50 ms.
• Reads outnumber writes about 1000 to 1.
• Recommendations can be hours stale but must be filtered immediately on block or unfriend.

Capacity estimation

• 100B mutual friendships stored in both directions is 200B directed rows at 16 bytes (two 8 byte IDs), about 3.2 TB, and 10 TB with indexes and replication overhead per copy. This is small enough to shard across a few dozen to hundreds of machines.
• Read traffic: 100M daily users each triggering 50 graph reads is 5B per day, about 58,000 per second average, peak 200,000.
• Writes: 50M edge changes per day, about 600 per second.
• Recommendation compute: candidate generation touches roughly 200 x 200 = 40,000 friends of friends per user, so compute it offline in batch.

High-level design

Client -> API -> Graph Service -> Cache (adjacency lists, hot users)
                       |
                       v
           Sharded edge store (by user_id)

Edge change events -> Kafka -> Graph index updaters (reverse edges, counts)
                           \-> Offline pipeline (Spark/graph jobs)
                                   -> Candidate generation -> Ranking model
                                   -> Recommendations store (user_id -> list)
Client -> Recommendation Service -> Recommendations store -> filter (blocks, existing)

Data model

edges(user_id, other_id, type, created_at)   PK (user_id, other_id)
   -- a mutual friendship writes two rows, one per owner
counts(user_id, friend_count, follower_count)
recommendations(user_id, [ (candidate_id, score, reasons) ])

Because each user owns their outgoing rows, sharding by user_id keeps one user's adjacency list on a single shard. A friendship spans two shards, so writes use a transaction, or two idempotent writes driven from a log for eventual consistency.

Deep dives

Storage choice. A graph database is not required. Most social queries are one or two hops, which an adjacency list in a sharded key-value or relational store handles well with cache. Deeper traversals are done in offline batch.

Sharding and hot users. Hash by user_id. Celebrity accounts have millions of followers and create skew. Store follower lists for hot accounts in chunks across multiple rows, and cache counts separately so they never need a scan.

Mutual friends. Intersect two adjacency lists. With sorted lists the cost is linear in their sizes, around 400 elements. Cache hot pairs. For users with huge lists, restrict to friends versus friends and use Bloom filters.

Friend of friend candidates. Offline, for each user collect friends of friends, count the number of mutual friends, and drop existing connections and blocked users. Additional signals: shared workplace or school, same city, contact book matches (with consent), and recent profile views. Rank with a model using features such as mutual friend count, interaction frequency and recency, then store the top 50.

Serving. The recommendation service reads precomputed lists, re-applies live filters (blocks, pending requests, dismissed suggestions), and shuffles slightly for variety. A few fresh signals, such as a newly accepted friend, can be handled by an online incremental job that updates just the affected users' neighbours.

Consistency. Edge adds and removes should be visible quickly to the actors. Use read-your-writes through session stickiness or by updating the cache write-through. Counts may lag slightly.

Privacy. Respect visibility settings and blocks in every query path, including mutual friend counts, since leaking a hidden connection is a privacy failure.

Failure modes and trade-offs

• Half-written friendship: one direction written, the other lost. Drive both from a durable log with idempotent apply, and run a reconciliation job.
• Stale recommendations: a suggested user may have blocked you. Always filter at serve time.
• Hot shard: a celebrity follow storm; use chunking, replicas and cached counters.
• Batch cost versus freshness: daily full recompute is simple and cheap; hybrid incremental updates improve freshness at complexity cost.
• Directed versus mutual edges change storage and write patterns, so model them as separate edge types.

Key takeaways

• Adjacency lists in a sharded store, plus cache, cover almost all online queries.
• Store each edge under both endpoints and keep them consistent through an idempotent log.
• Friends-of-friends scored by mutual connections and interaction signals drives most good suggestions.
• Compute recommendations offline, but apply blocks and privacy filters at serve time.
• Plan for skew from celebrity accounts from day one.