Building Everyone's Feed

Mira opens Courtyard, and the first thing she sees is her feed. She follows five hundred people, and the feed is meant to show her the most recent posts from all of them, newest first. Up to now you have taken this for granted, because on the single database of Part I it is an ordinary query. You ask for the posts whose author is someone Mira follows, sorted by time, and you take the first fifty. The database does the rest.

But the posts no longer live on one database. In Chapter 4 you sharded them across a hundred machines by author, and Mira’s five hundred followees are scattered across all hundred. To build her feed now, you have to ask every shard for its recent posts by whichever of Mira’s followees happen to live there, wait for all hundred to answer, merge the hundred lists, sort them by time, and take the top fifty. This is Chapter 4’s scatter-gather, with the latency of its slowest shard, and you have to do it every time Mira refreshes, and every other user on Courtyard is doing the same, constantly. Add up the feed query over every user and every refresh, and it comes to more work than the entire rest of the system put together. It is the query that fits nothing you have built so far, and it has run out.

What you have just described has a name, and it is fan-out on read. When Mira asks for her feed, you fan out to the data of everyone she follows and gather it back. The cost is the one you saw, a large scatter-gather on every read, and reads are the constant operation. Its virtues are real, though. Writing a post is trivial, since you store it once on the author’s shard and you are done. And the feed is always fresh, because it is built from the current truth at the moment she asks for it.

For someone who follows five hundred people and refreshes often, it is an expensive query repeated for very little gain. The same hundred-shard gather runs over and over and mostly returns the posts it returned last time. Chapter 8 taught you to recognise this shape, an answer being recomputed when it has barely changed, and the natural response is to cache it. But Mira’s feed is a hard thing to cache. It changes whenever any one of five hundred people posts, and it is unique to her, so nobody else’s cached feed will do.

So let us turn the problem inside out. Instead of building Mira’s feed at the moment she asks, build it at the moment the posts arrive. Give every user a stored, ready-made list of the posts they should see, newest first, and call it their feed. When Mira posts, you do not merely store the post on her shard. You push it into the feed of every one of her followers, appending it to each of their ready lists. When a follower opens the app, their feed is already built. It is one read of their own list, with no scatter and no merge, and it comes back at once. The expensive work has moved from read time, where it was repeated on every refresh, to write time, where it happens once per post.

This is fan-out on write, and for the ordinary case it works very well. Reads, which are the frequent operation, become a single lookup. The work has moved to writes, which by Chapter 3’s ratio are about a hundred times less frequent. Most social feeds are built this way, because reads outnumber posts by a wide margin.

Then a celebrity posts. This person has ten million followers, and fan-out on write means appending one post to ten million feeds. That is ten million writes in a burst, set off by a single tap on a phone. Nor can the burst be spread out at leisure, because the celebrity has ten million followers precisely because people want to see what they post right away. If a celebrity posts ten times a day, and there are a thousand celebrities, the write load from fan-out alone is enormous, and all of it is caused by the users with the most followers, who are also the most visible users. The scheme that was cheap for Mira’s few hundred followers is ruinous for a celebrity’s ten million.

Lay the two schemes side by side and their costs are mirror images. Fan-out on write is cheap for a user with few followers and ruinous for one with many. Fan-out on read is cheap to write for everyone and expensive to read for everyone. Both costs are sorted by the same quantity, the number of followers, and that suggests where to cut.

Most users, meaning everyone with an ordinary number of followers, fan out on write. When Mira posts, the post is pushed into her few hundred followers’ feeds, which is cheap, and their reads stay instant. Celebrities, the handful of accounts with enormous followings, do not fan out on write at all. Their posts stay on their own shard. When any user opens their feed, the system reads their ready-made list, which was built by write-time fan-out from the ordinary people they follow, and separately fetches the recent posts of the few celebrities they follow, and merges the two by time. The second step is fan-out on read, but across a handful of celebrities rather than five hundred people. The expensive read-time gather is now bounded, because a user follows at most a few dozen celebrities, and the expensive write-time explosion never happens, because celebrities do not fan out.

The threshold that decides how many followers make someone a celebrity is a dial, and you set it against the two costs. Set it high and few users get the read-time treatment, so the write load is higher. Set it low and more reads have to do the merge, so the read load is higher. There is no perfect setting. There is only a balance point, and it moves as the distribution of followers shifts under you. This is the recurring shape of Part III, a trade with no right answer and a dial you keep tuning.

Look at what fan-out on write actually did to your data. It stored each post many times, once on the author’s shard and again in every follower’s feed. That is duplication, the same post copied into ten thousand places, and every instinct trained on a single database says it is wrong. Data is supposed to live once, in one place, and be looked up rather than copied.

At this scale, that instinct is the thing that does not scale. Storing the post once and computing the feed by looking it up is fan-out on read, which is the expensive option. Storing it many times, pre-arranged into the shape that reads want, is what makes reads cheap. The duplication is the optimisation.

The field calls this denormalisation, the deliberate storing of data in more than one shape, each arranged for the queries that read it, accepting the duplication and the cost of keeping the copies in agreement in exchange for never having to compute the answer at read time. It is the caching of Chapter 8 carried to its conclusion. Rather than caching the computed answer, you store the data pre-computed into the form you will read. A user’s feed is a denormalised, materialised copy of posts that also live on their authors’ shards.

And it brings the antagonist of this part along with it, because every copy can be stale or wrong. Mira posts, the post is fanned out to five hundred feeds, and one of those writes fails, so one follower’s feed is missing the post. She edits it, and now five hundred copies need updating, and any you miss go on showing the old version. She deletes it, and that is five hundred deletions, and a missed one leaves a ghost. The single-copy database never had this problem. You created it, deliberately, by storing the data many times, because the alternative did not scale. Keeping the copies in agreement is the tax on denormalisation, and it is staleness arriving as a direct consequence of a choice you made for speed.

So feeds can now disagree with the posts they were built from. A post may be edited or deleted at its source and remain in its old form in some feeds. A fan-out write may fail and leave a feed incomplete. A post may appear in your feed and then return a 404 when you tap it, because it was deleted at its source after it was fanned out. The feed is a pile of copies, and copies drift. There is a further subtlety in the hybrid. Its two halves, the pre-built list and the celebrity fetch, have to be merged and sorted by time, and if the two sources are stale by different amounts the sort can flicker. A post appears, and then on the next refresh it jumps position as the other source catches up, which is Chapter 3’s monotonic-reads problem turning up inside the feed.

That is the eleventh revision of Courtyard. The feed query ran out, and you answered it by building feeds with fan-out on write for ordinary users and fan-out on read for celebrities, merged at read time. Feeds are now denormalised copies that can be incomplete, stale, or in contradiction with their source posts, and keeping them consistent is a cost you will go on paying. The feed is fast, at least, for anyone near the datacentre.