Problem 1: Design a URL Shortener

A URL shortener is a core system design problem that translates long, unwieldy web addresses into compact, easily shareable aliases. When an end-user navigates to a short link, the service intercepts the request and issues an HTTP redirect to the original target destination. Despite its simple premise, building a production-grade URL shortener requires solving fundamental distributed systems challenges: collision-free unique identifier generation, high-throughput low-latency read caching, tamper-resistant ID obfuscation, and intelligent HTTP redirect semantics.

1. Problem Overview & Core Requirements

Before designing any architectural components, we apply a structured requirements-gathering framework. In an interview setting, focus strictly on questions that directly influence the technical architecture.

Functional Requirements

• Short Link Generation: Given a standard URL, the system generates a unique, compact short code (e.g., 7 characters).
• Redirection: When a user accesses the short link, the system seamlessly redirects them to the original destination.
• Link Longevity: Short links live indefinitely (no automatic expiration or garbage collection overhead).
• Out of Scope (V1): Custom user-defined alias strings (e.g., sho.rt/my-custom-brand) are disabled for initial design scope. Real-time click analytics are treated as a non-blocking, secondary requirement.

Non-Functional Requirements

• Ultra-Low Latency: Link redirection must execute in single-digit milliseconds.
• Massive Read Availability: The redirection path must never go down, even during extreme viral traffic spikes.
• Collision Resistance: Two distinct long URLs must never resolve to the same short code.
• Non-Predictable Codes: Malicious actors must not be able to guess or sequentially enumerate valid links in the database.

2. Capacity Estimation & Traffic Ratios (Back-of-the-Envelope)

Calculations should directly dictate database sizing, throughput requirements, and caching topologies.

Write Traffic (Link Creation)

• Assumed Write Rate: $1\text{ million new links per day}$.
• Write Throughput (QPS):

• Insight: An ingest rate of 12 writes/second is negligible. Any standard relational database can comfortably handle this on modest single-node hardware.

Read Traffic (Link Redirection)

• Assumed Read-to-Write Ratio: $1,000 : 1$ (every generated link is clicked an average of 1,000 times).
• Read Throughput (QPS):

• Insight: The system is massively read-heavy. While a tuned database instance can handle $\sim11.6\text{k QPS}$, traffic is not evenly distributed. A single viral link can demand tens of thousands of requests per second instantly.

Storage Capacity (10-Year Horizon)

• Total Link Records:

• Data Sizing per Record:
  • id: 8 bytes (64-bit integer)
  • short_code: 7 bytes (VARCHAR/CHAR)
  • long_url: $\sim500$ bytes average (VARCHAR)
  • created_at: 8 bytes (Timestamp)
  • Overhead & Indexes: $\sim100$ bytes
  • Total per row: $\sim623 \text{ bytes}$
• Total Storage:

• Insight: Over a 10-year span, the raw dataset occupies around 2.3 TB, easily fitting within standard enterprise database storage arrays or distributed disks.

3. API Contract & Data Modeling

The system exposes two primary endpoints. The interface is lean, mapping cleanly to a single core relational data model.

API Specifications

1. Create Short Link

• Endpoint: POST /api/v1/shorten
• Request Payload:
  JSON

  Copy

  {
    "long_url": "https://www.example.com/deep/nested/resource/path"
  }
  

• Response Payload:
  JSON

  Copy

  {
    "short_code": "aZ9k2Lp",
    "short_url": "https://sho.rt/aZ9k2Lp"
  }
  

2. Redirect to Target

• Endpoint: GET /{short_code}
• Request Headers: Standard browser headers
• Response: HTTP 302 Found with Location: https://www.example.com/deep/nested/resource/path

Data Schema

Because the access pattern represents an exact 1:1 key-value lookup (short_code $\to$ long_url) with strict uniqueness constraints and no complex join requirements, PostgreSQL with a B-tree index on the lookup key is an ideal storage engine.

CREATE TABLE url_mappings (
    id BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
    short_code VARCHAR(7) NOT NULL,
    long_url TEXT NOT NULL,
    created_at TIMESTAMP WITH TIME ZONE DEFAULT CURRENT_TIMESTAMP
);

-- B-Tree Index for single-row O(log N) point lookups
CREATE UNIQUE INDEX idx_url_mappings_short_code ON url_mappings (short_code);

Note on Database Selection: Avoid justifying NoSQL purely with generic phrases like "NoSQL scales better." A relational database like PostgreSQL natively guarantees ACID transactions, handles unique index enforcement gracefully, and handles 2.3 TB of data across a decade with read replicas.

4. High-Level System Architecture

The core flow splits cleanly into an ingestion (write) pipeline and a retrieval (read) pipeline.

5. Short Code Generation: Hashing vs. Counter-Based Base62

Generating a unique, compact string is the central algorithmic challenge of a URL shortener.

Approach 1: Hash Truncation

1. Compute the cryptographic hash (MD5 or SHA-256) of the incoming long_url.
2. Extract the first 7 characters of the hash output.
3. The Collision Dilemma: Different long URLs can yield the exact same 7-character prefix. The server must issue a database query on every write to verify if the code already exists.
4. If a collision occurs, append a predefined salt or timestamp to the URL and repeat the hashing process until an unused code is generated.
5. Drawback: As the database grows toward billions of rows, hash collisions rise exponentially, introducing unpredictable latency and write retries.

Approach 2: Monotonic Counter + Base62 Encoding (Preferred)

Base62 uses alphanumeric characters: $[0\text{–}9, a\text{–}z, A\text{–}Z]$ (62 possible characters per digit).

• Capacity of a 7-character Base62 string:

