TinyURL (URL Shortener)

Metadata

Building Blocks Used

This case study builds upon the following foundational concepts:

• Hashing & Hash Functions (Base62 Encoding)
• Database Sharding (Scaling the data layer)
• Caching Strategies (Cache-Aside pattern)

1. System Requirements

Before designing any system, we must establish the boundaries and constraints.

Functional Requirements

• Given a long URL, the system returns a much shorter, unique URL.
• When users click the short URL, they are immediately redirected to the original long URL.
• Short URLs will expire after a standard default timespan (e.g., 5 years) but users can specify custom expiration times.
• Users can request a Custom Alias (e.g., tiny.url/my-custom-promo).
• (Out of Scope for MVP): Analytics tracking, user accounts.

Non-Functional Requirements

• High Availability: If the service goes down, all the shortened links on the internet break.
• Low Latency: URL redirection should happen with minimal delay.
• High Read-to-Write Ratio: URL shorteners are incredibly read-heavy. (Assumption: 100:1 read-to-write ratio).

2. Back-of-the-Envelope Estimation

Let's calculate our traffic and storage requirements assuming the service operates at a massive scale.

• Write Volume: 100 million new URLs generated per month.
• Read Volume: 100:1 ratio = 10 Billion reads (redirections) per month.

QPS (Queries Per Second)

• Writes: 100,000,000 / (30 × 24 × 3600) ≈ 40 Writes / second.
• Reads: 10,000,000,000 / (30 × 24 × 3600) ≈ 4,000 Reads / second.
• Takeaway: The QPS is easily manageable by a single web server, but we will use a Load Balancer and multiple servers for High Availability.

Storage Estimation (Over 5 Years)

• Total URLs: 100 Million/month × 12 months × 5 years = 6 Billion URLs.
• Let's assume each URL record requires 500 bytes of storage.
• Total Storage: 6 Billion × 500 Bytes = 3 Terabytes (TB).
• Takeaway: 3TB easily fits on a single modern hard drive. However, to handle 4,000 read QPS efficiently, we will likely need Database Replication or Sharding.

3. High-Level Architecture

%%{init: {'theme': 'base', 'themeVariables': { 'primaryColor': '#ffcc00', 'edgeLabelBackground':'#ffffff'}}}%%
graph TD
    classDef client fill:#f9f9f9,stroke:#333,stroke-width:2px;
    classDef lb fill:#d4edda,stroke:#28a745,stroke-width:2px;
    classDef app fill:#cce5ff,stroke:#007bff,stroke-width:2px;
    classDef db fill:#f8d7da,stroke:#dc3545,stroke-width:2px;
    classDef cache fill:#ffeeba,stroke:#ffc107,stroke-width:2px;

    C((User)):::client -->|POST /api/v1/data/shorten| LB[Load Balancer]:::lb
    C -->|GET /xyz123| LB
    
    LB --> App1[App Server]:::app
    LB --> App2[App Server]:::app
    
    App1 <-->|1. Check Cache| Cache[(Redis Cache)]:::cache
    App1 <-->|2. Read/Write DB| DB[(Relational DB<br/>PostgreSQL)]:::db
    
    App2 <--> Cache
    App2 <--> DB

4. Deep Dive: API Design

We need two primary REST API endpoints. See REST API Design for best practices.

1. Shorten URL (POST)

Endpoint: POST /api/v1/data/shorten Request Body:

{
  "original_url": "https://www.verylongdomain.com/article/12345"
}

Response (201 Created):

{
  "short_url": "https://tiny.url/Ab39Zf"
}

2. Redirect (GET)

Endpoint: GET /{short_alias} Behavior: The server receives the request, looks up the original URL, and returns an HTTP 301 (Moved Permanently) or HTTP 302 (Found) redirect.

[!TIP] 301 vs 302 Redirect

