System Design - URL Shortener (TinyURL)

Designing a URL shortening service (like TinyURL or bit.ly) is one of the most classic system design interview problems. It tests fundamental distributed systems concepts: hash collisions, base encoding, distributed counter coordination, read-heavy caching, and redirect status codes.

1. Requirements & Scope

Functional Requirements

Generate Short URL: Given a long URL, return a unique, compact alias (e.g., https://tiny.url/abc123X).
Redirection: Accessing the short URL redirects the user to the original long URL.
Custom Alias (Optional): Allow users to specify a custom short string if available.
Expiration: URLs expire after a configurable TTL (e.g., 2 years) or can be deleted.

Non-Functional Requirements

High Availability: Redirection must never be down (99.999% availability).
Ultra-Low Latency: Redirection resolution should take under 10ms.
Read-Heavy Workload: Typical read-to-write ratio is 100:1.
Unpredictable/Non-Guessable: Short URLs should not be trivially enumerable to prevent scraping.

2. Capacity & Scale Estimations

Following the Estimations playbook:

Traffic:
- 100 million new URLs created per month (~40 writes/sec).
- 100:1 read ratio → 4,000 read requests/sec (QPS). Peak QPS ≈ 8,000 reads/sec.
Storage:
- Average URL length: 500 bytes. Metadata: 100 bytes. Total per record ≈ 600 bytes.
- 100M URLs/month × 12 months × 5 years ≈ 6 billion URLs.
- Storage required: 6× 10^9 × 600 bytes ≈ 3.6 TB over 5 years. (Fits comfortably in modern databases with modest sharding).
Cache Memory:
- 80/20 rule: 20% of URLs drive 80% of read traffic.
- Daily reads: 4,000 QPS × 86,400 sec ≈ 350 million reads/day.
- Daily active cache working set (20%): 70 million URLs × 600 bytes ≈ 42 GB RAM. (Easily fits in a small Redis cluster).

3. Short Key Generation: The Core Trade-off

A short URL key typically uses Base62 encoding ([a-zA-Z0-9], $26 + 26 + 10 = 62$ characters):

6 characters: 62⁶ ≈ 56.8 billion combinations.
7 characters: 62⁷ ≈ 3.5 trillion combinations. (A 7-character key is standard).

There are two primary approaches to generate the 7-character key:

Approach A: Hash of Long URL + Collision Resolution

Compute MD5 or SHA-256 of the long URL.
Encode the first 43 bits into 7 Base62 characters.
Collision Problem: Multiple distinct URLs can produce the same 7-character prefix. If a collision occurs, append a salt or counter and re-hash.
Drawback: Requires querying the database to check if the key already exists on every write, adding write latency.

Approach B: Distributed Unique ID + Base62 Encoding (Recommended)

Generate a globally unique, monotonically increasing 64-bit integer ID using a distributed ID strategy (see ID Generation).
Convert the integer into Base62: ID 12519320568 ⟶ Base62 "cb199Xz"
Benefits: Guaranteed uniqueness without database lookups. No collisions possible.
Addressing Enumeration: To prevent competitors from crawling URLs by incrementing IDs, pass the ID through a bit-shuffling feistel cipher or token generator before Base62 conversion.

4. High-Level Architecture

[ Client / Browser ]
        │
        ▼
[ Global Load Balancer ]
        │
        ▼
[ API Gateway / Reverse Proxy ] ───► [ Throttling & Rate Limiter ]
        │
   ┌────┴─────────────────────────────┐
   │                                  │
[ Write Path (POST /shorten) ]     [ Read Path (GET /:shortKey) ]
   │                                  │
   ▼                                  ▼
[ ID Generator ]                  [ Distributed Cache (Redis) ]
(Snowflake / Range Allocator)         │ (Cache Hit: Redirect 302/301)
   │                                  │ (Cache Miss)
   ▼                                  ▼
[ Relational / NoSQL Store ]      [ Database Read Replica ]
(Partitioned by shortKey hash)

5. Detailed Component Design

API Design

Create Short URL:

POST /api/v1/urls
Content-Type: application/json

{
  "long_url": "https://example.com/very/long/path/to/resource",
  "custom_alias": "my-promo",
  "expire_at": "2028-01-01T00:00:00Z"
}

Response: 201 Created with {"short_url": "https://tiny.url/cb199Xz"}.

Redirect URL:
```
GET /:shortKey
```
Response: 301 Moved Permanently vs. 302 Found.

[!TIP] 301 vs. 302 Redirect in Interviews:

301 Moved Permanently: The browser caches the redirect locally. Subsequent clicks never touch your service, reducing server load.

302 Found (or 307 Temporary Redirect): Every click routes through your servers first. Use 302 if you need click analytics, rate limiting, or tracking.

Data Storage & Schema

Because URLs are key-value lookups with no complex relational joins:

NoSQL KV store (DynamoDB, Cassandra, or MongoDB) or Sharded MySQL/PostgreSQL works well.
Primary index: short_key (Primary Key).
Secondary index: created_by or user_id (if multi-user management is required).

Field	Type	Description
`short_key`	`VARCHAR(7)`	Primary Key (Base62 string)
`long_url`	`VARCHAR(2048)`	Target URL
`user_id`	`BIGINT`	Creator ID
`created_at`	`TIMESTAMP`	Creation time
`expires_at`	`TIMESTAMP`	Expiration time for eviction

Caching Strategy

Read operations vastly outnumber writes. Use a multi-layer Caching model:

Cache-Aside Pattern: When resolving GET /:shortKey, inspect Redis first. On miss, read database, backfill Redis with a TTL, and return.
Eviction Policy: LRU (Least Recently Used) ensures popular links remain hot.

6. Bottlenecks & Edge Cases

Hotspotting (Thundering Herd / Celebrity Links):
- A single viral link might receive 100,000 QPS.
- Mitigate by using in-memory local caching (e.g., Guava/Go memory cache) directly on API gateway instances, or distributing replicas across Redis clusters.
Expired Link Deletion:
- Active scans on large tables degrade DB performance.
- Instead, employ lazy deletion (delete/reject upon access if expired) combined with a scheduled background batch cleaner running during off-peak hours.
Database Sharding:
- Shard by hash(short_key) % num_shards to evenly distribute read/write traffic across database instances.