This is my reading notes for Chapter 8 in book “System Design Interview – An insider’s guide (Vol. 1)”.
Overview
Chapter 8 from System Design Interview: An Insider’s Guide explains how to design a URL shortening service like TinyURL or Bitly. The goal is to build a scalable, reliable, and low-latency system capable of handling massive traffic. The design involves solving distributed system challenges such as database scaling, hashing, and caching.
Key Concepts & Design Steps
1. Understanding Requirements
The primary functions of a URL shortener are:
- Convert long URLs to short aliases (e.g.,
tinyurl.com/abc123). - Redirect users from the short URL back to the original URL.
Key requirements include:
- Scale: Handle 100 million URL shortening requests per day.
- Read-to-Write Ratio: The system should handle 10 reads for every 1 write.
- Storage: Plan for at least 1 TB of storage for 10 years of data.
2. Back-of-the-Envelope Calculations
For 100 million requests per day, the system needs to handle approximately:
- 1160 write operations per second
- 11,600 read operations per second
Storage estimation: About 36.5 TB would be needed over 10 years to store URL mappings.
System Components
3. API Design
POST API (Shorten URL)
This API accepts a long URL and generates a short one.
POST /shorten
Request: { "longURL": "https://example.com/some-long-url" }
Response: { "shortURL": "https://tinyurl.com/abc123" }GET API (Redirect)
The GET API maps the short URL to the long URL and redirects the user.
GET /abc123
Response: Redirects to "https://example.com/some-long-url"
4. High-Level Architecture
- Client Requests: Clients send requests to shorten URLs, and the system generates a unique short URL.
- Hash Table Storage: Store
<shortURL, longURL>mappings in a hash table. - URL Redirection: Redirect users from the short URL to the original long URL using HTTP 301 or 302 responses.
5. Unique ID Generation
- Base 62 Encoding: Use a combination of [A-Z, a-z, 0-9] to represent shortened URLs.
- Example: A 7-character Base 62 string allows for around 3.5 trillion unique URLs.
6. Collision Handling
- Hash Collision: When collisions occur, recursively generate new short URLs by appending characters (e.g., from
abc123toabc124).
7. Caching
- Cache Layer: Use a distributed cache (e.g., Redis) to store frequently accessed short URLs. This reduces the load on the database.
8. Data Model
- Relational Schema Example:
Table: URL_Mappings
---------------------------------
ID | ShortURL | LongURL | CreatedAt
---------------------------------
1 | abc123 | https://example.com/long-url | 2024-08-18- NoSQL Option: Consider using a NoSQL solution like DynamoDB for distributed data handling.
9. Rate Limiting
To prevent abuse, limit the number of URL shortening requests per user/IP.
- Example: A user can shorten 5 URLs per minute.
System Scalability and Optimization
10. Horizontal Scaling
Scale horizontally by adding more servers to handle increased traffic.
- Database Sharding: Distribute data across multiple servers to prevent bottlenecks.
11. Database Replication
Use master-slave replication to distribute read operations and ensure high availability.
12. Fault Tolerance
Ensure resilience by replicating data across multiple data centers to protect against outages.
13. Analytics and Tracking
Track URL usage with analytics.
- Example: Add a field in the database to count how many times a short URL has been accessed.
14. Content Delivery Network (CDN)
Use a CDN to serve static assets quickly to end users globally.
Conclusion
Chapter 8 of System Design Interview: An Insider’s Guide outlines how to design a scalable URL shortening service, a common system design question. The design process covers everything from API structure and ID generation to scaling, caching, and fault tolerance, making it a great practice problem for system design interviews.