Design a news feed

Why is the same feed built 600,000 times at lunch?

By autumn the delivery service is a platform: 2,000 home cooks in three cities and 200,000 customers. Between nine and half past ten every cook posts the day’s menu. Customers follow the cooks they like, and the app opens on one screen, Today’s menus: the newest posts from the cooks you follow.

The first version builds that screen the direct way. When a customer opens the app, one SQL query finds the cooks she follows, gathers their recent posts, sorts them by time and returns the top twenty.

At 12:20 one Thursday the feed takes three seconds to load, and the kitchen’s order screen stalls with it. The two share one database.

Customers open the app about fifteen times before they order, and every open builds the feed again from scratch. The menus were finished at half past ten. Nothing in them changes at lunch, yet the database builds the same feed again for every customer on every open.

The alternative is to build each feed ahead of time. When a cook posts, write the post into each follower’s feed, so that opening the app becomes a single read. Before accepting that, read one number off the cook dashboard: the most-followed cook has 80,000 followers. Her morning menu would be written into 80,000 feeds, and again for the evening special, and half of those customers have not opened the app this month.

Both ways cost something. Building at read time pays on every open, and the opens outnumber the posts by hundreds to one. Building at write time pays on every post, and a few cooks make a post very expensive. Guess before reading on which product is larger: 1.5 million opens a day times ten follows each, or 4,000 posts a day times their followers.

Pause and predict One cook has 80,000 followers; most cooks have a few hundred. Opens outnumber posts hundreds to one. How should the feed be built?

What must never go wrong?

The System Context: customers and cooks, our one system, and what sits around it.

Two requirements come from outside the feed. The kitchen needs the feed never to slow down orders again. The cooks need a menu posted at 9:30 to be visible to customers well before lunch.

Core entities, in two minutes

A Cook and a Customer; a Follow between them; a Post by a cook. And one derived thing: each customer’s Feed, an ordered list of post ids that can always be rebuilt from Posts and Follows.

The estimate that changes the design

Reads outnumber writes by 375 to one. That ratio decides the main shape of the design: build the feed once, when a post is written, instead of on every open. The last row, a single post that costs 80,000 inserts, is why the design needs an exception for the most-followed cooks.

The obvious version, and how it breaks

The first version keeps everything in the orders database and builds the feed inside one query on every open:

SELECT p.* FROM posts p JOIN follows f ON f.cook_id = p.cook_id WHERE f.customer_id = $1 AND p.created_at > now() - interval '2 days' ORDER BY p.created_at DESC LIMIT 20; -- then join dishes, photos, cook names

With good indexes (lesson 2.4) each open is about ten index range reads, one per followed cook, then a sort and the joins to show the posts. Measured, it is about 35 ms of database time. That is fast for one customer.

Pause and predict At lunch the feed is opened 167 times a second, and each open costs about 35 ms of database time. How much database work is that every second?

And it gets worse in two ways:

• The work is repeated. The morning’s 4,000 posts do not change after 10:30, yet every open re-sorts the same rows.
• It grows with follows. A customer who follows 50 cooks costs five times as much as one who follows 10, and pays that cost on every open.

A read replica (lesson 3.1) would protect the orders, and is worth doing anyway. It would not remove the repeated work. The replica does the same work on another machine, and that machine must grow with every new customer.

A mental model

A housing society of 300 flats sorts its post the way a feed should be built.

Fan-out on write (push) and fan-out on read (pull)

Two places to do the work of building a feed. Push does it when a post is written: one insert per follower. Pull does it when a feed is read: one fetch per followed source, then a merge.

For example: A post by a cook with 600 followers costs 600 small inserts under push and nothing under pull. Opening a feed that follows 10 cooks costs one read under push and 10 reads plus a sort under pull.

Push everything, or pull the famous?

One path is simpler to build today; the other holds up when one cook has a hundred times the followers.

At today’s size pure push works, and a team with less time should start there. What decides it is the direction of growth: famous cooks get more famous, and the cost of a pushed post grows with them, while the cost of pulling a famous cook grows only with opens, which the caches already absorb.

What to remember

1. A feed can be built at write time (one insert per follower per post) or at read time (one fetch per followed source per open). Compare posts x followers with opens x follows.
2. When opens outnumber posts by hundreds to one, fan out on write: opening a feed becomes one read of a short list.
3. Uneven follower counts break pure push. Pull the famous few at read time and merge them in; protect their lists as hot keys.
4. Feed lists hold post ids, are trimmed, skip inactive customers, and can always be rebuilt from posts and follows.
5. Make fan-out idempotent (a sorted set by creation time) and acknowledge only after the last batch.

Do the feed work once per post, except for the few posts that would cost more than all the reads.

In the real world

Real feeds add a ranking step that our toy leaves out: a candidate set (often built exactly as here, from pushed lists and pulled sources) is scored by a model and reordered before it is shown. They also fan out across data centres, handle blocks and privacy settings at read time, and backfill or prune lists continuously.

As reported in Krikorian’s 2012 talk, Twitter kept each active user’s home timeline in Redis, capped at 800 entries, built by fan-out on write, and merged accounts with very large followings at read time. The shape you built is the same; the numbers are a thousand times smaller.