Loading...
Assume there are 1 million daily active user. Each one of them post a tweet daily on average. A tweet object is about 200B. Every day, we're storing 200MB of data without compression. That's 73GB over 5 years.
On the user side, each object is less than 100B. This is about 100MB total. If we forecast growth to 1billion user, this is still 100GB data. In addition, there is followership entity. It would follow a power-law distribution: some power user are super connected, while most are not. We can assume there are 10 followers on average per user. That's 10 million followings. So about 100MB.
To estimate request rate, we previously had 1 million write requests per day. That's about 11 requests/s on average. This is not a big number, even if we account it to be coming during active hours and not evenly over 24 hours. The factor to consider here is fanout and we will discuss it next during read.
For read, the most important piece is timeline. It requires reading tweets from followed users. One strategy which won't scale well is to join on request. If a user followed 10 users on average, this would mean it joins 10 times. It will create 10x load on the database. And for some power user it may be 1000x.
The alternative would be a early push strategy - write to users who followed this user. This will on average create 10 times more write, but read will be much simpler. The caveat is we have a variable number of followed user (in a power law distribution). So it would have a high write latency. Standard technique is to use a message queue for processing. The other aspect is that it will also increase storage cost by 10x if we all write it onto disk. We can consider storing recent timeline in cache so that storage is minimized but cache would contain the replicated version of timeline per user.
To estimate the cache size, it is about 200MB of data for new tweets per day. Suppose we replicate each tweet 10 times, and store only most recent 30 days. It would cost 60GB of memory. You can support this with redis or memcache.
Two entity: User and Tweet.
User:
Tweet:
Follow:
To view a user timeline, a query will join the followed_id and show the top N recent tweet. To support text search, we can build a full text search index on tweet. This is typically done by having an inverted index on doc list and doc ids.
We will have a API layer, a cache layer, and a database layer.
The API will receive read and write requests from users or clients. On read, it will read the cache layer for particular tweet or a whole timeline. On write, it will send write request to a message queue, which will be handled by storing the tweet into database and propagating it to the cache layer.
The cache layer is a distributed cache layer. It supports appending tweets to followed user. When data is not in cache, it is responsible to fetch from the database. It will keep recent tweets in cache and expired in LRU manner.
The database will be a relational database with tables specified in the database section. The user table can be sharded by user id and the tweet table sharded by tweet id. The follower table can be a child table of the user table.
In this diagram:
I'll focus on the cache layer and its interaction with the database layer. During normal time, the cache layer receives new tweets and propagates to the cluster to maintain timeline. It is intended to keep all active users' most recent tweets in memory to facilitate high latency read.
The cache layer is naturally sharded by user id, where a server will be responsible for a range of user. For availability, we consider storing the timeline copy more than once. Also, to support power user who may have many visits, we can store it in many servers.
There is one edge case about power user: it may be too costly to write to all followers. In this case, it is more beneficial to do join lazily on read. To facilitate that, we label the power user and their tweet will be kept in memory. When read is requested, this is joined to the power user tweet.
Now, how do we handle inactive user in the cache layer? Since our cache is intended to keep active users data, the data is not present in the cache layer. To optimize for latency, we can consider issuing parallel read request to followed user tweet and join it at the application level. This way, we can starts displaying some tweets rather than wait for the entire correct result.