• 301 (Moved Permanently): The browser caches the redirect. Subsequent clicks don't hit our server. Reduces server load, but we lose analytics tracking.
• 302 (Found / Temporary): The browser hits our server every single time. Increases server load, but allows us to track click analytics perfectly.

5. Deep Dive: The Hashing Algorithm

How do we convert a long URL into Ab39Zf? We need a Hash Function.

Approach 1: Standard Hash (MD5 / SHA-1)

If we hash the long URL using MD5, we get a 128-bit string (e.g., 5d41402abc4b2a76b9719d911017c592). This is way too long for a "tiny" URL. If we just take the first 7 characters (5d41402), we risk Hash Collisions.

Approach 2: Base62 Encoding (The Standard)

Base62 uses 62 characters: [a-z, A-Z, 0-9]. If our short URL has exactly 7 characters, how many unique URLs can we support? 62^7 = 3.5 Trillion unique URLs. (More than enough for our 6 Billion requirement).

To do this, we don't hash the long URL. Instead, we generate a unique ID for every new request, and then convert that base-10 ID integer into a Base62 string.

The Distributed ID Generator Bottleneck If we use a traditional relational database AUTO_INCREMENT primary key, that single database becomes a massive write bottleneck and a single point of failure. Instead, we use a distributed UUID Generator (like Snowflake). Snowflake runs independently on multiple worker nodes without coordination, guaranteeing strict uniqueness and eliminating the database bottleneck.

Example:

1. Snowflake Node 3 generates ID: 2009215674938
2. Convert 2009215674938 (Base-10) -> zn9edcu (Base-62).
3. The short URL is https://tiny.url/zn9edcu.

Approach 3: Custom Aliases

If a user requests a custom alias (e.g., tiny.url/my-promo), we can no longer rely on a reverse mapping from a numeric Snowflake ID. The system must accept the string directly.

1. App Server checks the Database: "Does my-promo exist?"
2. If yes, return 400 Bad Request (Alias Taken).
3. If no, write my-promo directly to the short_url column. This requires a UNIQUE constraint on the short_url column to prevent race conditions when two users request the same alias simultaneously.

6. Deep Dive: Database Design

Since we are storing billions of rows, but the schema is incredibly simple, what database do we use? SQL vs NoSQL?

Because we don't need complex JOINs and we require massive read scalability, a NoSQL database like Cassandra or DynamoDB is an excellent choice. However, a traditional RDBMS like PostgreSQL can easily handle 3TB of data and 4,000 QPS with modern hardware. Let's use PostgreSQL for simplicity.

Table: urls

Data Expiration and Cleanup

Since URLs expire after 5 years (or a custom time), how do we clean up billions of dead links to reclaim storage?

1. Lazy Deletion: When a user queries a URL, we check expires_at. If it has expired, we delete it on the spot and return a 404.
2. Background Cron Job: Lazy deletion alone means unvisited dead links stay on disk forever. A dedicated Cleanup Service runs in the background during off-peak hours, slowly scanning the database and purging expired rows.

Database Scaling

If we outgrow a single Postgres server, we can implement Database Replication. We set up 1 Master for writes, and 5 Read Replicas for reads, solving our 100:1 read-heavy workload.

If storage exceeds 10TB, we use Database Sharding. We shard by the short_url string.

7. Deep Dive: Caching

Even with Read Replicas, querying the database for every single click is slow and expensive. A URL shortener's traffic is highly skewed: 20% of the links generate 80% of the traffic (Pareto Principle). Viral links might be clicked 100,000 times a second!

We introduce a Redis cache using a Cache-Aside Strategy with an LRU Eviction Policy.

The Read Flow:

1. User requests GET /zn9edcu
2. App Server checks Redis for key zn9edcu.
3. If Cache Hit: Return long URL instantly.
4. If Cache Miss: Query PostgreSQL.
5. Save the result in Redis (with a TTL of 24 hours).
6. Return to user.

8. Summary of Building Blocks Used

This case study brings together the following fundamental components:

Website Metadata