Reddit

Community discussion forum

Design a community discussion site where people post into topic communities, vote on posts and comments, and read ranked listings and deeply nested comment threads.

Overview

A community discussion site groups posts by topic. Each community (a subreddit) has its own front page, readers vote posts and comments up or down, and the order of a page comes from those votes and the post's age. Under every post sits a comment thread that can nest dozens of levels deep.

Two things make it hard at scale. Listings are read far more than they are written, yet every vote can change their order; recomputing a sorted page on each view does not scale, and neither does rewriting it under a lock on each vote. And a popular thread can have tens of thousands of comments, so building the tree and choosing which part to show must not happen from scratch per request.

Questions to ask first

How many users and page views? — 50 million daily users, 20 listing pages each a day
How many posts, comments and votes? — 1 million posts, 10 million comments and 200 million votes a day
Which sorts? — Hot (default), New, Top and Controversial for posts; Best, Top and New for comments
How fresh must scores be? — A few seconds behind is fine; a user's own vote shows at once
How deep can threads go? — Unlimited nesting; show about 10 levels, then a link
Media? — Links only; images and video are out of scope

What you will be able to do

Explain the hot, best and controversial sorts, and compute them.
Design precomputed listings that votes update in the background.
Handle a vote storm on one community without lock pile-ups.
Store and page a comment tree with tens of thousands of comments.
Build a home feed from many communities' listings.

Key concepts

Hot ranking
Wilson score (Best)
Precomputed listings
Vote queues
Lock contention
Comment trees
Fan-out on read
Denormalized counts

Functional requirements

Create a community; subscribe and unsubscribe
Submit a text or link post to a community
Reply to a post or to any comment, nested without limit
Vote a post or comment up or down, change the vote, or take it back
Read a community sorted by Hot, New, Top or Controversial
Read comments sorted by Best, Top or New
Read a home feed of the communities you subscribe to

Non-functional requirements

Listing pages return in under 200 ms at p99 (a target we chose)
A new vote changes a listing's order within about 10 seconds (a target we chose)
A user sees their own vote immediately
One user has at most one vote on each post or comment
A thread with 50,000 comments opens as fast as a small one

Interview questions

How does the hot ranking work, and why can it be precomputed?
Why not sort comments by upvote percentage?
How do you serve a community's front page at thousands of reads a second?
Your vote queues are backing up. What do you look for?
How do you stop duplicate or changed votes from corrupting scores?
How do you load a thread with 50,000 comments?
How is the home feed built?
What would you do about vote manipulation?