notexOPENOverview
Notex/Systems/System design

System design

Always free to read

OPEN LEARNING PATH / SYSTEM DESIGN

Design systems, from the first user to millions.

Build system design fluency through scaling foundations, estimation, design frameworks, and complete architecture case studies. Original diagrams and a video placeholder for every section.

16 MODULES · 193 LESSONS · FREE TO READ
System design textured notebook cover
A little progress, one lesson at a time.Your progress stays in this browser.
Start learning →

CURRICULUM STRUCTURE

Full curriculum

0122 LESSONS · 30 MIN
  1. 01.01Scale from zero to millions of usersDesigning a system that supports millions of users is challenging, and it is a journey that requires continuous refinement and endless improvement. In this chapter, we build a…READING1 MIN
  2. 01.02Single server setupA journey of a thousand miles begins with a single step, and building a complex system is no different. To start with something simple, everything is running on a single…READING2 MIN
  3. 01.03DatabaseWith the growth of the user base, one server is not enough, and we need multiple servers: one for web/mobile traffic, the other for the database (Figure 1-3). Separating…READING1 MIN
  4. 01.04Which databases to use?You can choose between a traditional relational database and a non-relational database. Let us examine their differences. Relational databases are also called a relational…READING1 MIN
  5. 01.05Vertical scaling vs horizontal scalingVertical scaling, referred to as “scale up”, means the process of adding more power (CPU, RAM, etc.) to your servers. Horizontal scaling, referred to as “scale-out”, allows you…READING1 MIN
  6. 01.06Load balancerA load balancer evenly distributes incoming traffic among web servers that are defined in a load-balanced set. Figure 1-4 shows how a load balancer works. As shown in Figure…READING1 MIN
  7. 01.07Database replicationQuoted from Wikipedia: “Database replication can be used in many database management systems, usually with a master/slave relationship between the original (master) and the…READING3 MIN
  8. 01.08CacheA cache is a temporary storage area that stores the result of expensive responses or frequently accessed data in memory so that subsequent requests are served more quickly. As…READING1 MIN
  9. 01.09Cache tierThe cache tier is a temporary data store layer, much faster than the database. The benefits of having a separate cache tier include better system performance, ability to reduce…READING1 MIN
  10. 01.10Considerations for using cacheHere are a few considerations for using a cache system: Decide when to use cache. Consider using cache when data is read frequently but modified infrequently. Since cached data…READING2 MIN
  11. 01.11Content delivery network (CDN)A CDN is a network of geographically dispersed servers used to deliver static content. CDN servers cache static content like images, videos, CSS, JavaScript files, etc. Dynamic…READING2 MIN
  12. 01.12Considerations of using a CDNCost: CDNs are run by third-party providers, and you are charged for data transfers in and out of the CDN. Caching infrequently used assets provides no significant benefits so…READING1 MIN
  13. 01.13Stateless web tierNow it is time to consider scaling the web tier horizontally. For this, we need to move state (for instance user session data) out of the web tier. A good practice is to store…READING1 MIN
  14. 01.14Stateful architectureA stateful server and stateless server has some key differences. A stateful server remembers client data (state) from one request to the next. A stateless server keeps no state…READING1 MIN
  15. 01.15Stateless architectureFigure 1-13 shows the stateless architecture. In this stateless architecture, HTTP requests from users can be sent to any web servers, which fetch state data from a shared data…READING1 MIN
  16. 01.16Data centersFigure 1-15 shows an example setup with two data centers. In normal operation, users are geoDNS-routed, also known as geo-routed, to the closest data center, with a split…READING2 MIN
  17. 01.17Message queueA message queue is a durable component, stored in memory, that supports asynchronous communication. It serves as a buffer and distributes asynchronous requests. The basic…READING1 MIN
  18. 01.18Logging, metrics, automationWhen working with a small website that runs on a few servers, logging, metrics, and automation support are good practices but not a necessity. However, now that your site has…READING1 MIN
  19. 01.19Database scalingThere are two broad approaches for database scaling: vertical scaling and horizontal scaling.READING1 MIN
  20. 01.20Vertical scalingVertical scaling, also known as scaling up, is the scaling by adding more power (CPU, RAM, DISK, etc.) to an existing machine. There are some powerful database servers.…READING1 MIN
  21. 01.21Horizontal scalingHorizontal scaling, also known as sharding, is the practice of adding more servers. Figure 1- 20 compares vertical scaling with horizontal scaling. Sharding separates large…READING3 MIN
  22. 01.22Millions of users and beyondScaling a system is an iterative process. Iterating on what we have learned in this chapter could get us far. More fine-tuning and new strategies are needed to scale beyond…READING1 MIN
