URL Shortener: Framing, Scale Math, and Architecture

This lesson covers sections 1 to 3 of Chapter 17, Globally Distributed URL Shortener & Analytics, and is part of Part II, Production System Blueprints. The chapter continues in URL Shortener: Deep Dives, Data Models, and Schemas.

1. Executive Summary & The Problem Space

The Scene: The Super Bowl QR Code Meltdown

During the second quarter of the Super Bowl, a major cryptocurrency exchange broadcasts a 30-second commercial consisting entirely of a bouncing colorful QR code on a black screen.

Over 22 million viewers point their smartphones at the television screen simultaneously.

The QR code encodes a single shortened link: https://sho.rt/sb24.

Within eight seconds of the broadcast, the URL shortener's infrastructure collapses into an unrecoverable failure state.

The Senior engineers had built the URL shortener using a traditional relational database backed by an application layer that computed an MD5 hash of the incoming long URL, truncated it to seven characters, and checked the database for collisions before inserting.

Under an onslaught of 450,000 redirect requests per second, the read replica databases suffered complete thread pool saturation. But worse, the marketing team was simultaneously generating millions of personalized campaign links using the shortener API.

The write path locked: every concurrent link creation generated database unique-constraint collisions on truncated hash prefixes. Database CPU pinned at 100%, connection pools dried up, and the edge redirect proxies began returning HTTP 504 Gateway Timeout. Viewers tapping the QR code were greeted with browser error pages. The company spent $14,000,000 on television advertising to broadcast an error screen.

In the post-incident debrief, a Senior engineer suggested setting up a 100-node MySQL Galera cluster with multi-master replication to handle write collisions.

A Staff engineer stepped to the whiteboard: "A URL shortener is not a database problem. It is a distributed ID pre-allocation problem and an edge caching problem. Hashing with collision retries is an anti-pattern that guarantees write failure under concurrency. We should never generate IDs at write time, and the database should never see more than 0.5% of redirect traffic."

The architecture was redesigned around two Staff invariants:

1. Pre-Allocated Range-Leased Key Generation (KGS): A distributed consensus coordinator (ZooKeeper/Raft) leases blocks of 100,000 pre-generated numerical tokens to application nodes. Token assignment is a lock-free, local in-memory operation taking under 0.05 milliseconds with mathematically zero collision probability.
2. Edge Cache-First Redirection with Write-Behind Analytics: Redirects resolve directly out of global edge memory (Redis / Cloudflare Workers) in under 2.0 milliseconds using HTTP 302 Found, while click analytics stream asynchronously to Apache Kafka without delaying the user's browser redirect.

Clarifying Intent: Three Incompatible Shortener Systems

When an interviewer asks you to "Design Bitly" or "Design TinyURL," they are not testing whether you know what Base62 is. They are testing whether you understand how business intent dictates ID predictability, caching semantics, and analytics architecture:

THE THREE URL SHORTENER INTENTS

1. Intent 1: High-Volume Marketing Attribution (The Staff Bitly Standard): The shortener is primarily an analytics and attribution platform. Every single click must be captured, enriched with GeoIP/device data, and aggregated in real time. Requires HTTP 302/307 redirects and asynchronous write-behind telemetry.
2. Intent 2: Ultra-Low-Cost Static Redirection: Optimizes for minimal cloud compute costs. Uses HTTP 301 Moved Permanently so browsers cache the redirect locally, completely eliminating repeat server hits at the cost of losing click analytics.
3. Intent 3: Secure Enterprise Document Links: Short links point to confidential corporate documents, invoices, or reset tokens. Sequential predictability is a critical vulnerability. Requires cryptographic permutation so competitors and attackers cannot crawl links via enumeration attacks.

STAFF MOVE

Senior: "We will hash the long URL using MD5 or SHA-256, take the first 7 characters, and if there is a collision in the database, append a timestamp and re-hash."

Staff: "Hashing with collision checks introduces non-deterministic database round-trips and write lock contention that degrades under concurrency. Furthermore, sequential auto-incrementing counters expose our entire link catalog to competitor enumeration attacks. I will implement a distributed Key Generation Service (KGS) that leases token ranges (100,000 IDs) to application nodes via ZooKeeper/Raft. We will pass numeric IDs through a 64-bit Feistel cipher permutation before Base62 encoding. This guarantees mathematically zero write collisions, lock-free local memory allocation (< 0.05ms), and complete cryptographic unpredictability."

Why: The Staff engineer eliminates database write contention through offline token pre-allocation and addresses security risks upfront.

