url-shortener

The short_code is the primary key — every redirect performs a lookup by this field. Using it as the primary key ensures a single B-tree index serves both write (INSERT) and read (SELECT) paths.

Why is_active instead of DELETE? When malicious URLs are detected, we soft-delete by setting is_active = FALSE. This preserves the audit trail for abuse investigations and prevents the short code from being reassigned (which would break cached redirects).

URLMapping and Analytics have a one-to-one relationship. Each shortened URL has exactly one analytics record. The relationship is optional — URLs can exist without analytics if tracking is disabled.

The analytics table is separated from the mapping table to isolate the high-frequency increment path (every redirect) from the low-frequency write path (URL creation). This prevents write contention on the mapping table and allows the analytics table to use a different storage engine optimized for counters.

Requirement: Users submit a long URL and receive a unique shortened alias.

The simplest architecture: a single service that generates an ID, encodes it as Base62, stores the mapping, and returns the short URL.

ID Generation: Each server is assigned a unique machine prefix (e.g., A, B, C). Within each server, an auto-incrementing sequence number generates IDs. The combination MachineID + SequenceNumber is globally unique without coordination.

Why this approach? Alternative approaches (hash functions, UUIDs, Snowflake IDs) either produce IDs that are too long or require coordination between servers. Machine ID + Sequence gives us:

• Short IDs — we control the length precisely
• No coordination — each server generates IDs independently
• Scalable — add more servers by assigning new machine prefixes

Base62 Encoding: The numeric ID is converted to a 6-character string using a-z, A-Z, 0-9:

With 6 characters, Base62 supports 62⁶ = 56.8 billion unique codes. At 1M URLs/day, that's enough for 155 years before exhaustion — far beyond our 5-year retention requirement.

Requirement: Clicking a short URL redirects to the original URL with minimal delay.

Redirects are the dominant traffic pattern — 100× more frequent than URL creation. A naive approach (query the database for every redirect) would require 1,160 QPS to the database. With a caching layer, we can serve the vast majority of redirects from memory.

Read-through caching: When the Redirect Handler receives a request, it checks Redis first. On a cache miss, Redis itself fetches from the database, stores the result, and returns it to the handler. The handler never talks to the database directly — Redis acts as the unified read layer.

Why read-through instead of cache-aside? With cache-aside, the application must implement cache-miss logic (check cache → miss → query DB → populate cache). With read-through, the cache library handles this transparently. The Redirect Handler's code is simply:

original_url = cache.get(short_code)  # Read-through: auto-fetches from DB on miss
if original_url:
    return redirect(original_url, status=302)
return not_found(404)

Cache sizing: With 100M reads/day and Zipfian distribution (20% of URLs get 80% of traffic), we need to cache the top ~2M URLs. At 500 bytes per entry: 2M × 500B = 1 GB — easily fits in a single Redis instance.

TTL strategy: Set TTL to 24 hours for most URLs. Short URLs that are accessed frequently will be refreshed by natural reads. URLs that go cold expire from cache automatically, freeing memory for active URLs.

Requirement: Track the number of times each shortened URL is accessed.

Analytics must not slow down redirects. The redirect path returns a 302 in < 10 ms. Analytics recording happens asynchronously after the redirect response is sent.

Two-tier counting:

1. Redis INCR — Every click triggers INCR analytics:{short_code} in Redis. This is an atomic O(1) operation that handles any QPS. The counter is immediately queryable for real-time dashboards.

2. Periodic DB flush — A background worker reads Redis counters every 60 seconds and batch-writes them to the Analytics database:

Why not increment the DB directly? At 1,160 QPS, direct UPDATE statements would generate 1,160 transactions/sec on the analytics table. With 60-second batching, we reduce this to ~20 batch writes/sec — a 60× reduction in database load. The trade-off: click counts may be up to 60 seconds stale in the database, but they're always current in Redis.

The architecture has three independent scaling paths:

Key property: The Redirect Handler is stateless — any instance can serve any redirect. This makes horizontal scaling trivial: add more instances behind the load balancer.

Sequence: Create Short URL

Sequence: Redirect (Cache Hit)

What ID generation strategy should we use, and why?

The ID must have two properties: global uniqueness (no two URLs share a code) and shortness (compact enough to be useful as a short URL). These properties are in tension — longer IDs are easier to make unique; shorter IDs risk collisions.