026 LESSONS · 6 MIN
  1. 02.01Back-of-the-envelope estimationIn a system design interview, sometimes you are asked to estimate system capacity or performance requirements using a back-of-the-envelope estimation. According to Jeff Dean,…READING1 MIN
  2. 02.02Power of twoAlthough data volume can become enormous when dealing with distributed systems, calculation all boils down to the basics. To obtain correct calculations, it is critical to know…READING1 MIN
  3. 02.03Latency numbers every programmer should knowDr. Dean from Google reveals the length of typical computer operations in 2010 [1]. Some numbers are outdated as computers become faster and more powerful. However, those…READING1 MIN
  4. 02.04Availability numbersHigh availability is the ability of a system to be continuously operational for a desirably long period of time. High availability is measured as a percentage, with 100% means…READING1 MIN
  5. 02.05Example: Estimate Twitter QPS and storage requirementsPlease note the following numbers are for this exercise only as they are not real numbers from Twitter. Assumptions: 300 million monthly active users.50% of users use Twitter…READING1 MIN
  6. 02.06TipsBack-of-the-envelope estimation is all about the process. Solving the problem is more important than obtaining results. Interviewers may test your problem-solving skills. Here…READING1 MIN
037 LESSONS · 13 MIN
  1. 03.01A framework for system design interviewsYou have just landed a coveted on-site interview at your dream company. The hiring coordinator sends you a schedule for that day. Scanning down the list, you feel pretty good…READING2 MIN
  2. 03.02A 4-step process for effective system design interviewEvery system design interview is different. A great system design interview is open-ended and there is no one-size-fits-all solution. However, there are steps and common ground…READING1 MIN
  3. 03.03Step 1 - Understand the problem and establish design scope"Why did the tiger roar?" A hand shot up in the back of the class. "Yes, Jimmy?", the teacher responded. "Because he was HUNGRY". "Very good Jimmy." Throughout his childhood,…READING3 MIN
  4. 03.04Step 2 - Propose high-level design and get buy-inIn this step, we aim to develop a high-level design and reach an agreement with the interviewer on the design. It is a great idea to collaborate with the interviewer during the…READING2 MIN
  5. 03.05Step 3 - Design deep diveAt this step, you and your interviewer should have already achieved the following objectives: Agreed on the overall goals and feature scopeSketched out a high-level blueprint…READING2 MIN
  6. 03.06Step 4 - Wrap upIn this final step, the interviewer might ask you a few follow-up questions or give you the freedom to discuss other additional points. Here are a few directions to follow: The…READING2 MIN
  7. 03.07Time allocation on each stepSystem design interview questions are usually very broad, and 45 minutes or an hour is not enough to cover the entire design. Time management is essential. How much time should…READING1 MIN
04

DESIGN CASE STUDIES

Design a rate limiter

14 LESSONS · 24 MIN
  1. 04.01Design a rate limiterIn a network system, a rate limiter is used to control the rate of traffic sent by a client or a service. In the HTTP world, a rate limiter limits the number of client requests…READING1 MIN
  2. 04.02Step 1 - Understand the problem and establish design scopeRate limiting can be implemented using different algorithms, each with its pros and cons. The interactions between an interviewer and a candidate help to clarify the type of…READING1 MIN
  3. 04.03Step 2 - Propose high-level design and get buy-inLet us keep things simple and use a basic client and server model for communication.READING1 MIN
  4. 04.04Where to put the rate limiter?Intuitively, you can implement a rate limiter at either the client or server-side. Client-side implementation. Generally speaking, client is an unreliable place to enforce rate…READING2 MIN
  5. 04.05Algorithms for rate limitingRate limiting can be implemented using different algorithms, and each of them has distinct pros and cons. Even though this chapter does not focus on algorithms, understanding…READING8 MIN
  6. 04.06High-level architectureThe basic idea of rate limiting algorithms is simple. At the high-level, we need a counter to keep track of how many requests are sent from the same user, IP address, etc. If…READING1 MIN
  7. 04.07Step 3 - Design deep diveThe high-level design in Figure 4-12 does not answer the following questions: How are rate limiting rules created? Where are the rules stored?How to handle requests that are…READING1 MIN
  8. 04.08Rate limiting rulesLyft open-sourced their rate-limiting component [12]. We will peek inside of the component and look at some examples of rate limiting rules: domain: messaging descriptors: -…READING1 MIN
  9. 04.09Exceeding the rate limitIn case a request is rate limited, APIs return a HTTP response code 429 (too many requests) to the client. Depending on the use cases, we may enqueue the rate-limited requests…READING1 MIN
  10. 04.10Detailed designFigure 4-13 presents a detailed design of the system. Rules are stored on the disk. Workers frequently pull rules from the disk and store them in the cache.When a client sends…READING1 MIN
  11. 04.11Rate limiter in a distributed environmentBuilding a rate limiter that works in a single server environment is not difficult. However, scaling the system to support multiple servers and concurrent threads is a…READING2 MIN
  12. 04.12Performance optimizationPerformance optimization is a common topic in system design interviews. We will cover two areas to improve. First, multi-data center setup is crucial for a rate limiter because…READING1 MIN
  13. 04.13MonitoringAfter the rate limiter is put in place, it is important to gather analytics data to check whether the rate limiter is effective. Primarily, we want to make sure: The rate…READING1 MIN
  14. 04.14Step 4 - Wrap upIn this chapter, we discussed different algorithms of rate limiting and their pros/cons. Algorithms discussed include: Token bucketLeaking bucketFixed windowSliding window…READING2 MIN
