Data Partitioning and Replication Cache and Load Balancer Security and Permissions Designing Instagram 1. What is Instagram? High Level System Design 6. Database Schema 7. Data Size Estimation 8. Component Design 9. Reliability and Redundancy Data Sharding Ranking and News Feed Generation News Feed Creation with Sharded Data Cache and Load balancing Designing Dropbox 1. Why Cloud Storage? High Level Design 6. Client b. Metadata Database c. Synchronization Service d. Message Queuing Service e. File Processing Workflow 8. Data Deduplication 9. Metadata Partitioning Caching Security, Permissions and File Sharing Designing Facebook Messenger 1. What is Facebook Messenger? High Level Design 5. Detailed Component Design a. Messages Handling b. Storing and retrieving the messages from the database c.

Data partitioning 7. Cache 8. Load balancing 9. Fault tolerance and Replication Extended Requirements a. Group chat b. Push notifications Designing Twitter 1. What is Twitter? Data Sharding 8. Timeline Generation Replication and Fault Tolerance Load Balancing Monitoring Extended Requirements Designing Youtube or Netflix 1. Why Youtube? Detailed Component Design 8. Metadata Sharding 9. Video Deduplication Cache Content Delivery Network CDN Fault Tolerance Designing Typeahead Suggestion 1. What is Typeahead Suggestion? Basic System Design and Algorithm 4. Permanent Storage of the Trie 5. Scale Estimation 6. Data Partition 7. Replication and Load Balancer 9. Fault Tolerance Typeahead Client Personalization Designing an API Rate Limiter 1. What is a Rate Limiter? Why do we need API rate limiting? Requirements and Goals of the System 4.

How to do Rate Limiting? What are different types of throttling? What are different types of algorithms used for Rate Limiting? High level design for Rate Limiter 8. Basic System Design and Algorithm 9. Sliding Window algorithm Sliding Window with Counters Data Sharding and Caching Should we rate limit by IP or by user? Designing Twitter Search 1. What is Twitter Search? Detailed Component Design 7. Fault Tolerance 8. Ranking Designing a Web Crawler 1. What is a Web Crawler? High Level design How to crawl? Difficulties in implementing efficient web crawler 6. Fault tolerance 8. Data Partitioning 9. Database Design 6. High Level System Design 7. Feed Ranking 9. Data Partitioning Designing Yelp or Nearby Friends 1. Why Yelp or Proximity Server? Scale Estimation 4. Database Schema 5. SQL solution b. Grids c. Dynamic size grids 7. Data Partitioning 8.

Replication and Fault Tolerance 9. Load Balancing LB Ranking Designing Uber backend 1. What is Uber? Basic System Design and Algorithm 5. Fault Tolerance and Replication 6. Ranking 7. What is an online movie ticket booking system? Capacity Estimation 5. Database Design 7. Detailed Component Design 9. Concurrency Data Partitioning Additional Resources System Design Basics Key Characteristics of Distributed Systems Scalability Reliability Availability Efficiency Serviceability or Manageability Load Balancing Benefits of Load Balancing Load Balancing Algorithms Redundant Load Balancers Caching Application server cache Content Distribution Network CDN Cache Invalidation Cache eviction policies Sharding or Data Partitioning 1. Partitioning Methods 2. Partitioning Criteria 3. Common Problems of Sharding Indexes Example: A library catalog How do Indexes decrease write performance?

Proxies Proxy Server Types Open Proxy Reverse Proxy Redundancy and Replication SQL vs. NoSQL SQL NoSQL High level differences between SQL and NoSQL SQL VS. NoSQL - Which one to use? Reasons to use SQL database Reasons to use NoSQL database CAP Theorem Consistent Hashing What is Consistent Hashing? How does it work? Long-Polling vs WebSockets vs Server-Sent Events Ajax Polling HTTP Long-Polling WebSockets Server-Sent Events SSEs. Home Computers Grokking The System Design Interview [PDF] Includes Multiple formats No login requirement Instant download Verified by our users.

Grokking The System Design Interview [PDF] Authors: Design Gurus PDF Computers Add to Wishlist Share. This document was uploaded by our user. The uploader already confirmed that they had the permission to publish it. Report DMCA. E-Book Overview System design questions have become a standard part of the software engineering interview process. Performance in these interviews reflects upon your ability to work with complex systems and translates into the position and salary the interviewing company offers you. Most engineers struggle with the system design interview SDI , partly because of their lack of experience in developing large-scale systems and partly because of the unstructured nature of SDIs. This course is a complete guide to master the SDIs. We've carefully chosen a set of questions that have not only been repeatedly asked at top companies, but also provide a thorough experience to handle any system design problem. Candidates who spend enough time to define the end goals of the system always have a better chance to be successful in the interview.

Also, since we only have minutes to design a supposedly large system, we should clarify what parts of the system we will be focusing on. Will tweets contain photos and videos? Are we focusing on the backend only or are we developing the front-end too? Will users be able to search tweets? Do we need to display hot trending topics? Will there be any push notification for new or important tweets? All such question will determine how our end design will look like. Step 2: System interface definition Define what APIs are expected from the system. This will also help later when we will be focusing on scaling, partitioning, load balancing and caching.

We will have different numbers if users can have photos and videos in their tweets. This will be crucial in deciding how we will manage traffic and balance load between servers. Step 4: Defining data model Defining the data model early will clarify how data will flow among different components of the system. Later, it will guide towards data partitioning and management. The candidate should be able to identify various entities of the system, how they will interact with each other, and different aspect of data management like storage, transportation, encryption, etc. Here are some entities for our Twitterlike service: User: UserID, Name, Email, DoB, CreationData, LastLogin, etc. Tweet: TweetID, Content, TweetLocation, NumberOfLikes, TimeStamp, etc. UserFollowo: UserdID1, UserID2 FavoriteTweets: UserID, TweetID, TimeStamp Which database system should we use? Will NoSQL like Cassandra best fit our needs, or should we use a MySQL-like solution? What kind of block storage should we use to store photos and videos?

Step 5: High-level design Draw a block diagram with boxes representing the core components of our system. We should identify enough components that are needed to solve the actual problem from end-to-end. On the backend, we need an efficient database that can store all the tweets and can support a huge number of reads. We will also need a distributed file storage system for storing photos and videos. We should be able to present different approaches, their pros and cons, and explain why we will prefer one approach on the other. Remember there is no single answer, the only important thing is to consider tradeoffs between different options while keeping system constraints in mind. Should we try to store all the data of a user on the same database? What issue could it cause? Step 7: Identifying and resolving bottlenecks Try to discuss as many bottlenecks as possible and different approaches to mitigate them.

What are we doing to mitigate it? Do we get alerts whenever critical components fail or their performance degrades? Summary In short, preparation and being organized during the interview are the keys to be successful in system design interviews. The above-mentioned steps should guide you to remain on track and cover all the different aspects while designing a system. Designing a URL Shortening service like TinyURL Let's design a URL shortening service like TinyURL. This service will provide short aliases redirecting to long URLs. Similar services: bit. ly, goo. gl, qlink.

me, etc. Difficulty Level: Easy 1. URL shortening is used to create shorter aliases for long URLs. Short links save a lot of space when displayed, printed, messaged, or tweeted. Additionally, users are less likely to mistype shorter URLs. URL shortening is used for optimizing links across devices, tracking individual links to analyze audience and campaign performance, and hiding affiliated original URLs. com before, please try creating a new shortened URL and spend some time going through the various options their service offers. This will help you a lot in understanding this chapter. Requirements and Goals of the System � You should always clarify requirements at the beginning of the interview.

Be sure to ask questions to find the exact scope of the system that the interviewer has in mind. Our URL shortening system should meet the following requirements: Functional Requirements: 1. Given a URL, our service should generate a shorter and unique alias of it. This is called a short link. When users access a short link, our service should redirect them to the original link. Users should optionally be able to pick a custom short link for their URL. Links will expire after a standard default timespan. Users should be able to specify the expiration time. Non-Functional Requirements: 1.