The fundamental approach: generate a unique integer, then encode it into a compact string. Let's evaluate the integer generation options:

Option 1: Hash Functions (MD5 / SHA-256)

Hash the original URL to produce a fixed-length digest, then truncate to the desired length.

Problem: Truncation dramatically increases collision probability. Even with collision detection and retry logic, the write path becomes: hash → check DB → collision? → re-hash with salt → check again. Under load, this creates hot-path database reads on every write.

Option 2: UUID (v4 Random / v1 Timestamp)

Problem: 36 characters defeats the purpose of URL shortening. Even Base62-encoding a UUIDv4 produces ~22 characters. UUIDs solve uniqueness but fail the shortness requirement.

Option 3: Snowflake IDs (Twitter-style)

Structure: [timestamp: 41 bits][machine_id: 10 bits][sequence: 12 bits] = 64-bit integer.

Problem: Base62 encoding of a 64-bit integer produces ~11 characters. Still too long for a "short" URL. We could truncate, but that reintroduces collision risk.

Option 4: Machine ID + Sequence Number (Recommended)

Assign each server a unique 1-character prefix. Each server maintains an auto-incrementing counter. The ID is: MachinePrefix + SequenceNumber.

With 1 character for machine ID (62 options using Base62) and 5 characters for sequence (62⁵ = 916M per machine):

Advantages over alternatives:

The Machine ID + Sequence approach produces the shortest IDs with guaranteed uniqueness and no runtime coordination between servers. The only coordination point is machine ID assignment — a one-time setup operation when adding servers.

class BulkIDGenerator:
    BATCH_SIZE = 10_000

    def __init__(self, machine_id: str):
        self.machine_id = machine_id
        self.buffer = []
        self.sequence = self._load_last_sequence()
        self._refill()

    def next_id(self) -> str:
        if not self.buffer:
            self._refill()
        return self.buffer.pop()

    def _refill(self):
        batch = []
        for _ in range(self.BATCH_SIZE):
            self.sequence += 1
            batch.append(self.machine_id + base62_encode(self.sequence).zfill(5))
        self.buffer = batch
        self._persist_sequence()

How should we encode IDs into short, URL-safe strings?

After generating a unique integer, we need to encode it into a compact, human-readable string. The encoding must balance shortness with usability — avoiding characters that are confusing to type or problematic in URLs.

Encoding Options Comparison

Why Base62?

Base62 is the optimal choice because:

1. No special characters — +, /, and = from Base64 must be URL-encoded (%2B, %2F, %3D), defeating the purpose of shortening
2. 6 characters suffice — 62⁶ = 56.8B provides 30× headroom over our 5-year requirement
3. Human-friendly — All characters are easily typeable on any keyboard
4. Case-sensitive by definition — URLs are case-sensitive after the domain, so a1B2c3 and A1b2C3 are different short codes

How do we scale the system to handle high traffic?

Request handlers are stateless HTTP servers — scaling them is trivial (add more instances behind the load balancer). The interesting scaling challenges are in the ID generator and the database.

Scaling the ID Generator

Each ID generator uses 1 character for machine ID, giving us 62 possible machines. Each machine generates up to 916M IDs. But how do we route requests to them?

Load balancing strategies:

• Random selection: Each request handler picks a random ID generator. Simplest, good load distribution.
• Least-loaded: Pick the generator with the shortest queue. Better under skewed load.
• Sticky routing: Route by client ID. Unnecessary (any generator works for any request).

Sharding the Database

The machine ID prefix in each short code serves double duty as the shard key. Each machine writes to its own database shard — the write paths are completely independent.

Shard key = Machine ID prefix in the short code.

When machine A generates code a1B2c3 (prefix a), it writes to shard a. When machine B generates B7x9pQ (prefix B), it writes to shard B. No cross-shard coordination is needed for writes.

Write path: Completely parallel. Each machine writes to its own shard. No coordination, no locking, no cross-shard transactions. Adding a new machine = adding a new shard. Existing shards are unaffected.

Read path: On a cache miss, the redirect handler extracts the first character of the short code and routes to the correct shard. For example, a1B2c3 → shard a.

Why This Sharding Strategy Works

Table: url_mappings
  Partition Key: short_code (String)
  Attributes: original_url (String), created_at (Number), is_active (Boolean)
  Read Capacity: On-demand (auto-scales)
  Write Capacity: On-demand

