HLD: URL Shortener (Bitly)

Designing a massively scalable URL shortening platform involves architecting ultra-low latency redirection engines, globally deterministic key generation infrastructures, and high-throughput real-time analytics streaming pipelines. At enterprise scale, simple CRUD applications rapidly hit severe network IO bottlenecks and hashing collisions without meticulous storage design and distributed coordination.

1. System Requirements & Architectural Scope

Functional Requirements

• Short Link Generation: Given a verbose target URL, generate an alphanumeric alias (e.g., https://short.ly/e7R9pA2) of minimal length.
• Low-Latency Redirection: Given a short alias, reliably resolve and transition the browser via an appropriate HTTP redirect code directly to the original target URL.
• Custom Aliases & TTL Expirations: Users may optionally provide custom mnemonic aliases and specific expiration timestamps after which links become inactive.
• Real-Time Click Analytics: Accurately track spatial-temporal attribution data (referrers, User-Agent device profiles, geographic IP routing) for every link execution without introducing redirection latency.

Non-Functional Requirements

• Extreme Read High Availability ($99.999\%$): Redirection endpoints represent fundamental network plumbing; any outage breaks destination routing across millions of downstream external websites and campaigns.
• Minimal Latency Budget: Redirection execution (DNS resolution + Cache lookup + HTTP Response issuance) must finish within $< 50\text{ms}$ at edge boundaries.
• Immutable URL Permanence: Once generated, a standard URL mapping must never mutate or experience silent collisions across distinct customer accounts.

2. Capacity Sizing & Mathematical Modeling

URL Shorteners represent archetypical Read-Heavy distributed workloads.

                  [ Redirection vs Generation Workload ]
   
     New Short Link Generation              Short Link Redirection (Reads)
           [40 writes/sec]                        [4,000 reads/sec]
           ==                                     ======================================

Throughput Estimations

• Monthly New Link Generation: $100\text{ million new short links / month}$. $\text{Write Throughput} = \frac{100,000,000}{30 \times 86,400} \approx \mathbf{38.5 \text{ writes/sec (Peak: } \approx 200 \text{ writes/sec)}}$
• Read-to-Write Ratio: Estimated at $100:1$ (each short URL is clicked an average of $100\text{ times}$). $\text{Read Throughput} = 38.5 \times 100 = \mathbf{3,850 \text{ reads/sec (Peak: } \approx 20,000 \text{ reads/sec)}}$

10-Year Storage Sizing

• Record Volume: Over a 10-year service lifecycle: $\text{Total Objects} = 100,000,000 \times 12 \times 10 = \mathbf{12 \text{ billion target records}}$
• Record Size & Footprint: Each structured record requires roughly $500\text{ bytes}$ (Long URL: 256B, Short Key: 7B, Creation/Expiry Timestamps: 16B, Creator ID: 16B, Analytics flags: 100B, indexing & overhead: 105B). $\text{10-Year Storage Requirement} = 12 \text{ billion} \times 500 \text{ bytes} \approx \mathbf{6 \text{ Terabytes of persistent memory}}$
  • Architectural Takeaway: A simple relational database running on modest modern hardware can comfortably retain $6\text{ TB}$ of data without intense database sharding if proper horizontal read scaling is applied.

3. Key Space Exploration & Hashing Strategies

To store $12\text{ billion}$ distinct aliases, we must engineer a compact alphanumeric generation scheme that strictly eradicates cryptographic collisions.

Key Base Selection

We utilize Base62 encoding, comprised of alphanumeric ASCII characters ($[0-9, a-z, A-Z]$ $\implies 10 + 26 + 26 = 62\text{ symbols}$).

• With a short alias character length $L$, the maximum total universe of unique addressable permutations is $62^L$:
  • $L = 6 \implies 62^6 = 56,800,235,584$ (~$56.8\text{ billion}$ combinations)
  • $L = 7 \implies 62^7 = 3,521,614,606,208$ (~$\mathbf{3.52\text{ trillion}}$ combinations)
• Choosing $\mathbf{L = 7}$ offers sufficient overhead to sustain decades of operations while preventing sequence exhaustion.

Option A: Cryptographic Hashing (MD5 / SHA-256) & Truncation

We take the target long URL, compute a cryptographic digest (e.g., MD5("https://...") $\implies$ $128\text{ bits}$), and truncate the initial $42\text{ bits}$ into a 7-character Base62 string.

• The Fatal Flaw (Birthday Paradox & Hash Collisions): Different long URLs can yield identical truncated 7-character string hashes. Before storing, the backend must execute a database lookup (SELECT 1 FROM urls WHERE short_key = ?) to check if the generated token is already claimed. If a collision occurs, the system must iteratively append arbitrary noise salt and re-hash, introducing significant latency loops under high concurrency.

Option B: Offline Key Generation Service (KGS) — The Production Pattern

Instead of dynamically generating hashes computationally at request time, an isolated, continuous background architecture called the Key Generation Service (KGS) pre-computes valid, globally distinct random 7-character Base62 tokens offline and serializes them into a specialized Available Key Database.

    ┌──────────────────────────┐
    │  Offline Pre-Computation │
    │     Key Gen Service      │
    └────────────┬─────────────┘
                 │
                 ▼
     ┌────────────────────────┐
     │  Available Key DB      │ ◄── Store billions of unique pre-generated keys
     └────────────┬─────────────┘
                 │
                 ▼
    ┌──────────────────────────┐
    │ Local RAM Key Buffers    │ ◄── Workers lock & load chunks of 1,000 keys
    │ (Concurrently Isolated)  │     into memory; zero network DB lookups on URL creation!
    └──────────────────────────┘

• Zero-Latency Ingestion: When a create request hits an application worker, the node instantly plucks an already-verified key from its local thread-safe in-memory key buffer (pre-loaded in bulk chunks of $1,000$ keys from the KGS database). Zero real-time database collision checking occurs!
• Concurrency Protection: As application instances load key chunks into volatile memory, those tokens are permanently marked as ALLOCATED inside the primary KGS registry. Even if an application node experience catastrophic power loss and loses its unconsumed in-memory key buffer, the system simply drops those specific tokens; out of $3.52\text{ trillion}$ available permutations, dropping a few thousand uncommitted keys causes zero systemic architectural stress.

4. HTTP Redirection Deep Dive: 301 vs 302 vs 307

When a user visits https://short.ly/e7R9pA2, the server returns a redirect response containing an authoritative Location: https://target-url.com response header. Selecting the appropriate HTTP status code carries profound operational implications:

| HTTP Code | Canonical Status Name | Browser Caching Behavior | Analytics Observability | Server Computational Load | | :--- | :--- | :--- | :--- | :--- | | 301 | Moved Permanently | Browser aggregates & caches destination permanently in localized memory. | Complete Observability Loss: Subsequent user visits bypass our servers completely. | Minimal: Eliminates repeated server network egress and CPU routing load. | | 302 / 307 | Found / Temporary Redirect | Prohibits strict local caching; browser hits shortener servers on every subsequent click. | 100% Comprehensive Attribution: Complete auditability of every single user click event. | High: Demands robust CDN buffering and multi-tier elastic caching tiers. |

• Architectural Consensus: Enterprise shorteners almost universally issue HTTP 302 or 307 Temporary Redirects. Maintaining real-time spatial analytics, campaign attribution performance tracking, and immediate custom destination rerouting outweighs the incremental infrastructure server loads, which can be comfortably absorbed by Edge CDNs and in-memory caches.

5. High-Level System Architecture & Data Flows

flowchart TD
    Client["User Client / Browser"] -->|HTTP / HTTPS| CDN["Edge CDN & TLS Termination\n(Cloudflare / Fastly)"]
    CDN --> Gateway["API Gateway & Load Balancer"]
    
    subgraph Read & Write Path Architecture
        Gateway -->|POST /api/v1/shorten| WriteS["URL Creation Service"]
        Gateway -->|GET /{short_key}| ReadS["Redirection Query Service"]
        
        WriteS -->|Pull Pre-Verified Alias| KGS["Key Generation Service (KGS)"]
        WriteS -->|Write Primary Record| KeyValStore[(Primary URL Store\nScyllaDB / DynamoDB)]
        WriteS -->|Write-through Cache| Cache[(Redis Cluster Replicas\nHot URL Storage)]
        
        ReadS -->|1. High-Speed Lookup| Cache
        ReadS -->|2. Fallback Miss Query| KeyValStore
    end
    
    subgraph Asynchronous Real-Time Analytics Pipeline
        ReadS -->|Emit Click Vector| Kafka["Apache Kafka\n(Analytics Event Stream)"]
        Kafka -->|Consume & Aggregate| Flink["Apache Flink Stream Processors"]
        Flink -->|Write Pre-Aggregated Windows| Clickhouse[(ClickHouse / Druid OLAP Database)]
    end

6. Storage Tier Topology

Why select scalable NoSQL / Wide-Column (DynamoDB / ScyllaDB) structures over legacy Relational SQL databases for canonical URL persistence?

1. Zero Relational Joins: The structural domain features a singular, highly decoupled object mapping hierarchy ($(\text{Short Key}) \to (\text{Target Payload})$). Queries do not execute relational joins across multiple distinct schemas during critical routing paths.
2. Horizontal Elasticity: Key-Value engines inherently partition distributed keyspace across arbitrary underlying virtual storage nodes using consistent hashing algorithms, completely eradicating single-node index lock limitations during viral global campaign influxes.
3. Sub-Millisecond Read Latencies: Optimized distributed B-Tree or LSM-Tree read abstractions ensure consistent predictable tail latency thresholds ($p99 < 10\text{ms}$).

7. Production Code: High-Throughput Redirection & Analytics Emitter

The following Python production snippet uses asynchronous event pipelines, optimized Redis connection pooling, and multi-tier memory caching fallback layers to maximize query concurrency.

import asyncio
import time
from typing import Optional, Dict, Any

class KeyGenerationClient:
    def __init__(self, kgs_endpoint: str):
        self.kgs_endpoint = kgs_endpoint
        self.local_key_buffer = []
        self.lock = asyncio.Lock()

    async def get_unique_short_key(self) -> str:
        async with self.lock:
            if not self.local_key_buffer:
                await self.replenish_buffer_from_kgs()
            return self.local_key_buffer.pop()

    async def replenish_buffer_from_kgs(self) -> None:
        # Simulate network RPC call fetching 1000 pre-generated unique alphanumeric Base62 tokens
        await asyncio.sleep(0.02) 
        self.local_key_buffer = [f"k{int(time.time()*1000)}_{i}" for i in range(1000)]


class RedirectionService:
    def __init__(self, redis_client, nosql_client, kafka_producer, kgs_client: KeyGenerationClient):
        self.redis = redis_client
        self.db = nosql_client
        self.kafka = kafka_producer
        self.kgs = kgs_client
        self.cache_ttl = 86400 * 7  # 7 days Hot Key Retention

    async def create_short_url(self, long_url: str, custom_alias: Optional[str] = None, ttl_seconds: Optional[int] = None) -> str:
        """
        Registers new target destination against immutable Base62 short alias.
        """
        if custom_alias:
            # Atomic reservation check for requested custom aliases
            existing = await self.db.get_item(Key={"short_key": custom_alias})
            if existing:
                raise ValueError("Requested custom short alias is currently unavailable.")
            short_key = custom_alias
        else:
            short_key = await self.kgs.get_unique_short_key()

        created_at = int(time.time())
        expires_at = (created_at + ttl_seconds) if ttl_seconds else None

        record = {
            "short_key": short_key,
            "long_url": long_url,
            "created_at": created_at,
            "expires_at": expires_at
        }

        # Simultaneously execute primary permanent persistence and real-time cache warm-up
        await asyncio.gather(
            self.db.put_item(Item=record),
            self.redis.set(f"url:{short_key}", long_url, ex=(ttl_seconds or self.cache_ttl))
        )
        return f"https://short.ly/{short_key}"

    async def execute_redirection(self, short_key: str, client_ip: str, user_agent: str) -> Optional[str]:
        """
        Executes critical sub-millisecond read path with non-blocking analytics streaming.
        """
        cache_key = f"url:{short_key}"
        
        # 1. Hot cache query check
        target_url = await self.redis.get(cache_key)
        
        # 2. Fallback query to underlying canonical persistence table upon cache miss
        if not target_url:
            db_record = await self.db.get_item(Key={"short_key": short_key})
            if not db_record:
                return None  # Link strictly does not exist; trigger 404 handler
                
            # Verify expiration validity constraint
            if db_record.get("expires_at") and int(time.time()) > db_record["expires_at"]:
                return None  # Expired link; trigger termination page
                
            target_url = db_record["long_url"]
            # Proactively re-warm Redis cache to intercept immediate incoming repeated calls
            await self.redis.set(cache_key, target_url, ex=self.cache_ttl)

        # 3. Non-blocking asynchronous analytics firing to Kafka event logs
        asyncio.create_task(self.emit_analytics_event(short_key, client_ip, user_agent))
        
        return target_url

    async def emit_analytics_event(self, short_key: str, ip: str, ua: str) -> None:
        """
        Streams interaction analytics without blocking real-time redirection response timing.
        """
        payload = {
            "timestamp": int(time.time() * 1000),
            "short_key": short_key,
            "ip": ip,
            "user_agent": ua
        }
        # Emits fire-and-forget payload directly into Kafka analytics queue partitions
        await self.kafka.send_and_forget("topic:url_click_events", payload)

8. Edge Cases, Threat Mitigations & Resilience

Cache Stampede on Virally Trending Links

When a global celebrity tweets a shortened link, instant read traffic to that singular target token can surge past $50,000\text{ req/sec}$. If the underlying Redis cache key expires or suffers memory eviction simultaneously, tens of thousands of concurrent database fallback query threads will trigger instantly—a phenomenon known as a Cache Stampede (Thundering Herd).

• Mitigation (Distributed Mutex Locks): Upon experiencing a cache miss, an worker thread executes a localized non-blocking atomic mutex locking acquisition (SETEX lock:url:e7R9pA2 5 1 NX). The single successful winning thread executes the underlying database read query and hydrates the shared cache. The remaining $49,999$ concurrent thwarted worker processes suspend within short loop sleeps ($10\text{ms}$) and successfully retrieve the materialized cached string without hammering backend storage layers.

Phishing, Malware Ingestion & URL Scrubbing

Abusive threat actors frequently abuse public URL shortening engines to disguise malicious ransomware domains or interceptive phishing infrastructures behind reputable shortened brand domains.

• Asynchronous Sandboxed Domain Validation: Rather than blocking user UX workflows by running synchronous external reputation scanning calls during basic creation API execution, newly minted target links ingest into asynchronous worker queues. Workers evaluate target domains against authoritative threat intelligence registries (e.g., Google Safe Browsing API / Custom Domain Reputation Classifiers). Upon tagging positive malicious signatures, the worker immediately flips the record flag to BLOCKED_ABUSE, rendering future redirection attempts directly to security intervention portals.

9. Comprehensive Interview Questions & Answers

Q1: Why should click analytics events stream through Apache Kafka instead of updating an integer increment directly inside the canonical primary database during the redirection execution loop?

Answer: Applying continuous synchronous database UPDATE operations (UPDATE urls SET clicks = clicks + 1 WHERE short_key = ?) on high-traffic links creates intense transactional database row lock contention. During extreme viral surges ($20,000\text{ clicks/sec}$), writing directly to disk throttles redirection speeds, exhausting API connection thread pools and violating our sub-$50\text{ms}$ service level latency limits. Decoupling ingestion by emitting non-blocking asynchronous event payloads into high-throughput Apache Kafka event pipelines guarantees instantaneous zero-latency client redirect execution while allowing analytical processing engines (Flink/ClickHouse) to ingest and aggregate complex attribution metrics downstream at arbitrary speeds.

Q2: How does the platform gracefully prevent abusive automated web scraping engines from methodically enumerating and decoding the global dictionary of generated short link structures?

Answer: Because Base62 short links ($L = 7$) operate across a colossal mathematical permutations field of $\mathbf{3.52\text{ trillion}}$ available slots, allocating merely $12\text{ billion}$ legitimate real-world links implies our spatial dictionary saturation density sits at merely $\approx 0.34\%$. An automated scraping engine generating arbitrary random alphanumeric strings ($62^7$) will statistically hit invalid empty 404 boundaries more than $99.6\%$ of the time. Complementing this inherent entropy distribution, edge routing gateways integrate intelligent dynamic Leaky Bucket rate-limiting frameworks, automatically terminating IP access permissions upon registering repeated consecutive unresolved $404$ redirection error spikes.

Q3: Why avoids relying on database Auto-Increment Primary Keys directly converted into Base62 strings during scalable online record instantiation?

Answer: Relying on standard sequential Relational Auto-Increment sequences induces two monumental design anti-patterns:

1. Predictability / Business Intelligence Exposure: Auto-increment numbers generated consecutively enable competitive surveillance analysis; competitors can create test short links at exactly midnight across successive days, compare integer offsets, and derive explicit real-time enterprise operational growth velocity metrics.
2. Horizontal Distributed Scaling Bottlenecks: A singular database instance attempting to maintain globally authoritative, un-split atomic numerical counters across globally distributed server clusters introduces unbearable database coordination latency bottlenecks. Pre-generating shuffled, mathematically random Base62 tokens offline via a Key Generation Service eradicates numerical sequence pattern discovery while eliminating cross-node distributed lock serialization boundaries.