Engineering Atlas › Low-Level Design

Code a social network with friends and posts

16 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

Requirements

Functional

Non-functional

Out of scope

Entities and relationships

User has an id, a display name and a privacy default. Users are nodes; everything interesting is an edge.

FriendRequest links a sender to a recipient with a status: pending, accepted, declined or cancelled. Only pending requests drive behaviour; the rest are history, useful for abuse analysis.

Friendship is the symmetric edge. One record keyed by the ordered pair (smaller id, larger id) makes "exactly one edge" true by construction; two adjacency entries, one in each user's friend set, make "list my friends" and "are we friends?" cheap. In memory we use adjacency sets and update both sides in one critical section.

Block is a directed edge from the blocker to the blocked user, but its effect is symmetric: neither side sees the other. It is directed because only the blocker can lift it.

Post has an id, an author, text, a timestamp and an Audience. Comment and Reaction hang off a post and inherit its audience.

AudiencePolicy is the single place that answers "may viewer V see post P?" SocialNetwork is the facade with one method per user action, coordinating the graph, the posts and the policy.

Class diagram

classDiagram
    class User {
        +id
        +name
    }
    class FriendRequest {
        +from
        +to
        +status
        +accept()
        +decline()
    }
    class SocialGraph {
        +areFriends(a, b) bool
        +isBlocked(a, b) bool
        +friendsOf(u) set
        +befriend(a, b)
        +sever(a, b)
    }
    class Post {
        +id int
        +author
        +text
        +ts int
        +audience Audience
    }
    class Audience {
        <<interface>>
        +allows(viewer, author, graph) bool
    }
    class PublicAudience
    class FriendsAudience
    class OnlyMeAudience
    class AudiencePolicy {
        +canView(viewer, post) bool
    }
    class SocialNetwork {
        +sendRequest(from, to) string
        +accept(user, requester)
        +block(a, b)
        +post(author, text, audience, ts) int
        +feed(viewer, limit) list
        +suggestions(user, k) list
    }
    Audience <|.. PublicAudience
    Audience <|.. FriendsAudience
    Audience <|.. OnlyMeAudience
    Post --> Audience
    Post --> User
    FriendRequest --> User
    SocialGraph --> User
    AudiencePolicy --> SocialGraph
    AudiencePolicy --> Audience
    SocialNetwork --> SocialGraph
    SocialNetwork --> AudiencePolicy
    SocialNetwork --> Post

Key flows

The flow that shows why privacy is read-time is "Bea unfriends Ali, then Ali opens his feed". Nothing is deleted from Ali's feed when Bea unfriends him. The feed is assembled on read, and each candidate post passes through the policy, which reads the graph as it is now.

sequenceDiagram
    participant B as Bea
    participant A as Ali
    participant S as SocialNetwork
    participant G as SocialGraph
    participant P as AudiencePolicy
    B->>S: unfriend(bea, ali)
    S->>G: sever(bea, ali)
    G-->>S: both adjacency sets updated
    A->>S: feed(ali, 20)
    S->>G: friendsOf(ali)
    G-->>S: {cem}
    S->>S: candidates = posts by ali and cem
    loop each candidate
        S->>P: canView(ali, post)
        P->>G: isBlocked, areFriends
        P-->>S: true or false
    end
    S-->>A: newest 20 visible posts

Bea's friends posts are no longer candidates, and if Ali opens one by a direct link, the policy rejects it too. One graph change closes both doors.

Crossing requests are the other interesting flow. If Bea sends Ali a request while his request to her is pending, the second send_request turns the pair into a friendship. Without this rule, both users see "request sent" and wait for each other.

Design patterns used and why

Strategy for audiences. PublicAudience, FriendsAudience and OnlyMeAudience each implement allows(viewer, author, graph). Adding friends_of_friends is a new class, not a new branch in if chains spread across feed, profile and search code. The policy wraps the strategies with rules common to all of them: the author always sees their own post, and a block always wins.

Specification for composite rules. "Friends, except Dan" combines predicates. A Specification (and, or, not over small predicates) expresses that without a class per combination. Start with Strategy; move to Specification when product asks for exclusions.

State for friend requests. A request moves from pending to accepted, declined or cancelled and never back. Encoding that as a state machine stops bugs like accepting a request that was already declined because two devices were open.

Facade. SocialNetwork gives controllers one call per user action. Block touches the friendship, both request directions and the block set; callers should not coordinate those.

Observer for side effects. FriendshipCreated and PostCreated events feed notifications, the suggestions index and the feed cache, which can be slow or fail without blocking the action.

Concurrency and edge cases

Two sides of one friendship

Accepting a request writes two adjacency entries and deletes one pending request. In memory, do all three under one lock (or a lock per user pair, acquired in id order so two concurrent operations on the same pair cannot deadlock). In a sharded store the two users often live on different shards. Facebook's TAO paper describes exactly this: a friend edge has a configured inverse type, TAO writes the inverse first and then the forward edge, does not make the two writes atomic, and repairs any hanging association with an asynchronous job. That is a deliberate trade: symmetric edges are cheap to read and occasionally need repair.

Crossing requests and double taps

Two send_request calls between the same pair can race. Under a pair lock, the second one either sees the first (and auto-accepts or reports already_requested) or runs first itself. In a database, a unique index on the ordered pair for pending requests gives the same guarantee.

Block beats everything

A block removes the friendship and both pending requests, and makes every post invisible in both directions, including public ones. It also prevents new requests in both directions. Unblocking removes only the block edge. Restoring the friendship automatically would surprise the blocked person, who may have been blocked for a reason.

Audience changes and comments

