Design a URL Shortening Service

Question

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

Codemia · Accepted Answer

- **Functional Requirements**:
  - Generate a unique short URL for a given long URL.
  - Redirect users from short URLs to the original long URLs.
  - Provide analytics on URL usage (clicks, geography, device type).
  - Allow users to manage and delete their short URLs.

- **Non-Functional Requirements**:
  - **Scalability**: Handle millions of requests per day with low latency (sub-second response times).
  - **Availability**: The service should be available 99.99% of the time.
  - **Durability**: Ensure that URL mappings are stored reliably and can be retrieved even after failures.
  - **Security**: Protect against URL tampering and ensure that users cannot create malicious redirects.
  - **Rate Limiting**: Prevent abuse by limiting the number of URL creations per user/IP address.

- **Assumptions**:
  - Daily active users: 1 million.
  - Average URLs shortened per user per day: 5.
  - Total URLs created per day: 5 million.
  - Each URL shortening request will take an average of 50ms.

- **Calculations**:
  - **Requests Per Second (QPS)**: 5 million URLs/day / 86400 seconds/day ≈ 58 QPS.
  - **Storage Requirements**: Assuming an average of 100 bytes per URL mapping (long URL + short URL + metadata), total storage needed: 5 million * 100 bytes = 500 MB per day. For 30 days, that’s about 15 GB. Considering growth, we should plan for 1 TB of storage.
  - **Bandwidth**: If each redirect generates an average of 1 KB response, then for 58 QPS, the bandwidth can peak at ~58 KB/s, translating to about 5 MB/minute.

```plaintext
+----------------+       +-----------------+
|   API Gateway  | <---> |   Load Balancer  |
+----------------+       +-----------------+
         |                        |
         |                        |
+----------------+       +-----------------+
|  URL Service    |       |  Analytics Service |
|  (REST API)    |       |  (Event-Driven)   |
+----------------+       +-----------------+
         |                        |
+----------------+                |            +----------------+
|   Database     | <------------ |            |   Message Queue |
|  (Cassandra)   |                |            |   (Kafka)      |
+----------------+                |            +----------------+
         |                        |
+----------------+                |
|   Cache (Redis) | <-------------+
+----------------+                |
```
- **Technology Choices**:
  - **API Gateway**: AWS API Gateway or NGINX for routing.
  - **Load Balancer**: AWS ELB or HAProxy for distributing traffic.
  - **Database**: Cassandra for horizontal scalability and high availability.
  - **Cache**: Redis for quick retrieval of popular URLs.
  - **Message Queue**: Kafka to handle analytics events asynchronously.

- **Consistency vs Availability**:
  - Chose eventual consistency for analytics data to ensure high availability and low latency for URL redirects.
  - The main URL mappings table will prioritize strong consistency using a Cassandra setup with a quorum read/write strategy.

- **Database vs Cache**:
  - Caching popular short URLs in Redis for faster access but risking stale data. Trade-off accepted to enhance performance for frequently accessed URLs.

- **Handling Failures**:
  - Implement retries and circuit breakers for the analytics service to isolate failures without affecting the URL resolution service.
  - Use replication in Cassandra to ensure data durability across multiple availability zones.

Design a URL Shortening Service

Databricks

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

Capacity Estimation

Submit Your Answer

Databricks 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