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
Key Value Store
Final design
URL shortener
Final design
Web Crawler
Final design
Notification Service
Final design
News Feed
Final design
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
Search Autocomplete
Final design