• Comparison: $3.52\text{ Trillion}$ combinations far exceeds our 10-year requirement of $3.65\text{ Billion}$ links.

# Base62 Encoding Implementation Reference
BASE62_ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

def base62_encode(num: int) -> str:
    if num == 0:
        return BASE62_ALPHABET[0]
    
    digits = []
    base = len(BASE62_ALPHABET)
    while num > 0:
        remainder = num % base
        digits.append(BASE62_ALPHABET[remainder])
        num = num // base
        
    return "".join(reversed(digits)).rjust(7, '0')

6. Hardening the Counter: Security Obfuscation & Concurrency

While the counter-based approach eliminates collisions, it introduces two vulnerabilities in production environments.

Vulnerability 1: Sequential Enumeration Attacks

• The Problem: If link ID 1,000,000 encodes to 004c9Za, then the next link 1,000,001 translates to 004c9Zb. An attacker can decode Base62 back to its base-10 integer, increment the number by 1, re-encode it, and systematically crawl every link stored in the system.
• The Solution (Reversible Bijective Shuffling): Before Base62 encoding, pass the integer ID through a reversible bit-permutation function (such as a Feistel cipher or multiplicative modular inverse).
  • Every input number produces a pseudo-random output.
  • The operation is $1:1$ and fully reversible, meaning no two counter values will ever produce the same shuffled value.

Vulnerability 2: Concurrency & Race Conditions

• The Problem: If multiple application server nodes concurrently read the counter from a central source, two workers might receive the same integer ID, producing duplicate short codes.
• The Solution: Use a centralized distributed counter or segmented ID allocation:
  • Option A: Redis Atomic Counter: Use INCR to ensure thread-safe, monotonic sequence generation.
  • Option B: Range-Based Allocation (Token Service): A central coordinator assigns discrete ID ranges (e.g., Worker 1 gets 1–1,000,000, Worker 2 gets 1,000,001–2,000,000). Workers increment locally in-memory with zero network locking.

7. Scaling the Read Path: Caching Strategy & Hotkey Handling

With an average read-to-write ratio of 1,000:1, performance depends entirely on shielding the database from repetitive read traffic.

The "Dream Case" for Caching

In standard systems, caching is complicated by cache staleness (i.e., data is updated in the database while the cache continues serving obsolete values).

Core Architectural Insight: URL mappings are immutable. A short code, once written, is never updated to point to a different URL. Because records are append-only and immutable, the cache can never serve an incorrect, stale response.

Mitigating the Hotkey Problem (Celebrity Traffic)

When a high-profile entity posts a short link, millions of read requests hit the exact same key within minutes.

1. Redis Shared Layer: Answers queries in sub-millisecond time. Memory constraints are managed by an LRU (Least Recently Used) eviction policy. Active links remain in memory; dormant links are purged.
2. Local L1 In-Memory Cache: To prevent network saturation on the Redis cluster itself, each application instance stores the top 5,000 hottest keys in its local RAM (e.g., using Guava or Caffeine cache).
3. Edge / CDN Caching: Deploying reverse proxy edge caches (Cloudflare, CloudFront) across global points of presence (PoPs) resolves the redirect at the geographic edge, eliminating origin server hits altogether.

8. HTTP Redirect Mechanics: 301 Moved Permanently vs. 302 Found

When the application returns an HTTP redirect, selecting the correct status code represents an architectural trade-off between infrastructure cost and system visibility.

Direct Technical Comparison

Interview Verdict: Choose HTTP 302 Found. While a 301 redirect saves compute cycles, business requirements almost universally demand click analytics, attribution tracking, and security controls to block malicious domains.

9. Fault Tolerance, Data Durability & System Bottlenecks

Analyzing real-world production failure modes ensures the system remains robust during infrastructure outages.

Critical Component Failure Analysis

Key Durability Invariants

1. The Cache is a Performance Accelerator, Not the Source of Truth: A total cache failure degrades system throughput and increases latency, but will not corrupt data. Every mapping remains durably stored in PostgreSQL.
2. Immutable Primary Storage: Data loss in the PostgreSQL mapping table breaks links permanently. Primary databases must employ:
   • Synchronous write-ahead logging (WAL).
   • Multi-AZ Read Replicas.
   • Continuous snapshotting to durable cold storage (e.g., AWS S3).
3. Counter Non-Regression: An ID counter generator must never reset backwards after a crash. If a counter repeats previously issued values, the system will attempt to overwrite or duplicate existing mappings.

10. End-to-End Request Lifecycles

Creation Flow (Write Path)

Redirection Flow (Read Path)

11. Summary and Key Takeaways

• Read-Dominant Architecture: URL shorteners experience read-to-write ratios of $1,000 : 1$ or higher. The write path can easily be handled by a single relational database instance, while the read path requires dedicated multi-layer caching.
• Deterministic ID Generation: Counter-based Base62 generation outperforms cryptographic hash truncation by completely eliminating collisions, database lookup retries, and variable write latency.
• Bijective ID Shuffling: Monotonically increasing sequential IDs introduce security enumeration risks. Running the integer through a reversible, secret permutation before Base62 encoding creates an unpredictable output while preserving absolute mathematical uniqueness.
• Caching Without Invalidation Headaches: Because short-code-to-long-URL mappings are completely immutable, caches can hold mappings indefinitely under an LRU eviction model with zero risk of serving stale data.
• Redirect Semantics (301 vs. 302): Use HTTP 302 Found for redirects. A 301 Moved Permanently triggers browser-level caching that bypasses servers, breaking click-tracking analytics and stripping away security controls.
• Resilience Hierarchy: Treat the caching tier as a performance layer and the relational database as the single source of truth. Ensure that loss of the cache causes graceful latency degradation rather than data corruption.