How do we design the caching layer for 90%+ hit rates?

Caching is the single most impactful design decision for a URL shortener. With a 100:1 read-write ratio, the difference between 80% and 95% cache hit rate means 20× vs 5× load on the database — the difference between 1 database instance and 4.

Traffic Distribution: Zipf's Law

URL access follows a Zipfian distribution — a small fraction of URLs receive the vast majority of clicks. Empirical data from services like bit.ly shows:

• Top 1% of URLs → ~50% of all clicks
• Top 10% of URLs → ~90% of all clicks
• Bottom 50% of URLs → ~1% of clicks (many are clicked only once)

This is excellent for caching: a small cache capturing the top URLs handles most traffic.

Cache Sizing

At 1 GB (easily fits in a single Redis instance), we achieve ~93% hit rate, leaving only ~80 QPS hitting the database. This is well within a single database node's capacity.

Caching Strategies Compared

Recommended: Read-through + Write-through hybrid.

• Write path: When a new URL is created, write to both DB and cache (write-through). This ensures newly created URLs are immediately resolvable without a cache miss.
• Read path: On redirect, read from cache. On miss, the cache auto-fetches from DB (read-through).

import asyncio
from collections import defaultdict

class CoalescingCache:
    def __init__(self, redis_client, db_client):
        self.redis = redis_client
        self.db = db_client
        self._inflight = {}  # short_code → Future

    async def get(self, short_code: str) -> str:
        # Check cache first
        result = await self.redis.get(f"url:{short_code}")
        if result:
            return result

        # Coalesce concurrent misses for the same key
        if short_code in self._inflight:
            return await self._inflight[short_code]

        future = asyncio.get_event_loop().create_future()
        self._inflight[short_code] = future

        try:
            # Only ONE request hits the database
            url = await self.db.get(short_code)
            if url:
                await self.redis.set(f"url:{short_code}", url, ex=86400)
            future.set_result(url)
            return url
        finally:
            del self._inflight[short_code]

async def resolve_url(short_code: str) -> str:
    # Tier 1: In-process cache (no network)
    url = local_cache.get(short_code)
    if url:
        return url

    # Tier 2: Redis (1ms network)
    url = await redis.get(f"url:{short_code}")
    if url:
        local_cache.put(short_code, url)
        return url

    # Tier 3: Database (5-10ms)
    url = await db.get_url(short_code)
    if url:
        await redis.set(f"url:{short_code}", url, ex=86400)
        local_cache.put(short_code, url)
    return url

Should we use 301 or 302 redirects? What are the trade-offs?

The redirect status code determines browser behavior, caching semantics, and analytics accuracy. This seemingly small decision has significant downstream consequences.

Impact Analysis

When to Use Each

Use 302 (recommended for most URL shorteners):

• You need click analytics (the primary business model for many shorteners)
• You need ability to deactivate malicious URLs
• You want to A/B test destination URLs
• The redirect is for external/marketing links

Use 301 for specific cases:

• Internal tool links where analytics don't matter
• Links embedded in documentation that will never change
• When minimizing server load is critical and analytics are unnecessary

Hybrid Approach

The best of both worlds: use 302 with a Cache-Control header that enables short-term browser caching:

HTTP/1.1 302 Found
Location: https://example.com/destination
Cache-Control: private, max-age=86400

This tells the browser: "Cache this redirect for 24 hours, but check back with us after that." You lose at most 1 click per user per day to caching, while still getting analytics for most visits.

How do we prevent abuse and detect malicious URLs?

URL shorteners are prime targets for abuse. Attackers use them to disguise phishing URLs, distribute malware, and bypass email security filters. If security vendors blocklist your domain, legitimate users lose access — a business-critical failure.

Defense Layers

Layer 1: Pre-creation scanning (synchronous)

Before storing a URL, check it against known malicious URL databases:

Layer 2: Post-creation batch scanning (asynchronous)

URLs can become malicious after creation (e.g., destination changes, new threat intelligence). A background scanner rechecks URLs periodically:

Layer 3: Enumeration prevention

Short codes like a00001, a00002, a00003 are sequential and predictable. An attacker can enumerate all URLs by incrementing the code. Mitigations:

