Design Social Network (Facebook)

A high school yearbook is the social network nobody calls a social network. Every student has a page with their photo and a few sentences. The back has a list of signatures from friends — Alice signed Bob's book, Bob signed Alice's, and because the signing always went both ways, the friendship is the same fact from either side. The classroom bulletin board next door collects little notes pinned in the order they got posted, and the newest note sits at the top because that is what a person reading the board wants to see first. Combine the yearbook with the bulletin board and you have the shape Facebook shipped in 2004 — pages that know who signs them, plus a stream of notes filtered down to the ones the reader actually cares about.

Mark Zuckerberg's first version ran on a single PHP file and a MySQL database with two tables — one for people, one for the friendship edges between them. The friendship table was the trick. Each row was a pair, and the rule the code enforced was that every friendship existed as two rows — Alice-to-Bob and Bob-to-Alice — so a lookup from either side took the same single query. That choice traded a small amount of storage for a huge amount of read speed, and the read speed mattered because the average user loaded their own friend list 50 times for every time they added a friend. Reid Hoffman at LinkedIn made the opposite call a year earlier — store the edge once, look it up with a more expensive query — and spent the next two years explaining to engineers why every page felt slow. The yearbook lesson is that a friendship is one fact stored twice, on purpose.

The room map for our network has four people printed on the inside cover — Alice, Bob, Carol, Dave — and two structures that grow as the day goes on. The first is the signature page. For each user, a sorted set of the people who have signed their book. The second is the bulletin board. A single list of notes in the order they got pinned, with a number on each note so the reader can sort them newest first without checking a clock.

#[derive(Debug, Clone)]
struct Post {
    id: u32,
    author: String,
    text: String,
}

struct Network {
    friends: BTreeMap<String, BTreeSet<String>>,
    posts: Vec<Post>,
    next_id: u32,
}

enum Event {
    AddFriend(&'static str, &'static str),
    RemoveFriend(&'static str, &'static str),
    Post(&'static str, &'static str),
    GetFeed(&'static str),
}

A Post is the note on the bulletin board — a number, an author, and the text. The number is what an engineer calls a monotonic id, which is a fancy word for a counter that only goes up. Post 1 happened before post 2, post 2 before post 3, and the counter never reuses a number. The board itself does not need a timestamp because the id already tells the reader what came first, and that means the lesson binary runs the same on a fast laptop and a slow one. The Network struct ties everything together. The friend map keys on a name and points to a set of friend names. The post list grows at the end. The next id is the counter that ticks up every time someone posts.

The choice of BTreeMap and BTreeSet instead of the hashmap and hashset most introductions reach for is what makes the output of this lesson printable. A hashmap iterates in whatever order the internal buckets happen to land — which is fine for a backend that does not care about order, and a disaster for a snapshot test that has to match byte for byte across machines. A BTreeMap keeps its keys sorted alphabetically, so Alice always prints before Bob and Bob before Carol. Same trick for the friend sets. Real Facebook keeps friends in MySQL with an index on the user id and sorts on the way out, but the principle is the same — if humans are ever going to read the list, sort it before it leaves the building.

The Event enum is the list of buttons a user can press. AddFriend wires two people together. RemoveFriend cuts the wire. Post pins a new note to the board. GetFeed asks the network to print the filtered view of the board for one specific reader. The string slices are &'static str because the demo's event list is hardcoded in main and lives in the binary forever — the cheapest possible storage for a string the program never has to mutate.

The api lives on the Network struct. Four methods do the real work and the signatures explain themselves.

impl Network {
    fn new(users: &[&str]) -> Self {
        let mut friends = BTreeMap::new();
        for u in users {
            friends.insert((*u).to_string(), BTreeSet::new());
        }
        Self {
            friends,
            posts: Vec::new(),
            next_id: 1,
        }
    }

    fn add_friend(&mut self, a: &str, b: &str) {
        self.friends
            .entry(a.to_string())
            .or_default()
            .insert(b.to_string());
        self.friends
            .entry(b.to_string())
            .or_default()
            .insert(a.to_string());
    }

    fn remove_friend(&mut self, a: &str, b: &str) {
        if let Some(set) = self.friends.get_mut(a) {
            set.remove(b);
        }
        if let Some(set) = self.friends.get_mut(b) {
            set.remove(a);
        }
    }

    fn post(&mut self, author: &str, text: &str) -> u32 {
        let id = self.next_id;
        self.next_id += 1;
        self.posts.push(Post {
            id,
            author: author.to_string(),
            text: text.to_string(),
        });
        id
    }

