Grokking-the-System-Design-Interview.pdf

需积分: 44 37 浏览量更新于2023-03-03 18 收藏 4.35MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源推荐

1 
 
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 


 
Purging or DB Cleanup ..................................................................................................................... 37 
Data Partitioning and Replication .................................................................................................. 37 
Cache and Load Balancer .............................................................................................................. 37 
Security and Permissions ............................................................................................................... 37 
Designing Instagram...................................................................................................................................... 38 
What is Instagram? ............................................................................................................................ 38 
Requirements and Goals of the System ........................................................................................ 38 
Some Design Considerations .......................................................................................................... 39 
Capacity Estimation and Constraints .............................................................................................. 39 
High Level System Design ............................................................................................................... 39 
Database Schema ............................................................................................................................. 40 
Data Size Estimation ......................................................................................................................... 41 
Component Design ............................................................................................................................ 42 
Reliability and Redundancy .............................................................................................................. 43 
Data Sharding .................................................................................................................................. 44 
Ranking and News Feed Generation ........................................................................................... 45 
News Feed Creation with Sharded Data ...................................................................................... 46 
Cache and Load balancing ............................................................................................................ 47 
Designing Dropbox ........................................................................................................................................ 48 
Why Cloud Storage? ......................................................................................................................... 48 
Requirements and Goals of the System ........................................................................................ 49 
Some Design Considerations .......................................................................................................... 49 
Capacity Estimation and Constraints .............................................................................................. 50 
High Level Design .............................................................................................................................. 50 
Component Design ............................................................................................................................ 51 
a. Client .................................................................................................................................................... 51 
b. Metadata Database ........................................................................................................................... 53 
c. Synchronization Service.................................................................................................................... 54 
d. Message Queuing Service ............................................................................................................... 55 
e. Cloud/Block Storage .......................................................................................................................... 56 
File Processing Workflow ................................................................................................................. 56 
Data Deduplication ............................................................................................................................ 56 
Metadata Partitioning ........................................................................................................................ 57 
Caching ............................................................................................................................................. 58 
Load Balancer (LB) ......................................................................................................................... 58 
Security, Permissions and File Sharing ....................................................................................... 59 
Designing Facebook Messenger.................................................................................................................... 60 


 
What is Facebook Messenger? ....................................................................................................... 60 
Requirements and Goals of the System ........................................................................................ 60 
Capacity Estimation and Constraints .............................................................................................. 61 
High Level Design .............................................................................................................................. 62 
Detailed Component Design ............................................................................................................ 65 
a. Messages Handling ........................................................................................................................... 65 
b. Storing and retrieving the messages from the database ............................................................. 67 
c. Managing user’s status ..................................................................................................................... 68 
Data partitioning ................................................................................................................................. 69 
Cache................................................................................................................................................... 70 
Load balancing ................................................................................................................................... 70 
Fault tolerance and Replication ....................................................................................................... 70 
Extended Requirements ................................................................................................................. 71 
a. Group chat .......................................................................................................................................... 71 
b. Push notifications ............................................................................................................................... 71 
Designing Twitter .......................................................................................................................................... 72 
What is Twitter? ................................................................................................................................. 72 
Requirements and Goals of the System ........................................................................................ 72 
Capacity Estimation and Constraints .............................................................................................. 73 
System APIs ....................................................................................................................................... 74 
High Level System Design ............................................................................................................... 74 
Database Schema ............................................................................................................................. 75 
Data Sharding ..................................................................................................................................... 76 
Cache................................................................................................................................................... 78 
Timeline Generation .......................................................................................................................... 79 
Replication and Fault Tolerance .................................................................................................... 79 
Load Balancing ................................................................................................................................ 80 
Monitoring ......................................................................................................................................... 80 
Extended Requirements ................................................................................................................. 80 
Designing Youtube or Netflix ........................................................................................................................ 82 
Why Youtube? .................................................................................................................................... 82 
Requirements and Goals of the System ........................................................................................ 82 
Capacity Estimation and Constraints .............................................................................................. 83 
System APIs ....................................................................................................................................... 83 
High Level Design .............................................................................................................................. 85 
Database Schema ............................................................................................................................. 85 
Detailed Component Design ............................................................................................................ 86 


 
Metadata Sharding ............................................................................................................................ 88 
Video Deduplication ........................................................................................................................... 88 
Load Balancing ................................................................................................................................ 89 
Cache ................................................................................................................................................ 90 
Content Delivery Network (CDN) .................................................................................................. 90 
Fault Tolerance ................................................................................................................................ 91 
Designing Typeahead Suggestion ................................................................................................................. 92 
What is Typeahead Suggestion? .................................................................................................... 92 
Requirements and Goals of the System ........................................................................................ 92 
Basic System Design and Algorithm ............................................................................................... 92 
Permanent Storage of the Trie ........................................................................................................ 95 
Scale Estimation ................................................................................................................................ 96 
Data Partition ...................................................................................................................................... 97 
Cache................................................................................................................................................... 98 
Replication and Load Balancer ........................................................................................................ 99 
Fault Tolerance .................................................................................................................................. 99 
Typeahead Client ............................................................................................................................. 99 
Personalization ................................................................................................................................. 99 
Designing an API Rate Limiter ..................................................................................................................... 100 
What is a Rate Limiter? ................................................................................................................... 100 
Why do we need API rate limiting? ............................................................................................... 100 
Requirements and Goals of the System ...................................................................................... 101 
How to do Rate Limiting?................................................................................................................ 102 
What are different types of throttling? ........................................................................................... 102 
What are different types of algorithms used for Rate Limiting? ................................................ 102 
High level design for Rate Limiter ................................................................................................. 103 
Basic System Design and Algorithm ............................................................................................. 104 
Sliding Window algorithm ............................................................................................................... 107 
Sliding Window with Counters ..................................................................................................... 109 
Data Sharding and Caching ......................................................................................................... 111 
Should we rate limit by IP or by user? ........................................................................................ 112 
Designing Twitter Search ............................................................................................................................ 113 
What is Twitter Search? .................................................................................................................. 113 
Requirements and Goals of the System ...................................................................................... 113 
Capacity Estimation and Constraints ............................................................................................ 113 
System APIs ..................................................................................................................................... 114 
High Level Design ............................................................................................................................ 114 


 
Detailed Component Design .......................................................................................................... 115 
Fault Tolerance ................................................................................................................................ 117 
Cache................................................................................................................................................. 118 
Load Balancing ................................................................................................................................. 118 
Ranking ........................................................................................................................................... 118 
Designing a Web Crawler ............................................................................................................................ 119 
What is a Web Crawler? ................................................................................................................. 119 
Requirements and Goals of the System ...................................................................................... 119 
Some Design Considerations ........................................................................................................ 119 
Capacity Estimation and Constraints ............................................................................................ 120 
High Level design ............................................................................................................................ 121 
How to crawl? ....................................................................................................................................... 121 
Difficulties in implementing efficient web crawler ............................................................................ 121 
Detailed Component Design .......................................................................................................... 122 
Fault tolerance .................................................................................................................................. 127 
Data Partitioning ............................................................................................................................... 127 
Crawler Traps ................................................................................................................................... 127 
Designing Facebook’s Newsfeed ................................................................................................................. 128 
What is Facebook’s newsfeed? ..................................................................................................... 128 
Requirements and Goals of the System ...................................................................................... 128 
Capacity Estimation and Constraints ............................................................................................ 129 
System APIs ..................................................................................................................................... 129 
Database Design ............................................................................................................................. 130 
High Level System Design ............................................................................................................. 131 
Detailed Component Design .......................................................................................................... 132 
Feed Ranking ................................................................................................................................... 135 
Data Partitioning ............................................................................................................................... 136 
Designing Yelp or Nearby Friends ............................................................................................................... 137 
Why Yelp or Proximity Server? ...................................................................................................... 137 
Requirements and Goals of the System ...................................................................................... 137 
Scale Estimation .............................................................................................................................. 138 
Database Schema ........................................................................................................................... 138 
System APIs ..................................................................................................................................... 138 
Basic System Design and Algorithm ............................................................................................. 139 
a. SQL solution ..................................................................................................................................... 139 
b. Grids................................................................................................................................................... 140 
c. Dynamic size grids ........................................................................................................................... 142 