Design a URL Shortener (TinyURL / Bitly)

A URL shortener converts arbitrary-length URLs into compact, human-readable aliases and redirects incoming traffic to the original destination with minimal latency.

Functional Requirements

1. URL Shortening: Given a long URL (e.g., https://en.wikipedia.org/wiki/Distributed_computing), generate an alias of 7 characters (e.g., https://tiny.url/4bY7a9Z).
2. High-Speed Redirection: When a client accesses the short alias, immediately redirect them to the original destination.
3. Custom Aliases (Vanity URLs): Allow users to optionally supply custom alphanumeric slugs (e.g., https://tiny.url/my-promo).
4. Link Expiration & TTL: Support default retention periods (e.g., 5 years) and user-configurable expiration dates.
5. Click Analytics: Asynchronously capture telemetry: timestamp, IP geolocation, user agent, referrer, and cumulative click count.

Non-Functional Requirements

• Ultra-Low Latency: Redirection lookups must complete in < 10 ms (p99) from cache and < 30 ms on persistent store cache misses.
• High Availability & Durability: 99.999\% uptime for read operations. Saved URL mappings must never be lost.
• Collision-Free Generation: ID generation must guarantee zero duplicate short URLs under concurrent multi-region writes.
• Security & Guess-Resistance: Short keys should not be trivially sequential to prevent malicious scraping of private links.

Understanding read-to-write ratios and storage footprints dictates the caching and database partitioning strategy:

Traffic Estimation

• Write Volume: 100 million new URLs created per month.

Write QPS = \frac{100,000,000}{30 × 86,400} ≈ 38.6 ≈ 40 writes/sec (Peak: 100 writes/sec)

• Read Volume: 100:1 Read-to-Write ratio \implies 10 billion redirects per month.

Read QPS = \frac{10,000,000,000}{30 × 86,400} ≈ 3,858 ≈ 4,000 reads/sec (Peak: 15,000 reads/sec)

Storage Calculations (5-Year Horizon)

• Record Size:
  • short_key: 7 bytes
  • original_url: 512 bytes average
  • user_id: 16 bytes (UUID)
  • created_at, expires_at: 16 bytes
  • Overhead & indexing: ~50 bytes
  • Total per record: ~ 600 bytes
• Total Storage:

600 bytes × 100M/mo × 12 mo/yr × 5 yr = 3.6 Terabytes (TB)

Memory & Cache Sizing (80/20 Rule)

• 20% of the daily hot URLs account for 80% of daily redirect traffic:

Daily Reads = \frac{10B}{30} ≈ 333 Million requests/day

Hot 20% Volume = 333M × 0.20 = 66.6 Million URLs

RAM Needed = 66.6M × 600 bytes ≈ 40 GB of RAM

A modest Redis Cluster easily accommodates 40 GB in RAM.

Since URL mappings are key-value lookups with no complex relational joins, either a sharded relational database (PostgreSQL/Aurora) or a distributed NoSQL document/wide-column store (DynamoDB/Cassandra/MongoDB) can be used.

Relational / Document Schema

sql
Copy
CREATE TABLE url_mappings (
    short_key VARCHAR(10) PRIMARY KEY,
    original_url TEXT NOT NULL,
    user_id UUID,
    created_at TIMESTAMP WITH TIME ZONE DEFAULT NOW(),
    expires_at TIMESTAMP WITH TIME ZONE,
    is_custom BOOLEAN DEFAULT FALSE,
    click_count BIGINT DEFAULT 0
);

CREATE INDEX idx_user_id ON url_mappings(user_id);
CREATE INDEX idx_expires_at ON url_mappings(expires_at) WHERE expires_at IS NOT NULL;

Sharding Strategy

• Partition Key: short_key hash partition using Consistent Hashing across database shards. This distributes read traffic uniformly with zero hotspotting.

Endpoints

1. Create Short URL

   • POST /api/v1/urls
   • Request:

     json
     Copy
     {
       "original_url": "https://developer.mozilla.org/en-US/docs/Web/HTTP/Status/301",
       "custom_alias": "mdn-301",
       "expires_in_days": 30
     }

   • Response (201 Created):

     json
     Copy
     {
       "short_url": "https://tiny.url/mdn-301",
       "original_url": "https://developer.mozilla.org/en-US/docs/Web/HTTP/Status/301",
       "created_at": "2026-09-27T10:00:00Z",
       "expires_at": "2026-10-27T10:00:00Z"
     }

2. Redirect to Long URL

   • GET /{short_key}
   • Headers: Location: https://developer.mozilla.org/...
   • Status Code: 301 Moved Permanently vs 302 Found / 307 Temporary Redirect

We need a 7-character string using Base62 characters ([a-z, A-Z, 0-9]).

62^7 = 3,521,614,606,208 ≈ 3.52 Trillion unique URLs

Approach 1: Cryptographic Hash + Truncate (Flawed)

• Calculate MD5(original_url) or SHA-256(original_url) and convert the first 43 bits to 7 Base62 characters.
• Problem: Hash collisions! If two distinct long URLs produce the same 7-character prefix, we must query the database to detect collision, append a salt/nonce, and re-hash. Under high write loads, this creates quadratic database overhead.

Approach 2: Range-Based Distributed Counter (The Winning Senior Architecture)

Instead of hashing strings, use a monotonically increasing integer counter converted directly to Base62 (e.g., Integer 1,000,042 \implies Base62 4bY7).

How ZooKeeper Pre-Allocates Counter Ranges:

1. A central coordinator (Apache ZooKeeper or etcd) manages global integer blocks.
2. When App Server 1 boots, it requests a token range from ZooKeeper (e.g., Range 1,000,000 - 1,999,999).
3. App Server 2 requests the next block (Range 2,000,000 - 2,999,999).
4. Each App Server increments its local counter in atomic CPU memory (AtomicLong) with zero network round trips.
5. When a server exhausts its 1M range, it fetches a fresh block from ZooKeeper.
6. Result: Guarantees zero collisions, zero database checks, and sub-millisecond generation speed.

typescript
Copy
// Base62 Conversion Algorithm
const BASE62 = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

function encodeBase62(num: bigint): string {
  let encoded = "";
  while (num > 0n) {
    const remainder = Number(num % 62n);
    encoded = BASE62[remainder] + encoded;
    num = num / 62n;
  }
  return encoded.padStart(7, "0");
}

1. Counter Predictability & Security Mitigation

If integers increment sequentially (1000000, 1000001), attackers can enumerate all valid URLs by traversing Base62 values.

• Mitigation: Use a Shuffled Base62 Lookup Alphabet or pass the integer through a lightweight Feistel cipher (Format-Preserving Encryption) before Base62 encoding to produce pseudo-random yet collision-free slugs.

2. Multi-Tier Caching

• Edge CDN (Cloudflare Workers / Fastly): Caches popular 301/302 redirects with short TTLs (e.g., 10 minutes) at Points of Presence worldwide.
• Application Cache (Redis Cluster): Uses Least Recently Used (LRU) eviction policy. A write-through or cache-aside strategy ensures popular URLs are served from RAM in < 1 ms.

3. Asynchronous Expiration Sweeper

• Passive deletion: When a requested URL is found to have expires_at < NOW(), return HTTP 404 and trigger background cleanup.
• Active cleanup: A scheduled cron/worker sweeps expired records in time-bucketed batches during low-traffic off-peak hours to reclaim database storage.