    fn feed(&self, user: &str) -> Vec<&Post> {
        let mut allowed: BTreeSet<String> = BTreeSet::new();
        allowed.insert(user.to_string());
        if let Some(set) = self.friends.get(user) {
            for f in set {
                allowed.insert(f.clone());
            }
        }
        let mut out: Vec<&Post> = self
            .posts
            .iter()
            .filter(|p| allowed.contains(&p.author))
            .collect();
        out.sort_by(|a, b| b.id.cmp(&a.id));
        out
    }
}

add_friend does the yearbook trick. It inserts b into a's signature set and a into b's set. The entry(...).or_default() pattern is Rust's way of saying give me the set if it exists or make an empty one if it does not, then let me touch it. A naive version would write two if let Some blocks and miss the case where the user was never registered, and a paranoid version would return an error if the user did not exist — but for a demo with a fixed roster, the entry call is the honest middle ground. remove_friend does the inverse on both sides and uses if let because removing from a set that does not exist is a no-op, not an error.

post is the bulletin board pin. It grabs the next id, bumps the counter, pushes the note onto the list, and returns the id so the caller can log it. The id never goes down because the counter only ticks up, which is what makes the feed sortable later.

feed is the only method that combines both halves of the design. The reader's allowed set starts with the reader's own name, because everyone should see their own posts. Then every friend gets added to the allowed set. The post list filters down to authors whose names are in the allowed set, and the result sorts by id in descending order — newest first. The b.id.cmp(&a.id) is the comparator written backwards on purpose. Sorting a.cmp(&b) would put the oldest post at the top, which is the chronological order the database stores them in. The feed wants the opposite. That one swap is the difference between a wall that feels alive and one that feels like an archive.

Two small print helpers render the state so the reader can watch the structures change after every event.

fn show_friends(net: &Network) {
    println!("friends:");
    for (user, set) in &net.friends {
        let names: Vec<String> = set.iter().cloned().collect();
        println!("  {user} -> [{}]", names.join(", "));
    }
}

fn show_feed(net: &Network, user: &str) {
    let feed = net.feed(user);
    println!("feed for {user}:");
    if feed.is_empty() {
        println!("  (empty)");
        return;
    }
    for p in feed {
        println!("  #{} {}: {}", p.id, p.author, p.text);
    }
}

show_friends walks the map in alphabetical order — that is the BTreeMap payoff — and prints each user's signature list as a comma-separated row. show_feed runs the filter and prints either the feed in newest-first order or (empty) if nothing the reader is allowed to see has been posted yet.

The driver loops over a hardcoded list of events and prints one line per event, mirroring the shape a real UI would have — a button press, a state change, an acknowledgment.

fn run(net: &mut Network, events: &[Event]) {
    for event in events {
        match event {
            Event::AddFriend(a, b) => {
                net.add_friend(a, b);
                println!("-> {a} and {b} are now friends");
            }
            Event::RemoveFriend(a, b) => {
                net.remove_friend(a, b);
                println!("-> {a} and {b} are no longer friends");
            }
            Event::Post(author, text) => {
                let id = net.post(author, text);
                println!("-> {author} posted #{id}: {text}");
            }
            Event::GetFeed(user) => {
                show_feed(net, user);
            }
        }
        println!();
    }
}

The script for our network builds the friendships first, scatters some posts, asks Bob what is on his wall, then changes the friendship graph mid-run to prove the feed reacts to the latest state instead of remembering who used to be friends.

fn main() {
    let users = ["Alice", "Bob", "Carol", "Dave"];
    let mut net = Network::new(&users);

    let events = [
        Event::AddFriend("Alice", "Bob"),
        Event::AddFriend("Bob", "Carol"),
        Event::Post("Alice", "morning run done"),
        Event::Post("Carol", "trying a new recipe"),
        Event::GetFeed("Bob"),
        Event::AddFriend("Alice", "Dave"),
        Event::Post("Dave", "shipping the new build"),
        Event::RemoveFriend("Alice", "Bob"),
        Event::GetFeed("Alice"),
    ];

    run(&mut net, &events);

    println!("--- final state ---");
    show_friends(&net);
    println!();
    show_feed(&net, "Bob");
}

-> Alice and Bob are now friends

-> Bob and Carol are now friends

-> Alice posted #1: morning run done

-> Carol posted #2: trying a new recipe

feed for Bob:
  #2 Carol: trying a new recipe
  #1 Alice: morning run done

-> Alice and Dave are now friends

-> Dave posted #3: shipping the new build

-> Alice and Bob are no longer friends

feed for Alice:
  #3 Dave: shipping the new build
  #1 Alice: morning run done

--- final state ---
friends:
  Alice -> [Dave]
  Bob -> [Carol]
  Carol -> [Bob]
  Dave -> [Alice]

feed for Bob:
  #2 Carol: trying a new recipe

Read the output top to bottom. The first two lines wire Alice to Bob and Bob to Carol — that is two yearbook signatures in each direction, four rows in the friend map. Alice posts note 1 and Carol posts note 2. Bob asks for his feed and sees both posts — Alice because she is his friend, Carol because she is his friend, and the order is #2 then #1 because newest comes first. Then Alice and Dave become friends, Dave posts note 3, and Alice and Bob have a falling out and remove each other from their signature lists. When Alice asks for her feed, she sees #3 from Dave (her new friend) and #1 from herself, but not #2 from Carol — because Carol was never directly Alice's friend, only Bob's, and the falling out cut the only path that would have brought Carol's note onto Alice's wall. The final state dump confirms it. Alice's friend list reads [Dave]. Bob's reads [Carol]. And Bob's feed at the end still shows Carol's note, because their friendship survived.

One question worth answering from the trace — what would it take to put Carol's post back on Alice's feed? The answer is in the structure. The feed only walks one hop out from the reader. Friends of friends do not count. A real Facebook feed does pull from friends of friends in a few situations (suggested posts, mutual connections), and the engineering cost of that one extra hop is enormous — the friend graph branches by a factor of around 200 per hop on average, so a two-hop reach pulls roughly 40,000 candidate posts for a user with 200 friends, and a three-hop reach pulls millions. The single-hop rule is not a limitation the design forgot. It is the choice that keeps the feed query cheap enough to ship.

The thing this network cannot do is rank the feed. Everything that lands on a user's wall lands strictly by post id, which is fine for 3 posts but wrong for 30,000. The next bottleneck is how to score and order the posts a user could see — by recency, by engagement, by predicted interest — so the wall shows the right note at the top instead of just the newest one, which is the problem the recommendation systems behind every modern feed exist to solve.