The system should be highly available. This is required because, if our service is down, all the URL redirections will start failing. URL redirection should happen in real-time with minimal latency. Shortened links should not be guessable not predictable. Extended Requirements: 1. Analytics; e. Our service should also be accessible through REST APIs by other services. Capacity Estimation and Constraints Our system will be read-heavy. There will be lots of redirection requests compared to new URL shortenings. Since we have 20K requests per second, we will be getting 1. System APIs � Once we've finalized the requirements, it's always a good idea to define the system APIs.

This should explicitly state what is expected from the system. We can have SOAP or REST APIs to expose the functionality of our service. This will be used to, among other things, throttle users based on their allocated quota. Returns: string A successful insertion returns the shortened URL; otherwise, it returns an error code. How do we detect and prevent abuse? A malicious user can put us out of business by consuming all URL keys in the current design. Database Design � Defining the DB schema in the early stages of the interview would help to understand the data flow among various components and later would guide towards data partitioning. A few observations about the nature of the data we will store: 1. We need to store billions of records. Each object we store is small less than 1K. There are no relationships between records—other than storing which user created a URL.

Our service is read-heavy. A NoSQL choice would also be easier to scale. Please see SQL vs NoSQL for more details. Basic System Design and Algorithm The problem we are solving here is, how to generate a short and unique key for a given URL. The last six characters of this URL is the short key we want to generate. Encoding actual URL We can compute a unique hash e. of the given URL. The hash can then be encoded for displaying. A reasonable question would be, what should be the length of the short key? Since we only have space for 8 characters per short key, how will we choose our key then? We can take the first 6 or 8 letters for the key.

This could result in key duplication though, upon which we can choose some other characters out of the encoding string or swap some characters. What are different issues with our solution? We have the following couple of problems with our encoding scheme: 1. If multiple users enter the same URL, they can get the same shortened URL, which is not acceptable. What if parts of the URL are URL-encoded? Workaround for the issues: We can append an increasing sequence number to each input URL to make it unique, and then generate a hash of it. Possible problems with this approach could be an ever-increasing sequence number. Can it overflow? Appending an increasing sequence number will also impact the performance of the service. Another solution could be to append user id which should be unique to the input URL. However, if the user has not signed in, we would have to ask the user to choose a uniqueness key.

Even after this, if we have a conflict, we have to keep generating a key until we get a unique one. Request flow for shortening of a URL 1 of 9 b. Whenever we want to shorten a URL, we will just take one of the already-generated keys and use it. This approach will make things quite simple and fast. KGS will make sure all the keys inserted into key-DB are unique Can concurrency cause problems? If there are multiple servers reading keys concurrently, we might get a scenario where two or more servers try to read the same key from the database. How can we solve this concurrency problem?

KGS can use two tables to store keys: one for keys that are not used yet, and one for all the used keys. As soon as KGS gives keys to one of the servers, it can move them to the used keys table. KGS can always keep some keys in memory so that it can quickly provide them whenever a server needs them. For simplicity, as soon as KGS loads some keys in memory, it can move them to the used keys table. This ensures each server gets unique keys. If KGS dies before assigning all the loaded keys to some server, we will be wasting those keys—which is acceptable, given the huge number of keys we have. KGS also has to make sure not to give the same key to multiple servers. For that, it must synchronize or get a lock on the data structure holding the keys before removing keys from it and giving them to a server What would be the key-DB size? With base64 encoding, we can generate Yes, it is.

To solve this, we can have a standby replica of KGS. Whenever the primary server dies, the standby server can take over to generate and provide keys. Can each app server cache some keys from key-DB? Yes, this can surely speed things up. Although in this case, if the application server dies before consuming all the keys, we will end up losing those keys. This can be acceptable since we have 68B unique six letter keys. How would we perform a key lookup? We can look up the key in our database or key-value store to get the full URL. Should we impose size limits on custom aliases? Our service supports custom aliases. However, it is reasonable and often desirable to impose a size limit on a custom alias to ensure we have a consistent URL database.

High level system design for URL shortening 7. Data Partitioning and Replication To scale out our DB, we need to partition it so that it can store information about billions of URLs. We need to come up with a partitioning scheme that would divide and store our data to different DB servers. Range Based Partitioning: We can store URLs in separate partitions based on the first letter of the URL or the hash key. This approach is called range-based partitioning. We can even combine certain less frequently occurring letters into one database partition. The main problem with this approach is that it can lead to unbalanced servers. Hash-Based Partitioning: In this scheme, we take a hash of the object we are storing. We then calculate which partition to use based upon the hash. Our hashing function will randomly distribute URLs into different partitions e. This approach can still lead to overloaded partitions, which can be solved by using Consistent Hashing.

Cache We can cache URLs that are frequently accessed. We can use some off-the-shelf solution like Memcache, which can store full URLs with their respective hashes. The application servers, before hitting backend storage, can quickly check if the cache has the desired URL. How much cache should we have? Since a modern-day server can have GB memory, we can easily fit all the cache into one machine. Alternatively, we can use a couple of smaller servers to store all these hot URLs. Which cache eviction policy would best fit our needs?

Least Recently Used LRU can be a reasonable policy for our system. Under this policy, we discard the least recently used URL first. We can use a Linked Hash Map or a similar data structure to store our URLs and Hashes, which will also keep track of the URLs that have been accessed recently. To further increase the efficiency, we can replicate our caching servers to distribute load between them. How can each cache replica be updated? Whenever there is a cache miss, our servers would be hitting a backend database. Whenever this happens, we can update the cache and pass the new entry to all the cache replicas. Each replica can update their cache by adding the new entry. If a replica already has that entry, it can simply ignore it.

Request flow for accessing a shortened URL 1 of 11 9. Load Balancer LB We can add a Load balancing layer at three places in our system: 1. Between Clients and Application servers 2. Between Application Servers and database servers 3. Between Application Servers and Cache servers Initially, we could use a simple Round Robin approach that distributes incoming requests equally among backend servers. This LB is simple to implement and does not introduce any overhead. Another benefit of this approach is that if a server is dead, LB will take it out of the rotation and will stop sending any traffic to it. A problem with Round Robin LB is that server load is not taken into consideration.

If a server is overloaded or slow, the LB will not stop sending new requests to that server. To handle this, a more intelligent LB solution can be placed that periodically queries the backend server about its load and adjusts traffic based on that. Purging or DB cleanup Should entries stick around forever or should they be purged? If a user-specified expiration time is reached, what should happen to the link? If we chose to actively search for expired links to remove them, it would put a lot of pressure on our database. Instead, we can slowly remove expired links and do a lazy cleanup. Our service will make sure that only expired links will be deleted, although some expired links can live longer but will never be returned to users. This service should be very lightweight and can be scheduled to run only when the user traffic is expected to be low.

This could be tricky. Since storage is getting cheap, we can decide to keep links forever. Detailed component design for URL shortening Telemetry How many times a short URL has been used, what were user locations, etc.? How would we store these statistics? If it is part of a DB row that gets updated on each view, what will happen when a popular URL is slammed with a large number of concurrent requests? Some statistics worth tracking: country of the visitor, date and time of access, web page that refers the click, browser, or platform from where the page was accessed. Security and Permissions Can users create private URLs or allow a particular set of users to access a URL?

We can also create a separate table to store UserIDs that have permission to see a specific URL. If a user does not have permission and tries to access a URL, we can send an error HTTP back. The columns will store the UserIDs of those users that have permissions to see the URL. Designing Pastebin Let's design a Pastebin like web service, where users can store plain text. Users of the service will enter a piece of text and get a randomly generated URL to access it. Similar Services: pastebin. com, pasted. co, chopapp. com Difficulty Level: Easy 1. Pastebin like services enable users to store plain text or images over the network typically the Internet and generate unique URLs to access the uploaded data. Such services are also used to share data over the network quickly, as users would just need to pass the URL to let other users see it. Requirements and Goals of the System Our Pastebin service should meet the following requirements: Functional Requirements: 1. Users will only be able to upload text.

