Imagine we have been given the task of implementing a social network in the style of X (formerly Twitter), where users can post messages and follow other users. This will be a huge simplification of how such a service actually works, but it will help illustrate some of the issues that arise in large-scale systems.
Let’s assume that users make a total of 500 million posts per day, or 5,800 posts per second on average. Occasionally, the rate can spike to as high as 150,000 posts per second. Let’s also assume that the average user follows 200 people and has 200 followers (although there is a very wide range: most people have only a handful of followers, and a few celebrities, such as Barack Obama, have over 100 million followers).
Representing Users, Posts, and Follows
We keep all the data in a relational database, as shown in Figure 2-1. We have one table for users, one table for posts, and one table for follow relationships.
Diagram illustrating a simple relational schema for a social network, showing tables for users, posts, and follow relationships with sample data.
Figure 2-1. A simple relational schema for a social network in which users can follow one another
Let’s say the main read operation that our social network must support is the home timeline, which displays recent posts by people the user is following (for simplicity we will ignore ads, suggested posts from people they are not following, and other extensions). We could write the following SQL query to get the home timeline for a particular user:
SELECT posts.*, users.* FROM posts
JOIN follows ON posts.sender_id = follows.followee_id
JOIN users ON posts.sender_id = users.id
WHERE follows.follower_id = current_user
ORDER BY posts.timestamp DESC
LIMIT 1000
To execute this query, the database will use the follows table to find everybody who current_user is following, look up recent posts by those users, and sort them by timestamp to get the most recent 1,000 posts by any of the followed users.
Posts are supposed to be timely, so let’s assume that after somebody makes a post, we want their followers to be able to see it within five seconds. One approach is for the user’s client to repeat the preceding query every five seconds while the user is online (this is known as polling). If we assume that 10 million users are online and logged in at the same time, that would mean running the query 2 million times per second. Even if we were to poll less frequently, this is a lot.
This query is also quite expensive: if a user is following 200 people, the query needs to fetch a list of recent posts by each of those 200 people and merge those lists. Two million timeline queries per second times 200 followed accounts makes 400 million lookups per second—a huge number. And that’s the average case. Some users follow tens of thousands of accounts; for them, this query is very expensive to execute and difficult to make fast.
Materializing and Updating Timelines
How can we do better? First, instead of polling, it would be better if the server actively pushed new posts to any followers who are currently online. Second, we should precompute the results of the query so that a user’s request for their home timeline can be served from a cache.
Imagine that for each user, we store a data structure containing their home timeline (i.e., the recent posts by people they are following). Every time a user makes a post, we look up all their followers and insert that post into the home timeline of each follower—like delivering a message to a mailbox. Now when a user logs in, we can simply give them this precomputed home timeline. Moreover, to receive a notification about any new posts on their timeline, the user’s client simply needs to subscribe to the stream of posts being added to their home timeline.
The downside of this approach is that we now need to do more work every time a user makes a post, because the home timelines are derived data that needs to be updated. The process is illustrated in Figure 2-2. When one initial request results in several downstream requests being carried out, we use the term fan-out to describe the factor by which the number of requests increases.
Diagram showing the fan-out process, illustrating how a user's post is distributed to each follower's home timeline, demonstrating derived data updating in a messaging system.
Figure 2-2. Fan-out: delivering new posts to every follower of the user who made the post
At a rate of 5,800 posts per second, if the average post reaches 200 followers (i.e., a fan-out factor of 200), we will need to do just over 1 million home timeline writes per second. This is a lot, but it’s still a significant saving compared to the 400 million per-sender post lookups per second that we would otherwise have to do.
If the rate of posts spikes because of a special event, we don’t have to do the timeline deliveries immediately—we can enqueue them and accept that it will temporarily take a bit longer for posts to show up in followers’ timelines. Even during such load spikes, timelines remain fast to load, since we simply serve them from a cache.
This process of precomputing and updating the results of a query is called materialization, and the timeline cache is an example of a materialized view (a concept we will discuss further in later chapters). The materialized view speeds up reads, but in return we have to do more work on writes. The cost of writes for most users is modest, but a social network also has to consider some extreme cases:
-
If a user is following a very large number of accounts, and those accounts post a lot, that user will have a high rate of writes to their materialized timeline. However, that user is not likely reading all the posts in their timeline, so it’s OK to simply drop some of their timeline writes and show the user only a sample of the posts from the accounts they’re following.
-
When a celebrity account with a very large number of followers makes a post, we have to do a lot of work to insert that post into the home timelines of each of their millions of followers. In this case, dropping some of those writes is not OK. One way of solving this problem is to handle celebrity posts separately from everyone else’s posts: we can save ourselves the effort of adding celebrity posts to millions of timelines by storing them separately and merging them with the materialized timeline when it is read. Despite such optimizations, handling celebrities on a social network can require a lot of infrastructure.