05

DESIGN CASE STUDIES

Design consistent hashing

13 LESSONS · 15 MIN
  1. 05.01Design consistent hashingTo achieve horizontal scaling, it is important to distribute requests/data efficiently and evenly across servers. Consistent hashing is a commonly used technique to achieve…READING1 MIN
  2. 05.02The rehashing problemIf you have n cache servers, a common way to balance the load is to use the following hash method: serverIndex = hash(key) % N, where N is the size of the server pool. Let us…READING2 MIN
  3. 05.03Consistent hashingQuoted from Wikipedia: "Consistent hashing is a special kind of hashing such that when a hash table is re-sized and consistent hashing is used, only k/n keys need to be…READING1 MIN
  4. 05.04Hash space and hash ringNow we understand the definition of consistent hashing, let us find out how it works. Assume SHA-1 is used as the hash function f, and the output range of the hash function is:…READING1 MIN
  5. 05.05Hash serversUsing the same hash function f, we map servers based on server IP or name onto the ring. Figure 5-5 shows that 4 servers are mapped on the hash ring.READING1 MIN
  6. 05.06Hash keysOne thing worth mentioning is that hash function used here is different from the one in “the rehashing problem,” and there is no modular operation. As shown in Figure 5-6, 4…READING1 MIN
  7. 05.07Server lookupTo determine which server a key is stored on, we go clockwise from the key position on the ring until a server is found. Figure 5-7 explains this process. Going clockwise, key0…READING1 MIN
  8. 05.08Add a serverUsing the logic described above, adding a new server will only require redistribution of a fraction of keys. In Figure 5-8, after a new server 4 is added, only key0 needs to be…READING1 MIN
  9. 05.09Remove a serverWhen a server is removed, only a small fraction of keys require redistribution with consistent hashing. In Figure 5-9, when server 1 is removed, only key1 must be remapped to…READING1 MIN
  10. 05.10Two issues in the basic approachThe consistent hashing algorithm was introduced by Karger et al. at MIT [1]. The basic steps are: Map servers and keys on to the ring using a uniformly distributed hash…READING1 MIN
  11. 05.11Virtual nodesA virtual node refers to the real node, and each server is represented by multiple virtual nodes on the ring. In Figure 5-12, both server 0 and server 1 have 3 virtual nodes.…READING2 MIN
  12. 05.12Find affected keysWhen a server is added or removed, a fraction of data needs to be redistributed. How can we find the affected range to redistribute the keys? In Figure 5-14, server 4 is added…READING1 MIN
  13. 05.13Wrap upIn this chapter, we had an in-depth discussion about consistent hashing, including why it is needed and how it works. The benefits of consistent hashing include: Minimized keys…READING1 MIN
06

DESIGN CASE STUDIES

Design a key-value store

15 LESSONS · 25 MIN
  1. 06.01Design a key-value storeA key-value store, also referred to as a key-value database, is a non-relational database. Each unique identifier is stored as a key with its associated value. This data…READING1 MIN
  2. 06.02Understand the problem and establish design scopeThere is no perfect design. Each design achieves a specific balance regarding the tradeoffs of the read, write, and memory usage. Another tradeoff has to be made was between…READING1 MIN
  3. 06.03Single server key-value storeDeveloping a key-value store that resides in a single server is easy. An intuitive approach is to store key-value pairs in a hash table, which keeps everything in memory. Even…READING1 MIN
  4. 06.04Distributed key-value storeA distributed key-value store is also called a distributed hash table, which distributes keyvalue pairs across many servers. When designing a distributed system, it is…READING1 MIN
  5. 06.05CAP theoremCAP theorem states it is impossible for a distributed system to simultaneously provide more than two of these three guarantees: consistency, availability, and partition…READING3 MIN
  6. 06.06System componentsIn this section, we will discuss the following core components and techniques used to build a key-value store: Data partitionData replicationConsistencyInconsistency…READING1 MIN
  7. 06.07Data partitionFor large applications, it is infeasible to fit the complete data set in a single server. The simplest way to accomplish this is to split the data into smaller partitions and…READING1 MIN
  8. 06.08Data replicationTo achieve high availability and reliability, data must be replicated asynchronously over N servers, where N is a configurable parameter. These N servers are chosen using the…READING1 MIN
  9. 06.09ConsistencySince data is replicated at multiple nodes, it must be synchronized across replicas. Quorum consensus can guarantee consistency for both read and write operations. Let us…READING3 MIN
  10. 06.10Inconsistency resolution: versioningReplication gives high availability but causes inconsistencies among replicas. Versioning and vector locks are used to solve inconsistency problems. Versioning means treating…READING4 MIN
  11. 06.11Handling failuresAs with any large system at scale, failures are not only inevitable but common. Handling failure scenarios is very important. In this section, we first introduce techniques to…READING4 MIN
  12. 06.12System architecture diagramNow that we have discussed different technical considerations in designing a key-value store, we can shift our focus on the architecture diagram, shown in Figure 6-17. Main…READING1 MIN
  13. 06.13Write pathFigure 6-19 explains what happens after a write request is directed to a specific node. Please note the proposed designs for write/read paths are primary based on the…READING1 MIN
  14. 06.14Read pathAfter a read request is directed to a specific node, it first checks if data is in the memory cache. If so, the data is returned to the client as shown in Figure 6-20. If the…READING1 MIN
  15. 06.15SummaryThis chapter covers many concepts and techniques. To refresh your memory, the following table summarizes features and corresponding techniques used for a distributed key-value…READING1 MIN
