System Design: Building a Scalable URL Shortener from Requirements to Base62 Keys

What Is a URL Shortener?

A URL shortener converts a long URL into a short alias. When a user accesses the short link, the service redirects to the original URL. The core flow involves four steps: (1) the application sends the long URL to the shortener service; (2) the service generates a unique short code and returns it; (3) the user clicks the short link; (4) the service looks up the original URL and returns an HTTP 302 redirect.

Why Do We Need a URL Shortener?

Aesthetics and convenience: Short links fit character-limited channels (SMS, social media, QR codes) and are easier to share, print, and read aloud.

Tracking and analytics: The redirect layer can capture click counts, referrers, geographic distribution, and device information for marketing and operational decisions.

Feature extension: The proxy layer enables link expiration, password protection, and device-specific routing (mobile vs. desktop).

Hiding original URLs: Complex parameterized URLs can be masked behind a clean short link.

Interview Guide: Step-by-Step Design

Requirements Analysis

Start by clarifying functional and non-functional requirements with the interviewer.

Functional: generate short link, support custom alias, redirect to original URL, link expiration.

Non-functional: high availability (7x24), low-latency redirect, unique and unpredictable short codes.

Extensibility: analytics API, open REST API for integration.

Capacity Estimation

Assumptions: 500 million new URLs per month, read/write ratio 100:1, store data for 5 years, average record size 500 bytes.

Write QPS: 500M / (30*24*3600) ≈ 200/s

Read QPS: 200 * 100 = 20,000/s

Total records (5 years): 500M * 12 * 5 = 30 billion

Storage: 30B * 500 bytes ≈ 15 TB

Ingress bandwidth: 200 * 500B ≈ 100 KB/s

Egress bandwidth: 20K * 500B ≈ 10 MB/s

Cache memory (20% of daily requests): 17B daily requests * 20% * 500B ≈ 170 GB

These numbers highlight two core challenges: high-concurrency reads and massive data storage.

API Design

Define RESTful endpoints before macro architecture:

Create short link: POST /shorten with parameters original_url (required), custom_alias (optional), expiration_date (optional), user_id (optional). Returns shortened_url, creation_date, expiration_date.

Redirect: GET /{shortened_url} → HTTP 302 with Location header.

Analytics: GET /analytics/{shortened_url} with optional start_date, end_date. Returns click_count, unique_clicks, referring_sites, location_data, device_data.

User URL management: GET /user/urls with pagination.

Delete short link: DELETE /{shortened_url} with user_id.

Abuse prevention: rate-limit by IP or user ID (e.g., 10 requests/minute for anonymous users).

Database Design

Given 30B records and simple relationships, a NoSQL wide-column store (DynamoDB, Table Store, Riak) is preferred over sharded relational databases for horizontal scalability.

URL mapping table (url_mapping): Partition key Hash (short code), attributes OriginalURL, CreationDate, ExpirationDate, UserID.

User table (users): Partition key UserID, plus profile fields.

Analytics table (analytics): Partition key AnalyticsID, attributes URLHash, ClickTimestamp, ReferringSite, Location.

Core Algorithm: Generating Short Codes

Option 1: Hash Encoding

Hash the long URL (e.g., MD5 → 128-bit), Base64-encode, take first 6-8 characters. Base64^6 ≈ 68.7B combinations; Base64^8 ≈ 281T. Issues: standard Base64 uses '+' and '/' which are URL-reserved and require extra encoding; collisions possible when truncating; same URL yields same code (undesirable for per-user tracking); URL encoding variations produce different hashes. Mitigations: use URL-safe Base64 (replace '+' with '-', '/' with '_'), append unique salt or sequence number, but adds complexity and performance overhead.

Option 2: Auto-Increment ID with Base62 Conversion (Recommended)

Use a globally unique ID generator (Snowflake or database auto-increment). Convert the decimal ID to base62 (a-z, A-Z, 0-9). Example: 10086 (decimal) = "2Bi" (base62). Advantages: absolute uniqueness (no collisions), length grows gradually (efficient code-space usage), pure computation (fast). The ID generator becomes a Key Generation Service (KGS). To avoid single point of failure, run KGS as a highly available cluster with standby replicas. KGS pre-generates keys into a dedicated Key-DB with two tables: unused keys and used keys. When allocating, move key from unused to used under a lock. KGS can cache a batch of keys in memory for low-latency serving. Key-DB size estimate: 62^6 ≈ 56.8B combinations; 6 bytes per key ≈ 340 GB.

Data Partitioning and Replication

15 TB requires sharding. Two strategies:

Range-based: Partition by first character of short code. Simple but causes skew (e.g., 'E' may get disproportionate load).

Hash-based (preferred): Compute hash(short_code) % N for even distribution. Use consistent hashing to minimize data movement when adding/removing shards. Each shard runs master-replica for high availability and read/write separation.

Caching Strategy

Deploy a distributed cache (Redis/Memcached) between application servers and database.

Content: short code → original URL mapping.

Workflow: On request, check cache. Hit → return redirect. Miss → query DB, write to cache, then return.

Sizing: 170 GB for 20% of daily hot traffic. Modern servers with 256 GB RAM can hold entire cache on one node, or use a cluster of smaller nodes.

Eviction: LRU (Least Recently Used) fits the hot/cold access pattern.

Consistency: On cache miss, after DB fetch, write to all cache replicas to maintain consistency.

Load Balancing

Three load balancer tiers: client → app servers, app servers → database cluster, app servers → cache cluster. Start with round-robin; upgrade to least-connections or weighted round-robin based on response time for dynamic load awareness. Health checks enable automatic failover.

Expired Link Cleanup

Avoid expensive full-table scans. Use a combined lazy + async approach:

Default TTL: e.g., 2 years.

Lazy deletion: On access, check expiration; if expired, delete record and return 404/expired page.

Async cleanup: Low-priority background job runs during off-peak (e.g., early morning) to batch-delete stale "zombie" links.

Key reuse: Recycle expired short codes back into KGS unused pool.

Summary

From a simple requirement, we progressed through requirements clarification, capacity estimation, API definition, NoSQL data modeling, core key-generation algorithm (auto-increment ID + base62), hash-based sharding with consistent hashing, Redis caching with LRU, multi-tier load balancing, and lazy expiration cleanup. This systematic, trade-off-driven thinking — not just the final diagram — is what interviewers evaluate.