How to Ace a Billion‑Scale URL Shortening System Design Interview

1. What Is a Short‑Link System?

A short‑link system converts a long URL into a compact short URL; when a user accesses the short URL, the system redirects them to the original long address.

The core operations are "generate" and "redirect".

The interaction flow:

Generate : The application sends the original long URL to the short‑link service.

Return : The service creates a unique short URL and returns it.

Access : The user clicks the short URL.

Redirect : The service looks up the original URL and issues an HTTP 302 redirect.

2. Why Do We Need a URL Shortener?

Short links are valuable for several reasons:

Readability & Convenience : Ideal for platforms with character limits (social media, SMS, QR codes) and easier to share.

Data Tracking & Analysis : Enables precise click‑through statistics, source, geography, and device data.

Feature Extension : Allows expiration control, password protection, device‑specific redirects, etc.

Hide Original URL : Masks complex or parameter‑heavy URLs in promotional contexts.

3. Interview Practical Guide

3.1 Requirement Analysis

Interviewer: “Design a high‑performance short‑link system.”

“Before proposing a solution, I’d like to clarify the exact requirements and goals—what core features are needed and what performance and availability expectations you have?”

Typical clarified requirements:

Functional Requirements

Generate short link from a long URL.

Optional custom alias.

Redirect short link to the original URL.

Expiration mechanism.

Non‑Functional Requirements

High availability (24/7).

Low latency redirects.

Uniqueness and unpredictability of short codes.

Extensibility

Analytics for click counts, demographics, etc.

Open RESTful API for integration.

3.2 Capacity Estimation

Assume 5 × 10⁸ new URLs per month with a read/write ratio of 100:1.

Write QPS :

5e8 / (30 days × 24 h × 3600 s) ≈ 200 req/s

Read QPS : 200 × 100 = 20 000 req/s Storage : 5 years retention, 500 bytes per record → 5e8 × 12 × 5 = 3 × 10¹⁰ records → ≈ 15 TB.

Bandwidth : Write ≈ 100 KB/s, Read ≈ 10 MB/s.

Cache : 20 % of daily traffic (≈ 1.7 billion requests) → 170 GB memory.

3.3 System API Design

3.3.1 Create Short Link API

Request : GET /{shortened_url} Parameters : original_url (required) custom_alias (optional) expiration_date (optional) user_id (optional)

Response :

shortened_url

creation_date

expiration_date

(if provided)

3.3.2 Redirect API

Request : GET /{shortened_url} Parameter : shortened_url (required)

Response : HTTP 302 redirect to original_url.

3.3.3 Analytics API

Request : GET /analytics/{shortened_url} Parameters : shortened_url, optional start_date, end_date.

Response includes click_count, unique_clicks, referring_sites, location_data, device_data.

3.3.4 URL Management API

Request : GET /user/urls Parameters : user_id (required), page, page_size (optional).

Response : List of urls with metadata.

3.3.5 Delete Short Link API

Request : DELETE /{shortened_url} Parameters : shortened_url (required), user_id (required).

Response : status message.

Interviewer: “What if a malicious user exhausts all short codes?” “We need API rate limiting per IP or user—e.g., max 10 creations per minute for anonymous users.”

3.4 Database Design

Using a NoSQL wide‑column model for scalability:

url_mapping : Hash (PK), OriginalURL, CreationDate, ExpirationDate, UserID.

users : UserID (PK), Name, Email, PasswordHash, …

analytics : AnalyticsID (PK), URLHash, ClickTimestamp, ReferringSite, Location, …

3.5 Core Algorithm: Short Code Generation

3.5.1 Hash Encoding (Option 1)

Hash the long URL (e.g., MD5 → 128‑bit) and encode with Base64 or Base62. URL‑safe Base64 replaces ‘+’ with ‘‑’ and ‘/’ with ‘_’. Length choices (6, 8, 10 characters) affect collision probability: 6‑char Base64 gives ≈ 6.9 × 10⁸ combos.

“Standard Base64 includes ‘+’ and ‘/’, which must be URL‑encoded, so we use a URL‑friendly variant.”

3.5.2 Auto‑Increment ID + Base62 (Recommended)

Use a global unique ID generator (Snowflake or DB auto‑increment). Convert the decimal ID to Base62 (a‑z, A‑Z, 0‑9) to obtain a short code. Advantages: guaranteed uniqueness, controllable length, pure computational conversion.

Example: ID 10086 → Base62 2Bi.

Absolute uniqueness.

Length grows only as needed.

High performance.

“The ID service must be highly available; we can run it as a clustered service with standby replicas.”

3.6 Data Partitioning & Replication

Two main strategies:

Range Partition : Split by short‑code prefix (e.g., ‘a’, ‘b’). Simple but can cause hotspot skew.

Hash Partition : Compute hash(short_code) % N to distribute evenly across N shards.

Consistent hashing further eases node addition/removal. Each shard should have primary‑secondary replication for read‑write separation and failover.

3.7 Cache Strategy

Cache mapping short_code → original_url in a distributed cache (Redis/Memcached).

Client request hits cache first.

If cache hit → redirect immediately.

If miss → query DB, populate cache, then redirect.

Cache size estimate: 20 % of daily traffic ≈ 170 GB; a single 256 GB server can hold it, or a small cache cluster.

Eviction policy: LRU, because hot links are accessed frequently while cold links can be evicted.

3.8 Load Balancing

Three layers need load balancers:

Client → Application servers.

Application servers → Database cluster.

Application servers → Cache cluster.

Simple round‑robin works initially, but smarter algorithms (least connections, response‑time weighted) provide better stability under uneven load.

3.9 Expired Link Cleanup

Combine lazy deletion with asynchronous background cleanup:

Set a default TTL (e.g., two years).

On access, if the link is expired, delete it and return a “link expired” page.

Background job runs during low‑traffic periods to batch‑delete long‑unaccessed expired links.

Reclaim released short codes back to the key‑generation pool.

4. Summary

The interview answer demonstrates a systematic approach: start with requirement analysis, perform capacity estimation, define clear RESTful APIs, design a sharded NoSQL schema, choose a robust short‑code generation method, add caching, partitioning, replication, load balancing, and finally handle expiration and key reuse. This showcases both deep technical knowledge and architectural thinking required for a senior backend engineer.