Source
System Design Interview Review
Review of the book Alex Xu by Alexander Polomodov (Part 1 and Part 2)
System Design Interview: An Insider's Guide
Authors: Alex Xu, Sahn Lam
Publisher: Independently Published
Length: 276 pages
A detailed analysis of the legendary book by Alex Xu: scaling, estimation, rate limiter, consistent hashing, key-value store.
Original
TranslatedBook structure
Scaling, load assessment, interview framework
12 real cases on system design
List of sources for in-depth study
1. Scale from Zero to Millions of Users
In this chapter, the author starts by hosting the system on a single server and gradually scales it to millions of users.
Key Chapter Topics
Author's resume
- Keep web tier stateless
- Build redundancy at every tier
- Cache data as much as you can
- Support multiple data centers
- Host static assets in CDN
- Scale your data tier by sharding
- Split tiers into individual services
- Monitor your system and use automation tools
2. Back-of-the-envelope Estimation
The chapter on rough load calculations is a critical skill for the System Design Interview.
Powers of two
Latency Numbers
Availability
Recommendation
For more current data on latency, it is recommended to look rule-of-thumb-latency-numbers from Google SRE.
3. A Framework for System Design Interviews
The chapter on the 4-step framework for passing the System Design Interview is the central methodology of the book.
Understand the Problem
High-level Design
Design Deep Dive
Wrap Up
4. Design a Rate Limiter
A system for limiting the number of requests is the first practical task of the book.
Rate Limiting Algorithms
Tokens are added at a fixed rate, requests consume tokens
Requests are processed at a constant speed, excess is discarded
Counter of requests in a fixed time window
Log timestamps of queries with sliding window
Hybrid fixed window and sliding log
Review author's opinion
Rate limiter is more likely not a separate task, but a cube for other tasks. Although, with a deep analysis, this can be a non-trivial task - for example, you can read about YARL from Yandex.
5. Design Consistent Hashing
A mechanism for uniform distribution of data across servers with minimal redistribution when changes occur.
What is Consistent Hashing?
A special type of hashing in which changing the number of servers requires redistribution only n/m keys (where n is the number of keys, m is the number of slots), in contrast to conventional hashing, where almost all keys are redistributed.
Key Concepts
- Hash Ring - the key space is loopedHash Ring — the key space is looped
- Virtual Nodes - each physical server has several virtual points on the ringVirtual Nodes — each physical server has several virtual points on the ring
- Used in Cassandra, DynamoDB, and other distributed systems
6. Design a Key-Value Store
Designing a distributed key-value storage with support for get/put operations.
System requirements
- Key-value pair size < 10 KB
- Ability to store big data
- High availability
- High scalability
- Automatic scaling
- Tunable consistency
- Low latency
CAP Theorem
- CP — the system does not service some requests, but maintains consistency
- AP — the system weakens consistency for the sake of accessibility
- Partition tolerance is required in distributed systems
Consistency Models
Strong Consistency
This is linearizability: each read sees the result of the last completed write, as if there was a single copy of the data.
Weak Consistency
Subsequent readers may not see the latest updates.
Eventual Consistency
Given enough time, all replicas will become consistent.
Additional Chapter Topics
- Tunable Consistency — W + R > N for strong consistency
- Vector Clocks — for causal consistency and conflict resolution
- Failure Detection — heartbeats, pings, gossip protocol
- Anti-entropy — mechanisms for dealing with data discrepancies
- SSTable & LSM Trees — data storage structures
7. Design a Unique ID Generator
Designing a generator of unique identifiers for distributed systems.
Requirements
- IDs must be unique
- IDs are numerical values only
- IDs fit into 64-bit
- IDs are ordered by date
- Ability to generate over 10,000 unique IDs per second
Multi-master ReplicationJust
Each of the k servers generates an ID in steps of k:
- Server 1: 1, k+1, 2k+1...
- Server 2: 2, k+2, 2k+2...
UUIDPopular
128-bit identifier, generated without coordination.
Ticket ServerCentrally
A single service generates consistent IDs for everyone.
Twitter SnowflakeRecommended
64-bit ID with structure:
- 1 bit - sign
- 41 bit — timestamp (ms)
- 10 bit — machine ID
- 12 bit — sequence number
Summary of the first part of the book
The first seven chapters of the book form the foundation for the System Design Interview:
Strengths
- ✓ Clear 4-step framework
- ✓ Good introduction to scaling
- ✓ Practical algorithms (Rate Limiter)
- ✓ Useful building blocks
What to pay attention to
- ⚠ Simplified description of models consistency
- ⚠ Some tasks are more like “cubes”
- ⚠ It is recommended to add "Database Internals"
Analysis
System Design Interview Review — Part 2
A detailed overview of practical problems from the second part of the book.
Part 2: Practice Problems (Chapters 8-16)
The second part of the book is devoted to real-life System Design Interview tasks - from URL Shortener to Google Drive.
8. Design a URL Shortener
A classic task for System Design Interview is a service for shortening links like bit.ly or tinyurl.
Requirements
- 100 million URLs generated per day
- Read:Write ratio = 10:1
- Average URL length = 100 symbols
- Store for 10 years
API
POST /api/shorten— creating a short linkGET /:shortUrl- redirect to long URL
Hashing Options
| Approach | Description | Peculiarities |
|---|---|---|
| Base62 | [a-zA-Z0-9] | 62⁷ ≈ 3.5 trillion combinations |
| MD5/SHA | Hash + trim | Possible collisions |
| Counter + Base62 | Incremental ID | Predictability |
Additional questions
- Rate limiting on requests
- Database sharding
- Link Usage Analytics
9. Design a Web Crawler
A system for parsing pages on the Internet is the basis of search engines.
Requirements
- 1 billion pages per month
- Storage 5 years
- Average page size - 500 KB
- HTML only (extensible)
System components
URL Frontier: Politeness & Priority
Prioritizer distributes URLs into queues with different priorities. Front Queue Selector ensures politeness - requests to one domain go sequentially through one worker, limiting the load on external sites.
10. Design a Notification System
System for sending millions of push notifications, SMS and emails per day.
Architecture
- Notification API — accepting tasks, authentication, rate limiting
- Message Queues — separate queues for iOS, Android, SMS, Email
- Workers — queue handlers for each channel
- 3rd Party Services — APNs, FCM, Twilio, SendGrid
- Analytics Service — delivery tracking and metrics
11. Design a News Feed System
A social media-like news feed is a classic task, discussed in detail in Martin Kleppmann's DDIA.
Requirements
- 10M DAU
- Up to 5000 friends
- Posts with text, photos, videos
- Sort by time
Fan-out strategies
- Push — we write in the feeds of all subscribers
- Pull — collect the feed when requested
- Hybrid - combination for celebrities
Key Components
12. Design a Chat System
Messenger with peer-to-peer and group chats, online indicator.
Methods for obtaining data
Polling
Periodic server polling. Simple, but ineffective.
Long Polling
The request hangs until the data appears or timeout.
WebSocket ✓
Two-way channel. Recommended for chats.
Components
- Connection API - HTTP for auth and receiving chat server
- Chat API - WebSocket for messages and heartbeat
- Message Queue → Keeper Worker, Push Notification Worker
- Heartbeat Queue → Online Presence Worker → Presence DB
Stateful Chat Servers
Chat servers store active WebSocket connections - this makes them stateful. A mechanism is needed to route messages to the correct server.
13. Design Search Autocomplete
Hint system for auto-completion in the search bar.
Requirements
- 10M DAU
- 10 searches/user/day
- Top 5 tips by frequency
- English only
Key data structure
Allows you to efficiently search by prefix and store the frequency of queries
Architecture
- Search queries → Search QueueSearch Queue
- Workers update Trie with frequencyTrie with frequency
- Shard Manager determines the required shardShard Manager determines the required shard
- Autocomplete API returns top 5 hintsAutocomplete API returns top 5 tips
14. Design YouTube
Video hosting with a focus on transcoding and CDN.
Key aspects
Parallel video processing in different formats and resolutions
Distributing videos via a global CDN
Task graph for parallel processing
Feed of recommendations and subscriptions
15. Design Google Drive
Cloud storage with file synchronization between devices.
Requirements
- 10M DAU
- 10 GB per user
- Upload/Download files
- Synchronization between devices
- Sharing with other users
Key Components
16. The Learning Continues
In the final chapter, the author shares sources for further study.
Author's recommendations
- Engineering blogs of large companies (Netflix, Uber, Airbnb, Meta)
- Conferences and speeches (Strange Loop, QCon, InfoQ)
- Book "Designing Data-Intensive Applications" by Martin Kleppmann
- Practice on real problems and mock interviews
Summary of the book by Alex Xu
"System Design Interview: An Insider's Guide" is a great starting point for preparing for the System Design Interview.
Strengths
- ✓ Clear 4-step framework
- ✓ 12 practice problems
- ✓ Clear diagrams
- ✓ Back-of-the-envelope estimation
- ✓ Additional questions for each task
Recommendations
- ⚠ Supplement DDIA for theory
- ⚠ Learn Database Internals for the database
- ⚠ Practice on a mock interview
- ⚠ Read engineering blogs