Data and links will expire after a specific timespan automatically; users should also be able to specify expiration time. Users should optionally be able to pick a custom alias for their paste. The system should be highly reliable, any data uploaded should not be lost. This is required because if our service is down, users will not be able to access their Pastes. Users should be able to access their Pastes in real-time with minimum latency. Paste links should not be guessable not predictable. Analytics, e. Some Design Considerations Pastebin shares some requirements with URL Shortening service, but there are some additional design considerations we should keep in mind.

What should be the limit on the amount of text user can paste at a time? We can limit users not to have Pastes bigger than 10MB to stop the abuse of the service. Should we impose size limits on custom URLs? Since our service supports custom URLs, users can pick any URL that they like, but providing a custom URL is not mandatory. However, it is reasonable and often desirable to impose a size limit on custom URLs, so that we have a consistent URL database. Capacity Estimation and Constraints Our services will be read-heavy; there will be more read requests compared to new Pastes creation.

We can assume a ratio between read and write. This leaves us with five million reads per day. At this rate, we will be storing 10GB of data per day. With 1M pastes every day we will have 3. We need to generate and store keys to uniquely identify these pastes. If we use base64 encoding [A-Z, a-z, ,. Bandwidth estimates: For write requests, we expect 12 new pastes per second, resulting in KB of ingress per second. Therefore, total data egress sent to users will be 0. Memory estimates: We can cache some of the hot pastes that are frequently accessed. System APIs We can have SOAP or REST APIs to expose the functionality of our service. Returns: string A successful insertion returns the URL through which the paste can be accessed, otherwise, it will return an error code.

This API will return the textual data of the paste. Database Design A few observations about the nature of the data we are storing: 1. Each metadata object we are storing would be small less than bytes. Each paste object we are storing can be of medium size it can be a few MB. There are no relationships between records, except if we want to store which user created what Paste. High Level Design At a high level, we need an application layer that will serve all the read and write requests. Application layer will talk to a storage layer to store and retrieve data. We can segregate our storage layer with one database storing metadata related to each paste, users, etc. This division of data will also allow us to scale them individually. Application server Client Metadata storage Object storage 8. Application layer Our application layer will process all incoming and outgoing requests. The application servers will be talking to the backend data store components to serve the requests.

How to handle a write request? Upon receiving a write request, our application server will generate a six-letter random string, which would serve as the key of the paste if the user has not provided a custom key. The application server will then store the contents of the paste and the generated key in the database. After the successful insertion, the server can return the key to the user. One possible problem here could be that the insertion fails because of a duplicate key. Since we are generating a random key, there is a possibility that the newly generated key could match an existing one. In that case, we should regenerate a new key and try again. We should return an error to the user if the custom key they have provided is already present in our database.

Whenever we want to store a new paste, we will just take one of the already generated keys and use it. This approach will make things quite simple and fast since we will not be worrying about duplications or collisions. KGS will make sure all the keys inserted in key-DB are unique. KGS can use two tables to store keys, one for keys that are not used yet and one for all the used keys. As soon as KGS gives some keys to an application server, it can move these to the used keys table. KGS can always keep some keys in memory so that whenever a server needs them, it can quickly provide them. As soon as KGS loads some keys in memory, it can move them to the used keys table, this way we can make sure each server gets unique keys. If KGS dies before using all the keys loaded in memory, we will be wasting those keys. We can ignore these keys given that we have a huge number of them. To solve this, we can have a standby replica of KGS and whenever the primary server dies it can take over to generate and provide keys.

This could be acceptable since we have 68B unique six letters keys, which are a lot more than we require. How does it handle a paste read request? Upon receiving a read paste request, the application service layer contacts the datastore. Otherwise, an error code is returned. Datastore layer We can divide our datastore layer into two: 1. Metadata database: We can use a relational database like MySQL or a Distributed Key-Value store like Dynamo or Cassandra. Whenever we feel like hitting our full capacity on content storage, we can easily increase it by adding more servers. Detailed component design for Pastebin 9. Purging or DB Cleanup Please see Designing a URL Shortening service. Data Partitioning and Replication Please see Designing a URL Shortening service. Cache and Load Balancer Please see Designing a URL Shortening service.

Security and Permissions Please see Designing a URL Shortening service. Designing Instagram Let's design a photo-sharing service like Instagram, where users can upload photos to share them with other users. Similar Services: Flickr, Picasa Difficulty Level: Medium 1. Instagram is a social networking service which enables its users to upload and share their photos and videos with other users. Instagram users can choose to share information either publicly or privately. Anything shared publicly can be seen by any other user, whereas privately shared content can only be accessed by a specified set of people. Instagram also enables its users to share through many other social networking platforms, such as Facebook, Twitter, Flickr, and Tumblr.

For the sake of this exercise, we plan to design a simpler version of Instagram, where a user can share photos and can also follow other users. Users can follow other users. Non-functional Requirements 1. Our service needs to be highly available. The acceptable latency of the system is ms for News Feed generation. The system should be highly reliable; any uploaded photo or video should never be lost. Not in scope: Adding tags to photos, searching photos on tags, commenting on photos, tagging users to photos, who to follow, etc. Some Design Considerations The system would be read-heavy, so we will focus on building a system that can retrieve photos quickly. Practically, users can upload as many photos as they like. Efficient management of storage should be a crucial factor while designing this system. Low latency is expected while viewing photos. If a user uploads a photo, the system will guarantee that it will never be lost. Our service would need some object storage servers to store photos and also some database servers to store metadata information about the photos.

Database Schema � Defining the DB schema in the early stages of the interview would help to understand the data flow among various components and later would guide towards data partitioning. We need to store data about users, their uploaded photos, and people they follow. Photo table will store all data related to a photo; we need to have an index on PhotoID, CreationDate since we need to fetch recent photos first. A straightforward approach for storing the above schema would be to use an RDBMS like MySQL since we require joins. But relational databases come with their challenges, especially when we need to scale them. For details, please take a look at SQL vs. We can store photos in a distributed file storage like HDFS or S3. We can store the above schema in a distributed key-value store to enjoy the benefits offered by NoSQL.

We need to store relationships between users and photos, to know who owns which photo. We also need to store the list of people a user follows. For both of these tables, we can use a wide-column datastore like Cassandra. Cassandra or key-value stores in general, always maintain a certain number of replicas to offer reliability. UserFollow: Each row in the UserFollow table will consist of 8 bytes. If we have million users and on average each user follows users. We would need 1. Component Design Photo uploads or writes can be slow as they have to go to the disk, whereas reads will be faster, especially if they are being served from cache. Uploading users can consume all the available connections, as uploading is a slow process.

We should keep in mind that web servers have a connection limit before designing our system. To handle this bottleneck we can split reads and writes into separate services. Reliability and Redundancy Losing files is not an option for our service. Therefore, we will store multiple copies of each file so that if one storage server dies we can retrieve the photo from the other copy present on a different storage server. This same principle also applies to other components of the system. If we want to have high availability of the system, we need to have multiple replicas of services running in the system, so that if a few services die down the system still remains available and running. Redundancy removes the single point of failure in the system. If only one instance of a service is required to run at any point, we can run a redundant secondary copy of the service that is not serving any traffic, but it can take control after the failover when primary has a problem.

Creating redundancy in a system can remove single points of failure and provide a backup or spare functionality if needed in a crisis. For example, if there are two instances of the same service running in production and one fails or degrades, the system can failover to the healthy copy. Failover can happen automatically or require manual intervention. If one DB shard is 1TB, we will need four shards to store 3. To uniquely identify any photo in our system, we can append shard number with each PhotoID. How can we generate PhotoIDs? Each DB shard can have its own auto-increment sequence for PhotoIDs and since we will append ShardID with each PhotoID, it will make it unique throughout our system. What are the different issues with this partitioning scheme? How would we handle hot users? Several people follow such hot users and a lot of other people see any photo they upload.

Some users will have a lot of photos compared to others, thus making a non-uniform distribution of storage. What if we cannot store all pictures of a user on one shard? If we distribute photos of a user onto multiple shards will it cause higher latencies? We would not need to append ShardID with PhotoID in this case as PhotoID will itself be unique throughout the system. Here we cannot have an auto-incrementing sequence in each shard to define PhotoID because we need to know PhotoID first to find the shard where it will be stored. One solution could be that we dedicate a separate database instance to generate auto-incrementing IDs.

If our PhotoID can fit into 64 bits, we can define a table containing only a 64 bit ID field. So whenever we would like to add a photo in our system, we can insert a new row in this table and take that ID to be our PhotoID of the new photo. Yes, it would be. A workaround for that could be defining two such databases with one generating even numbered IDs and the other odd numbered. Both these servers could be out of sync with one generating more keys than the other, but this will not cause any issue in our system. We can extend this design by defining separate ID tables for Users, Photo-Comments, or other objects present in our system. How can we plan for the future growth of our system?

We can have a large number of logical partitions to accommodate future data growth, such that in the beginning, multiple logical partitions reside on a single physical database server. Since each database server can have multiple database instances on it, we can have separate databases for each logical partition on any server. So whenever we feel that a particular database server has a lot of data, we can migrate some logical partitions from it to another server. We can maintain a config file or a separate database that can map our logical partitions to database servers; this will enable us to move partitions around easily. Whenever we want to move a partition, we only have to update the config file to announce the change. Ranking and News Feed Generation To create the News Feed for any given user, we need to fetch the latest, most popular and relevant photos of the people the user follows.

Our application server will first get a list of people the user follows and then fetch metadata info of latest photos from each user. In the final step, the server will submit all these photos to our ranking algorithm which will determine the top photos based on recency, likeness, etc. and return them to the user. To improve the efficiency, we can pre-generate the News Feed and store it in a separate table. So whenever any user needs the latest photos for their News Feed, we will simply query this table and return the results to the user. Whenever these servers need to generate the News Feed of a user, they will first query the UserNewsFeed table to find the last time the News Feed was generated for that user.

Then, new News Feed data will be generated from that time onwards following the steps mentioned above. What are the different approaches for sending News Feed contents to the users? Pull: Clients can pull the News Feed contents from the server on a regular basis or manually whenever they need it. Possible problems with this approach are a New data might not be shown to the users until clients issue a pull request b Most of the time pull requests will result in an empty response if there is no new data. Push: Servers can push new data to the users as soon as it is available. To efficiently manage this, users have to maintain a Long Poll request with the server for receiving the updates. A possible problem with this approach is, a user who follows a lot of people or a celebrity user who has millions of followers; in this case, the server has to push updates quite frequently.

Hybrid: We can adopt a hybrid approach. We can move all the users who have a high number of follows to a pull-based model and only push data to those users who have a few hundred or thousand follows. News Feed Creation with Sharded Data One of the most important requirement to create the News Feed for any given user is to fetch the latest photos from all people the user follows. For this, we need to have a mechanism to sort photos on their time of creation. To efficiently do this, we can make photo creation time part of the PhotoID. As we will have a primary index on PhotoID, it will be quite quick to find the latest PhotoIDs.

We can use epoch time for this. So to make a new PhotoID, we can take the current epoch time and append an auto-incrementing ID from our keygenerating DB. What could be the size of our PhotoID? Since on the average, we are expecting 23 new photos per second; we can allocate 9 bits to store auto incremented sequence. We can reset our auto incrementing sequence every second. Cache and Load balancing Our service would need a massive-scale photo delivery system to serve the globally distributed users. Our service should push its content closer to the user using a large number of geographically distributed photo cache servers and use CDNs for details see Caching.

We can introduce a cache for metadata servers to cache hot database rows. We can use Memcache to cache the data and Application servers before hitting database can quickly check if the cache has desired rows. Least Recently Used LRU can be a reasonable cache eviction policy for our system. Under this policy, we discard the least recently viewed row first. How can we build more intelligent cache? If we go with rule, i. Designing Dropbox Let's design a file hosting service like Dropbox or Google Drive. Cloud file storage enables users to store their data on remote servers.

Usually, these servers are maintained by cloud storage providers and made available to users over a network typically through the Internet. Users pay for their cloud data storage on a monthly basis. Similar Services: OneDrive, Google Drive Difficulty Level: Medium 1. Cloud file storage services have become very popular recently as they simplify the storage and exchange of digital resources among multiple devices. The shift from using single personal computers to using multiple devices with different platforms and operating systems such as smartphones and tablets each with portable access from various geographical locations at any time, is believed to be accountable for the huge popularity of cloud storage services. Following are some of the top benefits of such services: Availability: The motto of cloud storage services is to have data availability anywhere, anytime.

Cloud storage ensures that users will never lose their data by keeping multiple copies of the data stored on different geographically located servers. Scalability: Users will never have to worry about getting out of storage space. With cloud storage you have unlimited storage as long as you are ready to pay for it. What do we wish to achieve from a Cloud Storage system? What is Typeahead Suggestion? Basic System Design and Algorithm 4. Permanent Storage of the Trie 5. Scale Estimation 6. Data Partition 7. Replication and Load Balancer 9. Fault Tolerance Typeahead Client Personalization Designing an API Rate Limiter 1. What is a Rate Limiter? Why do we need API rate limiting? Requirements and Goals of the System 4. How to do Rate Limiting? What are different types of throttling? What are different types of algorithms used for Rate Limiting?

High level design for Rate Limiter 8. Basic System Design and Algorithm 9. Sliding Window algorithm Sliding Window with Counters Data Sharding and Caching Should we rate limit by IP or by user? Designing Twitter Search 1. What is Twitter Search? Detailed Component Design 7. Fault Tolerance 8. Ranking Designing a Web Crawler 1. What is a Web Crawler? High Level design How to crawl? Difficulties in implementing efficient web crawler 6. Fault tolerance 8. Data Partitioning 9. Database Design 6. High Level System Design 7. Feed Ranking 9. Data Partitioning Designing Yelp or Nearby Friends 1.

Why Yelp or Proximity Server? Scale Estimation 4. Database Schema 5. SQL solution b. Grids c. Dynamic size grids 7. Data Partitioning 8. Replication and Fault Tolerance 9. Load Balancing LB Ranking Designing Uber backend 1. What is Uber? Basic System Design and Algorithm 5. Fault Tolerance and Replication 6. Ranking 7. What is an online movie ticket booking system? Capacity Estimation 5. Database Design 7. Detailed Component Design 9. Concurrency Data Partitioning Additional Resources System Design Basics Key Characteristics of Distributed Systems Scalability Reliability Availability Efficiency Serviceability or Manageability Load Balancing Benefits of Load Balancing Load Balancing Algorithms Redundant Load Balancers Caching Application server cache Content Distribution Network CDN Cache Invalidation Cache eviction policies Sharding or Data Partitioning 1.

Partitioning Methods 2. Partitioning Criteria 3. Common Problems of Sharding Indexes Example: A library catalog How do Indexes decrease write performance? Proxies Proxy Server Types Open Proxy Reverse Proxy Redundancy and Replication SQL vs. NoSQL SQL NoSQL High level differences between SQL and NoSQL SQL VS. NoSQL - Which one to use? Reasons to use SQL database Reasons to use NoSQL database CAP Theorem Consistent Hashing What is Consistent Hashing? How does it work? Long-Polling vs WebSockets vs Server-Sent Events Ajax Polling HTTP Long-Polling WebSockets Server-Sent Events SSEs. Home Computers Grokking The System Design Interview [PDF] Includes Multiple formats No login requirement Instant download Verified by our users. Grokking The System Design Interview [PDF] Authors: Design Gurus PDF Computers Add to Wishlist Share. This document was uploaded by our user. The uploader already confirmed that they had the permission to publish it.

Report DMCA. E-Book Overview System design questions have become a standard part of the software engineering interview process. Performance in these interviews reflects upon your ability to work with complex systems and translates into the position and salary the interviewing company offers you. Most engineers struggle with the system design interview SDI , partly because of their lack of experience in developing large-scale systems and partly because of the unstructured nature of SDIs. This course is a complete guide to master the SDIs. We've carefully chosen a set of questions that have not only been repeatedly asked at top companies, but also provide a thorough experience to handle any system design problem. Candidates who spend enough time to define the end goals of the system always have a better chance to be successful in the interview. Also, since we only have minutes to design a supposedly large system, we should clarify what parts of the system we will be focusing on.

Will tweets contain photos and videos? Are we focusing on the backend only or are we developing the front-end too? Will users be able to search tweets? Do we need to display hot trending topics? Will there be any push notification for new or important tweets? All such question will determine how our end design will look like. Step 2: System interface definition Define what APIs are expected from the system. This will also help later when we will be focusing on scaling, partitioning, load balancing and caching. We will have different numbers if users can have photos and videos in their tweets. This will be crucial in deciding how we will manage traffic and balance load between servers.

Step 4: Defining data model Defining the data model early will clarify how data will flow among different components of the system. Later, it will guide towards data partitioning and management. The candidate should be able to identify various entities of the system, how they will interact with each other, and different aspect of data management like storage, transportation, encryption, etc. Here are some entities for our Twitterlike service: User: UserID, Name, Email, DoB, CreationData, LastLogin, etc. Tweet: TweetID, Content, TweetLocation, NumberOfLikes, TimeStamp, etc. UserFollowo: UserdID1, UserID2 FavoriteTweets: UserID, TweetID, TimeStamp Which database system should we use? Will NoSQL like Cassandra best fit our needs, or should we use a MySQL-like solution? What kind of block storage should we use to store photos and videos? Step 5: High-level design Draw a block diagram with boxes representing the core components of our system. We should identify enough components that are needed to solve the actual problem from end-to-end.

On the backend, we need an efficient database that can store all the tweets and can support a huge number of reads. We will also need a distributed file storage system for storing photos and videos. We should be able to present different approaches, their pros and cons, and explain why we will prefer one approach on the other. Remember there is no single answer, the only important thing is to consider tradeoffs between different options while keeping system constraints in mind. Should we try to store all the data of a user on the same database?

What issue could it cause? Step 7: Identifying and resolving bottlenecks Try to discuss as many bottlenecks as possible and different approaches to mitigate them. What are we doing to mitigate it? Do we get alerts whenever critical components fail or their performance degrades? Summary In short, preparation and being organized during the interview are the keys to be successful in system design interviews. The above-mentioned steps should guide you to remain on track and cover all the different aspects while designing a system. Designing a URL Shortening service like TinyURL Let's design a URL shortening service like TinyURL. This service will provide short aliases redirecting to long URLs. Similar services: bit.

ly, goo. gl, qlink. me, etc. Difficulty Level: Easy 1. URL shortening is used to create shorter aliases for long URLs. Short links save a lot of space when displayed, printed, messaged, or tweeted. Additionally, users are less likely to mistype shorter URLs. URL shortening is used for optimizing links across devices, tracking individual links to analyze audience and campaign performance, and hiding affiliated original URLs. com before, please try creating a new shortened URL and spend some time going through the various options their service offers. This will help you a lot in understanding this chapter.

Requirements and Goals of the System � You should always clarify requirements at the beginning of the interview. Be sure to ask questions to find the exact scope of the system that the interviewer has in mind. Our URL shortening system should meet the following requirements: Functional Requirements: 1. Given a URL, our service should generate a shorter and unique alias of it. This is called a short link. When users access a short link, our service should redirect them to the original link. Users should optionally be able to pick a custom short link for their URL. Links will expire after a standard default timespan. Users should be able to specify the expiration time. Non-Functional Requirements: 1. The system should be highly available.

This is required because, if our service is down, all the URL redirections will start failing. URL redirection should happen in real-time with minimal latency. Shortened links should not be guessable not predictable. Extended Requirements: 1. Analytics; e. Our service should also be accessible through REST APIs by other services. Capacity Estimation and Constraints Our system will be read-heavy. There will be lots of redirection requests compared to new URL shortenings. Since we have 20K requests per second, we will be getting 1. System APIs � Once we've finalized the requirements, it's always a good idea to define the system APIs.

This should explicitly state what is expected from the system. We can have SOAP or REST APIs to expose the functionality of our service. This will be used to, among other things, throttle users based on their allocated quota. Returns: string A successful insertion returns the shortened URL; otherwise, it returns an error code. How do we detect and prevent abuse? A malicious user can put us out of business by consuming all URL keys in the current design. Database Design � Defining the DB schema in the early stages of the interview would help to understand the data flow among various components and later would guide towards data partitioning. A few observations about the nature of the data we will store: 1. We need to store billions of records. Each object we store is small less than 1K. There are no relationships between records—other than storing which user created a URL. Our service is read-heavy.

A NoSQL choice would also be easier to scale. Please see SQL vs NoSQL for more details. Basic System Design and Algorithm The problem we are solving here is, how to generate a short and unique key for a given URL. The last six characters of this URL is the short key we want to generate. Encoding actual URL We can compute a unique hash e. of the given URL. The hash can then be encoded for displaying. A reasonable question would be, what should be the length of the short key? Since we only have space for 8 characters per short key, how will we choose our key then?

We can take the first 6 or 8 letters for the key. This could result in key duplication though, upon which we can choose some other characters out of the encoding string or swap some characters. What are different issues with our solution? We have the following couple of problems with our encoding scheme: 1. If multiple users enter the same URL, they can get the same shortened URL, which is not acceptable. What if parts of the URL are URL-encoded? Workaround for the issues: We can append an increasing sequence number to each input URL to make it unique, and then generate a hash of it. Possible problems with this approach could be an ever-increasing sequence number. Can it overflow? Appending an increasing sequence number will also impact the performance of the service. Another solution could be to append user id which should be unique to the input URL.

However, if the user has not signed in, we would have to ask the user to choose a uniqueness key. Even after this, if we have a conflict, we have to keep generating a key until we get a unique one. Request flow for shortening of a URL 1 of 9 b. Whenever we want to shorten a URL, we will just take one of the already-generated keys and use it. This approach will make things quite simple and fast. KGS will make sure all the keys inserted into key-DB are unique Can concurrency cause problems? If there are multiple servers reading keys concurrently, we might get a scenario where two or more servers try to read the same key from the database. How can we solve this concurrency problem? KGS can use two tables to store keys: one for keys that are not used yet, and one for all the used keys. As soon as KGS gives keys to one of the servers, it can move them to the used keys table. KGS can always keep some keys in memory so that it can quickly provide them whenever a server needs them.

For simplicity, as soon as KGS loads some keys in memory, it can move them to the used keys table. This ensures each server gets unique keys. If KGS dies before assigning all the loaded keys to some server, we will be wasting those keys—which is acceptable, given the huge number of keys we have. KGS also has to make sure not to give the same key to multiple servers. For that, it must synchronize or get a lock on the data structure holding the keys before removing keys from it and giving them to a server What would be the key-DB size? With base64 encoding, we can generate Yes, it is. To solve this, we can have a standby replica of KGS. Whenever the primary server dies, the standby server can take over to generate and provide keys. Can each app server cache some keys from key-DB? Yes, this can surely speed things up. Although in this case, if the application server dies before consuming all the keys, we will end up losing those keys.

This can be acceptable since we have 68B unique six letter keys. How would we perform a key lookup? We can look up the key in our database or key-value store to get the full URL. Should we impose size limits on custom aliases? Our service supports custom aliases. However, it is reasonable and often desirable to impose a size limit on a custom alias to ensure we have a consistent URL database. High level system design for URL shortening 7. Data Partitioning and Replication To scale out our DB, we need to partition it so that it can store information about billions of URLs. We need to come up with a partitioning scheme that would divide and store our data to different DB servers.

Range Based Partitioning: We can store URLs in separate partitions based on the first letter of the URL or the hash key. This approach is called range-based partitioning. We can even combine certain less frequently occurring letters into one database partition. The main problem with this approach is that it can lead to unbalanced servers. Hash-Based Partitioning: In this scheme, we take a hash of the object we are storing. We then calculate which partition to use based upon the hash. Our hashing function will randomly distribute URLs into different partitions e. This approach can still lead to overloaded partitions, which can be solved by using Consistent Hashing. Cache We can cache URLs that are frequently accessed. We can use some off-the-shelf solution like Memcache, which can store full URLs with their respective hashes.

The application servers, before hitting backend storage, can quickly check if the cache has the desired URL. How much cache should we have? Since a modern-day server can have GB memory, we can easily fit all the cache into one machine. Alternatively, we can use a couple of smaller servers to store all these hot URLs. Which cache eviction policy would best fit our needs? Least Recently Used LRU can be a reasonable policy for our system. Under this policy, we discard the least recently used URL first. We can use a Linked Hash Map or a similar data structure to store our URLs and Hashes, which will also keep track of the URLs that have been accessed recently.

To further increase the efficiency, we can replicate our caching servers to distribute load between them. How can each cache replica be updated? Whenever there is a cache miss, our servers would be hitting a backend database. Whenever this happens, we can update the cache and pass the new entry to all the cache replicas. Each replica can update their cache by adding the new entry. If a replica already has that entry, it can simply ignore it. Request flow for accessing a shortened URL 1 of 11 9. Load Balancer LB We can add a Load balancing layer at three places in our system: 1. Between Clients and Application servers 2. Between Application Servers and database servers 3. Between Application Servers and Cache servers Initially, we could use a simple Round Robin approach that distributes incoming requests equally among backend servers. This LB is simple to implement and does not introduce any overhead.

Another benefit of this approach is that if a server is dead, LB will take it out of the rotation and will stop sending any traffic to it. A problem with Round Robin LB is that server load is not taken into consideration. If a server is overloaded or slow, the LB will not stop sending new requests to that server. To handle this, a more intelligent LB solution can be placed that periodically queries the backend server about its load and adjusts traffic based on that. Purging or DB cleanup Should entries stick around forever or should they be purged? If a user-specified expiration time is reached, what should happen to the link? If we chose to actively search for expired links to remove them, it would put a lot of pressure on our database. Instead, we can slowly remove expired links and do a lazy cleanup. Our service will make sure that only expired links will be deleted, although some expired links can live longer but will never be returned to users.

This service should be very lightweight and can be scheduled to run only when the user traffic is expected to be low. This could be tricky. Since storage is getting cheap, we can decide to keep links forever. Detailed component design for URL shortening Telemetry How many times a short URL has been used, what were user locations, etc.? How would we store these statistics? If it is part of a DB row that gets updated on each view, what will happen when a popular URL is slammed with a large number of concurrent requests? Some statistics worth tracking: country of the visitor, date and time of access, web page that refers the click, browser, or platform from where the page was accessed. Security and Permissions Can users create private URLs or allow a particular set of users to access a URL?

We can also create a separate table to store UserIDs that have permission to see a specific URL. If a user does not have permission and tries to access a URL, we can send an error HTTP back. The columns will store the UserIDs of those users that have permissions to see the URL. Designing Pastebin Let's design a Pastebin like web service, where users can store plain text. Users of the service will enter a piece of text and get a randomly generated URL to access it. Similar Services: pastebin. com, pasted. co, chopapp. com Difficulty Level: Easy 1. Pastebin like services enable users to store plain text or images over the network typically the Internet and generate unique URLs to access the uploaded data. Such services are also used to share data over the network quickly, as users would just need to pass the URL to let other users see it.

Requirements and Goals of the System Our Pastebin service should meet the following requirements: Functional Requirements: 1. Users will only be able to upload text. Data and links will expire after a specific timespan automatically; users should also be able to specify expiration time. Users should optionally be able to pick a custom alias for their paste. The system should be highly reliable, any data uploaded should not be lost. This is required because if our service is down, users will not be able to access their Pastes.

Users should be able to access their Pastes in real-time with minimum latency. Paste links should not be guessable not predictable. Analytics, e. Some Design Considerations Pastebin shares some requirements with URL Shortening service, but there are some additional design considerations we should keep in mind. What should be the limit on the amount of text user can paste at a time? We can limit users not to have Pastes bigger than 10MB to stop the abuse of the service. Should we impose size limits on custom URLs? Since our service supports custom URLs, users can pick any URL that they like, but providing a custom URL is not mandatory.

However, it is reasonable and often desirable to impose a size limit on custom URLs, so that we have a consistent URL database. Capacity Estimation and Constraints Our services will be read-heavy; there will be more read requests compared to new Pastes creation. We can assume a ratio between read and write. This leaves us with five million reads per day. At this rate, we will be storing 10GB of data per day. With 1M pastes every day we will have 3. We need to generate and store keys to uniquely identify these pastes. If we use base64 encoding [A-Z, a-z, ,. Bandwidth estimates: For write requests, we expect 12 new pastes per second, resulting in KB of ingress per second. Therefore, total data egress sent to users will be 0. Memory estimates: We can cache some of the hot pastes that are frequently accessed.

System APIs We can have SOAP or REST APIs to expose the functionality of our service. Returns: string A successful insertion returns the URL through which the paste can be accessed, otherwise, it will return an error code. This API will return the textual data of the paste. Database Design A few observations about the nature of the data we are storing: 1. Each metadata object we are storing would be small less than bytes. Each paste object we are storing can be of medium size it can be a few MB. There are no relationships between records, except if we want to store which user created what Paste. High Level Design At a high level, we need an application layer that will serve all the read and write requests.

Application layer will talk to a storage layer to store and retrieve data. We can segregate our storage layer with one database storing metadata related to each paste, users, etc. This division of data will also allow us to scale them individually. Application server Client Metadata storage Object storage 8. Application layer Our application layer will process all incoming and outgoing requests. The application servers will be talking to the backend data store components to serve the requests. How to handle a write request? Upon receiving a write request, our application server will generate a six-letter random string, which would serve as the key of the paste if the user has not provided a custom key.

The application server will then store the contents of the paste and the generated key in the database. After the successful insertion, the server can return the key to the user. One possible problem here could be that the insertion fails because of a duplicate key. Since we are generating a random key, there is a possibility that the newly generated key could match an existing one. In that case, we should regenerate a new key and try again. We should return an error to the user if the custom key they have provided is already present in our database. Whenever we want to store a new paste, we will just take one of the already generated keys and use it. This approach will make things quite simple and fast since we will not be worrying about duplications or collisions. KGS will make sure all the keys inserted in key-DB are unique.

KGS can use two tables to store keys, one for keys that are not used yet and one for all the used keys. As soon as KGS gives some keys to an application server, it can move these to the used keys table. KGS can always keep some keys in memory so that whenever a server needs them, it can quickly provide them. As soon as KGS loads some keys in memory, it can move them to the used keys table, this way we can make sure each server gets unique keys. If KGS dies before using all the keys loaded in memory, we will be wasting those keys. We can ignore these keys given that we have a huge number of them. To solve this, we can have a standby replica of KGS and whenever the primary server dies it can take over to generate and provide keys.

This could be acceptable since we have 68B unique six letters keys, which are a lot more than we require. How does it handle a paste read request? Upon receiving a read paste request, the application service layer contacts the datastore. Otherwise, an error code is returned. Datastore layer We can divide our datastore layer into two: 1. Metadata database: We can use a relational database like MySQL or a Distributed Key-Value store like Dynamo or Cassandra. Whenever we feel like hitting our full capacity on content storage, we can easily increase it by adding more servers.

Detailed component design for Pastebin 9. Purging or DB Cleanup Please see Designing a URL Shortening service. Data Partitioning and Replication Please see Designing a URL Shortening service. Cache and Load Balancer Please see Designing a URL Shortening service. Security and Permissions Please see Designing a URL Shortening service. Designing Instagram Let's design a photo-sharing service like Instagram, where users can upload photos to share them with other users. Similar Services: Flickr, Picasa Difficulty Level: Medium 1. Instagram is a social networking service which enables its users to upload and share their photos and videos with other users. Instagram users can choose to share information either publicly or privately. Anything shared publicly can be seen by any other user, whereas privately shared content can only be accessed by a specified set of people. Instagram also enables its users to share through many other social networking platforms, such as Facebook, Twitter, Flickr, and Tumblr.

For the sake of this exercise, we plan to design a simpler version of Instagram, where a user can share photos and can also follow other users. Users can follow other users. Non-functional Requirements 1. Our service needs to be highly available. The acceptable latency of the system is ms for News Feed generation. The system should be highly reliable; any uploaded photo or video should never be lost. Not in scope: Adding tags to photos, searching photos on tags, commenting on photos, tagging users to photos, who to follow, etc. Some Design Considerations The system would be read-heavy, so we will focus on building a system that can retrieve photos quickly. Practically, users can upload as many photos as they like. Efficient management of storage should be a crucial factor while designing this system. Low latency is expected while viewing photos.

If a user uploads a photo, the system will guarantee that it will never be lost. Our service would need some object storage servers to store photos and also some database servers to store metadata information about the photos. Database Schema � Defining the DB schema in the early stages of the interview would help to understand the data flow among various components and later would guide towards data partitioning. We need to store data about users, their uploaded photos, and people they follow. Photo table will store all data related to a photo; we need to have an index on PhotoID, CreationDate since we need to fetch recent photos first. A straightforward approach for storing the above schema would be to use an RDBMS like MySQL since we require joins. But relational databases come with their challenges, especially when we need to scale them.

For details, please take a look at SQL vs. We can store photos in a distributed file storage like HDFS or S3. We can store the above schema in a distributed key-value store to enjoy the benefits offered by NoSQL. We need to store relationships between users and photos, to know who owns which photo. We also need to store the list of people a user follows. For both of these tables, we can use a wide-column datastore like Cassandra. Cassandra or key-value stores in general, always maintain a certain number of replicas to offer reliability. UserFollow: Each row in the UserFollow table will consist of 8 bytes.

If we have million users and on average each user follows users. We would need 1. Component Design Photo uploads or writes can be slow as they have to go to the disk, whereas reads will be faster, especially if they are being served from cache. Uploading users can consume all the available connections, as uploading is a slow process. We should keep in mind that web servers have a connection limit before designing our system. To handle this bottleneck we can split reads and writes into separate services. Reliability and Redundancy Losing files is not an option for our service.

Therefore, we will store multiple copies of each file so that if one storage server dies we can retrieve the photo from the other copy present on a different storage server. This same principle also applies to other components of the system. If we want to have high availability of the system, we need to have multiple replicas of services running in the system, so that if a few services die down the system still remains available and running. Redundancy removes the single point of failure in the system. If only one instance of a service is required to run at any point, we can run a redundant secondary copy of the service that is not serving any traffic, but it can take control after the failover when primary has a problem. Creating redundancy in a system can remove single points of failure and provide a backup or spare functionality if needed in a crisis.

For example, if there are two instances of the same service running in production and one fails or degrades, the system can failover to the healthy copy. Failover can happen automatically or require manual intervention. If one DB shard is 1TB, we will need four shards to store 3. To uniquely identify any photo in our system, we can append shard number with each PhotoID. How can we generate PhotoIDs? Each DB shard can have its own auto-increment sequence for PhotoIDs and since we will append ShardID with each PhotoID, it will make it unique throughout our system. What are the different issues with this partitioning scheme?

How would we handle hot users? Several people follow such hot users and a lot of other people see any photo they upload. Some users will have a lot of photos compared to others, thus making a non-uniform distribution of storage. What if we cannot store all pictures of a user on one shard? If we distribute photos of a user onto multiple shards will it cause higher latencies? We would not need to append ShardID with PhotoID in this case as PhotoID will itself be unique throughout the system. Here we cannot have an auto-incrementing sequence in each shard to define PhotoID because we need to know PhotoID first to find the shard where it will be stored. One solution could be that we dedicate a separate database instance to generate auto-incrementing IDs.

If our PhotoID can fit into 64 bits, we can define a table containing only a 64 bit ID field. So whenever we would like to add a photo in our system, we can insert a new row in this table and take that ID to be our PhotoID of the new photo. Yes, it would be. A workaround for that could be defining two such databases with one generating even numbered IDs and the other odd numbered. Both these servers could be out of sync with one generating more keys than the other, but this will not cause any issue in our system. We can extend this design by defining separate ID tables for Users, Photo-Comments, or other objects present in our system. How can we plan for the future growth of our system?

We can have a large number of logical partitions to accommodate future data growth, such that in the beginning, multiple logical partitions reside on a single physical database server. Since each database server can have multiple database instances on it, we can have separate databases for each logical partition on any server. So whenever we feel that a particular database server has a lot of data, we can migrate some logical partitions from it to another server. We can maintain a config file or a separate database that can map our logical partitions to database servers; this will enable us to move partitions around easily. Whenever we want to move a partition, we only have to update the config file to announce the change. Ranking and News Feed Generation To create the News Feed for any given user, we need to fetch the latest, most popular and relevant photos of the people the user follows. Our application server will first get a list of people the user follows and then fetch metadata info of latest photos from each user.

In the final step, the server will submit all these photos to our ranking algorithm which will determine the top photos based on recency, likeness, etc. and return them to the user. To improve the efficiency, we can pre-generate the News Feed and store it in a separate table. So whenever any user needs the latest photos for their News Feed, we will simply query this table and return the results to the user. Whenever these servers need to generate the News Feed of a user, they will first query the UserNewsFeed table to find the last time the News Feed was generated for that user.

Then, new News Feed data will be generated from that time onwards following the steps mentioned above. What are the different approaches for sending News Feed contents to the users? Pull: Clients can pull the News Feed contents from the server on a regular basis or manually whenever they need it. Possible problems with this approach are a New data might not be shown to the users until clients issue a pull request b Most of the time pull requests will result in an empty response if there is no new data. Push: Servers can push new data to the users as soon as it is available. To efficiently manage this, users have to maintain a Long Poll request with the server for receiving the updates.

A possible problem with this approach is, a user who follows a lot of people or a celebrity user who has millions of followers; in this case, the server has to push updates quite frequently. Hybrid: We can adopt a hybrid approach. We can move all the users who have a high number of follows to a pull-based model and only push data to those users who have a few hundred or thousand follows. News Feed Creation with Sharded Data One of the most important requirement to create the News Feed for any given user is to fetch the latest photos from all people the user follows.

For this, we need to have a mechanism to sort photos on their time of creation. To efficiently do this, we can make photo creation time part of the PhotoID. As we will have a primary index on PhotoID, it will be quite quick to find the latest PhotoIDs. We can use epoch time for this. So to make a new PhotoID, we can take the current epoch time and append an auto-incrementing ID from our keygenerating DB. What could be the size of our PhotoID? Since on the average, we are expecting 23 new photos per second; we can allocate 9 bits to store auto incremented sequence. We can reset our auto incrementing sequence every second. Cache and Load balancing Our service would need a massive-scale photo delivery system to serve the globally distributed users. Our service should push its content closer to the user using a large number of geographically distributed photo cache servers and use CDNs for details see Caching.

We can introduce a cache for metadata servers to cache hot database rows. We can use Memcache to cache the data and Application servers before hitting database can quickly check if the cache has desired rows. Least Recently Used LRU can be a reasonable cache eviction policy for our system. Under this policy, we discard the least recently viewed row first. How can we build more intelligent cache? If we go with rule, i. Designing Dropbox Let's design a file hosting service like Dropbox or Google Drive. Cloud file storage enables users to store their data on remote servers. Usually, these servers are maintained by cloud storage providers and made available to users over a network typically through the Internet. Users pay for their cloud data storage on a monthly basis.

Similar Services: OneDrive, Google Drive Difficulty Level: Medium 1. Cloud file storage services have become very popular recently as they simplify the storage and exchange of digital resources among multiple devices. The shift from using single personal computers to using multiple devices with different platforms and operating systems such as smartphones and tablets each with portable access from various geographical locations at any time, is believed to be accountable for the huge popularity of cloud storage services. Following are some of the top benefits of such services: Availability: The motto of cloud storage services is to have data availability anywhere, anytime.

Cloud storage ensures that users will never lose their data by keeping multiple copies of the data stored on different geographically located servers. Scalability: Users will never have to worry about getting out of storage space. With cloud storage you have unlimited storage as long as you are ready to pay for it. What do we wish to achieve from a Cloud Storage system? Here are the top-level requirements for our system: 1. Users should be able to share files or folders with other users. Our service should support automatic synchronization between devices, i. The system should support storing large files up to a GB.

ACID-ity is required. Atomicity, Consistency, Isolation and Durability of all file operations should be guaranteed. Our system should support offline editing. all failed operations shall only be retried for smaller parts of a file. If a user fails to upload a file, then only the failing chunk will be retried. with the client can save us a lot of round trips to the server. Object 1 5. High Level Design The user will specify a folder as the workspace on their device. The user can specify similar workspaces on all their devices and any modification done on one device will be propagated to all other devices to have the same view of the workspace everywhere.

At a high level, we need to store files and their metadata information like File Name, File Size, Directory, etc. We also need some mechanism to notify all clients whenever an update happens so they can synchronize their files. Synchronization servers will handle the workflow of notifying all clients about different changes for synchronization. High level design for Dropbox 6. The client application will work with the storage servers to upload, download, and modify actual files to backend Cloud Storage. The client also interacts with the remote Synchronization Service to handle any file metadata updates, e. Here are some of the essential operations for the client: 1. Upload and download files. Detect file changes in the workspace folder. Handle conflict due to offline or concurrent updates. How do we handle file transfer efficiently? As mentioned above, we can break each file into smaller chunks so that we transfer only those chunks that are modified and not the whole file.

In our metadata, we should also keep a record of each file and the chunks that constitute it. Should we keep a copy of metadata with Client? Keeping a local copy of metadata not only enable us to do offline updates but also saves a lot of round trips to update remote metadata. How can clients efficiently listen to changes happening with other clients? One solution could be that the clients periodically check with the server if there are any changes. The problem with this approach is that we will have a delay in reflecting changes locally as clients will be checking for changes periodically compared to a server notifying whenever there is some change. If the client frequently checks the server for changes, it will not only be wasting bandwidth, as the server has to return an empty response most of the time, but will also be keeping the server busy. Pulling information in this manner is not scalable. A solution to the above problem could be to use HTTP long polling.

With long polling the client requests information from the server with the expectation that the server may not respond immediately. If the server has no new data for the client when the poll is received, instead of sending an empty response, the server holds the request open and waits for response information to become available. Upon receipt of the server response, the client can immediately issue another server request for future updates. Based on the above considerations, we can divide our client into following four parts: I. Internal Metadata Database will keep track of all the files, chunks, their versions, and their location in the file system. Chunker will split the files into smaller pieces called chunks. It will also be responsible for reconstructing a file from its chunks. Our chunking algorithm will detect the parts of the files that have been modified by the user and only transfer those parts to the Cloud Storage; this will save us bandwidth and synchronization time.

Watcher will monitor the local workspace folders and notify the Indexer discussed below of any action performed by the users, e. when users create, delete, or update files or folders. Watcher also listens to any changes happening on other clients that are broadcasted by Synchronization service. Indexer will process the events received from the Watcher and update the internal metadata database with information about the chunks of the modified files. How should clients handle slow servers? Meaning, if a server is too slow to respond, clients should delay their retries and this delay should increase exponentially.

Should mobile clients sync remote changes immediately? The Metadata Database can be a relational database such as MySQL, or a NoSQL database service such as DynamoDB.

This PDF book is become immediate popular in Electronic Books genre. Grokking the System Design Interview is written by famous author Design Gurus and Ready to Download in ePUB, PDF or Kindle formats. Released by Unknown in Click Download Book button to get book file and read directly from your devices. Here is a quick description and cover image of Grokking the System Design Interview book. This book also available online at www. System design questions have become a standard part of the software engineering interview process. These interviews determine your ability to work with complex systems and the position and salary you will be offered by the interviewing company. Unfortunately, SDI is difficult for most engineers, partly because they lack experience developing large-scale systems and partly because SDIs are unstructured in nature. Even engineers who've some experience building such systems aren't comfortable with these interviews, mainly due to the open-ended nature of design problems that don't have a standard answer.

This book is a comprehensive guide to master SDIs. It was created by hiring managers who have worked for Google, Facebook, Microsoft, and Amazon. The book contains a carefully chosen set of questions that have been repeatedly asked at top companies. What's inside? This book is divided into two parts. The first part includes a step-by-step guide on how to answer a system design question in an interview, followed by famous system design case studies. The second part of the book includes a glossary of system design concepts. Table of Contents First Part: System Design Interviews: A step-by-step guide. Designing a URL Shortening service like TinyURL. Designing Pastebin. Designing Instagram. Designing Dropbox. Designing Facebook Messenger. Designing Twitter. Designing YouTube or Netflix. Designing Typeahead Suggestion. Designing an API Rate Limiter. Designing Twitter Search.

Designing a Web Crawler. Designing Facebook's Newsfeed. Designing Yelp or Nearby Friends. Designing Uber backend. Designing Ticketmaster. Second Part: Key Characteristics of Distributed Systems. Load Balancing. Data Partitioning. Redundancy and Replication. SQL vs. CAP Theorem. PACELC Theorem. Consistent Hashing. Long-Polling vs. WebSockets vs. Server-Sent Events. Bloom Filters. Leader and Follower. About the Authors Designed Gurus is a platform that offers online courses to help software engineers prepare for coding and system design interviews. Learn more about our courses at www.

These interviews determine your ability to work with complex systems and the position. The system design interview is considered to be the most complex and most difficult technical job interview by many. Those questions are intimidating, but don't worry. It's just that nobody has taken the time to prepare you systematically. We take the time. We go slow. We draw lots of diagrams. The System Design Interview, by Lewis C. Lin and Shivam P. Patel, is a comprehensive book that provides the necessary knowledge, concepts, and skills to pass your system design interview. Get their insider perspective on the proven, practical techniques for answering system. Learning to build distributed systems is hard, especially if they are large scale. It's not that there is a lack of information out there. You can find academic papers, engineering blogs, and even books on the subject. The problem is that the available information is spread out all over the.

Cracking Java Interview is not easy and one of the main reasons for that is Java is very vast. There are a lot of concepts and APIs to master to become a decent Java developer. Many people who are good at general topics like Data Structure and Algorithms, System Design,. Now in the 5th edition, Cracking the Coding Interview gives you the interview preparation you need to get the top software developer jobs. This book provides: Programming Interview Questions and Solutions: From binary trees to binary search, this list of questions includes the most common and most useful questions in. Principles of Computer System Design is the first textbook to take a principles-based approach to the computer system design. It identifies, examines, and illustrates fundamental concepts in computer system design that are common across operating systems, networks, database systems, distributed systems, programming languages, software engineering, security, fault tolerance, and architecture.

Data is at the center of many challenges in system design today. Difficult issues need to be figured out, such as scalability, consistency, reliability, efficiency, and maintainability. In addition, we have an overwhelming variety of tools, including relational databases, NoSQL datastores, stream or batch processors, and message brokers. What are. Grokking the System Design Interview This PDF book is become immediate popular in Electronic Books genre. Home Grokking The System Design Interview. Grokking the System Design Interview. System Design Interview An Insider s Guide. The System Design Interview 2nd Edition. Understanding Distributed Systems. Grokking the Java Interview. Cracking the Coding Interview. Principles of Computer System Design. Designing Data Intensive Applications.

This approach solves the problem of hot users, but, in contrast to sharding by UserID, we have to query all database partitions to find tweets of a user, which can result in higher latencies. High Level Design At a high level, we need an application layer that will serve all the read and write requests. We can go two or three levels down to find famous people for the suggestions. If multiple users enter the same URL, they can get the same shortened URL, which is not acceptable. We can use a Linked Hash Map or a similar data structure to store our URLs and Hashes, which will also keep track of the URLs that have been accessed recently. We can reset our auto incrementing sequence every second. Database Design Database Schema: 6.

Categories:

• Games
• Music
• Soft
• Files
• Movies