System Design Interview by Alex Xu
4 min read
Checklist
Go through this checklist in every interview
- Clarify requirements
- Write QPS, average and peak (peak is 2x average)
- Read QPS (approx 10x write QPS)
- Total storage required
- Latency requirement
- Consistency vs Availability
- High level diagram that matches requirements. Get buy-in
- Deep Dive
- API
- Database schema
- Wrap up
- Error cases
- Potential bottlenecks
- Extra credit
- Cost (development vs ongoing)
- Logging, metrics, alerts
- Automation - CI, CD
- i18n
- CDN
- RPC
Primitives
- Load balancer
- Gateway (for ratelimiting, authentication)
- Server (optionally horizonatally scaled)
- Database
- SQL vs NoSQL, sharding strategy.
- If SQL, indices
- Cache (optionally clustered/sharded)
- Message queue, with workers
- CDN
- Lambdas
Be explicit about replication
Clarifying questions
Good for any problem
- Is this a mobile app? Or a web app? Or both?
- What are the most important features for the product?
- DAU, MAU? Derive peak/avg QPS from this.
- Is there any limit per request/stored object? Derive bandwidth/storage requirements from this.
- Will the system work in a distributed environment?
- Where are our users? Geographical constraints, as well as i18n.
- Can we leverage some of the existing cloud infrastructures provided by Amazon, Google, or Microsoft?
Rate Limiter
- Does the rate limiter throttle API requests based on IP, the user ID, or other properties?
- Is the rate limiter a separate service or should it be implemented in application code?
- Do we need to inform users who are throttled?
Key Value Store
Not questions, but these are the constraints
- Scalable
- Available
- Tunable consistency
- Auto scaling
- Size of key value pair - 10kB
- Low latency
ID generator
- What are the characteristics of unique IDs?
- For each new record, does ID increment by 1?
- Do IDs only contain numerical values?
- What is the ID length requirement?
URL shortener
- Can you give an example of how a URL shortener work?
- How long is the shortened URL?
- What characters are allowed in the shortened URL?
- Can shortened URLs be deleted or updated?
Web Crawler
- What is the main purpose of the crawler? Is it used for search engine indexing, data mining, or something else?
- How many web pages does the web crawler collect per month?
- What content types are included? HTML only or other content types such as PDFs and images as well?
- Shall we consider newly added or edited web pages?
- Do we need to store HTML pages crawled from the web?
- How do we handle web pages with duplicate content?
Notification system
- What types of notifications does the system support?
- Is it a real-time system? (ie, are delays allowed?)
- What triggers notifications?
- Will users be able to opt-out?
News Feed
- Is the news feed sorted in reverse chronological order or a particular order? The particular order means each post is given a different weight. For instance, posts from your close friends are more important than posts from a group.
- How many friends can a user have?
- Can feed contain images, videos, or just text?
Chat system
- What kind of chat app shall we design? 1 on 1 or group based?
- For group chat, what is the group member limit?
- Is end-to-end encryption required?
- How long shall we store the chat history? How about not storing chat history?
Search autocomplete
- Is the matching only supported at the beginning of a search query or in the middle as well?
- How many autocomplete suggestions should the system return?
- What criteria should decide the ordering of the suggestions?
- Does the system support spell check?
- Are search queries in English?
- Do we allow capitalization and special characters?
Youtube
- What are the supported video resolutions?
Google drive
- What are the supported file formats?
Final designs
Rate Limiter
Final design
![](/rate-limiter.png)
Key Value Store
Final design
![](/kv-write.png)
![](/kv-read.png)
![](/kv-read-uncached.png)
URL shortener
Final design
![](/url-shortener.png)
Web Crawler
Final design
![](/web-crawler.png)
Notification Service
Final design
![](/notification.png)
News Feed
Final design
![](/news-feed.png)
Chat service
- Only one system is stateful - the chat service
- Notification is an important part
- Storage of chat messages in Cassandra
- Each user has a queue of messages waiting to sync to them
Final design
![](/chat-service.png)
Search Autocomplete
Final design
![](/name.png)