Design Facebook a social network

What we are building

Facebook is an online social networking service. Members create a profile, connect with one another as friends, follow people and pages without friending them, join groups, publish posts, comment on and like posts, message each other, and search across members, groups, pages, and post text. This lesson walks through the object model that supports those behaviours and then dwells on one small method, SearchIndex.addMember, because the way it is written in the source material does not actually compile or behave the way its surrounding prose claims. Getting that one method right is a good lens on how a search index over a social graph is supposed to work.

The system supports several core requirements: members maintain a profile (work, education, basic info); anyone can search members, groups, and pages by name; members send, accept, and reject friend requests; members follow others without friending; members create and join groups and follow pages; members publish posts and add comments, likes, and shares; members build privacy lists and scope a post to a list; members message one another; members recommend pages; and the system notifies a member on a new message, friend request, or comment.

The classes at a glance

A handful of entities carry the model. Person is the abstract base for anyone with an account; Member extends it with the social-graph fields. Account holds credentials and status. Profile aggregates work history, education, places lived, and the member's photos and videos. Page and Group are followable and joinable entities. Post, Comment, and Message are the content types. SearchIndex is the cross-cutting service that makes members, groups, pages, and posts findable by name or by word.

The search index, and a bug worth dwelling on

SearchIndex implements a Search interface. The idea is sound: keep one hash map per searchable kind, mapping a key to the list of entities that share it. Two different members can share the name "John Smith," so the value type is a list, not a single member:

public interface Search {
  List<Member> searchMember(String name);
  List<Group>  searchGroup(String name);
  List<Page>   searchPage(String name);
  List<Post>   searchPost(String word);
}

public class SearchIndex implements Search {
  HashMap<String, List<Member>> memberNames = new HashMap<>();
  // ... groupNames, pageTitles, posts, all List-valued ...

  public boolean addMember(Member member) {
    if (memberNames.containsKey(member.getName())) {
      memberNames.get(member.getName()).add(member);   // key present
    } else {
      memberNames.put(member.getName(), member);        // key absent  ← BUG
    }
    // ...also: no return value
  }
}

Read the two branches carefully, because it is easy to describe them backwards. The map is keyed by name, and the value is a List<Member>.

• The if branch fires when the key is already present — i.e. a list for that name already exists — and appends the new member to it with .add(member). That is exactly right.
• The else branch fires when the key is absent — i.e. on the first insert for that name, before any list exists. This is where the bug lives.

The bug is in that first-insert path: memberNames.put(member.getName(), member) stores a bare Member as the map value, but the map's declared value type is List<Member>. The types do not match, so the line does not even compile. And the intent it was reaching for is also wrong: the first insert is supposed to seed a new list containing this one member, so that a later second member with the same name has a real list for the if branch's .add() to append to. Because the else never creates a list, the .add() target in the if branch would never be a proper list even if the code did compile. The method also declares boolean but returns nothing.

The fix is to seed a fresh list on the first insert and append on every later one — the standard get-or-create pattern, expressed cleanly with computeIfAbsent:

public boolean addMember(Member member) {
  if (member == null || member.getName() == null) return false;
  memberNames
      .computeIfAbsent(member.getName(), k -> new ArrayList<>())
      .add(member);
  return true;
}

public List<Member> searchMember(String name) {
  return memberNames.getOrDefault(name, Collections.emptyList());
}

Now the first insert for a name creates the list (the old else's real job), every later insert appends to it (the old if's job), the value is always a List<Member> so it compiles, and searchMember hands back an empty list rather than null for an unknown name.

Tracing two inserts and a search

To see why seeding the list on the first insert matters, trace the corrected addMember with two members who happen to share the name "Ann Lee," followed by a search. The action column shows the get-or-create decision computeIfAbsent makes on each call.

The first row is precisely the case the original else branch was meant to handle and got wrong: on the first insert there is no list yet, so the index must create one. The second row is the original if branch, which was already correct. With both paths funneled through computeIfAbsent, the two cases collapse into a single, branch-free expression that always leaves a List<Member> in the map.

Beyond the search index: friend requests, privacy, and feed

A real social-network design interview does not stop at one corrected method. The three topics below are the follow-up questions a senior interviewer will ask next.

Two modeling cautions before we go there. First, scope discipline: in a 45-minute LLD round, model the graph, posts, privacy, and search well — do not sprawl into messaging, ads, and ML ranking unless the interviewer explicitly pivots you to HLD; breadth without depth reads as junior. Second, composition over inheritance for entities: it is tempting to make Page extends Member or Group extends Member because "they all have a name and can be searched," but that is a classic is-a/has-a error — a Page is not a kind of user, it does not send friend requests or have a login. Model the shared bits (name, searchability) as a small interface or a composed field, and keep Profile and Account as things a Member has, not things it is.

Friend-request state machine

A friend request is not a boolean; it has a lifecycle. Model it explicitly so you can enforce rules such as "only a pending request can be accepted" and "block prevents a new request."

Why a state machine: it collapses fuzzy rules into explicit transitions. Without it, code ends up with scattered if checks for "can I accept this?" in every service method.

enum FriendRequestStatus { PENDING, ACCEPTED, REJECTED, CANCELLED, BLOCKED }

class FriendRequest {
  private final Member from;
  private final Member to;
  private FriendRequestStatus status;

