System Design Interview Question: Design TinyURL (URL Shortener / Bitly)

A URL shortener (such as Bitly or TinyURL) is a classic high-level system design interview question. This guide walks through a rigorous 5-step framework—from gathering functional and non-functional requirements to high-level architecture, API design, and an advanced low-level design leveraging distributed coordination and Snowflake IDs.

1. Problem Statement & Real-Life Mental Model

Real-Life Analogy: The Postal Forwarding Service

Imagine running a postal forwarding office. People bring extremely long, unmanageable destination addresses (long-form URLs like https://www.facebook.com/profile.php?id=10000...). Your service assigns a tiny, convenient 5-to-6 character tracking code (e.g., bit.ly/ASD). When anyone hands you that tiny code, your office instantly looks up the master ledger, finds the original long address, and forwards (redirects) the visitor there.

Long URL: https://www.facebook.com/profile.php?id=100008372728
   |
   | (Submitted to Bitly)
   v
Short URL: http://bit.ly/ASD
   |
   | (User enters in browser address bar)
   v
Bitly Server looks up mapping & redirects browser to Long URL

2. Step 1: Gathering Requirements

In an interview, never jump straight into coding or drawing boxes. Spend the first 10–15 minutes clarifying requirements.

Functional Requirements

1. URL Shortening: Given a long-form URL, the system generates a unique, shorter alias.
2. Redirection: When a user visits the short URL, they are redirected to the original long-form URL.
3. Custom Aliases (Premium): Allow users to specify a custom short string (e.g., bit.ly/my-custom-link).
4. Expiration Control: Support default expiration (e.g., 90 days) and custom expiration dates for premium users.

Non-Functional Requirements

1. Low Latency: High performance on both creation and redirection (target < 200 ms response time).
2. High Scale: Support 100 million Daily Active Users (DAU) and generate 1 billion shortened URLs.
3. High Availability over Consistency (CAP Theorem): The service must never go down. Availability (A) is prioritized over immediate strict consistency (C). Eventual consistency is acceptable because users naturally experience a brief delay before sharing links.
4. Uniqueness: Short URLs must be globally unique with zero collisions.

3. Step 2: Identifying Core Entities

Based on the requirements, the system requires three core data entities:

4. Step 3: API Design

RESTful endpoints map directly to our functional requirements:

5. Step 4: High-Level System Architecture

At a high level, the system needs clients, a backend compute server, and a persistent database.

6. Step 5: Low-Level Design (LLD) & Evolution of Shortening Approaches

The core technical challenge in a URL shortener is generating short, unique identifiers efficiently at massive scale without database bottlenecks or collisions. Let's examine three evolutionary approaches.

7. Approach 1: Naive Hash Encryption (MD5 / SHA-1)

How It Works

Take the long URL, pass it through a cryptographic hash function like MD5 or SHA-1, and take the first 6 characters of the resulting hexadecimal/Base64 string.

Limitations & Flaws

• Collisions: Cropping the first 6 characters of different long URLs frequently results in identical strings (hash collision).
• Database Scanning Overhead: To resolve collisions, every generated hash must be checked against the entire database (SELECT * FROM urls WHERE short_url = ?), taking $\approx 10\text{ ms}$ per check. If a collision occurs, the process must re-hash and re-query, compounding latency and degrading user experience.

8. Approach 2: Counter-Based Generation with Redis

How It Works

Maintain an auto-incrementing counter. The first URL gets 1, the second gets 2, and so on. Convert this counter integer to Base62 (a-z, A-Z, 0-9) to form a compact short string.

Scaling & Distributed Bottlenecks

• Local Counter Collision: If running multiple server instances behind a load balancer, each server maintaining a local counter starting at 0 will generate duplicate keys (server1 produces 1, server2 produces 1).
• Centralized Redis Counter: Moving the counter to a single Redis instance eliminates duplicates because Redis is single-threaded and provides atomic increments.

Failure Mode

A single Redis instance is a Single Point of Failure (SPOF). If Redis goes down, URL creation halts entirely. Using a Redis cluster introduces separate counters per node, bringing back the duplicate key problem.

9. Approach 3: Advanced Hybrid Solution (Zookeeper & Snowflake IDs)

To achieve zero single points of failure, zero database collision checks, and lightning-fast local generation, we combine Apache Zookeeper with Twitter Snowflake IDs.

What is Apache Zookeeper?

Zookeeper is a distributed coordination service that manages configuration, naming, synchronization, and distributed locking. It structures data hierarchically like a file system directory. Nodes in Zookeeper can be Persistent (survive reboots) or Ephemeral (automatically deleted when a server sends a heartbeat timeout/dies).

Snowflake ID Structure (64-Bit Integer)

Instead of relying on a centralized counter, each backend server generates its own globally unique 64-bit ID locally:

1. Sign Bit: Always 0 for positive numbers.
2. Timestamp: Milliseconds precision ensuring chronological ordering.
3. Worker ID: Assigned dynamically by Zookeeper when a server boots up and registers as an ephemeral node.
4. Local Counter: A local atomic counter inside the server instance that rolls over every millisecond.

Data Flow Walkthrough with Zookeeper

10. System Optimization: Separation of Concerns & Caching

At 100 million DAU, read operations (redirections) vastly outnumber write operations (URL shortening) by an 80/20 ratio. Coupling them on the same server wastes resources.

Microservice Separation

• Encryption/Shortening Servers (20% Traffic): Handle POST /shorten, compute Snowflake IDs, and write to the database. Scaled to fewer instances.
• Decryption/Redirection Servers (80% Traffic): Handle GET /{shortUrl} and perform lookups. Scaled to more instances.

Multi-Tier Caching Layer

To protect the database from expensive queries ($\approx 10\text{ ms}$ latency), insert a Redis Cache Cluster in front of the database for redirection lookups.

11. Redirection Strategy: HTTP 301 vs. HTTP 302

When redirecting users from the short URL to the long URL, choose between two HTTP status codes based on business requirements:

12. Summary and Key Takeaways

• Clarify First: Spend the first 10–15 minutes gathering functional requirements (shortening, redirection, custom aliases, expiration) and non-functional requirements (low latency, high scale, availability).
• Availability over Consistency: Prioritize High Availability (AP in CAP theorem) so the service is always reachable.
• Avoid Naive Hashing: MD5 and SHA-1 hashing combined with string cropping lead to frequent database collisions and high latency.
• Counter Limits: Local counters drift across servers; single Redis instances act as single points of failure.
• The Ultimate Hybrid Solution: Use Apache Zookeeper to assign persistent Worker IDs to application servers, combined with Snowflake IDs for 100% unique, locally generated IDs without external blocking calls.
• Separation of Concerns: Isolate Encryption (Write) and Decryption (Read) services to scale them independently based on the 20/80 traffic ratio.
• Caching & Indexing: Place a Redis Cache in front of the database and add strict database indexing on the short_url column to maintain sub-200ms response times.
• Choose the Right Redirect: Use 301 for server load reduction or 302 when robust click analytics tracking is required.