Reddit (votes, "hot" ranking, comments)

01 · CONTEXT AND REQUIREMENTS

What Reddit needs to do

This case uses Reddit's open-source code as a map of a real system. The central objects are links, comments, accounts, and subreddits, and three paths deserve attention: voting, reading a sorted listing, and commenting.

As an exercise in requirements gathering, the functional requirements are creating a post, voting, viewing a subreddit's listing in orders such as hot, new, and top, and commenting in tree form. Among the non-functional ones, the listing must respond fast, the vote should not make the user wait, and the count can lag slightly, that is, eventual consistency.

The software described by the project itself is monolithic: the application receives the HTTP request and does the work of fetching data and assembling the response on its own. There are two central permanent stores, PostgreSQL and Cassandra, and memcached is used heavily to speed up queries.

1. The browser calls the application, which on its own fetches the data and assembles the response.

2. Before going to the databases, the application uses memcached to speed up queries.

3. Permanent data lives in two stores, PostgreSQL and Cassandra.

Data model: links, comments, accounts, and subreddits live in PostgreSQL through the ThingDB mechanism, a nearly schemaless key/value store with two tables per type. The main table gathers common columns, among them the vote counts, and this fixed schema makes relatively fast sorting easier.

Cassandra, for its part, offers transparent sharding and survives hardware failures. Part of the write load is done outside the user's request, precisely so that processing slowdowns do not show up in the response.

02 · RANKING

How each sort is computed

The starting point is the score, the difference between upvotes and downvotes. The hot sort adds two terms: the sign of the score multiplied by its order of magnitude, which is the log10 of the absolute value of the score with a floor of one, and the seconds since a fixed reference date divided by a constant.

For confidence, the code keeps a table of precomputed values, indexed by upvotes and downvotes, and only computes on the fly when the counts fall outside the table's range.

In the database, each sort points to a column of the item: hot to the hot column, new to the date, top to the score, and controversial to the controversy column. Only top and controversial accept a time filter.

03 · THE VOTE PATH

Voting without making the user wait

The cast_vote function records the vote and puts it in a queue for processing, and writes the vote marker to memcached so the interface updates immediately. Votes on links and on comments go to different queues.

1. The user votes and the application records the vote.

2. The application writes the vote marker to memcached so the interface updates immediately.

3. The serialized vote enters the vote queue.

4. A consumer creates the vote under a lock that combines user and link, to keep the vote state and the cached query consistent.

5. Once confirmed, the vote increments the item's count and is stored per account.

6. If the vote is valid, the link goes to the queue that updates the listings.

When the user changes their vote, the effect of the previous vote is undone and that of the new one is applied. Each account's vote is kept in VotesByAccount, a denormalized relation on top of Cassandra.

The code also handles votes still in the queue: it only queries memcache for not-yet-processed votes if the user voted within the grace period. Corrupted records in the queue are ignored.

04 · PRECOMPUTED LISTINGS

Reading a hot page without recomputing

O cache of listings works like this: each query has a cached result that fetches the list, on demand, from the persistent cache. Each stored item carries the item's full name and the sort columns, and the list has an item limit, given by a constant.

The key point is to insert instead of recompute: when possible, a new item is inserted into the listing instead of re-running the query. Creating a link updates only the new listing, and the hot, top, and controversial listings follow the vote path.

1. The application fetches the query's list, on demand, from the persistent cache.

2. A valid vote sends the link to the per-subreddit update queue.

3. The consumer reads the messages in batches and groups the links by subreddit.

4. For each subreddit, it inserts the links into the hot, top, and controversial listings.

5. Updating the list requires reading, modifying, and writing under a lock, and sharding by subreddit allows several consumers without lock contention.

05 · COMMENTS

Comment trees and votes at scale

Comments have their own vote queue. The consumer loads the voted comment and, when it already has many votes, only updates the scores from time to time: the update is skipped when the number of votes exceeds a configurable limit and is not a multiple of a period, also configurable.

1. The comment vote enters its own queue, separate from the link queue.

2. The consumer loads the voted comment.

3. With many votes, the score update is only periodic.

4. If the link uses precomputed sorts, the comment goes to the tree queue.

5. The updater handles the per-link scores and the order of comments.

The scores are kept in CommentScoresByLink, a view on top of Cassandra whose row key combines the link and the sort. There are stored scores for four comment sorts. If scores are missing, the code recomputes them and limits the rewrite to once per minute.

Comments can also be enqueued in different ways. Those from links marked in the configuration as fastlane go to a dedicated queue; with the sharding option on, the queue is chosen by the link, and without it there is a single queue. To sort by date, the code uses the comment's own id, because ids grow monotonically.

06 · LESSONS AND LIMITS

Problem and mechanism, side by side

This case describes mechanisms, not traffic numbers. Treat them as patterns to justify by the requirements, and do the scale estimate with your own assumptions.