URL Shortener (bit.ly)

What is a URL Shortener?

A URL shortener converts a long URL into a short, unique alias (e.g. bit.ly/4c92aB) that redirects the user to the original destination. When a user requests the short URL, the system performs a high-speed lookup of the original mapping and returns an HTTP redirect status.

Real-World Applications

• bit.ly, tinyurl.com, t.co (Twitter link wrapper)
• Analytics tracking, marketing campaign monitoring, and SMS-friendly links.

Core API Contracts

1. Shorten Link

POST /api/v1/shorten
Content-Type: application/json

{
  "longUrl": "https://example.com/very/long/path/to/resource?ref=marketing&utm_source=campaign",
  "customAlias": "campaign2026", // optional
  "expiresAt": "2026-12-31T23:59:59Z" // optional
}

Response (201 Created):
{
  "shortUrl": "https://bit.ly/campaign2026",
  "longUrl": "https://example.com/very/long/path/to/resource?ref=marketing&utm_source=campaign",
  "createdAt": "2026-06-21T14:20:00Z",
  "expiresAt": "2026-12-31T23:59:59Z"
}

2. Redirect Link

GET /{shortKey}

Response (302 Found or 301 Moved Permanently):
Headers:
Location: https://example.com/very/long/path/to/resource?ref=marketing&utm_source=campaign

Functional Requirements

• Core Shortening: Given a long URL, generate a unique short alias of fixed size (7-8 characters).
• Core Redirection: When a user hits the short URL, redirect them to the original long URL with minimum latency.
• Custom Aliases: Users can supply a custom short key (e.g., bit.ly/my-custom-key) subject to availability.
• Link Expiration: Links should have a configurable expiration time, after which they are deleted or disabled.
• Analytics (Basic): Track click metrics (daily clicks, browser, country, referring site) without blocking the redirect flow.

Non-Functional Requirements

• Massive Read-Heavy Ratio: 100:1 read-to-write ratio (100M shortening writes/day vs 10B redirection reads/day).
• Ultra-low Latency: Redirection lookup must take less than 50ms at the P99.9 level.
• High Availability: 99.99% uptime to prevent breaking links worldwide.
• Consistency: Eventual consistency is acceptable for metadata and analytics, but once a short URL is created, it must be instantly redirectable (read-after-write consistency).

Capacity Estimates (Back-of-the-Envelope Math)

1. Redirection (Read) QPS:
   • 10 Billion reads/day $div$ 86,400 seconds/day $approx$ 115,740 QPS.
2. Shortening (Write) QPS:
   • 100 Million writes/day $div$ 86,400 seconds/day $approx$ 1,160 QPS.
3. Storage Requirements:
   • Let's store each record for 5 years.
   • Size per record $approx$ 500 bytes (ID, original URL, short key, created timestamp, expiration).
   • Total records over 5 years: $100 ext{M/day} imes 365 ext{ days/year} imes 5 ext{ years} = 182.5 ext{ Billion records}$.
   • Total Storage: $182.5 ext{B} imes 500 ext{ bytes} approx 91.25 ext{ Terabytes}$.
4. Cache Size (Redis):
   • Follow the 80/20 rule: 20% of the URLs generate 80% of redirect traffic.
   • Daily read footprint: 10B reads. Cache 20% of daily keys: $2 ext{ Billion keys}$.
   • Each cache item: shortKey + originalUrl $approx$ 250 bytes.
   • RAM needed: $2 ext{B} imes 250 ext{ bytes} = 500 ext{ Gigabytes}$ of Redis cluster memory.

How to Approach This Problem

When designing a URL shortener in an interview, keep this systematic, step-by-step mental roadmap in mind:

Step 1: Characterize the System

Recognize that this is an extreme read-heavy key-value mapping service. The primary bottleneck is database read IOPS under a massive 116k QPS. Conversely, the write QPS (1.16k) is relatively relaxed.

Step 2: Establish the Core Operations

Define how you will fetch the mapping:

• How does the system generate a unique key?
• How does the system look up a key and redirect? Identify that the core problem is conflict-free distributed ID generation matching against a high-speed lookup engine.

Step 3: Layer the Architecture

1. Stateless Web Layer: Handles client requests. Easy to scale horizontally.
2. Distributed ID Generator: Crucial to avoid key collisions in multi-server write scenarios.
3. Aggressive Cache Layer: Sits in front of the database to handle the 116k QPS reads.
4. Partitioned Database Layer: Houses the 91TB of long-term mappings.

Step 4: Scale Out & Optimize

• Determine sharding key (must partition by short key to enable single-node point lookups).
• Introduce asynchronous event ingestion (Kafka) for click analytics so click tracking does not slow down the client redirect path.

Core Design Intuition

To succeed at scale, a URL shortener must decouple key creation from key resolution and shield the database using a multi-layered cache.

The Request Lifecycle Flow

Key Insights

