Distributed URL Shortener: Base62 Token Generation, Range Allocation, and Low-Latency Redirection

1. Problem and Motivation

URL shortening services—exemplified by TinyURL, Bitly, and Twitter’s t.co wrapper—perform an apparently elementary task: take an arbitrary long URL (such as https://example.com/products/electronics/item-9842104-special-offer?source=newsletter&campaign=summer_2026), assign it a compact slug (such as https://short.ly/7xQ9pA2), and immediately redirect any client visiting that short URL to the original destination.

However, operating a redirection engine at planetary scale presents severe engineering challenges:

1. Extreme Asymmetric Read-to-Write Ratio: Redirection systems typically operate at a 100:1 to 500:1 read-to-write ratio. While link creation might run at 1,000 writes per second, redirection requests frequently exceed 100,000 to 500,000 reads per second during breaking news, viral social posts, or global marketing blasts.
2. Strict Latency SLA: A redirection hop adds friction to every page load. The service must resolve the short token and respond with an HTTP redirect within sub-10ms at p99, including global network traversal.
3. Infinite Key Retention & Zero Collisions: Short URLs are embedded in printed billboards, SMS messages, books, and legacy web links. Over a 10-year lifespan, tens of billions of unique tokens must remain permanently resolvable without duplicate slug collisions.
4. Real-Time Clickstream Telemetry: Link creators demand real-time analytics: total click counts, referral domains, geographic distributions, browser user-agents, and timestamp histograms. Tracking clicks must never add latency to the user’s redirect path.
5. Malicious Link & Penetration Protection: Attackers routinely generate synthetic random short tokens to probe for hidden links or purposefully cause cache penetration—forcing cache misses that exhaust primary database disk IOPS.

+-------------------------------------------------------------------------------------------------+
|                                    NAIVE URL SHORTENING PITFALLS                                 |
+-------------------------------------------------------------------------------------------------+
|  1. Auto-Incrementing Integer: Monolithic DB bottleneck; trivial ID enumeration leaks business |
|     volume and competitor metrics (predictable URL scanning).                                   |
|  2. MD5 / SHA-256 Truncation: Birthday Paradox causes rapid collisions after a few million keys; |
|     costly database probe-and-retry loops degrade write latency.                                |
|  3. Centralized Database Reads: Database connections saturate instantly under viral spikes;      |
|     lack of multi-tier caching yields multi-second timeouts.                                    |
|  4. Synchronous Click Logging: Writing analytics to a relational DB in the redirect request loop |
|     amplifies latency 10x and turns DB write lock contention into full service outage.          |
+-------------------------------------------------------------------------------------------------+

2. Mental Model & Architectural Overview

The core architecture decouples Token Generation (Write Path), Redirection Resolution (Read Path), and Clickstream Telemetry (Asynchronous Analytics) into autonomous, horizontally scalable tiers.

SYSTEM ARCHITECTURE BLUEPRINTAPPLICATION ARCHITECTURES

⤢Expand

ARCHITECTURAL FLOW · STEP 1 OF 3

1. API Client / Web User & ZooKeeper / etcd Range Coordinator

Establishes the ingress and structural boundary across API Client / Web User & ZooKeeper / etcd Range Coordinator: POST /api/v1/shorten; { "url": "https://example.com/very/long..." }; Leases atomic non-overlapping ID blocks.

Architectural Invariant: Local in-memory AtomicInteger increment Counter = 1,000,042 → Base62.

ARCHITECTURAL FLOW · STEP 2 OF 3

2. Browser / Mobile User & Edge Bloom Filter (Fast-Path Guard)

Coordinates core data-plane execution and state transitions through Browser / Mobile User & Edge Bloom Filter (Fast-Path Guard): GET /4c9Q7aZ (100k+ req/sec); Host: short.ly; Check if token is known (k=7 hash functions).

Architectural Invariant: Redirects client browser to destination.

ARCHITECTURAL FLOW · STEP 3 OF 3

3. Asynchronous Event Dispatch & Kafka Partitioned Log

Enforces durability, state convergence, and output verification across Asynchronous Event Dispatch & Kafka Partitioned Log: Fire-and-forget payload: token, timestamp, IP, User-Agent, referer, geo_country; Topic: `url-click-events`; Partitioned by `hash(short_code)` High-throughput disk append.

Architectural Invariant: Real-time click graphs & geo-maps.

The Architectural Tiers

1. Write Path (Token Generation):
   • Client sends long URL to Write API Gateway.
   • The Token Generation Service (TGS) acquires an exclusive, non-overlapping numeric ID block (e.g., [10,000,000 - 11,000,000)) from a distributed consensus coordinator (ZooKeeper or etcd).
   • The TGS service increments a local in-memory counter (AtomicLong) and encodes the resulting 64-bit integer into a Base62 alphanumeric token ([0-9a-zA-Z]).
   • The token mapping is persisted to a distributed primary Key-Value store (ScyllaDB / DynamoDB), written to a Redis cluster, and recorded in an edge Bloom filter.
2. Read Path (Ultra-Low Latency Redirection):
   • The edge DNS routes the user request via Anycast to the nearest CDN Edge Point of Presence (PoP).
   • If the token is not cached at the edge, an Edge Bloom Filter verifies whether the token exists. If the filter returns false, the request is rejected immediately with HTTP 404 Not Found—completely shielding backing caches and databases from cache penetration attacks.
   • If present in the Bloom filter, the Redis Cluster (or local in-memory cache) provides the long URL in $<2\text{ ms}$.
   • If a cache miss occurs, the Redirection Service reads the master key-value database, populates the Redis cache, and returns an HTTP redirect.
3. Asynchronous Clickstream Pipeline:
   • The Redirection Service emits an asynchronous event to an Apache Kafka topic (url-click-events) containing timestamp, token, client IP, User-Agent, and Referer headers.
   • Stream processing engines (Apache Flink) aggregate click metrics over sliding/tumbling windows.
   • Aggregated metrics are stored in a columnar analytical database (ClickHouse) powering real-time customer dashboards.

3. Terminology & Core Mechanics

• Base62 Encoding: An alphanumeric positional numeral system utilizing characters 0-9, a-z, and A-Z ($62$ symbols). Unlike Base64, Base62 omits special characters (+, /, =) that require URL percent-encoding or conflict with path delimiters.
• Birthday Paradox: Under uniform random sampling over $H$ possible outputs ($N\ll H$), the probability that at least two items collide reaches $50\%$ at $N_{0.5}\approx \sqrt{2H\ln 2}\approx 1.1774\sqrt{H}$—orders of magnitude earlier than $H/2$.
• Monotonic Range Coordinator: A consensus-backed state store (ZooKeeper or etcd) that advances a persistent high-water mark via atomic compare-and-swap (CAS) to hand out permanently disjoint numeric ID blocks.
• HTTP 301 (Moved Permanently): Instructs browsers and intermediary caches that the resource has permanently moved; clients cache the redirect locally, bypassing the shortener on subsequent clicks.
• HTTP 302 (Found) / HTTP 307 (Temporary Redirect): Directs the client to the destination temporarily; paired with Cache-Control: private, no-store, every click traverses the redirection tier for accurate telemetry.
• Cache Penetration: A traffic pattern or attack querying keys that exist neither in cache nor in primary storage, causing every lookup to miss cache and hit disk I/O unless filtered at the edge.
• Bloom Filter: A compact probabilistic bit array testing set membership with zero false negatives and tunable false-positive probability $p$.

4. Token Generation Algorithms: Hash Truncation vs. Monotonic Range Allocation

A central architectural decision is how to map each write request to a unique 7-character Base62 slug.

Approach 1: Cryptographic Hash Truncation (MD5 / SHA-256)

A naive design hashes the destination URL with SHA-256, interprets a slice of the digest in Base62, and truncates to the first 7 characters:

Why Hash Truncation Degrades at Scale:

1. The Birthday Paradox Collision Threshold: A 7-character Base62 token space contains $H=62^7=3,521,614,606,208\approx 3.5216\times 10^{12}$ distinct slugs (${\log }_2(62^7)\approx 41.68\text{ bits}$). Assuming (a) uniform, independent hash outputs across all $H$ buckets and (b) $N\ll H$ so $\ln (1-k/H)\approx -k/H$, the probability of observing at least one collision across $N$ generated URLs is: $$P(\text{at least one collision})=1-\prod _{k=0}^{N-1}\left(1-\frac{k}{H}\right)\approx 1-\exp \left(-\frac{N(N-1)}{2H}\right)\approx 1-\exp \left(-\frac{N^2}{2H}\right)$$ Solving $1-e^{-N^2/(2H)}=0.50$ gives $N^2=2H\ln 2$: $$N_{0.50}\approx \sqrt{2H\ln 2}=\sqrt{2\times 3.5216\times 10^{12}\times 0.69315}\approx 2.21\times 10^6\text{ URLs}$$ (Note: Omitting the $\ln 2\approx 0.69315$ factor yields $\sqrt{2H}\approx 2.65\times 10^6$, which corresponds to a $1-e^{-1}\approx 63.2\%$ collision probability rather than $50\%$.) Thus, the very first duplicate slug becomes more likely than not after just 2.21 million URLs—less than 37 minutes of writes at $1,000\text{ writes/sec}$! Furthermore, as the repository grows to $M$ stored URLs, every individual new insert suffers a per-write collision probability of $P_{\text{write\_collision}}=M/H$ (reaching $0.28\%$ at $10\text{B}$ URLs and $28.4\%$ at $1\text{T}$ URLs).
2. Synchronous Read-Before-Write Retry Amplification: Because collisions are inevitable, every hash-based write must execute a conditional database uniqueness check (INSERT ... ON CONFLICT or quorum Compare-And-Swap). Upon collision, the server must append a deterministic or random salt, re-hash, and probe storage again: $${\text{Token}}_2=\text{Base62}(\text{SHA256}(\text{URL}\parallel {\text{salt}}_1))[\mathrm{0..6}]$$ In distributed wide-column stores (Cassandra / ScyllaDB), conditional Lightweight Transactions (Paxos/Raft LWT) cost 3–4x the latency of blind partition writes.
3. Multi-Tenant Analytics Isolation: If two marketing teams shorten https://example.com/launch, deterministic URL hashing produces the identical slug, merging their clickstream analytics and making per-customer link deletion or target editing impossible unless a unique request nonce is salted into every hash.

Approach 2: Monotonic Counter Range Allocation (ZooKeeper / etcd)

Instead of truncating hashes, we assign each URL a strictly unique non-negative integer $id\in [0,62^7-1]$ and apply a bijective Base62 encoding. Because Base62 encoding is a one-to-one mapping over $[0,62^7-1]$, token collisions are mathematically zero ($P_{\text{collision}}=0$)—allowing blind, lock-free database inserts!

To eliminate a single-database sequence bottleneck, we partition the integer space into contiguous blocks via Monotonic Range Allocation:

+-----------------------------------------------------------------------+
|              ETCD / ZOOKEEPER MONOTONIC RANGE COORDINATOR             |
|         Durable High-Water Mark: `/url-shortener/next-id-hwm`         |
+-----------------------------------------------------------------------+
                 |                                      |
      Atomic CAS Claim (+1M):                Atomic CAS Claim (+1M):
       [1,000,000 - 2,000,000)                [2,000,000 - 3,000,000)
                 v                                      v
+-------------------------------+      +-------------------------------+
|   Token Generator Node A      |      |    Token Generator Node B     |
| - Local Atomic Counter: 1.0M  |      | - Local Atomic Counter: 2.0M  |
| - Next: 1,000,001 -> '0004c93'|      | - Next: 2,000,001 -> '0008oi5'|
| - ~20 ns local RAM increment  |      | - ~20 ns local RAM increment  |
+-------------------------------+      +-------------------------------+

Range Allocation Lifecycle, Crash Semantics & Keyspace Bounds:

1. Atomic High-Water Mark Claim (Why Ranges Must Never Be Recycled on Lease Expiry): When a Token Generator Service (TGS) worker boots, it executes a linearizable Compare-And-Swap (Txn in etcd or setData with version check in ZooKeeper) advancing a persistent high-water mark by BLOCK_SIZE ($B$, typically $100,000$ to $1,000,000$): $$[\text{start},\text{end})=[\text{HWM},\text{HWM}+B),\text{HWM}\leftarrow \text{HWM}+B$$ Critical Invariant: Unlike distributed mutex locks, numeric ID ranges must never use TTL lease expiry to reclaim and re-issue unused IDs. If a coordinator reclaimed [1,000,000, 2,000,000) after a 15-second heartbeat timeout while Node A was merely frozen in a Stop-The-World GC pause or asymmetric network partition, Node A would wake up and emit duplicate IDs concurrently with the new owner (split-brain collision). Permanently advancing HWM eliminates split-brain collisions without needing per-write storage fencing tokens.
2. Sub-Microsecond Local Allocation & Asynchronous Prefetch: Workers increment an in-memory atomic counter in $<20\text{ ns}$ with zero network RPCs on the request path. When remaining capacity drops below $20\%$ ($0.2B$), a background task prefetches a standby block [start_2, end_2) so block transitions add zero tail latency.
3. Node Crash, Restart & Block-Size Sizing Against the 7-Character Base62 Ceiling: When a worker crashes or restarts during deployments, it holds no local disk state; any unconsumed IDs in its in-memory [currentId, rangeEnd) window (on average $B/2$ IDs per restart) are permanently burned, and the rebooted pod claims a fresh block from HWM. Important Keyspace Distinction: Although the counter is stored in a 64-bit integer ($2^{64}\approx 1.84\times 10^{19}$), a strict 7-character Base62 slug caps the usable keyspace at $62^7=3,521,614,606,208\approx 3.52\times 10^{12}$ ($\approx 2^{41.68}$), not $1.84\times 10^{19}$! Once id >= 62^7, Base62 encoding widens to 8 characters. Let us check whether crash burn threatens the 7-character ceiling:
   • With $B=100,000$, the 7-character keyspace contains $3.5216\times 10^{12}/10^5=35,216,146$ blocks.
   • Even if a 50-node TGS fleet restarts twice daily for 10 years ($365,000$ restarts, burning an average of $50,000$ IDs each), total burned IDs equal $1.825\times 10^{10}$—just $0.52\%$ of the 7-character keyspace!
4. Local Block Exhaustion During Coordinator Outage & Global Keyspace Exhaustion:
   • Local Exhaustion: At $1,000\text{ writes/sec}$ across 20 workers ($50\text{ writes/sec/worker}$), a $B=100,000$ active block plus a $100,000$ prefetched standby block provides up to 66 minutes of autonomous write survivability during a total etcd/ZooKeeper quorum outage. If quorum remains down after both blocks drain, the worker fails closed on writes (HTTP 503 Service Unavailable with Retry-After), never guessing IDs, while the read redirection path ($99\%$ of traffic) continues $100\%$ unaffected.
   • Global Exhaustion: Monitoring alerts fire when HWM / 62^7 crosses $70\%$ and $85\%$. Because Base62 decoding is length-agnostic, crossing $62^7-1$ seamlessly emits 8-character tokens ($62^8\approx 2.18\times 10^{14}$, a $62\times$ expansion) with zero downtime for existing 7-character links.
5. Preventing Sequential Enumeration: Raw monotonic counters (0000001, 0000002) leak creation volume and allow scrapers to enumerate consecutive links. Passing the integer through a cycle-walking 42-bit bijective Feistel cipher (or Format-Preserving Encryption over $[0,62^7-1]$) before Base62 encoding scrambles sequential IDs into pseudorandom-looking slugs while preserving strict $P_{\text{collision}}=0$.

5. Mathematical Derivations & Capacity Planning

Let us evaluate the mathematics of a global URL shortener supporting 10 billion URLs over 5 years and handling 100,000 read requests/sec and 1,000 write requests/sec.

1. Token Length & Base62 Combinatorial Space

Characters available in Base62: $$\Sigma =\{\mathrm{0..9},a..z,A..Z\}⟹|\Sigma |=10+26+26=62$$

For a token of length $L$: $$\text{Total Combinations}=62^L$$

A length of $L=7$ characters safely accommodates 3.52 trillion URLs while keeping the link short enough to fit inside SMS character limits.

2. Storage Estimation

Suppose each record stores:

• short_code: 7 bytes (ASCII)
• original_url: 500 bytes (average)
• created_at: 8 bytes (int64 timestamp)
• user_id: 16 bytes (UUID)
• expiration_date: 8 bytes (int64 timestamp)
• Overhead & B-Tree / SSTable indexing metadata: $\approx 100\text{ bytes}$

For 10 billion URLs: $$\text{Raw Storage}=10^{10}\times 650\text{ bytes}=6.5\times 10^{12}\text{ bytes}=6.5\text{ TB}$$

With 3x distributed replication factor ($R=3$): $$\text{Total Disk Storage}=6.5\text{ TB}\times 3=19.5\text{ TB}$$

19.5 TB of storage is remarkably modest and easily fits on a small cluster of NVMe SSD nodes (e.g., 4 nodes with 8 TB NVMe each).

3. Read & Write Throughput

• Write QPS: $$\text{Writes}=1,000\text{ requests/sec}$$ $$\text{Write Bandwidth}=1,000\times 650\text{ bytes}=650\text{ KB/sec}\approx 5.2\text{ Mbps}$$

• Read QPS (Redirections): $$\text{Reads}=100,000\text{ requests/sec}$$ $$\text{Read Egress (HTTP Response Headers }\approx 500\text{ bytes)}=100,000\times 500\text{ bytes}=50\text{ MB/sec}=400\text{ Mbps}$$

4. Cache Memory Sizing (80-20 Pareto Principle)

In URL redirection, traffic adheres strictly to the Pareto distribution: 20% of the short URLs generate 80% of total read traffic.

We size the Redis cache to hold the active 20% of URLs requested per day: $$\text{Daily Read Requests}=100,000\text{ req/sec}\times 86,400\text{ sec}=8.64\times 10^9\text{ requests/day}$$

Unique URLs visited per day ($\approx 10\%$ of requests): $$\text{Unique Visited URLs}=8.64\times 10^8\text{ URLs}$$

Caching 20% of the active daily links: $$\text{Cached URLs}=0.20\times (8.64\times 10^8)=1.728\times 10^8\text{ URLs}$$

RAM required in Redis cluster: $$\text{Memory}=1.728\times 10^8\times 650\text{ bytes}\approx 112.3\text{ GB of RAM}$$

A small 3-node Redis cluster with 64 GB RAM per node provides 192 GB total capacity—comfortably delivering a $>95\%$ cache hit rate with sub-2ms response latency.

6. Design Alternatives & Architectural Trade-Offs: HTTP Semantics and ID Generators

6.1 Token Generation Strategy Trade-Off Matrix

6.2 Redirection Semantics: HTTP 301 vs. HTTP 302 / 307

When a browser requests https://short.ly/7xQ9pA2, the server issues an HTTP redirection header. Choosing between status code 301 and 302 (or 307) governs both origin load and analytics fidelity:

+---------------------------------------------------------------------------------------------------+
|                                  HTTP 301 vs HTTP 302 COMPARISON                                  |
+---------------------------------------------------------------------------------------------------+
| Feature               | HTTP 301 Moved Permanently             | HTTP 302 Found (Temporary)       |
+-----------------------+----------------------------------------+----------------------------------+
| Client Caching        | Browser aggressively caches redirect;  | Browser NEVER caches; every click|
|                       | subsequent visits bypass shortener.    | hits the redirection server.     |
| Server Load           | Minimum (Zero server load on re-visit) | High (Every visit requires hit)  |
| Analytics Accuracy    | Inaccurate: Only 1st visit is counted. | 100% Exact: All clicks captured. |
| URL Modification      | Impossible to change long destination. | Creator can update target URL.   |
| Search Engine SEO     | Passes PageRank to destination URL.    | Does not pass PageRank.          |
+-----------------------+----------------------------------------+----------------------------------+

The Production Consensus:

Commercial platforms (Bitly, TinyURL) choose HTTP 302 Found (or HTTP 307 Temporary Redirect) because link creators require granular analytics (click counts by country, device, referrer).

If server bandwidth conservation is paramount and analytics tracking is not required, HTTP 301 is preferred.

HTTP/1.1 302 Found
Location: https://example.com/products/item-9842104
Cache-Control: private, no-cache, no-store, max-age=0
Date: Fri, 31 Oct 2026 10:15:00 GMT
Content-Length: 0

7. Production Implementation: Range Lease Coordinator & Base62 Code Engine

The following production-grade TypeScript implementation demonstrates:

1. The Base62 Bijective Encoder/Decoder.
2. The Distributed Token Range Coordinator managing atomic ranges with prefetching.
3. The Redirection Service with cache-aside and async event dispatch.

/**
 * Production Distributed URL Shortener Engine
 * Implements Base62 bijective mapping and atomic Range Lease allocation.
 */

export class Base62Encoder {
  private static readonly ALPHABET =
    '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
  private static readonly BASE = 62n;
  // Exact 7-character Base62 ceiling: 62^7 - 1 = 3,521,614,606,207
  public static readonly MAX_SEVEN_CHAR_ID = 62n ** 7n - 1n;

  /**
   * Encodes a non-negative integer into a Base62 token (7 chars up to 62^7 - 1; widens to 8+ above).
   */
  public static encode(id: bigint, minLength = 7): string {
    if (id < 0n) throw new Error('ID must be a non-negative integer');
    if (id === 0n) return this.ALPHABET[0].repeat(minLength);

    const chars: string[] = [];
    let current = id;

    while (current > 0n) {
      const remainder = Number(current % this.BASE);
      chars.push(this.ALPHABET[remainder]);
      current = current / this.BASE;
    }

    let result = chars.reverse().join('');
    // Pad left to preserve fixed token width
    if (result.length < minLength) {
      result = this.ALPHABET[0].repeat(minLength - result.length) + result;
    }
    return result;
  }

  /**
   * Decodes a Base62 token back to a 64-bit integer ID.
   */
  public static decode(token: string): bigint {
    let id = 0n;
    for (let i = 0; i < token.length; i++) {
      const char = token[i];
      const val = BigInt(this.ALPHABET.indexOf(char));
      if (val === -1n) throw new Error(`Invalid Base62 character: ${char}`);
      id = id * this.BASE + val;
    }
    return id;
  }
}

/**
 * Mock Distributed Coordinator (ZooKeeper / etcd atomic sequence)
 */
export class DistributedRangeCoordinator {
  private globalCounter = 10_000_000n; // Initial offset
  private readonly blockSize = 1_000_000n; // 1M IDs per lease

  public async acquireNextRange(): Promise<{ start: bigint; end: bigint }> {
    // In production: ZooKeeper atomic CAS on /url-shortener/range-lease
    const start = this.globalCounter;
    this.globalCounter += this.blockSize;
    const end = this.globalCounter;
    return { start, end };
  }
}

/**
 * Local Worker Token Generator Service
 */
export class TokenGeneratorService {
  private currentId = 0n;
  private rangeEnd = 0n;
  private isPrefetching = false;
  private nextRangePromise: Promise<{ start: bigint; end: bigint }> | null = null;

  constructor(private readonly coordinator: DistributedRangeCoordinator) {}

  public async initialize(): Promise<void> {
    const range = await this.coordinator.acquireNextRange();
    this.currentId = range.start;
    this.rangeEnd = range.end;
  }

  /**
   * Generates next guaranteed-unique Base62 token in sub-microsecond local RAM.
   */
  public async generateNextToken(): Promise<string> {
    // Trigger asynchronous background prefetch when 80% through current block
    const remaining = this.rangeEnd - this.currentId;
    if (remaining < 200_000n && !this.isPrefetching) {
      this.isPrefetching = true;
      this.nextRangePromise = this.coordinator.acquireNextRange();
    }

    // Exhausted current range - switch to pre-fetched block
    if (this.currentId >= this.rangeEnd) {
      if (!this.nextRangePromise) {
        this.nextRangePromise = this.coordinator.acquireNextRange();
      }
      const newRange = await this.nextRangePromise;
      this.currentId = newRange.start;
      this.rangeEnd = newRange.end;
      this.isPrefetching = false;
      this.nextRangePromise = null;
    }

    const assignedId = this.currentId;
    this.currentId += 1n;

    return Base62Encoder.encode(assignedId);
  }
}

/**
 * Redirection Engine & Cache-Aside Handler
 */
export interface UrlRecord {
  shortCode: string;
  originalUrl: string;
  createdAt: number;
}

export class RedirectionEngine {
  constructor(
    private readonly redisCache: Map<string, string>,
    private readonly primaryDatabase: Map<string, UrlRecord>,
    private readonly clickStreamProducer: (event: object) => void
  ) {}

  public async resolveRedirect(
    shortCode: string,
    clientContext: { ip: string; userAgent: string; referer: string }
  ): Promise<{ status: 301 | 302; destinationUrl: string } | null> {
    // 1. Check Distributed Cache (Redis)
    let destination = this.redisCache.get(shortCode);

    if (!destination) {
      // 2. Cache Miss: Query Database
      const record = this.primaryDatabase.get(shortCode);
      if (!record) {
        return null; // 404 Not Found
      }
      destination = record.originalUrl;
      // Populate cache for subsequent reads
      this.redisCache.set(shortCode, destination);
    }

    // 3. Emit Asynchronous Clickstream Event (Non-blocking portable microtask)
    queueMicrotask(() => {
      this.clickStreamProducer({
        shortCode,
        timestamp: Date.now(),
        clientIp: clientContext.ip,
        userAgent: clientContext.userAgent,
        referer: clientContext.referer,
      });
    });

    // 4. Return HTTP 302 Found for exact analytics tracking
    return {
      status: 302,
      destinationUrl: destination,
    };
  }
}

async function runDemo(): Promise<void> {
  console.log("=== URL Shortener & Distributed Token Generation Engine ===");
  const coordinator = new DistributedRangeCoordinator();
  const tokenService = new TokenGeneratorService(coordinator);
  await tokenService.initialize();
  console.log("Initialized TokenGeneratorService with distributed counter ranges");
  const token1 = await tokenService.generateNextToken();
  const token2 = await tokenService.generateNextToken();
  console.log(`Generated Base62 URL Tokens: '${token1}', '${token2}'`);
  const decoded1 = Base62Encoder.decode(token1);
  console.log(`Decoded token '${token1}' back to numeric ID: ${decoded1}`);
}

runDemo();

8. Edge Fast-Path Rejection & Cache Stampede Protection

1. The Cache Penetration Attack

An attacker executes a script generating random 7-character Base62 strings:

curl https://short.ly/9zK2p1Q  # Does not exist
curl https://short.ly/aB3xM90  # Does not exist

Because random tokens are not in the Redis cache, each request punches directly through to the database disks. If an attacker floods 50,000 requests/sec, the database thread pool and disk I/O queue saturate completely, causing catastrophic system outage.

Attacker Request (Random Slug)
         |
         v
+------------------+     Definitive Non-Existence (0)
| Edge Bloom Filter| ----------------------------------> HTTP 404 Fast Reject (0 Disk I/O)
+------------------+
         |
         | Probable Existence (1)
         v
+------------------+     Cache Hit
|   Redis Cache    | ----------------------------------> HTTP 302 Found (< 2ms)
+------------------+
         |
         | Cache Miss (Rare)
         v
+------------------+
| Primary Database |
+------------------+

2. Bloom Filter Sizing at the Edge

For $N=10^{10}$ links and an acceptable false positive probability $p=0.01$ (1%):

A single 12 GB Bloom filter loaded into edge gateway RAM intercepts and drops 99% of invalid random probes, completely shielding the storage layer.

3. Cache Stampede & Singleflight

When a viral short URL expires from cache while receiving 20,000 queries per second, all 20,000 concurrent requests would simultaneously query the database for the same key.

We prevent this using the Singleflight pattern (Mutex Coalescing): When a cache miss occurs for key k, only the first incoming thread acquires a local mutex to query the database; all subsequent concurrent threads for key k wait on a shared promise/channel and receive the result of that single flight.

9. Asynchronous Clickstream Analytics Pipeline

To satisfy the sub-10ms redirect SLA, analytical computations are strictly excluded from the request-response thread.

[ Redirection Node ]
         |
         | Fire-and-forget JSON Event
         v
+-------------------------------------------------------+
|             Apache Kafka: `click-events`             |
| Partition Key: hash(short_code)                       |
+-------------------------------------------------------+
         |
         | High-throughput consumer group
         v
+-------------------------------------------------------+
|               Apache Flink Stream Processor           |
| - 1-Minute Tumbling Windows by (short_code, country)  |
| - Sliding 24-Hour Unique IP Counting (HyperLogLog)    |
+-------------------------------------------------------+
         |
         | Batched Micro-Inserts
         v
+-------------------------------------------------------+
|             ClickHouse Columnar OLAP Database         |
| Table Engine: AggregatingMergeTree                    |
+-------------------------------------------------------+

ClickHouse Table Schema:

CREATE TABLE url_click_aggregates (
    short_code LowCardinality(String),
    event_minute DateTime,
    country_code LowCardinality(FixedString(2)),
    device_category LowCardinality(String),
    total_clicks UInt32,
    unique_visitors AggregateFunction(uniq, UUID)
) ENGINE = AggregatingMergeTree()
PARTITION BY toYYYYMM(event_minute)
ORDER BY (short_code, event_minute, country_code);

10. Failure Modes, Edge Cases & Threat Modeling

11. Summary & Architectural Decision Guide

• Use Monotonic Range Allocation + Bijective Feistel Permutation when 7-character compact slugs ($62^7\approx 3.52\times 10^{12}$) and blind lock-free database writes are required; use 64-bit Snowflake IDs only when 11-character slugs are acceptable and time-ordered IDs simplify index locality.
• Never recycle numeric ID ranges via TTL lease expiry: advance a persistent high-water mark in etcd/ZooKeeper and burn unused tail IDs on worker restart to guarantee $P_{\text{collision}}=0$ across arbitrary GC pauses.
• Select HTTP 302 / 307 with Cache-Control: private, no-store whenever click analytics, fraud filtering, or mutable destination targets are product requirements; reserve HTTP 301 for immutable archival redirects where origin offload outweighs telemetry.
• Layer Edge Bloom Filters + Singleflight Coalescing ahead of Redis and primary KV storage so random non-existent slug floods (cache penetration) and viral link expirations (cache stampedes) cannot saturate disk IOPS.

Verify your mastery of these design invariants using the interactive assessment quiz at the end of this lesson.

12. Practical Exercises & Deliverables

Exercise 1: Implement Feistel Permutation for Non-Sequential Tokens

Problem: Sequential tokens (0000001, 0000002) allow competitors to scrape links and deduce business volume.
Deliverable: Implement a cycle-walking 42-bit Feistel cipher over $[0,62^7-1]$ in TypeScript or Go. Prove that:

1. Every integer in $[0,62^7-1]$ maps bijectively to another integer in $[0,62^7-1]$ with zero collisions and fits strictly in 7 Base62 characters.
2. Successive integers $N$ and $N+1$ produce non-enumerable Base62 slugs with ~50% character avalanche.

Exercise 2: Benchmark Redis Cache Stampede vs. Singleflight

Problem: Simulate 1,000 concurrent threads requesting an expired viral short URL key. Deliverable:

1. Run a baseline test where all 1,000 cache-miss requests hit backing PostgreSQL/ScyllaDB simultaneously. Measure connection pool exhaustion and p99 tail latency.
2. Wrap the database loader with a Singleflight coalescing promise map. Verify that exactly 1 storage query executes while all 999 concurrent callers share the resolved redirect target.

13. Authoritative References & Version Context

• IETF RFC 9110 — HTTP Semantics (June 2022): Normative caching and redirection specifications for 301 Moved Permanently (§15.4.2), 302 Found (§15.4.3), and 307 Temporary Redirect (§15.4.8) — datatracker.ietf.org/doc/html/rfc9110
• Burton H. Bloom (1970), “Space/Time Trade-offs in Hash Coding with Allowable Errors”, Communications of the ACM 13(7): Foundational false-positive derivation for edge membership filters — doi.org/10.1145/362686.362692
• Patrick Hunt, Mahadev Konar, Flavio P. Junqueira, and Benjamin Reed (2010), “ZooKeeper: Wait-free Coordination for Internet-scale Systems”, USENIX ATC ‘10: Atomic znode versioning and coordination primitives — usenix.org/conference/usenix-atc-10/zookeeper-wait-free-coordination-internet-scale-systems
• etcd v3.5 Official Documentation — Transactions & Linearizable CAS: Atomic high-water mark range allocation via Txn revision comparisons — etcd.io/docs/v3.5/learning/api/
• ClickHouse Official Documentation — AggregatingMergeTree Engine (ClickHouse 24.x LTS): Incremental streaming rollups and uniq HyperLogLog state merges for high-volume clickstream analytics — clickhouse.com/docs/en/engines/table-engines/mergetree-family/aggregatingmergetree
• Version & Runtime Context: Capacity, HTTP semantics, and schema examples target HTTP/1.1–HTTP/3 (RFC 9110), etcd v3.5+ / Apache ZooKeeper 3.9+, Redis 7.2+, Apache Kafka 3.7+ (KRaft), Apache Flink 1.19+, and ClickHouse 24.x LTS.