Narrowing a post from public to friends takes effect on the next read automatically; a feed cache must still filter on read or be invalidated by an AudienceChanged event. A comment is visible only to its post's audience, whatever the commenter's own settings, or comments become a side channel that leaks the post.

In the wild

Down the stack

Layer 1The contract

For any two users, are_friends(a, b) == are_friends(b, a). At most one pending request exists per ordered pair, and never two crossing ones. can_view(v, p) is true when v is the author. Otherwise it is false whenever either user blocks the other, and otherwise it follows the audience. Every read, including feeds, applies can_view against the graph as it stands at that moment. A rejected action changes nothing.

Layer 2The mechanism

Friend sets are hash sets, so "are we friends?" is one O(1) membership test, and mutual friends is an intersection costing O(min(|A|, |B|)). "People you may know" counts, for each friend f, every friend of f who is not u, not a friend and not blocked. That costs the sum of the friends' degrees: 300 friends with 300 friends each is about 90,000 increments, so production systems precompute candidates offline.

The feed is a k-way merge of per-author lists already in time order. Push each author's newest post onto a max-heap keyed by (ts, id), pop the top, check can_view, and push that author's next post. Twenty results from 300 friends cost about 170 heap comparisons plus 20 policy checks, however much each friend has posted. TAO keeps association lists newest first for the same reason: assoc_range reads the head without scanning the rest.

Layer 3The machine

A CPython set of 500 friend ids reports about 32 KB from sys.getsizeof (a 2,048-slot table at 16 bytes per slot, hash plus pointer), before the id strings themselves. A Go map[string]bool stores a 16-byte string header and a byte per entry in 8-entry buckets, roughly 15 KB for 500 friends. Facebook caps a profile at 5,000 friends, where the Python set is about half a megabyte. A membership test touches one or two cache lines, about 50 to 100 ns on a cache miss. A policy check is therefore far cheaper than the network hop that fetched the post. A heap of 300 tuples is a contiguous array, so the merge stays in L1 and L2 caches.

Why it's built this way

Relationships change constantly and privacy mistakes are expensive, so privacy is evaluated on read against the live graph. Read-time checks run on every post shown, so the graph must answer membership in O(1), which means hash sets keyed by user. Symmetric friendship read from either side needs two adjacency entries, and two entries can disagree, so writes to both sides go under one lock in memory or get a repair job across shards. Feeds read only the newest few posts of many authors, so per-author lists are kept sorted and merged with a heap instead of sorted from scratch. This is the shape Facebook's TAO stores: objects, typed associations with inverse edges, and time-ordered association lists. Google's Zanzibar answers the same "may this user see this?" question from relationship tuples.

Extensibility

Variant: professional networking (LinkedIn-style)

A professional network keeps the same graph machinery but changes the relationship rules and the read that matters most.

Two relationships, not one. A connection is symmetric and needs consent, like friendship. A follow is one-way and needs none, and connecting implies following in both directions. Model Connection and Follow as separate types, because they have different rules. One Relationship class with a type flag ends up as a pile of if statements.

A richer invitation. The invitation is a State pattern object (pending, accepted, ignored, withdrawn) and carries a note and a sender-side rate limit over a rolling week, so the network cannot be used for bulk outreach. A withdrawn invitation does not refund its slot, and a rejected attempt consumes nothing. Ignoring is not blocking: decide whether the sender may retry at once, after a cool-down, or never. Crossing invitations resolve as in friend requests: the second one accepts the first. Accept and withdraw race, so both are conditional updates on status = 'PENDING', and exactly one wins.

Degree is the new core query. Every profile and search result shows 1st, 2nd, 3rd or out of network, plus mutual connections. Degree is a breadth-first search capped at three hops. Searching from both ends and expanding the smaller frontier turns a three-hop question into two short expansions that meet in the middle (bidirectional search). Mutuals are a set intersection that iterates the smaller set and probes the larger. The cost explodes with depth: with around 500 connections each, second degree is up to 250,000 ids and third reaches tens of millions. So a page view never runs a full search. Production systems cache second-degree sets and accept seconds of staleness. At hundreds of millions of members the adjacency leaves the process entirely; LinkedIn built its own graph database for this (LIquid).

Different consistency budget. Privacy here is mostly profile visibility by degree, so a stale degree badge is cosmetic, unlike a stale friends-only post. Accept must still create the edge and close the invitation together, in one transaction or as an idempotent edge write driven by invitation state. Everything downstream (feeds, counters, suggestions) runs on a ConnectionCreated event after commit and may lag.

What carries over. Blocks still override everything, and "people you may know" still ranks second-degree members by mutuals. A block also removes a member from any degree path.

Leadership lens

Check yourself

  1. Why not filter posts at write time by copying each post only into the feeds of people allowed to see it?

    Show answer

    The allowed set changes after the post is written: an unfriend, a block or an audience edit would leave stale copies that still show the post. A read-time check against the live graph is the only way to make those changes take effect on the next read.

  2. Ali and Bea each send the other a friend request at almost the same moment. What should the system end up with?

    Show answer

    One friendship and no pending requests. Whichever request is processed second sees the opposite pending request and accepts it instead of creating a crossing request.

  3. Bea blocks Ali, then unblocks him a day later. Are they friends? Can Ali see Bea's public posts?

    Show answer

    They are not friends, because the block severed the friendship and unblock does not restore it. Ali can see Bea's public posts again, because only the block was hiding them.

  4. Why does a comment on a friends-only post not become visible to the commenter's own friends?

    Show answer

    A comment inherits the post's audience. Showing it to a wider audience would leak the existence and context of the post.

Sources and further study

Primary

Engineering blogs

Reference

Books

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →