第1页 / 共196页
第2页 / 共196页
第3页 / 共196页
第4页 / 共196页
第5页 / 共196页
第6页 / 共196页
第7页 / 共196页
第8页 / 共196页
Grokking-the-System-Design-Interview.pdf
System Design Problems
System Design Interviews: A step by step guide
Step 1: Requirements clarifications
Step 2: System interface definition
Step 3: Back-of-the-envelope estimation
Step 4: Defining data model
Step 5: High-level design
Step 6: Detailed design
Step 7: Identifying and resolving bottlenecks
Summary
Designing a URL Shortening service like TinyURL
1. Why do we need URL shortening?
2. Requirements and Goals of the System
3. Capacity Estimation and Constraints
4. System APIs
5. Database Design
Database Schema:
6. Basic System Design and Algorithm
a. Encoding actual URL
b. Generating keys offline
7. Data Partitioning and Replication
8. Cache
9. Load Balancer (LB)
10. Purging or DB cleanup
11. Telemetry
12. Security and Permissions
Designing Pastebin
1. What is Pastebin?
2. Requirements and Goals of the System
3. Some Design Considerations
4. Capacity Estimation and Constraints
5. System APIs
6. Database Design
Database Schema:
7. High Level Design
8. Component Design
a. Application layer
b. Datastore layer
9. Purging or DB Cleanup
10. Data Partitioning and Replication
11. Cache and Load Balancer
12. Security and Permissions
Designing Instagram
1. What is Instagram?
2. Requirements and Goals of the System
3. Some Design Considerations
4. Capacity Estimation and Constraints
5. High Level System Design
6. Database Schema
7. Data Size Estimation
8. Component Design
9. Reliability and Redundancy
10. Data Sharding
11. Ranking and News Feed Generation
12. News Feed Creation with Sharded Data
13. Cache and Load balancing
Designing Dropbox
1. Why Cloud Storage?
2. Requirements and Goals of the System
3. Some Design Considerations
4. Capacity Estimation and Constraints
5. High Level Design
6. Component Design
a. Client
b. Metadata Database
c. Synchronization Service
d. Message Queuing Service
e. Cloud/Block Storage
7. File Processing Workflow
8. Data Deduplication
9. Metadata Partitioning
10. Caching
11. Load Balancer (LB)
12. Security, Permissions and File Sharing
Designing Facebook Messenger
1. What is Facebook Messenger?
2. Requirements and Goals of the System
3. Capacity Estimation and Constraints
4. High Level Design
5. Detailed Component Design
a. Messages Handling
b. Storing and retrieving the messages from the database
c. Managing user’s status
6. Data partitioning
7. Cache
8. Load balancing
9. Fault tolerance and Replication
10. Extended Requirements
a. Group chat
b. Push notifications
Designing Twitter
1. What is Twitter?
2. Requirements and Goals of the System
3. Capacity Estimation and Constraints
4. System APIs
5. High Level System Design
6. Database Schema
7. Data Sharding
8. Cache
9. Timeline Generation
10. Replication and Fault Tolerance
11. Load Balancing
12. Monitoring
13. Extended Requirements
Designing Youtube or Netflix
1. Why Youtube?
2. Requirements and Goals of the System
3. Capacity Estimation and Constraints
4. System APIs
5. High Level Design
6. Database Schema
7. Detailed Component Design
8. Metadata Sharding
9. Video Deduplication
10. Load Balancing
11. Cache
12. Content Delivery Network (CDN)
13. Fault Tolerance
Designing Typeahead Suggestion
1. What is Typeahead Suggestion?
2. Requirements and Goals of the System
3. Basic System Design and Algorithm
4. Permanent Storage of the Trie
5. Scale Estimation
6. Data Partition
7. Cache
8. Replication and Load Balancer
9. Fault Tolerance
10. Typeahead Client
11. Personalization
Designing an API Rate Limiter
1. What is a Rate Limiter?
2. Why do we need API rate limiting?
3. Requirements and Goals of the System
4. How to do Rate Limiting?
5. What are different types of throttling?
6. What are different types of algorithms used for Rate Limiting?
7. High level design for Rate Limiter
8. Basic System Design and Algorithm
9. Sliding Window algorithm
10. Sliding Window with Counters
11. Data Sharding and Caching
12. Should we rate limit by IP or by user?
Designing Twitter Search
1. What is Twitter Search?
2. Requirements and Goals of the System
3. Capacity Estimation and Constraints
4. System APIs
5. High Level Design
6. Detailed Component Design
7. Fault Tolerance
8. Cache
9. Load Balancing
10. Ranking
Designing a Web Crawler
1. What is a Web Crawler?
2. Requirements and Goals of the System
3. Some Design Considerations
4. Capacity Estimation and Constraints
5. High Level design
How to crawl?
Difficulties in implementing efficient web crawler
6. Detailed Component Design
7. Fault tolerance
8. Data Partitioning
9. Crawler Traps
Designing Facebook’s Newsfeed
1. What is Facebook’s newsfeed?
2. Requirements and Goals of the System
3. Capacity Estimation and Constraints
4. System APIs
5. Database Design
6. High Level System Design
7. Detailed Component Design
8. Feed Ranking
9. Data Partitioning
Designing Yelp or Nearby Friends
1. Why Yelp or Proximity Server?
2. Requirements and Goals of the System
3. Scale Estimation
4. Database Schema
5. System APIs
6. Basic System Design and Algorithm
a. SQL solution
b. Grids
c. Dynamic size grids
7. Data Partitioning
8. Replication and Fault Tolerance
9. Cache
10. Load Balancing (LB)
11. Ranking
Designing Uber backend
1. What is Uber?
2. Requirements and Goals of the System
3. Capacity Estimation and Constraints
4. Basic System Design and Algorithm
5. Fault Tolerance and Replication
6. Ranking
7. Advanced Issues
Design Ticketmaster (*New*)
1. What is an online movie ticket booking system?
2. Requirements and Goals of the System
3. Some Design Considerations
4. Capacity Estimation
5. System APIs
6. Database Design
7. High Level Design
8. Detailed Component Design
9. Concurrency
10. Fault Tolerance
11. 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)
SYSTEM DESIGN
System Design Problems ......................................................................................................................................8
System Design Interviews: A step by step guide .............................................................................................8
Step 1: Requirements clarifications ........................................................................................................8
Step 2: System interface definition .........................................................................................................9
Step 3: Back-of-the-envelope estimation ...............................................................................................9
Step 4: Defining data model ....................................................................................................................9
Step 5: High-level design ...................................................................................................................... 10
Step 6: Detailed design ......................................................................................................................... 10
Step 7: Identifying and resolving bottlenecks .................................................................................... 11
Summary ................................................................................................................................................. 11
Designing a URL Shortening service like TinyURL ......................................................................................... 12
1. Why do we need URL shortening? ................................................................................................. 12
2. Requirements and Goals of the System ........................................................................................ 12
3. Capacity Estimation and Constraints .............................................................................................. 13
4. System APIs ....................................................................................................................................... 15
5. Database Design ............................................................................................................................... 16
6. Basic System Design and Algorithm ............................................................................................... 17
a. Encoding actual URL ......................................................................................................................... 17
b. Generating keys offline ..................................................................................................................... 21
7. Data Partitioning and Replication .................................................................................................... 23
8. Cache................................................................................................................................................... 23
9. Load Balancer (LB) ............................................................................................................................ 27
10. Purging or DB cleanup .................................................................................................................... 28
11. Telemetry .......................................................................................................................................... 29
12. Security and Permissions ............................................................................................................... 29
Designing Pastebin ........................................................................................................................................ 30
1. What is Pastebin? .............................................................................................................................. 30
2. Requirements and Goals of the System ........................................................................................ 30
3. Some Design Considerations .......................................................................................................... 31
4. Capacity Estimation and Constraints .............................................................................................. 31
5. System APIs ....................................................................................................................................... 32
6. Database Design ............................................................................................................................... 33
7. High Level Design .............................................................................................................................. 34
8. Component Design ............................................................................................................................ 35
a. Application layer ................................................................................................................................. 35
b. Datastore layer ................................................................................................................................... 36
1
9. Purging or DB Cleanup ..................................................................................................................... 37
10. Data Partitioning and Replication .................................................................................................. 37
11. Cache and Load Balancer .............................................................................................................. 37
12. Security and Permissions ............................................................................................................... 37
Designing Instagram...................................................................................................................................... 38
1. What is Instagram? ............................................................................................................................ 38
2. Requirements and Goals of the System ........................................................................................ 38
3. Some Design Considerations .......................................................................................................... 39
4. Capacity Estimation and Constraints .............................................................................................. 39
5. High Level System Design ............................................................................................................... 39
6. Database Schema ............................................................................................................................. 40
7. Data Size Estimation ......................................................................................................................... 41
8. Component Design ............................................................................................................................ 42
9. Reliability and Redundancy .............................................................................................................. 43
10. Data Sharding .................................................................................................................................. 44
11. Ranking and News Feed Generation ........................................................................................... 45
12. News Feed Creation with Sharded Data ...................................................................................... 46
13. Cache and Load balancing ............................................................................................................ 47
Designing Dropbox ........................................................................................................................................ 48
1. Why Cloud Storage? ......................................................................................................................... 48
2. Requirements and Goals of the System ........................................................................................ 49
3. Some Design Considerations .......................................................................................................... 49
4. Capacity Estimation and Constraints .............................................................................................. 50
5. High Level Design .............................................................................................................................. 50
6. Component Design ............................................................................................................................ 51
a. Client .................................................................................................................................................... 51
b. Metadata Database ........................................................................................................................... 53
c. Synchronization Service.................................................................................................................... 54
d. Message Queuing Service ............................................................................................................... 55
e. Cloud/Block Storage .......................................................................................................................... 56
7. File Processing Workflow ................................................................................................................. 56
8. Data Deduplication ............................................................................................................................ 56
9. Metadata Partitioning ........................................................................................................................ 57
10. Caching ............................................................................................................................................. 58
11. Load Balancer (LB) ......................................................................................................................... 58
12. Security, Permissions and File Sharing ....................................................................................... 59
Designing Facebook Messenger.................................................................................................................... 60
2
1. What is Facebook Messenger? ....................................................................................................... 60
2. Requirements and Goals of the System ........................................................................................ 60
3. Capacity Estimation and Constraints .............................................................................................. 61
4. High Level Design .............................................................................................................................. 62
5. Detailed Component Design ............................................................................................................ 65
a. Messages Handling ........................................................................................................................... 65
b. Storing and retrieving the messages from the database ............................................................. 67
c. Managing user’s status ..................................................................................................................... 68
6. Data partitioning ................................................................................................................................. 69
7. Cache................................................................................................................................................... 70
8. Load balancing ................................................................................................................................... 70
9. Fault tolerance and Replication ....................................................................................................... 70
10. Extended Requirements ................................................................................................................. 71
a. Group chat .......................................................................................................................................... 71
b. Push notifications ............................................................................................................................... 71
Designing Twitter .......................................................................................................................................... 72
1. What is Twitter? ................................................................................................................................. 72
2. Requirements and Goals of the System ........................................................................................ 72
3. Capacity Estimation and Constraints .............................................................................................. 73
4. System APIs ....................................................................................................................................... 74
5. High Level System Design ............................................................................................................... 74
6. Database Schema ............................................................................................................................. 75
7. Data Sharding ..................................................................................................................................... 76
8. Cache................................................................................................................................................... 78
9. Timeline Generation .......................................................................................................................... 79
10. Replication and Fault Tolerance .................................................................................................... 79
11. Load Balancing ................................................................................................................................ 80
12. Monitoring ......................................................................................................................................... 80
13. Extended Requirements ................................................................................................................. 80
Designing Youtube or Netflix ........................................................................................................................ 82
1. Why Youtube? .................................................................................................................................... 82
2. Requirements and Goals of the System ........................................................................................ 82
3. Capacity Estimation and Constraints .............................................................................................. 83
4. System APIs ....................................................................................................................................... 83
5. High Level Design .............................................................................................................................. 85
6. Database Schema ............................................................................................................................. 85
7. Detailed Component Design ............................................................................................................ 86
3
8. Metadata Sharding ............................................................................................................................ 88
9. Video Deduplication ........................................................................................................................... 88
10. Load Balancing ................................................................................................................................ 89
11. Cache ................................................................................................................................................ 90
12. Content Delivery Network (CDN) .................................................................................................. 90
13. Fault Tolerance ................................................................................................................................ 91
Designing Typeahead Suggestion ................................................................................................................. 92
1. What is Typeahead Suggestion? .................................................................................................... 92
2. Requirements and Goals of the System ........................................................................................ 92
3. Basic System Design and Algorithm ............................................................................................... 92
4. Permanent Storage of the Trie ........................................................................................................ 95
5. Scale Estimation ................................................................................................................................ 96
6. Data Partition ...................................................................................................................................... 97
7. Cache................................................................................................................................................... 98
8. Replication and Load Balancer ........................................................................................................ 99
9. Fault Tolerance .................................................................................................................................. 99
10. Typeahead Client ............................................................................................................................. 99
11. Personalization ................................................................................................................................. 99
Designing an API Rate Limiter ..................................................................................................................... 100
1. What is a Rate Limiter? ................................................................................................................... 100
2. Why do we need API rate limiting? ............................................................................................... 100
3. Requirements and Goals of the System ...................................................................................... 101
4. How to do Rate Limiting?................................................................................................................ 102
5. What are different types of throttling? ........................................................................................... 102
6. What are different types of algorithms used for Rate Limiting? ................................................ 102
7. High level design for Rate Limiter ................................................................................................. 103
8. Basic System Design and Algorithm ............................................................................................. 104
9. Sliding Window algorithm ............................................................................................................... 107
10. Sliding Window with Counters ..................................................................................................... 109
11. Data Sharding and Caching ......................................................................................................... 111
12. Should we rate limit by IP or by user? ........................................................................................ 112
Designing Twitter Search ............................................................................................................................ 113
1. What is Twitter Search? .................................................................................................................. 113
2. Requirements and Goals of the System ...................................................................................... 113
3. Capacity Estimation and Constraints ............................................................................................ 113
4. System APIs ..................................................................................................................................... 114
5. High Level Design ............................................................................................................................ 114
4
6. Detailed Component Design .......................................................................................................... 115
7. Fault Tolerance ................................................................................................................................ 117
8. Cache................................................................................................................................................. 118
9. Load Balancing ................................................................................................................................. 118
10. Ranking ........................................................................................................................................... 118
Designing a Web Crawler ............................................................................................................................ 119
1. What is a Web Crawler? ................................................................................................................. 119
2. Requirements and Goals of the System ...................................................................................... 119
3. Some Design Considerations ........................................................................................................ 119
4. Capacity Estimation and Constraints ............................................................................................ 120
5. High Level design ............................................................................................................................ 121
How to crawl? ....................................................................................................................................... 121
Difficulties in implementing efficient web crawler ............................................................................ 121
6. Detailed Component Design .......................................................................................................... 122
7. Fault tolerance .................................................................................................................................. 127
8. Data Partitioning ............................................................................................................................... 127
9. Crawler Traps ................................................................................................................................... 127
Designing Facebook’s Newsfeed ................................................................................................................. 128
1. What is Facebook’s newsfeed? ..................................................................................................... 128
2. Requirements and Goals of the System ...................................................................................... 128
3. Capacity Estimation and Constraints ............................................................................................ 129
4. System APIs ..................................................................................................................................... 129
5. Database Design ............................................................................................................................. 130
6. High Level System Design ............................................................................................................. 131
7. Detailed Component Design .......................................................................................................... 132
8. Feed Ranking ................................................................................................................................... 135
9. Data Partitioning ............................................................................................................................... 136
Designing Yelp or Nearby Friends ............................................................................................................... 137
1. Why Yelp or Proximity Server? ...................................................................................................... 137
2. Requirements and Goals of the System ...................................................................................... 137
3. Scale Estimation .............................................................................................................................. 138
4. Database Schema ........................................................................................................................... 138
5. System APIs ..................................................................................................................................... 138
6. Basic System Design and Algorithm ............................................................................................. 139
a. SQL solution ..................................................................................................................................... 139
b. Grids................................................................................................................................................... 140
c. Dynamic size grids ........................................................................................................................... 142
5
7. Data Partitioning ............................................................................................................................... 144
8. Replication and Fault Tolerance .................................................................................................... 145
9. Cache................................................................................................................................................. 146
10. Load Balancing (LB) ...................................................................................................................... 146
11. Ranking ........................................................................................................................................... 146
Designing Uber backend ............................................................................................................................. 148
1. What is Uber? ................................................................................................................................... 148
2. Requirements and Goals of the System ...................................................................................... 148
3. Capacity Estimation and Constraints ............................................................................................ 148
4. Basic System Design and Algorithm ............................................................................................. 149
5. Fault Tolerance and Replication .................................................................................................... 152
6. Ranking ............................................................................................................................................. 153
7. Advanced Issues .............................................................................................................................. 153
Design Ticketmaster (*New*) ..................................................................................................................... 154
1. What is an online movie ticket booking system? ........................................................................ 154
2. Requirements and Goals of the System ...................................................................................... 154
3. Some Design Considerations ........................................................................................................ 155
4. Capacity Estimation ......................................................................................................................... 155
5. System APIs ..................................................................................................................................... 156
6. Database Design ............................................................................................................................. 158
7. High Level Design ............................................................................................................................ 159
8. Detailed Component Design .......................................................................................................... 160
9. Concurrency ..................................................................................................................................... 165
10. Fault Tolerance .............................................................................................................................. 166
11. Data Partitioning ............................................................................................................................ 166
Additional Resources .................................................................................................................................. 168
System Design Basics ...................................................................................................................................... 169
Key Characteristics of Distributed Systems ................................................................................................ 169
Scalability............................................................................................................................................... 169
Reliability ............................................................................................................................................... 170
Availability .............................................................................................................................................. 171
Efficiency ............................................................................................................................................... 172
Serviceability or Manageability ........................................................................................................... 172
Load Balancing ............................................................................................................................................ 173
Benefits of Load Balancing ................................................................................................................. 174
Load Balancing Algorithms ................................................................................................................. 174
Redundant Load Balancers ................................................................................................................ 175
6
Caching ........................................................................................................................................................ 176
Application server cache ..................................................................................................................... 176
Content Distribution Network (CDN) ................................................................................................. 176
Cache Invalidation ................................................................................................................................ 177
Cache eviction policies ........................................................................................................................ 177
Sharding or Data Partitioning...................................................................................................................... 178
1. Partitioning Methods ........................................................................................................................ 178
2. Partitioning Criteria .......................................................................................................................... 179
3. Common Problems of Sharding .................................................................................................... 180
Indexes ........................................................................................................................................................ 181
Example: A library catalog .................................................................................................................. 181
How do Indexes decrease write performance? ............................................................................... 182
Proxies ......................................................................................................................................................... 183
Proxy Server Types ............................................................................................................................. 183
Redundancy and Replication ...................................................................................................................... 184
SQL vs. NoSQL ............................................................................................................................................. 185
SQL......................................................................................................................................................... 185
NoSQL ................................................................................................................................................... 185
High level differences between SQL and NoSQL ........................................................................... 186
SQL VS. NoSQL - Which one to use? .............................................................................................. 187
Reasons to use SQL database .......................................................................................................... 187
Reasons to use NoSQL database ..................................................................................................... 187
CAP Theorem .............................................................................................................................................. 188
Consistent Hashing...................................................................................................................................... 189
What is Consistent Hashing? ............................................................................................................. 190
How does it work? ................................................................................................................................ 190
Long-Polling vs WebSockets vs Server-Sent Events .................................................................................... 193
Ajax Polling ............................................................................................................................................ 193
HTTP Long-Polling ............................................................................................................................... 194
WebSockets .......................................................................................................................................... 195
Server-Sent Events (SSEs) ................................................................................................................ 196
7
System Design Problems
System Design Interviews: A step by step guide
A lot of software engineers struggle with system design interviews (SDIs) primarily
because of three reasons:
The unstructured nature of SDIs, where they are asked to work on an open-
ended design problem that doesn’t have a standard answer.
Their lack of experience in developing large scale systems.
They did not prepare for SDIs.
Like coding interviews, candidates who haven’t put a conscious effort to prepare for
SDIs, mostly perform poorly especially at top companies like Google, Facebook,
Amazon, Microsoft, etc. In these companies, candidates who don’t perform above
average, have a limited chance to get an offer. On the other hand, a good
performance always results in a better offer (higher position and salary), since it
shows the candidate’s ability to handle a complex system.
In this course, we’ll follow a step by step approach to solve multiple design
problems. First, let’s go through these steps:
Step 1: Requirements clarifications
It is always a good idea to ask questions about the exact scope of the problem we are
solving. Design questions are mostly open-ended, and they don’t have ONE correct
answer, that’s why clarifying ambiguities early in the interview becomes critical.
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 35-40
minutes to design a (supposedly) large system, we should clarify what parts of the
system we will be focusing on.
Let’s expand this with an actual example of designing a Twitter-like service. Here are
some questions for designing Twitter that should be answered before moving on to
the next steps:
Will users of our service be able to post tweets and follow other people?
Should we also design to create and display the user’s timeline?
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?
8
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