Scale & Back-of-the-Envelope Economics

To ground the design in hyperscale production realities:

New Short Links Created per Month: 100,000,000 links / month (~40 writes/sec average, 500 writes/sec peak).

Redirect Click Traffic (100:1 Read-to-Write Ratio): 10,000,000,000 clicks / month.

Peak Redirect Query Rate (QPS):

Average QPS = 10,000,000,000 / (30 * 86,400) = ~3,850 QPS . Peak traffic spike (10x marketing event) = 38,500 Redirect QPS (or up to 100,000 QPS during global viral surges).

10-Year Link Storage Footprint:

100,000,000 links/month × 12 months × 10 years = 12,000,000,000 total URLs (12 Billion).

Base62 Key Length Mathematics:

Base62 uses [a-z, A-Z, 0-9] (62 characters).

62^6 = 56,800,235,584 (56.8 Billion unique keys).

62^7 = 3,521,614,606,208 (3.52 Trillion unique keys).

A 7-character Base62 string provides 3.52 trillion unique combinations—sufficient to sustain 100 million writes per month for over 2,900 years!

Database Storage Volume:

• short_code : 7 bytes
• original_url : ~500 bytes (average)
• user_id : 8 bytes
• created_at : 8 bytes

Total per record: ~550 bytes.

12 Billion records × 550 bytes = 6.6 Terabytes total storage over 10 years! (Easily fits across a sharded PostgreSQL cluster or Amazon DynamoDB).

SCALE & HARDWARE CAPACITY REQUIREMENTS

2. Requirements & High-Level Architecture

Functional Requirements