079 LESSONS · 10 MIN
  1. 07.01Design a unique ID generator in distributed systemsIn this chapter, you are asked to design a unique ID generator in distributed systems. Your first thought might be to use a primary key with the auto_increment attribute in a…READING1 MIN
  2. 07.02Step 1 - Understand the problem and establish design scopeAsking clarification questions is the first step to tackle any system design interview question. Here is an example of candidate-interviewer interaction: Candidate: What are…READING1 MIN
  3. 07.03Step 2 - Propose high-level design and get buy-inMultiple options can be used to generate unique IDs in distributed systems. The options we considered are: Multi-master replicationUniversally unique identifier (UUID)Ticket…READING1 MIN
  4. 07.04Multi-master replicationAs shown in Figure 7-2, the first approach is multi-master replication. This approach uses the databases’ auto_increment feature. Instead of increasing the next ID by 1, we…READING1 MIN
  5. 07.05UUIDA UUID is another easy way to obtain unique IDs. UUID is a 128-bit number used to identify information in computer systems. UUID has a very low probability of getting…READING1 MIN
  6. 07.06Ticket ServerTicket servers are another interesting way to generate unique IDs. Flicker developed ticket servers to generate distributed primary keys [2]. It is worth mentioning how the…READING1 MIN
  7. 07.07Twitter snowflake approachApproaches mentioned above give us some ideas about how different ID generation systems work. However, none of them meet our specific requirements; thus, we need another…READING1 MIN
  8. 07.08Step 3 - Design deep diveIn the high-level design, we discussed various options to design a unique ID generator in distributed systems. We settle on an approach that is based on the Twitter snowflake…READING2 MIN
  9. 07.09Step 4 - Wrap upIn this chapter, we discussed different approaches to design a unique ID generator: multi-master replication, UUID, ticket server, and Twitter snowflake-like unique ID…READING1 MIN
08

DESIGN CASE STUDIES

Design a URL shortener

13 LESSONS · 15 MIN
  1. 08.01Design a URL shortenerIn this chapter, we will tackle an interesting and classic system design interview question: designing a URL shortening service like tinyurl.READING1 MIN
  2. 08.02Step 1 - Understand the problem and establish design scopeSystem design interview questions are intentionally left open-ended. To design a well-crafted system, it is critical to ask clarification questions. Candidate: Can you give an…READING1 MIN
  3. 08.03Back of the envelope estimationWrite operation: 100 million URLs are generated per day.Write operation per second: 100 million / 24 /3600 = 1160Read operation: Assuming ratio of read operation to write…READING1 MIN
  4. 08.04Step 2 - Propose high-level design and get buy-inIn this section, we discuss the API endpoints, URL redirecting, and URL shortening flows.READING1 MIN
  5. 08.05API EndpointsAPI endpoints facilitate the communication between clients and servers. We will design the APIs REST-style. If you are unfamiliar with restful API, you can consult external…READING1 MIN
  6. 08.06URL redirectingFigure 8-1 shows what happens when you enter a tinyurl onto the browser. Once the server receives a tinyurl request, it changes the short URL to the long URL with 301 redirect.…READING1 MIN
  7. 08.07URL shorteningLet us assume the short URL looks like this: www.tinyurl.com/{hashValue}. To support the URL shortening use case, we must find a hash function fx that maps a long URL to the…READING1 MIN
  8. 08.08Step 3 - Design deep diveUp until now, we have discussed the high-level design of URL shortening and URL redirecting. In this section, we dive deep into the following: data model, hash function, URL…READING1 MIN
  9. 08.09Data modelIn the high-level design, everything is stored in a hash table. This is a good starting point; however, this approach is not feasible for real-world systems as memory resources…READING1 MIN
  10. 08.10Hash functionHash function is used to hash a long URL to a short URL, also known as hashValue. Hash value length The hashValue consists of characters from [0-9, a-z, A-Z], containing 10 +…READING3 MIN
  11. 08.11URL shortening deep diveAs one of the core pieces of the system, we want the URL shortening flow to be logically simple and functional. Base 62 conversion is used in our design. We build the following…READING1 MIN
  12. 08.12URL redirecting deep diveFigure 8-8 shows the detailed design of the URL redirecting. As there are more reads than writes, <shortURL, longURL> mapping is stored in a cache to improve performance.…READING1 MIN
  13. 08.13Step 4 - Wrap upIn this chapter, we talked about the API design, data model, hash function, URL shortening, and URL redirecting. If there is extra time at the end of the interview, here are a…READING1 MIN
