Reddit Architecture, in depth: hot, best and controversial ranking, precomputed listings, the asynchronous vote path and comment trees

What the system has to do

Start from the access pattern, because it drives everything else. Reads outnumber writes by a large margin: a popular post is viewed far more often than it is voted on, and voted on far more often than it is commented on. Most reads are listings, meaning the first page of 25 or so items for a community under a given sort, and comment pages, meaning a post plus a tree of comments under a sort.

Votes are the dominant write. Each vote changes the score of one item, which may move it within several listings at once: the community's hot, top and controversial lists, the global aggregate lists and the author's profile. Users also expect their own vote to show immediately, while nobody notices if another person's vote takes a few seconds to move a post.

That combination suggests three design rules. Make listings cheap to read by storing them already sorted. Make each vote cheap to apply by updating only the listings it affects, asynchronously. Accept bounded staleness everywhere except the voter's own view, which can be patched on the client or from a per-user vote record.

Things, fullnames and the data model

r2 stored most objects as Things: links (posts), comments, accounts, subreddits and messages. Each type had a narrow table of fixed columns such as id, score-related counts, creation date and deleted or spam flags, plus a key-value data table holding everything else as rows of thing id, key and value. Relations such as votes and saves were stored the same way, as Relations between two Things. Every Thing is addressed by a fullname that combines a type prefix with a base-36 id, such as t3_abc12 for a link and t1_ for a comment.

The entity-attribute-value layout made schema changes free, since adding a property meant writing new keys rather than altering a large table, at the cost of making ad hoc queries across properties expensive. That cost is acceptable precisely because the system almost never queries the database for a listing on the read path. Objects are cached by fullname in memcached, and listings are cached as lists of fullnames, so a page render is one listing fetch followed by a batched multi-get of the objects it names.

The ranking functions

The ranking functions are short enough to quote. In r2 they lived in r2/lib/db/_sorts.pyx, compiled with Cython, with matching definitions in Postgres so the database could sort by them too. Hot ranking combines the logarithm of the net score with the submission time:

from math import log10, sqrt

def hot(ups, downs, epoch_seconds):
    s = ups - downs
    order = log10(max(abs(s), 1))
    sign = 1 if s > 0 else -1 if s < 0 else 0
    seconds = epoch_seconds - 1134028003          # an offset in December 2005
    return round(sign * order + seconds / 45000, 7)

def confidence(ups, downs):                       # the "best" comment sort
    n = ups + downs
    if n == 0:
        return 0
    z = 1.281551565545                            # 80 percent one-sided
    p = ups / n
    left = p + z * z / (2 * n)
    right = z * sqrt(p * (1 - p) / n + z * z / (4 * n * n))
    return (left - right) / (1 + z * z / n)

def controversy(ups, downs):
    if ups <= 0 or downs <= 0:
        return 0
    balance = downs / ups if ups > downs else ups / downs
    return (ups + downs) ** balance

Hot. The time term grows by 1 every 45,000 seconds, which is 12.5 hours, and the score term grows by 1 for every factor of ten in net votes. So a post must collect ten times the net score of a post submitted 12.5 hours later to rank level with it: a post at net 1,000 submitted at noon ties a post at net 100 submitted at 00:30 the next day, and a post at net 10 submitted at 13:00 on that next day. The logarithm means the first ten votes matter as much as the next ninety.

The most important property is not obvious from the formula: hot does not depend on the current time. It depends on submission time and votes only. Newer posts simply get larger numbers. A post's hot value therefore changes only when someone votes on it, so a sorted hot listing stays correctly sorted between votes without any background re-scoring. Formulas of the form score divided by a power of age, popular in other designs, decay continuously and force periodic recomputation of every listing.

Best. For comments, r2 used the lower bound of the Wilson score interval for the fraction of upvotes, at 80 percent confidence. A comment with 1 upvote and 0 downvotes scores about 0.378, while one with 80 up and 20 down scores about 0.744, so a well-supported 80 percent beats an unsupported 100 percent. It ignores time, which suits comment threads where the reader wants the best replies regardless of when they arrived.

Controversial. The magnitude of total votes is raised to the power of the balance between the two sides. 100 up and 90 down gives 190 to the power 0.9, about 112; 1,000 up and 100 down gives 1,100 to the power 0.1, about 2. Many votes, evenly split, wins. Top is simply net score, filtered by a time window such as day, week or all time.

Precomputed listings and the vote path

Because hot only changes on a vote, a listing can be maintained as a stored, sorted array of tuples, each holding a fullname and its sort values. In r2 these precomputed results were kept in a permanent cache with a cap of 1,000 items per listing, the precompute_limit in r2/lib/db/queries.py. Nobody pages past the thousandth item of a hot listing, so the cap bounds both storage and update cost.