1. Base62 Encoding vs Hashing: Standard MD5 hashes (128-bit) produce long strings. We need a 7-character string. Converting a unique 64-bit integer into Base62 ($62^7 approx 3.5 ext{ Trillion}$ keys) guarantees uniqueness and avoids collisions entirely.
2. Redirection Status Codes:
   • 301 (Moved Permanently): Browser caches the redirect. Reduces server load but eliminates analytics collection.
   • 302 (Found): Browser requests the server every time. Essential for analytics tracking.
3. Decouple Analytics: Writing to a DB directly on every redirect will instantly overwhelm any transactional database. We must broadcast redirect events to a message queue and process them asynchronously.

System Architecture & Data Flow

Component Breakdown

1. Clients: Web browsers or mobile devices hitting http://bit.ly/{shortKey}.
2. DNS & Load Balancer: Directs traffic to App servers using round-robin routing.
3. App Servers (Stateless): Hosts REST endpoints. Written in lightweight async frameworks (e.g., Go, Node.js).
4. Unique ID Generator (Zookeeper + Range Allocation): Allocates unique numeric ranges (e.g., 1 to 1,000,000) to each app server. App servers increment locally, converting the integer to Base62 without talking to a central coordinator on every request.
5. Cache Cluster (Redis): Holds hot mapping data. Key: short_key, Value: long_url.
6. Relational DB Cluster (MySQL): Primary persistent store, sharded by the hash of the short_key.

MySQL Table Schema

CREATE TABLE url_mappings (
  short_key VARCHAR(8) PRIMARY KEY, -- Base62 key
  long_url VARCHAR(2048) NOT NULL,  -- Original URL
  created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP,
  expires_at TIMESTAMP NULL,
  user_id BIGINT UNSIGNED NULL      -- Reference for user accounts
) ENGINE=InnoDB;

Execution Flow: Redirection (Read Path)

1. Browser issues GET /abc123.
2. Load Balancer routes request to App Server.
3. App Server checks Redis:
   • Hit: Return HTTP 302 with Location: {long_url}.
   • Miss: Query sharded MySQL. If found, write back to Redis, then return HTTP 302. If not found, return HTTP 404.

Advanced Scaling & Engineering Edge Cases

1. Distributed ID Generation Strategies

To scale ID generation without a single point of failure (SPOF) or coordination bottleneck:

• Range Allocation (Token Range): A central service like Apache ZooKeeper maintains a global counter. When an App Server starts, it requests a range of 1,000,000 IDs (e.g., 1,000,001 to 2,000,000). The App Server increments this locally in memory. If it crashes, the remaining IDs in that range are lost, which is perfectly fine since the ID space ($3.5 ext{ Trillion}$) is vast.
• Snowflake Algorithm: Generates 64-bit unique IDs using timestamp, worker node ID, and sequence number. Does not require ZooKeeper coordination but keys are longer when converted to Base62.

2. Database Partitioning (Sharding)

A single MySQL instance cannot support 91TB of data or 116k QPS.

• Sharding Key: We shard MySQL nodes using a hash of the short_key (e.g., hash(short_key) % N_SHARDS). This distributes traffic evenly.
• Why not shard by User ID? If we sharded by user_id, looking up a redirect request (which only contains the short_key) would require broadcasting the query to all DB shards, defeating the purpose of sharding.

3. Eviction Policy and TTL

• Eviction Strategy: Use Least Recently Used (LRU) eviction in Redis since it automatically ejects cold keys.
• Cache Invalidation: Set an explicit TTL on Redis keys equal to the link's expiration, or a maximum of 30 days for active links to save RAM.

4. High-Performance Click Analytics Ingestion

To collect geographical and client information without blocking redirects:

1. When a redirect occurs, the App Server pushes a structured payload to Apache Kafka:
   json

   { "shortKey": "abc123", "ip": "192.168.1.1", "userAgent": "Chrome", "timestamp": 1782051600 }
   

   Expand
2. ClickHouse or Apache Druid consumers ingest events in batches from Kafka.
3. OLAP databases query these statistics at scale without impacting the operational transactional database.

Engineering Trade-offs & Decisions

Succeeding in the Interview

What Interviewers Look For

1. Requirement Clarification: Ask if links can expire, if custom aliases are allowed, and how detailed analytics need to be.
2. Scale Mathematical Literacy: Demonstrate comfortable calculation of QPS and memory storage sizes.
3. The 301 vs 302 Distinction: Mentioning the browser caching behavior of 301 vs 302 is a major signal of real-world web experience.
4. Collision Management: If you propose a hashing method, you must address what happens when two URLs hash to the same key.

Common Mistakes

• Designing for Celebrities: A URL shortener does not have "celebrity links" in the social network sense. A link shared by a celebrity simply causes a massive read spike. Discuss caching and CDN distribution to solve this, not hybrid write/read paths.
• Synchronous Analytics: Storing click stats in MySQL during the redirect request will cause database lockups. Always decouple analytics via message queues.
• Using UUIDs: UUIDs are 128-bit and look horrible as short URLs. Stick to Base62.