09

DESIGN CASE STUDIES

Design a web crawler

12 LESSONS · 22 MIN
  1. 09.01Design a web crawlerIn this chapter, we focus on web crawler design: an interesting and classic system design interview question. A web crawler is known as a robot or spider. It is widely used by…READING2 MIN
  2. 09.02Step 1 - Understand the problem and establish design scopeThe basic algorithm of a web crawler is simple: Given a set of URLs, download all the web pages addressed by the URLs.Extract URLs from these web pagesAdd new URLs to the list…READING2 MIN
  3. 09.03Back of the envelope estimationThe following estimations are based on many assumptions, and it is important to communicate with the interviewer to be on the same page. Assume 1 billion web pages are…READING1 MIN
  4. 09.04Step 2 - Propose high-level design and get buy-inOnce the requirements are clear, we move on to the high-level design. Inspired by previous studies on web crawling [4] [5], we propose a high-level design as shown in Figure…READING5 MIN
  5. 09.05Step 3 - Design deep diveUp until now, we have discussed the high-level design. Next, we will discuss the most important building components and techniques in depth: Depth-first search (DFS) vs…READING1 MIN
  6. 09.06DFS vs BFSYou can think of the web as a directed graph where web pages serve as nodes and hyperlinks (URLs) as edges. The crawl process can be seen as traversing a directed graph from…READING1 MIN
  7. 09.07URL frontierURL frontier helps to address these problems. A URL frontier is a data structure that stores URLs to be downloaded. The URL frontier is an important component to ensure…READING3 MIN
  8. 09.08HTML DownloaderThe HTML Downloader downloads web pages from the internet using the HTTP protocol. Before discussing the HTML Downloader, we look at Robots Exclusion Protocol first. Robots.txt…READING2 MIN
  9. 09.09RobustnessBesides performance optimization, robustness is also an important consideration. We present a few approaches to improve the system robustness: Consistent hashing: This helps to…READING1 MIN
  10. 09.10ExtensibilityAs almost every system evolves, one of the design goals is to make the system flexible enough to support new content types. The crawler can be extended by plugging in new…READING1 MIN
  11. 09.11Detect and avoid problematic contentThis section discusses the detection and prevention of redundant, meaningless, or harmful content. 1. Redundant content As discussed previously, nearly 30% of the web pages are…READING1 MIN
  12. 09.12Step 4 - Wrap upIn this chapter, we first discussed the characteristics of a good crawler: scalability, politeness, extensibility, and robustness. Then, we proposed a design and discussed key…READING2 MIN
10

DESIGN CASE STUDIES

Design a notification system

11 LESSONS · 15 MIN
  1. 10.01Design a notification systemA notification system has already become a very popular feature for many applications in recent years. A notification alerts a user with important information like breaking…READING1 MIN
  2. 10.02Step 1 - Understand the problem and establish design scopeBuilding a scalable system that sends out millions of notifications a day is not an easy task. It requires a deep understanding of the notification ecosystem. The interview…READING1 MIN
  3. 10.03Step 2 - Propose high-level design and get buy-inThis section shows the high-level design that supports various notification types: iOS push notification, Android push notification, SMS message, and Email. It is structured as…READING1 MIN
  4. 10.04Different types of notificationsWe start by looking at how each notification type works at a high level. iOS push notification We primary need three components to send an iOS push notification: Provider. A…READING2 MIN
  5. 10.05Contact info gathering flowTo send notifications, we need to gather mobile device tokens, phone numbers, or email addresses. As shown in Figure 10-7, when a user installs our app or signs up for the…READING1 MIN
  6. 10.06Notification sending/receiving flowWe will first present the initial design; then, propose some optimizations. High-level design Figure 10-9 shows the design, and each system component is explained below.…READING3 MIN
  7. 10.07Step 3 - Design deep diveIn the high-level design, we discussed different types of notifications, contact info gathering flow, and notification sending/receiving flow. We will explore the following in…READING1 MIN
  8. 10.08ReliabilityWe must answer a few important reliability questions when designing a notification system in distributed environments. How to prevent data loss? One of the most important…READING1 MIN
  9. 10.09Additional components and considerationsWe have discussed how to collect user contact info, send, and receive a notification. A notification system is a lot more than that. Here we discuss additional components…READING2 MIN
  10. 10.10Updated designPutting everything together, Figure 10-14 shows the updated notification system design. In this design, many new components are added in comparison with the previous design.…READING1 MIN
  11. 10.11Step 4 - Wrap upNotifications are indispensable because they keep us posted with important information. It could be a push notification about your favorite movie on Netflix, an email about…READING1 MIN
