Build a low-latency URL Shortening Pipeline

Question

Design a low-latency url shortening system that handles millions of requests. Discuss trade-offs in consistency, availability, and performance.

Codemia · Accepted Answer

### Functional Requirements:
1. **URL Shortening**: Users should be able to submit a long URL and receive a shortened version.
2. **Redirection**: When a shortened URL is accessed, it should redirect to the original long URL.
3. **Analytics**: Provide metrics on the number of clicks for each shortened URL.
4. **User Authentication**: Users should be able to create accounts to manage their shortened URLs.
5. **Rate Limiting**: Implement rate limiting per user to prevent abuse.

### Non-Functional Requirements:
1. **Low Latency**: Response time for shortening URLs and redirection should be under 100ms.
2. **Scalability**: System should handle up to 10,000 QPS initially, scaling to 100,000 QPS as needed.
3. **High Availability**: System should be available 99.99% of the time.
4. **Security**: Protect against URL injection attacks and ensure data integrity.

Assuming we expect an initial load of 10,000 QPS:
- **Requests per second**: 10,000 QPS = 864 million requests per day.
- **Storage**: Each URL mapping (original + shortened) could average 100 bytes. For 10 million URLs, we need:
  - `10,000,000 URLs * 100 bytes = 1,000,000,000 bytes` (or ~1 GB).
- **Bandwidth**: Each redirection could involve a 1KB payload. For 10,000 QPS, we would need:
  - `10,000 * 1KB * 60 seconds = 600 MB/minute` bandwidth.
- Plan for a **10x growth** in the next few years to accommodate future scaling.

### Component Diagram:
- **API Gateway**: Routes incoming requests to appropriate services.
- **URL Shortening Service**: Handles URL shortening and redirection logic.
- **Database**: A NoSQL database like MongoDB to store URL mappings.
- **Cache**: A Redis cache to store frequently accessed URL mappings for low-latency retrieval.
- **Analytics Service**: Collects click metrics asynchronously to avoid blocking the main URL service.

### Technology Choices:
- **API Gateway**: Kong or NGINX for routing and load balancing.
- **Database**: MongoDB for flexibility in schema and scalability.
- **Caching**: Redis for in-memory caching of URL mappings.

### Schema Design:
1. **URL Mapping Collection**:
   - `shortUrl`: String (unique identifier for the shortened URL)
   - `longUrl`: String (the original URL)
   - `createdAt`: Date (timestamp of creation)
   - `userId`: String (if applicable, for user-specific URLs)
   - `clickCount`: Integer (number of times the short URL has been accessed)

2. **User Collection (optional)**:
   - `userId`: String (unique identifier)
   - `username`: String (user's display name)
   - `passwordHash`: String (hashed password)

### Access Patterns:
- Shortening a URL will involve writing to the database and cache. 
- Redirection will primarily read from the cache, falling back to the database if not found.

### Architectural Decisions:
1. **Consistency vs. Availability**: Opting for eventual consistency in click metrics to ensure low latency in URL shortening and redirection. This means that while the click count may not be immediately accurate, it will eventually reflect the correct number.
2. **Database vs. Cache**: Using Redis for caching to meet low-latency requirements, trading off some consistency for speed. We accept that cache misses will require a database hit but aim to minimize this with effective TTL settings.
3. **Horizontal Scaling**: The architecture can scale horizontally by adding more instances of the URL shortener service and database shards as load increases, ensuring high availability.
4. **Monitoring and Alerting**: Implementing monitoring tools like Prometheus for real-time metrics and Grafana for dashboards, along with alerting through PagerDuty for failures or unusual patterns in request rates.

Build a low-latency URL Shortening Pipeline

Reddit

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Practice a Similar Problem on Codemia

Sample Answer

Requirements

Functional Requirements:

Capacity Estimation

Submit Your Answer

Reddit Software Engineer Interview Guide

Related Questions

Design a high-throughput Inventory Management System

Design a low-latency Rate Limiting System

Design a fault-tolerant Payment System

Design a fault-tolerant Messaging System

Design Walmart Product Search