First design walkthrough (URL shortener) in HLD - System Design Exercise

Design: URL Shortener

Design covers URL shortening, redirection, and basic analytics. User authentication, advanced analytics, and monetization are out of scope.

Functional Requirements

FR1: Generate a short alias for a given long URL

FR2: Redirect users from the short URL to the original long URL

FR3: Handle at least 100 million URLs

FR4: Support 10,000 requests per second for redirection

FR5: Ensure short URLs are unique and not easily guessable

FR6: Provide basic analytics: number of clicks per short URL

FR7: Allow users to customize the short URL alias (optional)

Non-Functional Requirements

NFR1: Latency for redirection should be under 100ms (p99)

NFR2: Availability target of 99.9% uptime

NFR3: Storage must be scalable to handle growth

NFR4: System should prevent collisions in short URL generation

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

❓ Question 6

Key Components

API Gateway or Load Balancer

URL Shortening Service

Database for storing URL mappings

Cache layer for fast redirection

Analytics Service

Unique ID generator or hashing mechanism

Design Patterns

Hashing and Base62 encoding for short URL generation

Cache-Aside pattern for caching URL mappings

Database sharding for scalability

Rate limiting to prevent abuse

Asynchronous processing for analytics

Reference Architecture

API Gateway / Load Balancer

↓

URL Shortening Service

↓

Cache

↓

Analytics Service

Components

API Gateway / Load Balancer

Nginx or AWS ALB

Distribute incoming requests and provide a single entry point

URL Shortening Service

Stateless microservice (e.g., Node.js, Python Flask)

Generate short URLs, handle redirection, and validate requests

Database

Relational DB like PostgreSQL or NoSQL like Cassandra

Store mappings between short URLs and original URLs

Cache

Redis or Memcached

Store frequently accessed URL mappings for fast redirection

Analytics Service

Background worker with message queue (e.g., Kafka, RabbitMQ)

Collect and process click data asynchronously

Unique ID Generator

Base62 encoding of auto-increment ID or hash function

Create unique, short, and collision-resistant aliases

Request Flow

1. User sends a request to shorten a URL via API Gateway.

2. URL Shortening Service validates the URL and checks for custom alias if provided.

3. If no custom alias, service generates a unique ID and encodes it to create short URL.

4. Mapping of short URL to original URL is stored in the database.

5. Short URL is returned to the user.

6. When a user accesses the short URL, request goes to API Gateway then URL Shortening Service.

7. Service checks cache for the original URL; if not found, queries the database.

8. Redirects user to the original URL.

9. Click event is sent asynchronously to Analytics Service for processing.

Database Schema

Entities: - URLMapping: id (PK), short_url (unique), original_url, creation_date, custom_alias (nullable), click_count - Analytics: short_url (FK), timestamp, user_agent, ip_address Relationships: - URLMapping has many Analytics records - short_url is unique and indexed for fast lookup

Scaling Discussion

Bottlenecks

Database write and read throughput limits with growing URL mappings

Cache size and eviction policies under heavy read load

Unique ID generation collisions or bottlenecks

Analytics processing delays with high click volume

API Gateway handling large concurrent requests

Solutions

Shard database by URL hash or user to distribute load

Use distributed cache clusters with consistent hashing

Use distributed ID generators like Snowflake or UUIDs with collision checks

Process analytics asynchronously with scalable message queues and workers

Auto-scale API Gateway and use CDN for static content

Interview Tips

Time: Spend 10 minutes clarifying requirements and constraints, 20 minutes designing components and data flow, 10 minutes discussing scaling and trade-offs, 5 minutes summarizing.

Clarify assumptions and requirements before starting design

Explain choice of unique ID generation and collision avoidance

Discuss caching strategy to reduce latency

Highlight asynchronous analytics processing for scalability

Address how to handle scaling bottlenecks realistically

Mention trade-offs between consistency and availability

Practice

1. What is the primary purpose of a URL shortener system?

easy

A. To generate random passwords for users

B. To increase the length of URLs for security

C. To store user passwords securely

D. To convert long URLs into short, easy-to-share links

Solution

