Design a low-latency URL Shortening System

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**:
  - Generate short URLs from long URLs.
  - Redirect users from short URLs to the corresponding long URLs with minimal latency.
  - Provide analytics on URL usage (clicks, geographic distribution, etc.).
  - Allow users to customize the short URL.
  - Support bulk URL shortening.

- **Non-Functional Requirements**:
  - **Low Latency**: Redirects should complete within 50 ms.
  - **Scalability**: Handle 1 million requests per minute at peak.
  - **High Availability**: 99.99% uptime for URL shortening and redirection services.
  - **Data Durability**: Ensure URLs are not lost and are retrievable even in case of failures.

To estimate capacity for this system, we can start with the following calculations:

- **Daily Requests**: Assuming peak of 1 million requests/minute:
  - 1,000,000 requests/minute * 60 minutes/hour * 24 hours/day = 1.44 billion requests/day.

- **Data Storage**: Each URL mapping might require:
  - Long URL: 200 characters (approx. 200 bytes)
  - Short URL: 10 characters (approx. 10 bytes)
  - Metadata (timestamp, analytics): 100 bytes
  - Total per mapping: 310 bytes
  - Total storage for 1 billion URLs = 310 bytes * 1,440,000,000 = 447 GB/day.

- **Database Requirements**: We need to support rapid reads and writes, so a distributed database with horizontal scaling is necessary.

To support our functional and non-functional requirements:

- **Components**:
  - **API Gateway**: Handles incoming requests, routes them to appropriate services.
  - **URL Shortening Service**: Responsible for generating short URLs, validating long URLs, and saving mappings.
  - **Redirection Service**: Quickly retrieves the long URL from the short URL and performs the redirect.
  - **Analytics Service**: Collects data on URL usage and generates reports.
  - **Database**: A distributed NoSQL database (like DynamoDB or Cassandra) to store URL mappings for high availability and low latency.

- **Technology Choices**:
  - **API Gateway**: AWS API Gateway.
  - **Shortening and Redirection Services**: Node.js or Go for lightweight, high-performance services.
  - **Database**: Amazon DynamoDB for scalability and fast access.

The schema design for storing URL mappings would include:

- **URL Mapping Table**:
  - **short_url** (Primary Key, STRING): Unique identifier for the short URL.
  - **long_url** (STRING): The original long URL.
  - **creation_time** (TIMESTAMP): Time when the URL was created.
  - **click_count** (INTEGER): Number of times the short URL has been accessed.
  - **user_id** (STRING, optional): Identifier for the user who created the URL.

- **Access Patterns**:
  - Quick retrieval of long URL by short URL for redirection.
  - Frequent updates to click counts for analytics.

In designing this URL shortening system, several trade-offs need consideration:

- **Consistency vs. Availability**: We can choose eventual consistency for the analytics data (click counts) to ensure availability during peak loads, allowing users to access URLs even if analytics data is slightly stale.

- **Latency vs. Durability**: To ensure low-latency redirects, we may opt for in-memory caching (using Redis) for frequently accessed URLs, trading off some durability for speed.

- **Scalability vs. Complexity**: Using a distributed NoSQL database simplifies horizontal scaling but may introduce complexity in managing data consistency and transactions. We need to carefully design our caching strategy to mitigate this.

Design a low-latency URL Shortening System

CrowdStrike

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

CrowdStrike 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