Requirements
The system is Instagram, and the requirements are four key features agreed with the interviewer.
Storing and getting images is the only feature that is obvious in an Instagram interview. Every other feature is asked for, because the time constraints do not allow a deep design of all of them.
- Store and get images.
- Like and comment on posts.
- Follow someone. Every Instagram account is a user. Facebook is more complicated, because pages are followed too.
- Publish a news feed.
An image is a post. The questions on a post are whether a comment takes a comment, which makes it recursive, and whether a comment takes a like.
Instagram allows a like on a comment. It allows a reply to a comment but no reply to a reply, so there is one level of comment and then reply. That keeps the complexity constrained.
Here the design is simpler still: a post takes a single comment, a comment takes a like, and a comment takes no reply.
Designing the Data Schema
The data schema for liking and commenting on Instagram is an ER diagram of likes, comments, posts and an activity table.
The likes table holds a like ID, the user ID, the timestamp and whether the like is active. A like is on a post or on a comment, so the table holds a parent ID and a type field, comment or post. The type tells where to query.
The number of likes on a post has three designs:
- A select count from likes where the post ID matches. A news feed with many posts fires many of these, and it is slow.
- A likes column on the post and on the comment, incremented on each like. It is aggregation information, and it does not belong in the original table.
- An activity table that stores the number of likes for each parent ID. It needs no type.
The comment has an ID, the text and a timestamp. The post has a user ID, which answers a query for all the posts of a user.
Following Users
Following is one user following another user, and it is stored in a single table.
The table has three columns: the follower user ID, the followee user ID and the time at which the following started. The follower is the person who is following someone. The followee is the person who is being followed.
Gaurav follows Stephen Hawking, and the row holds the two user IDs and today's timestamp.
The table answers two questions:
- Who follows me. An equals condition on the followee column with Hawking's user ID gives all his followers as a list.
- Who are the people I follow. A single equals on the follower column with Gaurav's user ID gives their user IDs, Bill Gates among them.
In an interview, an answer that is known and given directly saves time for the interviewer and the candidate, and shows preparation. The interviewer expects to ask more questions, and a quick answer to a simple one leaves time for the advanced topics.
User Feed Service
The user feed service returns the user feed: the top 20 posts a user needs to look at.
A cell phone reaches the server side through a gateway. The gateway is the reverse proxy. It holds security mechanisms such as authentication tokens, and converts external protocols such as HTTP into an internal protocol.
The service runs on multiple servers. A load balancer keeps the state of the entire system and sends it to the gateway as a snapshot, updated every 10 seconds. The gateway hashes the user ID to find the box.
The feed is computed in a chain:
- The follow service returns the users followed by that user.
- The posts service returns the posts of each of them, so 10 followed users mean 10 requests.
- One call that takes a set of user IDs returns all the posts in one go.
- A limit on the number of posts reduces the load on the database and the network.
This does not scale. Every feed request recomputes all the posts, and the posts service gets bombarded.
Scaling the Instagram news feed
A precomputed user feed is a list of posts kept ready for each user, so a feed request is answered in one shot.
The feed is updated when a followed user posts:
- The post request goes to the posts service and is persisted in the database.
- The posts service notifies the user feed service.
- The user feed service gets the followers of the poster and adds the post to each one's queue. A queue holds at most 20 posts.
The queues live in a cache. Lost data is recomputed with the brute force formula, and the feed of a user who logs in infrequently is dropped and recomputed at login.
The user feed service notifies the followers. Polling every ten seconds costs the cell phone bandwidth and battery. A push over WebSockets is seamless.
A celebrity has millions of followers, and a million notifications at once crash the system. Batch processing rate limits them. In the pull model the followers ask the server.
The answer is a hybrid: pull for a celebrity, push for a normal user.