Applying a vote is then a small, local operation, sketched below. Compute the item's new sort values, and for each listing that contains it or should now contain it, replace or insert the tuple, re-sort, and trim to the cap. Sorting 1,000 already-sorted tuples with one changed is cheap. The listings to touch are known from the item itself: its subreddit's hot, new, top and controversial lists, plus aggregates such as the front page of all communities.

def apply_vote(item, listings_for, cache, cap=1000):
    keys = {"hot": hot(item.ups, item.downs, item.created),
            "top": item.ups - item.downs,
            "controversial": controversy(item.ups, item.downs)}
    for listing_id, sort in listings_for(item):          # e.g. ("sr:pics:hot", "hot")
        with cache.lock(listing_id):                     # one writer per listing
            rows = cache.get(listing_id) or []
            rows = [r for r in rows if r[0] != item.fullname]
            rows.append((item.fullname, keys[sort], item.created))
            rows.sort(key=lambda r: (r[1], r[2]), reverse=True)
            cache.set(listing_id, rows[:cap])

Two details carry the design. First, the per-listing lock: concurrent consumers that read, modify and write the same listing would otherwise lose updates, so either serialise writers per listing or route all votes for a subreddit to one consumer. Second, the trim: an item that falls off the bottom is gone from the precomputed listing, and if votes later push it back up it must be re-inserted, which works because the insert step does not assume the item was present.

Comment trees

Comment pages have a different shape: a tree, sorted at each level, often with thousands of nodes on a popular post. r2 kept, per link, a cached structure of the tree, mapping each comment to its children, and a separate cached map of sort values per comment. New comments flowed through their own queue, whose consumer inserted each comment into its parent's child list, so posting a comment did not rebuild the tree synchronously.

Rendering a comment page then works top-down with a budget. Sort the top-level comments by the chosen sort value, walk depth-first, stop after a fixed number of comments or a maximum depth, and emit placeholders for the rest, the familiar load-more-comments links, which fetch the next slice of the same cached tree on demand. The budget is what keeps a 40,000-comment thread from turning into a 40,000-object render.

Worked example: one post's first hour

Follow one post through the system. A user submits a link to a community at 09:00. The app server writes the Thing to Postgres, caches the object, and inserts its fullname into the community's new listing and, with a hot value equal to the time term plus zero, into the hot listing. It immediately sits near the top of new and at whatever position its timestamp earns in hot.

In the next hour it receives 120 upvotes and 20 downvotes. Each vote is recorded as a relation between account and link, so a user cannot vote twice, the voter's page reflects the vote at once, and a message is enqueued. Consumers update the stored counts, recompute hot as log10 of 100, which is 2, plus the time term, and rewrite the community's hot and top listings plus any aggregate listing the post belongs to. By the time it has net 100 it is two full units ahead of a zero-score post submitted at the same moment, equivalent to being 25 hours newer.

A reader opening the community's hot page at 10:00 costs one listing fetch, which returns up to 1,000 sorted fullnames, a slice of the first 25, and one multi-get for those 25 objects, almost always served from memcached. No query to Postgres and no sorting happens on that path.

Failure modes

The design fails in recognisable ways, and each has a standard mitigation.

The asynchronous path converts load spikes into lag rather than errors, which is the right trade only if lag is visible: alert on the age of the oldest unprocessed vote, not only on queue length, because a short queue that is not moving is worse than a long one that is.

Trade-offs and what to change today

Precomputed listings trade storage and write amplification for read speed: every vote touches several listings, and every listing is stored whether or not anyone reads it. That works when the number of sorts and communities is moderate. It works less well for personalised feeds, where every user effectively has their own listing; for those, the patterns in Instagram feed generation and the Twitter feed design, candidate generation followed by per-request ranking, take over. A modern home feed mixing subscriptions and recommendations is that kind of problem, and should not be assumed to use the community-listing machinery described here.

The ranking formulas are also deliberately simple. They are transparent, cheap and, in the case of hot, time-invariant, which is what makes incremental maintenance possible. A learned ranking model is more accurate but depends on the reader and the moment, so it moves you back towards computing order at read time over a candidate set. Many systems keep both: a cheap, cacheable, time-invariant score to choose candidates, and a model to order the final page. The caching layer underneath either design is covered in caching strategies, and the queue semantics the vote path relies on are in message queues.

What to do next

1. Write down your read-to-write ratio and the sorts you must serve; if reads dominate and sorts are few, plan for precomputed listings.
2. Choose ranking functions whose value changes only on events, as hot does, so stored listings stay sorted between events.
3. Store listings as capped arrays of IDs plus sort values, and render pages with one listing read and one batched object fetch.
4. Route votes through a queue, enforce one writer per listing, and coalesce repeated updates to the same item.
5. Use a Wilson lower bound rather than raw ratios wherever items with few votes compete with items with many.
6. Give comment rendering a hard budget and lazy expansion before your first large thread arrives.
7. Alert on the age of the oldest unprocessed vote and keep an offline rebuild for every listing.