• Randomize sequence within machine: Instead of strictly incrementing, use a permutation function that maps sequential integers to non-sequential outputs
• Rate limit redirect requests: Detect enumeration patterns (sequential codes from same IP)
• Don't expose creation-order information: Ensure short codes don't reveal when they were created

async def deactivate_url(short_code: str, reason: str):
    await db.execute(
        "UPDATE url_mappings SET is_active = FALSE WHERE short_code = %s",
        short_code
    )
    await redis.delete(f"url:{short_code}")
    await redis.set(f"deactivated:{short_code}", reason, ex=86400*30)
    await audit_log.record(short_code, "DEACTIVATED", reason)

async def handle_redirect(short_code: str):
    # Check deactivation first (cached check)
    deactivation_reason = await redis.get(f"deactivated:{short_code}")
    if deactivation_reason:
        return render_warning_page(short_code, deactivation_reason)

    url = await resolve_url(short_code)
    if url:
        await record_click(short_code)  # Async analytics
        return redirect(url, status=302)
    return not_found()

How do we deploy across regions for global availability?

A user in California creates a short URL. Seconds later, someone in Tokyo clicks it. The URL must resolve globally with minimal latency. This requires multi-region deployment with careful consistency trade-offs.

The Consistency Challenge

A newly created URL must be globally resolvable within seconds. But cross-region replication takes 100-300 ms. During this window, a request to the AP-EAST region returns 404 for a URL that exists in US-WEST.

Solution: Read-after-write consistency for creators

async def shorten_url(long_url: str) -> dict:
    short_code = generate_id()

    # Write to primary (US-WEST)
    await primary_db.insert(short_code, long_url)

    # Write-through to LOCAL cache (immediate availability in creation region)
    await local_redis.set(f"url:{short_code}", long_url, ex=86400)

    # Return short URL — creator can immediately share it
    return {"shortUrl": f"https://short.ly/{short_code}"}

The creator's region has the URL immediately in cache. Other regions receive it within 300 ms via replication. For the rare case where someone clicks a URL within 300 ms of creation from a different region:

Fallback: Cross-region read on miss

async def resolve_url(short_code: str) -> str:
    # 1. Check local cache
    url = await local_redis.get(f"url:{short_code}")
    if url:
        return url

    # 2. Check local DB replica
    url = await local_db.get(short_code)
    if url:
        await local_redis.set(f"url:{short_code}", url, ex=86400)
        return url

    # 3. Fallback: check primary region (adds 100-200ms latency)
    url = await primary_db.get(short_code)
    if url:
        await local_redis.set(f"url:{short_code}", url, ex=86400)
        return url

    return None  # URL truly doesn't exist

The cross-region fallback adds 100-200 ms but only triggers for URLs created within the last 300 ms and accessed from a different region — an extremely rare path.

Regional Cache Warming

For high-profile URLs (e.g., a marketing campaign shared on social media), pre-warm caches in all regions at creation time:

How do we handle URL expiration and storage growth?

At 1M URLs/day for 5 years, we accumulate 1.825B records (~1 TB). Without cleanup, storage grows indefinitely. But deleting URLs is dangerous — a "dead link" is worse than a "slightly slow link."

Expiration Policy

TTL-Based Cleanup

def cleanup_expired_urls():
    """Runs daily as a scheduled batch job."""
    # Never delete — archive and soft-delete
    expired = db.query("""
        SELECT short_code FROM url_mappings
        WHERE is_active = TRUE
          AND created_at < NOW() - INTERVAL '5 years'
          AND short_code NOT IN (
              SELECT short_code FROM url_analytics
              WHERE last_accessed > NOW() - INTERVAL '90 days'
          )
    """)

    for batch in chunk(expired, 1000):
        # Archive to cold storage (S3/Glacier)
        archive_to_cold_storage(batch)
        # Soft-delete
        db.execute(
            "UPDATE url_mappings SET is_active = FALSE WHERE short_code IN %s",
            batch
        )
        # Invalidate cache
        redis.delete(*[f"url:{code}" for code in batch])

Storage Tiering

Key principle: Never delete a short code that might be embedded somewhere. Soft-delete, archive, and serve a "this link has expired" page instead of a 404.

The following topics contain open-ended architectural questions without prescriptive solutions. They are designed for staff+ conversations where you demonstrate systems thinking, trade-off analysis, and strategic decision-making.