11

DESIGN CASE STUDIES

Design a news feed system

11 LESSONS · 13 MIN
  1. 11.01Design a news feed systemIn this chapter, you are asked to design a news feed system. What is news feed? According to the Facebook help page, “News feed is the constantly updating list of stories in…READING1 MIN
  2. 11.02Step 1 - Understand the problem and establish design scopeThe first set of clarification questions are to understand what the interviewer has in mind when she asks you to design a news feed system. At the very least, you should figure…READING1 MIN
  3. 11.03Step 2 - Propose high-level design and get buy-inThe design is divided into two flows: feed publishing and news feed building. Feed publishing: when a user publishes a post, corresponding data is written into cache and…READING1 MIN
  4. 11.04Newsfeed APIsThe news feed APIs are the primary ways for clients to communicate with servers. Those APIs are HTTP based that allow clients to perform actions, which include posting a…READING1 MIN
  5. 11.05Feed publishingFigure 11-2 shows the high-level design of the feed publishing flow. User: a user can view news feeds on a browser or mobile app. A user makes a post with content “Hello”…READING1 MIN
  6. 11.06Newsfeed buildingIn this section, we discuss how news feed is built behind the scenes. Figure 11-3 shows the high-level design: User: a user sends a request to retrieve her news feed. The…READING1 MIN
  7. 11.07Step 3 - Design deep diveThe high-level design briefly covered two flows: feed publishing and news feed building. Here, we discuss those topics in more depth.READING1 MIN
  8. 11.08Feed publishing deep diveFigure 11-4 outlines the detailed design for feed publishing. We have discussed most of components in high-level design, and we will focus on two components: web servers and…READING3 MIN
  9. 11.09Newsfeed retrieval deep diveFigure 11-7 illustrates the detailed design for news feed retrieval. As shown in Figure 11-7, media content (images, videos, etc.) are stored in CDN for fast retrieval. Let us…READING1 MIN
  10. 11.10Cache architectureCache is extremely important for a news feed system. We divide the cache tier into 5 layers as shown in Figure 11-8. News Feed: It stores IDs of news feeds.Content: It stores…READING1 MIN
  11. 11.11Step 4 - Wrap upIn this chapter, we designed a news feed system. Our design contains two flows: feed publishing and news feed retrieval. Like any system design interview questions, there is no…READING1 MIN
12

DESIGN CASE STUDIES

Design a chat system

13 LESSONS · 24 MIN
  1. 12.01Design a chat systemIn this chapter we explore the design of a chat system. Almost everyone uses a chat app. Figure 12-1 shows some of the most popular apps in the marketplace. A chat app performs…READING1 MIN
  2. 12.02Step 1 - Understand the problem and establish design scopeIt is vital to agree on the type of chat app to design. In the marketplace, there are one-on-one chat apps like Facebook Messenger, WeChat, and WhatsApp, office chat apps that…READING2 MIN
  3. 12.03Step 2 - Propose high-level design and get buy-inTo develop a high-quality design, we should have a basic knowledge of how clients and servers communicate. In a chat system, clients can be either mobile applications or web…READING2 MIN
  4. 12.04PollingAs shown in Figure 12-3, polling is a technique that the client periodically asks the server if there are messages available. Depending on polling frequency, polling could be…READING1 MIN
  5. 12.05Long pollingBecause polling could be inefficient, the next progression is long polling (Figure 12-4). In long polling, a client holds the connection open until there are actually new…READING1 MIN
  6. 12.06WebSocketWebSocket is the most common solution for sending asynchronous updates from server to client. Figure 12-5 shows how it works. WebSocket connection is initiated by the client.…READING1 MIN
  7. 12.07High-level designJust now we mentioned that WebSocket was chosen as the main communication protocol between the client and server for its bidirectional communication, it is important to note…READING4 MIN
  8. 12.08Data modelsJust now, we talked about using key-value stores as our storage layer. The most important data is message data. Let us take a close look. Message table for 1 on 1 chat Figure…READING2 MIN
  9. 12.09Step 3 - Design deep diveIn a system design interview, usually you are expected to dive deep into some of the components in the high-level design. For the chat system, service discovery, messaging…READING1 MIN
  10. 12.10Service discoveryThe primary role of service discovery is to recommend the best chat server for a client based on the criteria like geographical location, server capacity, etc. Apache Zookeeper…READING1 MIN
  11. 12.11Message flowsIt is interesting to understand the end-to-end flow of a chat system. In this section, we will explore 1 on 1 chat flow, message synchronization across multiple devices and…READING3 MIN
  12. 12.12Online presenceAn online presence indicator is an essential feature of many chat applications. Usually, you can see a green dot next to a user’s profile picture or username. This section…READING3 MIN
  13. 12.13Step 4 - Wrap upIn this chapter, we presented a chat system architecture that supports both 1-to-1 chat and small group chat. WebSocket is used for real-time communication between the client…READING2 MIN
