System design is one of the most significant parts of software engineering. It is intimidating to start designing a system. One of the main reasons is that the terminologies described in software architecture books are hard to understand. And there are no fixed guidelines. Everywhere you check seems to have a different approach. It becomes confusing for a new learner.
So, I set out to design a system based on my experience of learning architecture courses. This is part of a series on system design for beginners (link is given below). For this one, let’s design a photo-sharing service like Instagram.
Definition of the System:
We need to clarify the goal of the system. System design is such a vast topic; if we don’t narrow it down to a specific purpose, it will become complicated to design the system, especially for newbies.
Instagram is a photo-sharing service that enables its users to upload and share their photos and videos with other users, mostly their followers. As this is an exercise, we will design a simpler version of the main Instagram service.
In this service, a user can share photos and follow other users. There will be a newsfeed for each user. The ‘News Feed’ consists of top photos of all the people the user follows.
Requirements of The System:
In this part, we select the features of the system. The system requirements are divided into two parts:
Functional Requirements:
This type of requirement what the system has to deliver. You may say it is the main goal of the system.
Firstly, for Instagram, the users should be able to upload/download/view photos. Users may perform searches for images based on photo/video titles. One User can follow other users. Another essential feature is that the system should display a user’s News Feed that consists of photos of all the people the user follows.
As this is a practice for the system, we are not considering tags in photos, tag-based search, like and comment features, etc.
Non-functional Requirements
Performance, availability, consistency, scalability, reliability, etc., are important quality requirements in system design. We need to analyze these requirements for the system.
As a system designer, we might want to have a design that will be highly available, very high performant, top-notch consistency in the system, highly secured system, etc. But it’s not possible to achieve all these targets in one system. We need to have requirements that will work as restrictions on the design of a system. So, let’s define our NFRs:
Our system should be highly available. In the case of any web service, it’s a mandatory requirement. Home page generation latency should be at most 200 msec. If the home page generation takes too long, users will be dissatisfied, which is not acceptable.
As we choose for the system’s high availability, we should keep in mind that may hamper consistency across the system. The system should also be highly reliable, which means any uploaded photo or video by users should never be lost.
In this system, photos search and views would be more than uploading. As the system would have more read-heavy operations, we will focus on building a system that can retrieve photos quickly. While viewing photos, latency needs to be as low as possible.
Data flow:
If you are not sure where to start in a system design, always start with the data storing system. It will help to keep your focus aligning with the requirements of the system.
We need to support two scenarios at a high-level, one is to upload photos, and another is to view/search photos. Our system would need some object storage servers to store photos and some database servers to store metadata information.
Defining the database schema is the first phase of understanding the data flow between different components of the system. We need to store user profile data like the follower list, uploaded photos by users. There should be a table that stores all data regarding photos. If we want to show recent photos first, we need to index (PhotoID, CreationDate). Tables in the DB could be:
Table Name : table indexe1,index2 etc
Photo: PhotoID (pk), UserID, PhotoLocation, CreationDate
User: UserID(pk), Name, Email, DOB, LastLoginTime
Follow: UserID1, UserID2 (paired pk)
FeedItem: FeedID(pk), UserID,Contents, PhotoID,CreationDate
**pk = primary key
We may store the above tables in an RDBMS like MySQL as we will require joins between tables. But relational databases have some challenges of their own. Though it is possible to scale a relational database across multiple servers, it is a challenging process. We may store photos in a distributed file storage like HDFS or S3.
When users upload photos, storing them in the database is a slow process as they are stored on a disk. But in the case of reads, the process will be faster, especially if we serve them from the cache.
As uploading is a slow process, if we put both write and read photos on the same server, the system may get too busy with all the ‘write’ requests. We have to consider web servers have a connection limit before designing our system.
Let’s say a server can have a maximum of 5000 connections at any time. So, it can’t have more than 5000 concurrent uploads or downloads. To handle this type of bottleneck, we can use responsibility segregation.
We can split reads and writes into two separate services. So, we will have some servers for reads and different servers for writes. This separation will also give us a chance to scale each operation independently.
Availability and Reliability:
We can not lose the photos uploaded by the users. Reliability is a huge factor for this system. So, we need to have more than one copy of each file. In that case, if one server is dead, we still have other copies of those photos.
We can not have a single point of failure in a system. If we keep multiple copies of a component, it may remove the single point of failure in the system. For making a highly available system, we need to keep multiple replicas of the services in the system. So, even if some of the servers are down, the system may remain available. Creating redundancy in a system also provides a backup in a crisis.
Scalability:
For supporting millions of users, we need to partition our database to divide and store our data into different DB servers. We can use database sharding for metadata.
Partitioning based on UserID:
If we partition metadata DB based on ‘UserID,’ we may keep all the user photos in the same shard. One User seems to have almost 3 TB of data. If one DB shard is 1TB, we will need three shards of data of each User.
For better performance and scalability, we may keep ten shards. In that case, we can find the shard number by UserId%10 and store data there.
We may face some problems in this approach if a user is a popular celebrity. That portion of shards will be hit frequently.
Besides, some users may upload more photos compared to others. In that case, the distribution might not be uniform.
More importantly, if we can not store all user pictures in one shard, we may need to distribute photos into different shards.
And if a shard is down, we may face an unavailability issue for a user.
Partitioning based on PhotoID:
Another way of partitioning DB can be by using PhotoID. We need to create a unique ID for each photo. Each DB shard needs to have its auto-increment sequence for PhotoIDs, but then each shard will have the same photo iD in its portion. We can add ShardId with each photoID; this can make the photoID unique within the system.
Load balancer:
As we use multiple copies of a server, we need to distribute the user traffic to those servers efficiently. The load balancer will distribute the user requests to various servers uniformly. We can use IP-based routing for the Newsfeed service, as the same user requests go to the same server, and caching can be used to get a faster response.
If there are no such requirements, round-robin should be a simple and good solution for the server selection strategy of load balancers.
API GateWay:
We have a lot of services for our system. Some will generate newsfeed, some help storing photos, some viewing the photos, etc. We need to have a single entry point for all clients. This entry point is API Gateway.
It will handle all the requests by sending them to multiple services. And for some requests, it will just route to the specific server. The API gateway may also implement security, such as verifying the client’s permission to perform the request.
NewsFeed Generation:
The News Feed for any user contains the latest, most popular, and relevant photos of the people that the User follows. If we generate the newsfeed in real-time, it would be very high latency. So, we will try to pre-generate the newsfeed. So, the Post service will store the photos in the database. Newsfeed service precomputes feed for all the users.
We need to have specific servers which would continuously generate user newsfeed and store them in the database. So, when the User needs the latest photos for the newsfeed, we need to query the table.
Now, how does a user get the latest newsfeed from the server? We may consider below approaches:
Pull-Based Approach
In this approach, each User may poll the server after a regular interval to check if any friend has a new update. The server has to find all the user connections and check for each friend to create a new post. If there are new posts, the database’s query will get all the recent posts created by a user’s connections and show them on their home page.
The users may ping the Newsfeed servers for pre-generated feeds after a regular interval. The lower the time interval, the more recent data will be found in the feed.
This approach is time-consuming. As users are polling the database after a regular interval, it will put a huge amount of unnecessary load on the database.
Push-Based Approach
In this approach, servers can push new data to the users as soon as it is available. Users have to maintain a long polling request with the server for receiving the updates.
As the Newsfeed service is pre generating the feeds, the Notification service will notify the active users about the new posts. Session DB will keep data of the user’s connections who are online.
You may check the various notification approaches at this link.
We may implement a pull-based model for all the users who have a high number of followers. And we can use a push-based approach for those who have a few hundred followers.
Pagination:
The newsfeed of users can be a large response. So, we may design the API to return a single page of the feed. Let’s say we are sending at most 50 posts every time a feed request is made.
The user may send another request for the next page of feeds for the next time. And within that period, if there is not enough feed, Newsfeed may generate the next page. This technique is called pagination.
Conclusion:
To ensure the availability of the system, we used replication of servers so that others can still provide service if one goes down. Databases are also replicated to ensure data reliability. as we can not afford to lose data. We may use a hybrid approach of pull and push-based for the user newsfeed. We are precomputing feed because, in real-time, it would take a long time.
Resource: Grokking the System Design Interview, Video Designing Instagram
This article is part of the system design series. Some article links of the series are given here:
Design a distributed logging system
System Design Basics: Getting started with Caching
System Design Basics: Client-Server architecture
System Design Basics: Availability in Distributed Systems
System Design Basics: Load balancer 101
System Design of Google Auto-Suggestion Service
System Design Analysis of Google Drive
