Key Generation Service

Overview

This is the deep dive on the question URL Shortening only gestures at: how do you actually generate the code? It’s usually the single question that decides whether a URL-shortener interview goes well, because it’s a clean, self-contained distributed-systems problem — uniqueness, without coordination, at scale.

API Design

This subsystem has no public HTTP endpoint of its own — it’s an internal service the write path (URL Shortening) calls. Its contract looks more like an internal API:

KGS.checkout()              → "aZ9kQ2f"   // hands back one guaranteed-unique key
KGS.markUsed("aZ9kQ2f")     // called once the key is durably written

Database Schema

CREATE TABLE key_pool (
  short_code  VARCHAR(10) PRIMARY KEY,
  status      VARCHAR(10) NOT NULL DEFAULT 'unused'  -- 'unused' | 'used'
);

CREATE INDEX idx_key_pool_status ON key_pool (status);

The advanced tier below replaces this table entirely with two integers (a range’s start and end) — worth noting explicitly, since it’s the clearest illustration in this whole guide of “storage cost vs. coordination cost” as a direct tradeoff.

Basic Approach — Hash the Long URL, Truncate

How it works

Run the long URL through a hash function (e.g., MD5), take the first 6–7 characters of the base62-encoded digest as the short code.

Long URL ──▶ MD5 hash ──▶ take first 7 chars (base62) ──▶ short_code

Tradeoffs

• Pro: No coordination or storage needed at all — the same input deterministically produces the same code on any server, independently.
• Con: Truncating a hash to 6–7 characters produces collisions far more often than the full hash would (the birthday paradox bites hard at this length), forcing a collision-detect-and-retry loop on every single write.
• Con: Two different users shortening the exact same long URL get the exact same short code, whether they intended to share one or not — rarely the desired product behavior for per-user link management.

Scaled Approach — Pre-generated Key Pool

How it works

A background job continuously generates random base62 strings, checks each against existing keys, and stores the unique, unused ones in two buffers: one actively being handed out, one refilling in the background. A server claims a block from the active buffer atomically, so no two servers can ever claim the same block.

Background Generator ──▶ writes unique keys ──▶ Key Pool (buffer A: in use | buffer B: refilling)
API Server ──▶ checks out a block from buffer A ──▶ hands keys to writes as they arrive

Tradeoffs

• Pro: Uniqueness is guaranteed structurally — checked once, at generation time — instead of needing a collision-retry loop on the hot write path.
• Pro: API servers never coordinate with each other directly, only with the key-gen service, which is a far smaller coordination problem.
• Con: Running out of pre-generated keys (the background generator falls behind) stalls new link creation entirely — the service is now a hard dependency and single point of failure that didn’t exist before.
• Con: The two-buffer handoff itself must be atomic (a lock or a distributed counter), or two servers could still be handed one block.

Advanced Approach — Distributed Range Allocation

How it works

Instead of a central service physically generating and storing every individual key, a lightweight coordinator (Zookeeper, or a Redis INCRBY call) hands out numeric ranges — e.g., “you own IDs 4,000,001 through 4,001,000” — to each API node. Each node deterministically encodes its own range into base62 keys locally, with zero further coordination until the range is exhausted.

API Node ──▶ requests a range from Coordinator (Zookeeper znode, or Redis INCRBY 1000)
        └▶ owns [4000001, 4001000] ──▶ encodes IDs to base62 locally, no more coordination needed

Tradeoffs

• Pro: Coordination cost drops from “once per key” to “once per 1,000 keys,” so the coordinator’s load barely grows even as API nodes scale up.
• Pro: No storage cost for pre-generated keys sitting idle — a range is just two integers until a node actually consumes it.
• Con: A node that crashes with unused IDs left in its range abandons those specific codes permanently — fine given the base62 keyspace’s size (62⁷ ≈ 3.5 trillion), but worth naming as a deliberate tradeoff.
• Con: Codes minted this way are sequential-ish within one node’s range, leaking a little information about creation timing unless the range is shuffled before encoding.

Tech Choices

• Base62 alphabet (0-9a-zA-Z) — URL-safe and case-sensitive, for maximum entropy density per character.
• Zookeeper (or Redis INCRBY) — cheap, coordination-light range allocation.
• Bloom filter — an optional fast pre-check (“have we possibly used this key before?”) that lets a node skip a database round-trip in the common case of “definitely not used yet.”

How to Vocalize This in an Interview

This is the question that separates candidates who’ve thought about distributed systems from those who haven’t. Open with hash-and-truncate to show you understand why collisions happen at short lengths, then say the sentence that gets you most of the way to the pre-generated pool: “instead of generating a code per request, what if we generate a lot of them ahead of time?”