1313 LESSONS · 20 MIN
  1. 13.01Design a search autocomplete systemWhen searching on Google or shopping at Amazon, as you type in the search box, one or more matches for the search term are presented to you. This feature is referred to as…READING1 MIN
  2. 13.02Step 1 - Understand the problem and establish design scopeThe first step to tackle any system design interview question is to ask enough questions to clarify requirements. Here is an example of candidate-interviewer interaction:…READING1 MIN
  3. 13.03Back of the envelope estimationAssume 10 million daily active users (DAU).An average person performs 10 searches per day.20 bytes of data per query string:Assume we use ASCII character encoding. 1 character…READING1 MIN
  4. 13.04Step 2 - Propose high-level design and get buy-inAt the high-level, the system is broken down into two: Data gathering service: It gathers user input queries and aggregates them in real-time. Real-time processing is not…READING1 MIN
  5. 13.05Data gathering serviceLet us use a simplified example to see how data gathering service works. Assume we have a frequency table that stores the query string and its frequency as shown in Figure…READING1 MIN
  6. 13.06Query serviceAssume we have a frequency table as shown in Table 13-1. It has two fields. Query: it stores the query string.Frequency: it represents the number of times a query has been…READING1 MIN
  7. 13.07Step 3 - Design deep diveIn the high-level design, we discussed data gathering service and query service. The high-level design is not optimal, but it serves as a good starting point. In this section,…READING1 MIN
  8. 13.08Trie data structureRelational databases are used for storage in the high-level design. However, fetching the top 5 search queries from a relational database is inefficient. The data structure…READING4 MIN
  9. 13.09Data gathering serviceIn our previous design, whenever a user types a search query, data is updated in real-time. This approach is not practical for the following two reasons: Users may enter…READING3 MIN
  10. 13.10Query serviceIn the high-level design, query service calls the database directly to fetch the top 5 results. Figure 13-11 shows the improved design as previous design is inefficient. A…READING2 MIN
  11. 13.11Trie operationsTrie is a core component of the autocomplete system. Let us look at how trie operations (create, update, and delete) work. Create Trie is created by workers using aggregated…READING1 MIN
  12. 13.12Scale the storageNow that we have developed a system to bring autocomplete queries to users, it is time to solve the scalability issue when the trie grows too large to fit in one server. Since…READING1 MIN
  13. 13.13Step 4 - Wrap upAfter you finish the deep dive, your interviewer might ask you some follow up questions. Interviewer: How do you extend your design to support multiple languages? To support…READING2 MIN
14

DESIGN CASE STUDIES

Design YouTube

13 LESSONS · 21 MIN
  1. 14.01Design YouTubeIn this chapter, you are asked to design YouTube. The solution to this question can be applied to other interview questions like designing a video sharing platform such as…READING1 MIN
  2. 14.02Step 1 - Understand the problem and establish design scopeAs revealed in Figure 14-1, besides watching a video, you can do a lot more on YouTube. For example, comment, share, or like a video, save a video to playlists, subscribe to a…READING1 MIN
  3. 14.03Back of the envelope estimationThe following estimations are based on many assumptions, so it is important to communicate with the interviewer to make sure she is on the same page. Assume the product has 5…READING1 MIN
  4. 14.04Step 2 - Propose high-level design and get buy-inAs discussed previously, the interviewer recommended leveraging existing cloud services instead of building everything from scratch. CDN and blob storage are the cloud services…READING1 MIN
  5. 14.05Video uploading flowFigure 14-4 shows the high-level design for the video uploading. It consists of the following components: User: A user watches YouTube on devices such as a computer, mobile…READING2 MIN
  6. 14.06Video streaming flowWhenever you watch a video on YouTube, it usually starts streaming immediately and you do not wait until the whole video is downloaded. Downloading means the whole video is…READING1 MIN
  7. 14.07Step 3 - Design deep diveIn the high-level design, the entire system is broken down in two parts: video uploading flow and video streaming flow. In this section, we will refine both flows with…READING1 MIN
  8. 14.08Video transcodingWhen you record a video, the device (usually a phone or camera) gives the video file a certain format. If you want the video to be played smoothly on other devices, the video…READING1 MIN
  9. 14.09Directed acyclic graph (DAG) modelTranscoding a video is computationally expensive and time-consuming. Besides, different content creators may have different video processing requirements. For instance, some…READING1 MIN
  10. 14.10Video transcoding architectureThe proposed video transcoding architecture that leverages the cloud services, is shown in Figure 14-10. The architecture has six main components: preprocessor, DAG scheduler,…READING4 MIN
  11. 14.11System optimizationsAt this point, you ought to have good understanding about the video uploading flow, video streaming flow and video transcoding. Next, we will refine the system with…READING4 MIN
  12. 14.12Error handlingFor a large-scale system, system errors are unavoidable. To build a highly fault-tolerant system, we must handle errors gracefully and recover from them fast. Two types of…READING1 MIN
  13. 14.13Step 4 - Wrap upIn this chapter, we presented the architecture design for video streaming services like YouTube. If there is extra time at the end of the interview, here are a few additional…READING2 MIN