  public void accept() {
    if (status != PENDING) throw new IllegalStateException(...);
    status = ACCEPTED;
    from.addFriend(to);
    to.addFriend(from);
  }
}

Privacy lists and post scoping

Members do not broadcast every post to everyone. A post has an audience. Common scopes are:

• PUBLIC — anyone, even non-friends.
• FRIENDS — all current friends.
• CUSTOM_LIST — a named privacy list such as "Family" or "Work".
• SELF — only the author.

At post time the author picks a scope. At read time the feed generator checks whether the viewer is in that scope. A privacy list is just a set of Member references owned by one member; the post stores the list ID, not a copy of the members, so edits to the list apply retroactively to visibility.

The alternative — and why you should name it out loud. The opposite design is to snapshot the audience at publish time (copy the member IDs into the post). The two are a real product trade-off, not an implementation detail: storing the listId means adding "Family" today changes who can see a post you made last year (edits apply retroactively); snapshotting freezes the audience to whoever was in the list at publish, so later edits never widen or narrow an old post's reach. A senior answer states which one it picks and why — most consumer social networks choose the listId (live) semantics because users expect "who's in my Family list" to be one current thing, but a compliance-sensitive context (a post that legally must never become visible to someone added later) argues for the snapshot.

class Post {
  private final Member author;
  private final PostVisibility visibility;
  private final PrivacyList privacyList; // null unless CUSTOM_LIST
  private final String content;

  boolean isVisibleTo(Member viewer) {
    switch (visibility) {
      case PUBLIC:  return true;
      case FRIENDS: return author.getFriends().contains(viewer);
      case CUSTOM_LIST: return privacyList.contains(viewer);
      case SELF:    return viewer.equals(author);
      default:      return false;
    }
  }
}

Feed generation: two architectures

Pull (fan-out on read). When a user opens their feed, the system queries recent posts from every friend, merges and ranks them, and returns the top N. Simple but slow for users with many friends; fine for small scale or demonstration.

Push (fan-out on write). When a user creates a post, the system immediately inserts it into a feed cache for every member in the audience. Reading the feed becomes a single key lookup. This is how Facebook operates at scale, with a hybrid fallback for celebrities with millions of followers (push to active users, pull for the long tail).

Celebrity hybrid: numbers and failure modes

Threshold rule of thumb used in interviews: treat accounts with > ~10k–100k followers (or a measured "hot" tier) as celebrities. Ordinary users: full push fan-out on write. Celebrities: push only to online / highly-active followers (e.g. active in last 7 days); everyone else pulls celebrity posts when they open the feed. Concrete example: 50M followers, 2% active weekly → push ~1M keys, not 50M.

Partial fan-out failure (worker crash mid-push). Job must process followers in ordered pages with a durable cursor:

// Fan-out job state
// postId=P, lastFollowerId=F_k, status=RUNNING
// Worker dies after pushing to followers F_1..F_k
// On restart: resume WHERE follower_id > F_k ORDER BY follower_id
// Idempotent insert into feed_cache (post_id, follower_id) UNIQUE
// so retries do not duplicate lines

Without a cursor: some followers see the post, others never will, and a full restart double-writes. Ops signal: fan-out lag / incomplete job metrics; alert when jobs stay RUNNING past SLA. Cache stampede on celebrity pull: many inactive users open the app after a viral post and all miss cache — mitigate with singleflight / request coalescing on the celebrity timeline key.

Concurrent friend-request CAS

Two devices can accept/reject the same PENDING request, or both users send requests to each other. Enforce transitions with conditional updates:

// Accept only if still PENDING (CAS on status)
UPDATE friend_request
SET status = 'ACCEPTED', version = version + 1
WHERE id = ? AND status = 'PENDING' AND version = ?;
// rows == 0 → already decided; do not addFriend twice

// Symmetric send: unique pair key LEAST(a,b), GREATEST(a,b)
// so A→B and B→A cannot both stay PENDING

Takeaways

• Model friend requests as a state machine, not a boolean, so lifecycle rules are explicit and testable; CAS the status transition.
• Store post visibility as a scope + optional privacy-list reference; evaluate visibility at read time so list edits take effect immediately.
• Feeds trade read cost against write cost: pull is simpler, push is faster at scale; most real systems use a hybrid with a celebrity threshold and resumable fan-out jobs.
• SearchIndex is one piece of a larger design; correctness in small methods (like addMember) is necessary but not sufficient for a senior OOD answer.

Recall question

You are designing the feed for a social network. A celebrity with 50 million followers posts. Why is pure push fan-out a bad idea, and what hybrid would you use? What happens if the fan-out worker crashes halfway?

Answer: Pushing to 50 million caches in real time creates a write burst and wastes space for followers who never open the app. A hybrid pushes to highly-active followers and leaves the rest for pull on read. Mid-crash partial push is recovered with a durable job cursor over follower ids and idempotent feed inserts so resume does not duplicate or skip permanently.

Source

Based on the "Design Facebook — a social network" object-oriented design problem, Grokking the Object Oriented Design Interview (Design Gurus / Educative). The original SearchIndex.addMember listing is reproduced from that source; the control-flow analysis and computeIfAbsent correction, friend-request state machine, privacy scoping, feed fan-out, celebrity hybrid failure, and concurrent accept CAS are this lesson's own.