Nested Comments

The problem

"Design a comment system that other websites embed." A news site adds the widget under its articles, and its readers comment and reply to each other, nested to any depth. 50,000 sites use it, each with its own moderators and rules.

This practice problem reuses Reddit's comments. Five things are new: many sites in one system, threads hundreds of replies deep, a sort the reader picks at every level, deletes inside a tree, and moderators per site. Park reply emails for later.

The numbers

From the interviewer: every page view on those sites loads the widget, 500 million loads a day, and readers post 5 million comments a day. Round a day to 100,000 seconds (86,400 really); busy hours run about 5× the average.

• Loads: 500 million ÷ 100,000 = 5,000 a second on average (about 5,800 with 86,400), so about 25,000 a second at busy hours.
• New comments: 50 a second, 250 at busy hours: reads outnumber writes 100 to 1.
• Storage: at about 500 bytes a comment, 2.5 GB a day, about 900 GB a year. A popular page with 20,000 comments is about 10 MB, too much to send at once.

Storing the tree: a path per comment

Three common ways, each with a cost:

• Adjacency list: each comment keeps only its parent's id. Cheapest to write, and fine for loading a whole page at once, as in Reddit. But the thread under one comment takes a query per level, each waiting for the last: a thread 100 deep is 100 queries in a row. A recursive SQL query does the same walk inside the database.
• Closure table: a row for every ancestor and descendant pair, with the depth between them. Any thread is one indexed query, but a reply 100 deep writes 101 rows, and one argument 300 replies long stores 45,150 pairs.
• Materialized path: each comment keeps its path from the top, like c1/c2/c3. A reply writes one row: its parent's path plus its own id.

With reads 100 times the writes and deep threads, the path wins here. In an index on (site, page, path) a thread's comments sit side by side, so loading one is a single range scan, in reading order, and the depth is the number of steps. The costs: deep comments carry long paths (8-character ids and a slash make a comment 300 deep carry 2,700 bytes, so some designs cap how deep replies nest), and moving a comment would rewrite its subtree, which never happens here. Give all ids the same length, so text order is time order and c5 never matches c51.

Deep threads: continue this thread

No screen fits 300 levels of indent, so the widget shows 5 levels and, under a comment at depth 5 that has replies, a "continue this thread" link; a reply count kept on each comment says where it goes. Page p9's index, in path order:

path                    by
c1                      cy
c1/c2                   ana
c1/c2/c3                ben
c1/c2/c3/c4             ana
c1/c2/c3/c4/c5          ben
c1/c2/c3/c4/c5/c6       ana
c1/c2/c3/c4/c5/c6/c7    ben
c1/c2/c8                dee

The first screen reads the rows down to 5 steps (c1 to c5, and c8). "Continue this thread" under c5 asks for every path that starts with c1/c2/c3/c4/c5: c5, c6 and c7, three rows side by side, one range scan that stops at c1/c2/c8.

GET /comments?site=news.org&page=p9&sort=top   → the first 5 levels
GET /comments/c5/thread?sort=top                → c5, c6, c7

Sorting: top or new at every level

Path order puts each reply under its parent, with siblings oldest first. For top or new, the server sorts each comment's replies by score or by time while it builds the tree in memory. Sorting all of a page's comments by score in one query would pull replies away from their parents: if c8 scores higher than c2, it shows above the comment it answers. And the score can't live in the path: every vote would rewrite a whole subtree's paths, 7 for one upvote on c2.

Cache each built page per sort, say for 5 seconds: a busy page is built once every 5 seconds instead of on every load.

Editing and deleting: a tombstone

When Ben deletes c3, four replies hang under it. Deleting the row would leave c4 to c7 under a comment that's gone, and deleting the subtree would erase other people's words. Instead keep the row and its path, blank its text and author, and show [deleted]. An edit changes only the text and marks it edited; the path never changes.

Moderation per site: the site id everywhere

All 50,000 sites share one system (a multi-tenant design), so every comment's key starts with its site id, and so does every role:

site · user      role
news.org · lia   moderator
blog.net · tom   moderator
news.org · ben   banned

Lia can remove c5 because her role and c5 both say news.org; she can't touch a comment on blog.net or ban Ben from other sites. She removes but never rewrites. Bans and rules live in each site's settings, checked when a comment is posted. Comments are split by site and page, so a page lives on one shard.

Same pattern as Reddit

Votes, scores, parent ids and cached built pages work as in Reddit. What changed is how a thread is found: by its path, not by walking parent ids.

Summary

• Scope: nested replies on 50,000 sites, top or new, edits and deletes, moderators per site.
• Data: a path per comment, like c1/c2/c3; the site id leads every key.
• API: GET /comments?site=…&page=…, GET /comments/{id}/thread, POST /comments.
• Numbers: about 25,000 loads and 250 new comments a second at busy hours.
• Deep threads: 5 levels first, then one range scan by path prefix.
• Sorting: siblings sorted in memory; built pages cached per sort.
• Deleting: a [deleted] tombstone keeps the tree.
• Moderation: the site id on every row and role.