Grokking the System Design Interview

✍ Scribed by Design Gurus

• Tongue: English
• Leaves: 163
• Category: Library

✦ Synopsis

System design questions have become a standard part of the software engineering interview process. Performance in these interviews reflects upon your ability to work with complex systems and translates into the position and salary the interviewing company offers you. Most engineers struggle with the system design interview (SDI), partly because of their lack of experience in developing large-scale systems and partly because of the unstructured nature of SDIs. Even engineers who’ve some experience building such systems aren't comfortable with these interviews, mainly due to the open-ended nature of design problems that don't have a standard answer.

This course is a complete guide to master the SDIs. It is created by hiring managers who’ve been working at Google, Facebook, Microsoft, and Amazon. We've carefully chosen a set of questions that have not only been repeatedly asked at top companies, but also provide a thorough experience to handle any system design problem.

✦ Table of Contents

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)