15

DESIGN CASE STUDIES

Design Google Drive

18 LESSONS · 23 MIN
  1. 15.01Design Google DriveIn recent years, cloud storage services such as Google Drive, Dropbox, Microsoft OneDrive, and Apple iCloud have become very popular. In this chapter, you are asked to design…READING1 MIN
  2. 15.02Step 1 - Understand the problem and establish design scopeDesigning a Google drive is a big project, so it is important to ask questions to narrow down the scope. Candidate: What are the most important features? Interviewer: Upload…READING2 MIN
  3. 15.03Back of the envelope estimationAssume the application has 50 million signed up users and 10 million DAU.Users get 10 GB free space.Assume users upload 2 files per day. The average file size is 500 KB.1:1…READING1 MIN
  4. 15.04Step 2 - Propose high-level design and get buy-inInstead of showing the high-level design diagram from the beginning, we will use a slightly different approach. We will start with something simple: build everything in a…READING1 MIN
  5. 15.05APIsWhat do the APIs look like? We primary need 3 APIs: upload a file, download a file, and get file revisions. 1. Upload a file to Google Drive Two types of uploads are supported:…READING1 MIN
  6. 15.06Move away from single serverAs more files are uploaded, eventually you get the space full alert as shown in Figure 15-4. Only 10 MB of storage space is left! This is an emergency as users cannot upload…READING2 MIN
  7. 15.07Sync conflictsFor a large storage system like Google Drive, sync conflicts happen from time to time. When two users modify the same file or folder at the same time, a conflict happens. How…READING1 MIN
  8. 15.08High-level designFigure 15-10 illustrates the proposed high-level design. Let us examine each component of the system. User: A user uses the application either through a browser or mobile app.…READING2 MIN
  9. 15.09Step 3 - Design deep diveIn this section, we will take a close look at the following: block servers, metadata database, upload flow, download flow, notification service, save storage space and failure…READING1 MIN
  10. 15.10Block serversFor large files that are updated regularly, sending the whole file on each update consumes a lot of bandwidth. Two optimizations are proposed to minimize the amount of network…READING1 MIN
  11. 15.11High consistency requirementOur system requires strong consistency by default. It is unacceptable for a file to be shown differently by different clients at the same time. The system needs to provide…READING1 MIN
  12. 15.12Metadata databaseFigure 15-13 shows the database schema design. Please note this is a highly simplified version as it only includes the most important tables and interesting fields. User: The…READING1 MIN
  13. 15.13Upload flowLet us discuss what happens when a client uploads a file. To better understand the flow, we draw the sequence diagram as shown in Figure 15-14. In Figure 15-14, two requests…READING1 MIN
  14. 15.14Download flowDownload flow is triggered when a file is added or edited elsewhere. How does a client know if a file is added or edited by another client? There are two ways a client can…READING1 MIN
  15. 15.15Notification serviceTo maintain file consistency, any mutation of a file performed locally needs to be informed to other clients to reduce conflicts. Notification service is built to serve this…READING1 MIN
  16. 15.16Save storage spaceTo support file version history and ensure reliability, multiple versions of the same file are stored across multiple data centers. Storage space can be filled up quickly with…READING1 MIN
  17. 15.17Failure HandlingFailures can occur in a large-scale system and we must adopt design strategies to address these failures. Your interviewer might be interested in hearing about how you handle…READING2 MIN
  18. 15.18Step 4 - Wrap upIn this chapter, we proposed a system design to support Google Drive. The combination of strong consistency, low network bandwidth and fast sync make the design interesting.…READING2 MIN
163 LESSONS · 3 MIN
  1. 16.01The learning continuesDesigning good systems requires years of accumulation of knowledge. One shortcut is to dive into real-world system architectures. Below is a collection of helpful reading…READING1 MIN
  2. 16.02Real-world systemsThe following materials can help you understand general design ideas of real system architectures behind different companies. Facebook Timeline: Brought To You By The Power Of…READING1 MIN
  3. 16.03Company engineering blogsIf you are going to interview with a company, it is a great idea to read their engineering blogs and get familiar with technologies and systems adopted and implemented there.…READING1 MIN
KEEP EXPLORING

One note leads to another.

Back to the library →
⌕
Search across the entire library ⌘ K