1. Step 1: Understand the function of a URL shortener

   A URL shortener takes a long URL and creates a shorter alias that redirects to the original URL.

2. Step 2: Identify the correct purpose among options

   Only To convert long URLs into short, easy-to-share links describes this function correctly; others describe unrelated tasks.

3. Final Answer:

   To convert long URLs into short, easy-to-share links -> Option D

4. Quick Check:

   URL shortener purpose = convert long URLs to short [OK]

Hint: Focus on what URL shorteners do: shorten URLs [OK]

Common Mistakes:

• Confusing URL shortening with security features
• Thinking it stores passwords
• Assuming it generates random data unrelated to URLs

2. Which component is essential for generating unique short codes in a URL shortener?

easy

A. Cache server

B. Load balancer

C. Short code generator

D. User authentication module

Solution

1. Step 1: Identify the role of each component

   Short code generator creates unique short strings; load balancer distributes traffic; cache stores data temporarily; authentication manages users.

2. Step 2: Match component to short code creation

   Only the short code generator is responsible for creating unique short URLs.

3. Final Answer:

   Short code generator -> Option C

4. Quick Check:

   Unique code creation = short code generator [OK]

Hint: Short codes come from the short code generator [OK]

Common Mistakes:

• Confusing load balancer with code generation
• Thinking cache generates codes
• Assuming authentication creates short URLs

3. Given a URL shortener system, what happens when a user clicks a short URL http://short.ly/abc123?

medium

A. The system looks up abc123 in storage and redirects to the original long URL

B. The system generates a new short code for abc123

C. The system deletes the short URL from the database

D. The system asks the user to enter the long URL manually

Solution

1. Step 1: Understand the redirection process

   When a short URL is accessed, the system finds the original URL mapped to the short code and redirects the user.

2. Step 2: Evaluate each option

   The system looks up abc123 in storage and redirects to the original long URL correctly describes this lookup and redirect. Others describe incorrect or unrelated actions.

3. Final Answer:

   The system looks up abc123 in storage and redirects to the original long URL -> Option A

4. Quick Check:

   Click short URL = lookup and redirect [OK]

Hint: Clicking short URL triggers lookup and redirect [OK]

Common Mistakes:

• Thinking system creates new codes on click
• Assuming deletion happens on access
• Believing user must input original URL manually

4. In a URL shortener design, which issue arises if the short code generator does not check for duplicates?

medium

A. The system runs out of storage space quickly

B. Multiple long URLs map to the same short code causing incorrect redirects

C. Users cannot create new accounts

D. The system slows down due to too many cache hits

Solution

1. Step 1: Understand duplicate short code impact

   If duplicates exist, different long URLs share the same short code, causing wrong redirection.

2. Step 2: Analyze options for relevance

   Multiple long URLs map to the same short code causing incorrect redirects correctly identifies this problem. Others describe unrelated issues.

3. Final Answer:

   Multiple long URLs map to the same short code causing incorrect redirects -> Option B

4. Quick Check:

   Duplicate codes cause wrong redirects [OK]

Hint: Duplicates cause wrong URL redirects [OK]

Common Mistakes:

• Confusing storage issues with duplicate codes
• Thinking duplicates affect user accounts
• Assuming cache hits cause this problem

5. To scale a URL shortener for millions of users, which design choice improves performance and availability?

hard

A. Use distributed storage with caching and load balancing

B. Store all data on a single server to simplify access

C. Generate short codes sequentially without randomness

D. Disable caching to ensure fresh data every time

Solution

1. Step 1: Identify scalability needs

   Millions of users require fast access, high availability, and fault tolerance.

2. Step 2: Evaluate design choices

   Distributed storage spreads data load; caching speeds up lookups; load balancing distributes traffic. This combination supports scale.

3. Step 3: Reject poor choices

   Single server limits scale; sequential codes risk collisions; disabling cache slows response.

4. Final Answer:

   Use distributed storage with caching and load balancing -> Option A

5. Quick Check:

   Scaling needs distributed storage + cache + load balancer [OK]

Hint: Scale with distributed storage, caching, and load balancing [OK]

Common Mistakes:

• Choosing single server for large scale
• Ignoring caching benefits
• Using sequential codes risking collisions