1. URL Shortening: Given an arbitrary long URL, generate a globally unique 7-character short URL (https://sho.rt/7wK9xQ ).
2. High-Speed Redirection: When a user accesses a short URL, redirect their browser to the original long URL within 10 milliseconds.
3. Real-Time Click Analytics: Track total clicks, geographic location (country/city), referring domain, device OS, and browser type, visible on a dashboard within 2 seconds.
4. Link Management & Expiration: Creators can optionally specify an expiration timestamp or custom vanity alias (e.g. sho.rt/blackfriday ).

Non-Functional Requirements (Staff Invariants)

1. Sub-10ms P99 Redirect Latency: The redirect must feel instantaneous to the user.
2. Zero Write Collision Invariant: The link creation service must never fail due to ID collisions, even under concurrent write spikes.
3. Non-Predictable Keys (Anti-Scraping): Short codes must not be sequential. It must be computationally infeasible for a third party to enumerate or scrape private links.
4. 99.999% Read Availability: Link redirection must remain operational even during database maintenance or regional network outages.

3. End-to-End System Architecture

The architecture isolates the low-latency, read-heavy Redirect Serving Tier from the offline Key Generation Service (KGS) and the asynchronous Clickstream Analytics Pipeline:

Figure 17.1: End-to-End Globally Distributed URL Shortener & Real-Time Analytics Pipeline

Architectural Components in Depth

COMPONENT 1: CLIENT & ANYCAST EDGE REDIRECT PROXY

The high-throughput ingress gateway terminating incoming redirect clicks and management API requests:

• BGP Anycast Ingress: Announces a single shared Anycast IPv4/IPv6 address across 300+ global Edge Points of Presence (Cloudflare Workers, Fastly Compute, or AWS CloudFront edge). A user in Singapore routes directly to the Singapore edge gateway within 5ms.
• Edge TLS 1.3 Termination & 0-RTT: Terminates TLS handshakes at the edge, eliminating cross-continental round-trips to central origin servers and saving 120–180ms of latency per click.
• HTTP 302 Found Redirection Engine: Emits an immediate HTTP 302 Found (or 307 Temporary Redirect) header Location: https://target-destination.com/landing with Cache-Control: private, max-age=90. This ensures browsers do not permanently cache the destination, preserving attribution tracking on subsequent visits.
• Edge Anti-Phishing Bloom Filter: Checks incoming short codes against an in-memory 50MB Counting Bloom filter containing millions of known malicious URLs (flagged by Google Safe Browsing / PhishTank). Blocked URLs return an immediate HTTP 403 Forbidden intercept page.

COMPONENT 2: DISTRIBUTED EDGE CACHE (REDIS CLUSTER / EDGE KV)

The primary in-memory caching tier designed to absorb over 99.2% of global read traffic:

• Geo-Distributed Edge KV Deployment: Deployed as local Redis Sentinel/Cluster nodes or distributed Key-Value stores (Cloudflare KV / DynamoDB Global Tables) directly inside edge PoP zones.
• Memory-Packed String Layout: Key = u:{short_code}, Value = {long_url}. Using raw binary strings keeps memory overhead under 120 bytes per cached record.
• Sub-2ms Lookup SLA: Resolves 99.2% of redirect queries in < 1.8 milliseconds directly from edge RAM.
• SingleFlight Coalescing on Cache Miss: When a viral short link experiences a cache miss across thousands of concurrent edge worker threads, the proxy locks the key locally and dispatches exactly one upstream database query. All other 9,999 threads await that single result, shielding the origin database from thundering herd spikes.
• Segmented LRU Eviction & 7-Day TTL: Inactive links naturally evict after 7 days, ensuring that edge RAM only holds active working sets.

COMPONENT 3: URL SHORTENER WRITE SERVICE

The stateless application tier that ingests long URLs and provisions unique short links:

• API Endpoint: Exposes POST /v1/shorten behind rate limiters (e.g., maximum 50 links/minute per IP, 10,000 links/minute per authenticated enterprise API key).
• Zero-Coordination Local Token Allocation: Maintains an in-memory token buffer pre-leased from the Key Generation Service (KGS). When a request arrives, the service atomically increments a local memory counter (atomic.AddUint64(&local_counter, 1)). Generating a new unique link requires zero network hops and zero database coordination!
• Dual-Write Pipeline: Writes the new URL entity to the persistent database and synchronously populates the local edge cache, guaranteeing that the link resolves instantly on the very first click.
• Custom Vanity Slug Engine: If a customer requests a custom alias (sho.rt/summer-sale ), the service bypasses the KGS token pool and executes an atomic conditional insert (INSERT ... ON CONFLICT DO NOTHING) against the database to guarantee global uniqueness.

COMPONENT 4: SHARDED URL RELATIONAL STORE (POSTGRESQL / DYNAMODB)

The authoritative persistent system of record for billions of shortened links:

• Horizontal Sharding via Consistent Hashing: Sharded across 64 database nodes partitioned on hash(short_code) % 64.
• Append-Only Immutability: URL mappings are treated as immutable facts. The primary table contains (id, short_code, original_url, account_id, created_at, expires_at). Modifying a destination URL creates a new version record rather than overwriting historical rows.
• Cross-Region Asynchronous Read Replicas: The primary cluster in US-East replicates asynchronously to Europe and Asia-Pacific read replicas with sub-second replication lag, providing ultra-low latency fallback when edge caches miss.

COMPONENT 5: KEY GENERATION SERVICE (KGS) & RANGE LEASING

The centralized authority that guarantees 100% collision-free token distribution:

• Consensus-Backed Global Counter: Uses a highly available Apache ZooKeeper or Etcd cluster holding a persistent 64-bit integer counter.
• Block Range Leasing Protocol: When a Write Service pod boots up, it requests a token block lease from the KGS. The KGS atomically increments the master counter by 100,000 and grants the range: [RangeStart: 50,000,000, RangeEnd: 50,100,000].
• Zero Lock Contention: The application server exhausts its 100,000 tokens locally in RAM without ever contacting the KGS again. When the local buffer reaches 80% capacity, the server asynchronously requests the next block in the background.
• Crash Recovery & Capacity Buffer: If a server crashes mid-range, unused tokens are simply abandoned. In a 7-character Base62 keyspace (62^7 = 3.52 trillion links), losing 50,000 tokens consumes only 0.0000014% of the keyspace—a negligible cost for total lock-free concurrency!

COMPONENT 6: WRITE-BEHIND CLICKSTREAM BUS (APACHE KAFKA)

The non-blocking telemetry ingestion engine:

• Asynchronous Fire-and-Forget Egress: When the Edge Redirect Proxy issues an HTTP 302 response to the user, it immediately emits a binary Protobuf ClickEvent into a local non-blocking ring buffer. The user receives their redirect without waiting for analytics processing.
• Key-Partitioned Topic: Published to Kafka topic url.clicks.raw partitioned by hash(short_code) % num_partitions. This ensures all clicks for a specific link land on the same partition in chronological order.
• Surge Buffering: Absorbs global traffic spikes up to 250,000 events/second without dropping events or exerting backpressure on user-facing redirection proxies.

COMPONENT 7: COLUMNAR ANALYTICS STORE (CLICKHOUSE) & DASHBOARD

The real-time business intelligence and campaign attribution engine:

• Stream Processing Consumers: Horizontally scaled Apache Flink consumers consume raw click events from Kafka in micro-batches (e.g., 20,000 events or 1-second tumbling windows).
• Metadata Enrichment: Performs zero-copy lookups against an in-memory MaxMind GeoIP database to resolve IP to Country/City/ASN and decodes User-Agent strings into browser, operating system, and device type.
• Columnar MergeTree Engine: Writes enriched records to a ClickHouse cluster utilizing the ReplacingMergeTree storage engine, achieving 12x data compression compared to row stores.
• Materialized Rollup Views: Maintains pre-aggregated 1-minute, 1-hour, and 1-day rollups (clicks_by_country_hourly, clicks_by_device_daily), enabling marketing analytics dashboards to scan 100,000,000 historical clicks in sub-25 milliseconds.

ByteByteGo-Style Step-by-Step Shortening & Clickstream Flow

To master the Staff interview, walk the interviewer through the two distinct lifecycles: Link Creation and Link Redirection:

STEP-BY-STEP LINK CREATION & REDIRECT CLICK FLOW

flowchart LR
    subgraph CREATE["CREATION FLOW"]
        C1["Client"] -->|"(1) POST /v1/shorten"| WS["Write Service"]
        WS --> W2["(2) Claims local leased token (no KGS wait)"]
        WS --> W3["(3) Applies Feistel cipher + Base62"]
        WS --> W4["(4) Writes to PostgreSQL primary"]
        WS --> W5["(5) Warms Edge Redis Cache (sub-5ms)"]
    end
    subgraph REDIRECT["REDIRECTION & CLICKSTREAM FLOW"]
        V1["Viewer"] -->|"(1) GET sho.rt/7wK9xQ"| EP["Anycast Edge Proxy"]
        EP --> R2["(2) Checks Edge Redis Cache (<1.8ms hit)"]
        EP --> R3["(3) Returns HTTP 302 Found to Viewer"]
        EP --> R4["(4) Asynchronously emits ClickEvent to Kafka [Topic: url.clicks.raw]"]
        R4 --> R5["(5) Flink filters bots & enriches"]
        R5 --> CH["ClickHouse Columnar Storage"]
    end

STEP 1: LINK CREATION INGESTION & AUTHENTICATION

The client application submits POST /v1/shorten { "url": "https://company.com/promo" }. The Write Service validates OAuth2 credentials and checks account rate limits.

STEP 2: ZERO-COORDINATION LOCAL TOKEN CLAIM

The service fetches the next sequential 64-bit integer from its pre-leased local RAM buffer (e.g., 1,000,042 ) in under 10 nanoseconds without network hops.

STEP 3: FEISTEL CIPHER SCRAMBLING & BASE62 ENCODING

The service feeds the sequential ID through a 4-round Feistel permutation to prevent link enumeration, producing pseudo-random integer 2,847,192,831 , which encodes into the 7-character Base62 string "7wK9xQ".

STEP 4: PERSISTENT RELATIONAL COMMIT

The service commits the mapping ("7wK9xQ", "https://company.com/promo") to the primary sharded PostgreSQL cluster with read-after-write guarantees.

STEP 5: EDGE CACHE WARMING & HTTP 201 RESPONSE

The service writes the mapping synchronously to the local Edge Redis cache and returns HTTP 201 Created { "short_url": "https://sho.rt/7wK9xQ" } to the client in < 5ms.

STEP 6: EDGE REDIRECT REQUEST EVALUATION

A user clicks sho.rt/7wK9xQ. The request reaches the nearest Anycast Edge Proxy, which queries its local in-memory Redis cluster.

STEP 7: SUB-2MS REDIRECTION DELIVERY

Redis returns the target URL from local RAM in < 1.8ms. The edge proxy immediately emits an HTTP 302 Found with Location: https://company.com/promo.

STEP 8: ASYNCHRONOUS NON-BLOCKING ANALYTICS EGRESS

The edge proxy enqueues a binary Protobuf click record <IP, UserAgent, Timestamp, "7wK9xQ"> into an asynchronous buffer and streams it to Kafka topic url.clicks.raw.

STEP 9: STREAM ENRICHMENT & COLUMNAR STORAGE ROLLUP

Apache Flink workers consume the clickstream, filter crawler traffic, resolve GeoIP locations, and stream micro-batches into ClickHouse ReplacingMergeTree tables and pre-aggregated materialized views for instant dashboard querying.