Case Study: Design a URL Shortener (TinyURL/Bitly)

Case Study: Design TinyURL (URL Shortener)

Designing a URL shortener like TinyURL or Bitly is a classic, high-impact system design interview problem. It evaluates your grasp of ID generation in distributed systems, high-speed read pathways, storage optimization, and asynchronous analytics pipelines. While simple on the surface, scaling this system to handle billions of operations requires eliminating database lookups from the hot write path.

1. Requirements & Core Constraints

Functional Requirements

• URL Shortening: The system takes a long destination URL and generates a unique, alphanumeric short alias of 7 or 8 characters.
• Redirection: When a client accesses a short link (e.g., https://tiny.io/aBc12X), the system redirects them to the original destination URL via an HTTP 301 or 302 redirect.
• Custom Aliases: Users can specify custom short codes (e.g., https://tiny.io/my-custom-doc).
• Link Expiration: Short links support custom TTL values (e.g., expire after 2 years), automatically freeing storage upon expiry.
• Click Telemetry: Real-time click tracking must capture aggregate metrics (device type, geolocation, referrer, click count) on every redirect.

Non-Functional Requirements (SLAs)

• Sub-10ms Redirection Latency: The redirect operation must execute with minimal latency to avoid slowing down user navigations.
• Highly Read-Heavy System: Target a 100:1 Read-to-Write ratio. The read path must scale to billions of monthly redirects.
• High Availability: The redirection path must achieve 99.999% (five nines) availability; link generation can target a 99.9% availability SLA.
• Zero Collision Tolerance: The short ID space must guarantee absolute uniqueness; no two distinct long URLs can map to the exact same short code.

Back-of-the-Envelope Capacity Estimates

We size our architecture based on 100 Million new URLs shortened per month and a 100:1 read-heavy ratio:

• New URLs (Writes): 100,000,000 per month $\approx$ 38.6 writes per second.
• Redirect Requests (Reads): 10,000,000,000 per month $\approx$ 3,858 reads per second.
• Average Record Size: 500 bytes (storing original URL, short code, owner UUID, timestamps).
• Target Lifetime: 5 years.

Storage Capacity Calculation:

• Total records over 5 years: $$100,000,000 \text{ URLs/month} \times 12 \text{ months/year} \times 5 \text{ years} = 6 \text{ Billion links.}$$
• Persistent storage required: $$6,000,000,000 \text{ links} \times 500 \text{ bytes/link} \approx \mathbf{3 \text{ Terabytes (TB)}} \text{ total storage.}$$ Because links are independent entities that never require recursive relational joins, 3TB of data fits comfortably within a sharded NoSQL wide-column store like Apache Cassandra.

Cache Memory Capacity Calculation (Redis):

We apply the 80/20 rule: 20% of our active links generate 80% of read traffic. We cache the active 20% of daily redirects:

• Daily redirects: $$\frac{10\text{B redirects}}{30 \text{ days}} \approx 333,333,333 \text{ redirects/day.}$$
• 20% Hot-Link caching target: $$333,333,333 \text{ links/day} \times 0.20 \approx 66,666,666 \text{ hot links cached.}$$
• Cache memory footprint: $$66,666,666 \text{ links} \times 500 \text{ bytes} \approx \mathbf{33.3 \text{ Gigabytes (GB)}} \text{ of RAM for the cache cluster.}$$

2. API Design & Core Contracts

Stateless API gateways routing to microservices handle redirection and shortening workflows.

A. Shorten URL Endpoint

POST /v1/urls
Authorization: Bearer <JWT_TOKEN>
Content-Type: application/json

{
  "long_url": "https://codesprintpro.github.io/blog/system-design-roadmap",
  "custom_alias": "roadmap-2026",
  "expire_date": "2031-01-01T00:00:00Z"
}

Response:

{
  "short_url": "https://csp.io/roadmap-2026",
  "short_code": "roadmap-2026",
  "long_url": "https://codesprintpro.github.io/blog/system-design-roadmap",
  "expires_at": "2031-01-01T00:00:00Z"
}

B. Redirect Endpoint

When a client hits the short link:

GET /aBc12X
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7)
Referer: https://twitter.com/

Response:

HTTP/1.1 302 Found
Location: https://codesprintpro.github.io/blog/system-design-roadmap
Cache-Control: private, max-age=86400

Note: We utilize HTTP 302 (Found) / Temporary Redirect instead of HTTP 301. An HTTP 301 is permanently cached by client browsers, which bypasses our server layers for subsequent clicks and ruins our ability to capture precise click analytics.

3. High-Level Design (HLD)

To handle extreme scales with sub-10ms redirection latencies, we separate the Write (Shortening) Pathway from the Read (Redirect) Pathway.

graph TD
    %% Redirection Read Pathway
    Reader((Reader Client)) -->|1. GET /aBc12X| RedirSrv[Redirect Read Service]
    RedirSrv -->|2. Check Cache| RedisCache[(Redis Cluster)]
    RedisCache -->|Cache Miss| NoSQLStore[(ScyllaDB / Cassandra Persistent Store)]
    RedirSrv -->|3. Push Click Event| TelemetryBus[Kafka Analytics Topic]
    
    %% Analytics Pipeline
    TelemetryBus --> Flink[Apache Flink Stream Processor]
    Flink --> RealtimeDB[(ClickHouse Analytics Storage)]
    
    %% Shortening Write Pathway
    Creator((Creator Client)) -->|4. POST /v1/urls| ShortenSrv[Shorten Write Service]
    ShortenSrv -->|5. Request Unique Token| KGS[Key Generation Service]
    ShortenSrv -->|6. Write Mapping| NoSQLStore
    ShortenSrv -->|7. Invalidate / Warm Cache| RedisCache
    
    %% State Coordinators
    ZK[ZooKeeper Cluster] <--->|8. Range Lock Coordination| KGS

The Key Allocation & Base62 Encoding Pipeline

To guarantee $O(1)$ writes with zero ID collisions without hitting the database, the system uses a Key Generation Service (KGS) coordinated by ZooKeeper.

sequenceDiagram
    autonumber
    participant ZK as ZooKeeper Cluster
    participant KGS as Key Gen Service Cluster
    participant WriteNode as Shorten Write Server

    Note over ZK: Manages global unique integer index
    KGS->>ZK: Request lock on range (e.g. 1M - 2M)
    ZK-->>KGS: Granted lock for index [1,000,000 to 2,000,000]
    
    Note over KGS: Holds allocated integers in memory
    WriteNode->>KGS: Get Unique ID
    KGS-->>WriteNode: Returns ID "1000293" (Extremely fast, memory only!)
    
    Note over WriteNode: Converts 1000293 to Base62
    Note over WriteNode: 1000293 -> "eB9t"
    
    WriteNode->>WriteNode: Map 'eB9t' to Long URL

4. Low-Level Design (LLD) & Data Models

Database Selection Rationale

• Persistent Storage (Apache Cassandra / ScyllaDB): URL mappings are strictly independent key-value lookups (short_code -> long_url). Cassandra handles this beautifully because it is a distributed wide-column NoSQL store. It scales linearly, handles massive writes via LSM-tree structures, and features zero single points of failure.
• Analytics Database (ClickHouse): Click logs generate billions of rows daily. A relational database will choke under this analytical volume. A column-oriented database like ClickHouse handles real-time aggregations (e.g., "Clicks per day grouped by country") with sub-second execution speeds.

Low-Level Schemas

-- Cassandra Keyspace Definition
CREATE KEYSPACE tinyurl_registry 
WITH replication = {'class': 'NetworkTopologyStrategy', 'us-east-1': 3, 'us-west-2': 3};

-- Cassandra Mappings Table sharded by short_code partition key
CREATE TABLE tinyurl_registry.url_mappings (
    short_code text PRIMARY KEY,
    long_url text,
    user_id uuid,
    created_at timestamp,
    expires_at timestamp
);

-- ClickHouse Analytics Schema for click logs
CREATE TABLE click_analytics (
    short_code String,
    click_time DateTime,
    ip_address String,
    country String,
    device_type LowCardinality(String),
    referrer String
) ENGINE = MergeTree()
ORDER BY (short_code, click_time);

LLD Implementation: Base62 Converter Engine

Base62 represents numbers using [a-z, A-Z, 0-9] character maps (representing 62 possibilities).

A 7-character string in Base62 can represent: $$62^7 \approx \mathbf{3.5 \text{ Trillion unique short codes.}}$$ This is more than enough to handle our 6 Billion links over 5 years.

Compilable Java Base62 Converter Code:

public class Base62Converter {
    private static final String BASE62_CHARACTERS = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    private static final int BASE = 62;

    /**
     * Encodes a unique 64-bit integer index into a Base62 alphanumeric string.
     */
    public static String encode(long number) {
        StringBuilder sb = new StringBuilder();
        while (number > 0) {
            int remainder = (int) (number % BASE);
            sb.append(BASE62_CHARACTERS.charAt(remainder));
            number /= BASE;
        }
        // Reverse string because calculations extract remainders from lowest bit up
        return sb.reverse().toString();
    }

    /**
     * Decodes a Base62 alphanumeric string back into a unique 64-bit integer.
     */
    public static long decode(String base62Str) {
        long result = 0;
        long power = 1;
        for (int i = base62Str.length() - 1; i >= 0; i--) {
            int digit = BASE62_CHARACTERS.indexOf(base62Str.charAt(i));
            if (digit == -1) {
                throw new IllegalArgumentException("Invalid Base62 string character: " + base62Str.charAt(i));
            }
            result += digit * power;
            power *= BASE;
        }
        return result;
    }
}

5. Scaling Challenges & Bottlenecks

A. ID Collisions in Distributed Systems

A typical naive approach generates a short ID by applying MD5 or SHA-256 hashing to the long URL and truncating the output to 7 characters.

• The Problem: Truncating hashes leads to Hash Collisions (distinct long URLs mapping to identical 7-character hashes). To prevent this, the server must run a SELECT query against the database before every write. Under heavy traffic, checking for collisions adds database round-trip latencies that slow down shorten requests.
• The Solution: Avoid hashing raw URLs entirely. The Key Generation Service (KGS) handles ID generation using auto-incrementing integers assigned to different workers in isolated ranges. Each worker node grabs a range of 1 Million IDs (e.g., Worker 1 gets 1,000,000 to 2,000,000, Worker 2 gets 2,000,001 to 3,000,000) coordinated by ZooKeeper range locks. The KGS workers increment these integers in memory and encode them to Base62. Collision checking is completely bypassed because integers are mathematically guaranteed to be unique.

B. Custom Aliases Collision Handling

If a user requests a custom alias like https://tiny.io/google, this code does not come from the KGS incrementing integer loop.

• Solution: We divide the short ID space:
  • Base62 auto-generated keys start with a specific format or have lengths capped at 7 characters.
  • Custom aliases bypass KGS. The write service attempts to insert the custom alias directly into Cassandra using the INSERT ... IF NOT EXISTS lightweight transaction. If Cassandra rejects the insert, we notify the user that the custom alias is already occupied.

6. Real-World Trade-offs

A. HTTP 301 (Permanent) vs. HTTP 302 (Temporary) Redirection

• HTTP 301 Redirection:
  • Pros: Browser caches the mapping permanently. Subsequent clicks are handled entirely on the client side, drastically reducing read QPS on our backend.
  • Cons: Telemetry is lost. Because the browser never contacts our redirect servers again, we cannot track click counts, geographical shifts, or referrers for cached users.
• HTTP 302 Redirection:
  • Pros: Client browser always contacts our servers, ensuring 100% accurate click analytics and real-time link de-activation capabilities.
  • Cons: Substantially higher read traffic hitting our servers.
• Our Decision: We select HTTP 302 (Temporary) redirects to preserve the business intelligence metrics of our clients, using a massive horizontal Redis cache layer to absorb the read QPS.

7. Failure Scenarios & Fault Tolerance

A. KGS Worker Crash & Range Loss

If a KGS worker node crashes mid-operation, the integers it held in memory (but had not yet fully dispensed) are lost.

• Resilience: Standby KGS nodes detect the crash via ZooKeeper heartbeat loss. The standby node claims a fresh new range from ZooKeeper. The un-allocated keys from the crashed node are abandoned, leaving small gaps in our integer index sequence. This is a highly optimal trade-off; losing a few thousand numbers is trivial compared to the operational cost of managing persistent range synchronization states.

B. Redirect Cache Storm (Thundering Herd on Redis Crash)

If the Redis caching cluster crashes, all 3,858 read QPS will hammer the persistent Cassandra DB cluster.

• Mitigation: We implement a Consistent Hashing Layer for Redis cache nodes. Replicas are maintained for each caching shard. If a master cache node goes offline, the client libraries failover to the read replica automatically, preserving the hot hit-ratio and shielding the underlying storage engines from collapse.

8. Staff Engineer Perspective (Operational Deep Dive)

9. Candidate Verbal Script (Mock Interview Guide)

Below is a first-person verbal walk-through displaying elite technical mastery:

Candidate: "To design TinyURL at a scale of 10 Billion monthly redirects, the primary bottleneck to eliminate is collision checking on the hot write path. A naive approach of hashing the long URL and check-inserting in the database creates massive I/O loops that slow down link creation. To solve this, my primary architectural decision is implementing a Key Generation Service (KGS) coordinated by a ZooKeeper cluster.

The KGS workers will acquire locks from ZooKeeper on isolated integer ranges—for example, Node A locks indices 1 to 2 Million, while Node B locks 2 to 4 Million. These nodes increment these unique numbers locally in memory. When the Shorten Write Service requests a token, KGS dispenses the integer from RAM in under a millisecond. The Write Service then encodes this integer into Base62 alphanumeric codes like eB9t. Because integers are mathematically distinct, we guarantee zero ID collisions without running any database checks.

To handle the 100:1 read-heavy redirect traffic, I will deploy a Redis caching layer using a consistent hashing topology. When a user requests a redirect, the Redirect Service attempts to retrieve the long URL from Redis. On cache misses, it fetches the record from Apache Cassandra—our NoSQL persistent store sharded by the short_code partition key. To record click telemetry without slowing down client redirects, the Redirect Service returns an HTTP 302 temporary redirect, and immediately publishes a tracking payload to a Kafka topic. Asynchronous Apache Flink stream consumers then pull from Kafka and batch writes into ClickHouse, enabling high-performance analytics tracking with zero impact on user redirection times."

Read Next

• Case Study: Designing YouTube (Video Streaming at Global Scale)
• Case Study: Designing Ticketmaster (High-Concurrency Booking)