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
A little progress, one lesson at a time.Your progress stays in this browser.
Start learning →CURRICULUM STRUCTURE
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 01.19Database scalingThere are two broad approaches for database scaling: vertical scaling and horizontal scaling.
- 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.…
- 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…
- 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…
- 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,…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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,…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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.
- 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…
- 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…
- 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…
- 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…
- 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: -…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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:…
- 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.
- 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…
- 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…
- 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…
- 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…
- 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…
- 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.…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 06.06System componentsIn this section, we will discuss the following core components and techniques used to build a key-value store: Data partitionData replicationConsistencyInconsistency…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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.
- 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…
- 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…
- 08.04Step 2 - Propose high-level design and get buy-inIn this section, we discuss the API endpoints, URL redirecting, and URL shortening flows.
- 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…
- 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.…
- 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…
- 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…
- 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…
- 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 +…
- 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…
- 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.…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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.…
- 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…
- 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…
- 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…
- 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.…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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”…
- 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…
- 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.
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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.…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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:…
- 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…
- 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…
- 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…
- 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…
- 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,…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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,…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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:…
- 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…
- 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…
- 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.…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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.…
- 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…
- 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…
- 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.…
No practice lessons in this collection. Choose Reading to explore the curriculum.