Grokking the System Design Interview

【实例截图】

【核心代码】

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
2
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
3
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
4
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
5
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
6
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
7
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