How to Design a Billion‑Scale URL Shortening System for an Interview

1. What Is a URL Shortening System?

A URL shortener converts a long URL into a compact alias that redirects users to the original address. The core operations are generation (client sends a long URL and receives a short alias) and redirection (browser follows the short URL, the service looks up the original URL and issues an HTTP 302 redirect).

2. Why Build a URL Shortener?

Usability : Short links fit character‑limited channels like social media, SMS, and QR codes.

Analytics : By logging each redirect, you can collect click counts, referrers, geographic distribution, and device types.

Feature Extension : Short links can carry expiration, password protection, or device‑specific redirects.

Link Masking : Complex query parameters can be hidden behind a short alias.

3. Interview‑Style Walkthrough

3.1 Requirement Analysis

Start by confirming functional and non‑functional needs with the interviewer. Example dialogue:

“Before designing, could you clarify the required features, performance targets, and availability expectations?”

Typical clarified requirements:

Functional : generate short link, optional custom alias, expiration, redirection, analytics.

Non‑functional : 7×24 high availability, ultra‑low latency reads, unique unpredictable codes.

Scalability : support billions of records and high read‑write disparity.

3.2 Capacity Estimation

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

Write QPS ≈ 200 req/s (5 × 10⁸ / 30 days / 86400 ≈ 200).

Read QPS ≈ 20 000 req/s (200 × 100).

Total records over 5 years: 5 × 10⁸ × 12 × 5 = 3 × 10¹¹.

Assuming 500 bytes per record → ≈ 15 TB storage.

Ingress bandwidth ≈ 100 KB/s; egress bandwidth ≈ 10 MB/s.

Cache estimation (80 % of traffic on 20 % of URLs): 2 × 10⁴ req/s × 3600 × 24 ≈ 1.7 × 10⁹ daily requests; cache 20 % → ~170 GB memory.

3.3 API Design

Define RESTful endpoints:

Create short link – POST /shorten with parameters original_url, custom_alias, expiration_date, user_id. Returns shortened_url, creation_date, expiration_date.

Redirect – GET /{shortened_url} returns HTTP 302 to original_url.

Analytics – GET /analytics/{shortened_url} with optional start_date / end_date, returns click count, unique clicks, referrers, location, device data.

URL Management – GET /user/urls (list user’s short links) and DELETE /{shortened_url} (remove a link).

3.4 Database Design

Given the scale, a NoSQL wide‑column store (e.g., DynamoDB, Table Store, Riak) is preferred over a single relational instance.

Key tables (illustrated as plain text):

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

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

analytics : AnalyticsID (PK), URLHash, ClickTimestamp, ReferringSite, Location, DeviceData.

3.5 Short‑Code Generation Algorithms

Option 1 – Hash + Base64 : Hash the long URL (e.g., MD5), encode with Base64 or Base62, then truncate to 6–8 characters. Issues include URL‑unsafe characters (+, /) and potential collisions requiring re‑hash or salting.

Option 2 – Incremental ID + Base62 (Recommended) : Use a globally unique ID generator (Snowflake or auto‑increment), convert the decimal ID to Base62 (a‑z, A‑Z, 0‑9). Benefits:

Absolute uniqueness.

Controllable length (shorter IDs early, longer later).

Pure computation, very fast.

Example: ID 10086 → Base62 2Bi.

To avoid a single point of failure, the ID service (KGS) should be deployed as a HA cluster with standby replicas and a pre‑generated key pool.

3.6 Partitioning & Replication

Two main sharding strategies:

Range‑based : partition by the first character of the short code (e.g., ‘a’‑bucket, ‘b’‑bucket). Simple but can cause hotspot skew.

Hash‑based : compute hash(short_code) % N (e.g., N = 256) to evenly distribute records. Adding consistent hashing further eases node addition/removal.

Each shard should have primary‑secondary replication for read‑write separation and failover.

3.7 Caching Strategy

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

Incoming request checks cache first.

If cache hit, return the original URL immediately.

If miss, query the database, populate the cache, then redirect.

Cache size ~170 GB (20 % of daily traffic). Use LRU eviction to keep hot URLs.

3.8 Load Balancing

Three layers need load balancers:

Client → Application servers.

Application servers → Database cluster.

Application servers → Cache cluster.

Prefer intelligent algorithms (least connections, response‑time weighted round‑robin) over simple round‑robin.

3.9 Expiration & Cleanup

Combine lazy deletion with asynchronous background cleanup:

When a request hits an expired short link, delete it on‑the‑fly and return a “link expired” page.

A low‑priority background job runs during off‑peak hours to batch‑delete long‑inactive expired links.

Re‑use reclaimed short codes by returning them to the KGS key pool.

4. Summary

The interview answer should demonstrate a systematic approach: start with clear requirement gathering, perform realistic capacity planning, design clean REST APIs, choose a storage model that scales to billions of rows, pick a collision‑free short‑code algorithm, shard data uniformly, add caching and load balancing for performance, enforce rate limiting to prevent abuse, and finally address maintenance concerns such as expiration handling. This end‑to‑end reasoning showcases both depth and breadth of backend system design skills.