Design a URL Shortener

Question

Design a URL shortening service like bit.ly. Cover hash generation strategies, database design for billions of URLs, redirect latency optimization, analytics tracking, and handling collisions.

Codemia · Accepted Answer

### Functional Requirements:
1. **URL Shortening**: Generate a short URL from a long URL.
2. **Redirecting**: Users should be redirected to the original URL when accessing the short URL.
3. **Analytics Tracking**: Track the number of clicks, referrer information, and geographic data.
4. **Custom Short URLs**: Allow users to choose custom short URLs if available.
5. **Link Expiry**: Provide an option for users to set an expiry time for their short links.

### Non-Functional Requirements:
1. **Scalability**: The system should handle billions of URLs and millions of redirects per day.
2. **Availability**: Ensure 99.99% uptime.
3. **Latency**: Redirects should occur in less than 100ms.
4. **Data Consistency**: Ensure that analytics data is consistent across all read/write operations.
5. **Security**: Protect against malicious URLs and ensure data privacy.

Assuming the service is designed for Meta, let's estimate the scale:
- **Daily New URLs**: Assume 10 million new URLs created per day.
- **Total URLs**: In one year, this would lead to approximately 3.65 billion URLs.
- **Daily Redirects**: If each URL is clicked on average 100 times a day, this results in 1 trillion (1,000,000,000,000) redirects per day.
- **Storage Needs**: Assuming each URL record is 200 bytes (including metadata), storing 3.65 billion URLs would require about 730 GB of storage, not accounting for replication and backups.

### Component Diagram:
- **Client**: Web and mobile applications.
- **Load Balancer**: Distributes incoming requests to multiple web servers.
- **Web Servers**: Handle user requests for shortening URLs and redirecting.
- **Application Logic**: Implements URL shortening, redirection, and analytics.
- **Database**: A distributed NoSQL database (e.g., Cassandra) for storing URL mappings and analytics data.
- **Cache**: Redis for caching frequently accessed URLs to reduce redirect latency.
- **Analytics Service**: A separate microservice for processing and storing analytics data.

### Technology Choices:
- **Load Balancer**: Nginx
- **Web Server**: Node.js
- **Database**: Cassandra for scalability and availability
- **Cache**: Redis for fast access
- **Analytics**: Kafka for real-time analytics processing

### URL Mapping Table:
| Column Name     | Data Type    | Description                                |
|------------------|--------------|--------------------------------------------|
| id               | UUID         | Unique identifier for the record.         |
| short_url        | VARCHAR(10)  | The generated short URL.                  |
| long_url         | TEXT         | The original long URL.                     |
| created_at       | TIMESTAMP    | When the URL was created.                  |
| expiry_time      | TIMESTAMP    | Expiration time for the short URL.        |
| click_count      | INT          | Number of times the short URL has been clicked. |
| created_by       | VARCHAR(255) | User ID of who created the short URL.     |

### Analytics Table:
| Column Name      | Data Type    | Description                                |
|------------------|--------------|--------------------------------------------|
| id               | UUID         | Unique identifier for the record.         |
| short_url        | VARCHAR(10)  | The short URL being tracked.               |
| click_time       | TIMESTAMP    | When the click occurred.                   |
| referrer         | VARCHAR(255) | URL of the page where the click originated.|
| user_agent       | VARCHAR(512) | User agent string of the client.          |

1. **Short URL Generation**: Using a base-62 encoding for the URL hash generation can lead to collisions. To handle this, we can implement a collision resolution strategy (e.g., appending a random character) but at the cost of increased complexity.
2. **Consistency vs. Availability**: In a distributed database like Cassandra, we may choose to prioritize availability over strong consistency, which means some analytic data may be stale temporarily but the system remains operational.
3. **Caching**: Utilizing Redis for caching can significantly reduce redirect latency, but it adds complexity in cache invalidation and potential consistency issues with the main database.
4. **Custom Short URLs**: Allowing users to create custom URLs increases user satisfaction but requires additional checks for uniqueness, impacting performance under heavy load.

Design a URL Shortener

Meta

How to Approach This

Sharpen Your Skills on Codemia

Sample Answer

Requirements

Functional Requirements:

Capacity Estimation

Submit Your Answer

Meta 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