URL Shortening & Encoding

Overview

Before you can redirect anyone or show anyone a click count, you need a write path that durably stores a {short_code → long_url} mapping and hands back a code that’s short, URL-safe, and (almost always) unique. This is the very first thing to sketch in an interview, because every other subsystem exists to serve, protect, or scale this one mapping.

API Design

POST /api/shorten

// request
{ "long_url": "https://example.com/some/very/long/path?query=1", "custom_alias": null }

// 201 Created
{
  "short_code": "aZ9kQ2f",
  "short_url": "https://shrt.ly/aZ9kQ2f",
  "long_url": "https://example.com/some/very/long/path?query=1",
  "created_at": "2026-08-20T10:00:00Z"
}

The short_code is the field that changes shape as the design scales from the basic tier’s encoded auto-increment ID to the advanced tier’s range-allocated one — worth calling out explicitly, since the response contract itself never changes even though what’s behind it does.

Database Schema

Basic tier — a single relational table:

CREATE TABLE urls (
  id          BIGSERIAL PRIMARY KEY,
  short_code  VARCHAR(10) UNIQUE NOT NULL,
  long_url    TEXT NOT NULL,
  owner_id    BIGINT,
  created_at  TIMESTAMPTZ NOT NULL DEFAULT now()
);

CREATE UNIQUE INDEX idx_urls_short_code ON urls (short_code);

Scaled tier — a wide-column table keyed directly by the code:

urls_by_code             (wide-column, e.g. Cassandra/DynamoDB)
  partition key: short_code
  columns: long_url, owner_id, created_at, active

Partitioning by short_code means the redirect path’s lookup — by far the system’s hottest read — always resolves from a single partition, no secondary index required.

Basic Approach — Auto-Increment ID + Base62 Encode

How it works

The client posts a long URL. The API inserts a row into a single relational database and gets back an auto-incrementing integer ID, then encodes that integer into a compact, URL-safe string using a base62 alphabet (0-9a-zA-Z).

Client ──▶ API ──▶ Database (auto-increment id) ──▶ base62 encode ──▶ short_code

Tradeoffs

• Pro: Trivial to implement, and uniqueness comes for free — the database already guarantees the integer ID is unique.
• Con: Codes are sequential and guessable — anyone can enumerate every link ever created just by incrementing the decoded integer.
• Con: A single database is a write bottleneck and single point of failure, capping how many links per second the system can accept.

Scaled Approach — Dedicated Key Generation Service

How it works

A separate Key Generation Service pre-generates a large batch of random, non-sequential base62 keys ahead of time and holds them in a pool of unused keys. When a write comes in, the API asks the service for one already-generated key, marks it used, and writes the mapping — uniqueness is now decided once, at generation time, not on every write.

Client ──▶ API ──▶ Key-Gen Service (hands out a pre-generated unused key)
                └▶ API writes {key → long_url} to storage

Tradeoffs

• Pro: Keys are non-sequential and non-guessable, since they were generated randomly rather than derived from a counter.
• Pro: API servers never need to coordinate directly with each other — only with the key-gen service, a much smaller coordination problem.
• Con: The service must guarantee no two servers are ever handed the same key (typically via an atomically-swapped two-buffer handoff) — new infrastructure that has to stay highly available.
• Con: Pre-generating and storing millions of unused keys ahead of time costs real storage that a purely computed scheme doesn’t.

Advanced Approach — Range-Allocated IDs + Async Write-Behind

How it works

Each API node checks out a numeric range (e.g., 1,000 IDs at a time) from a lightweight coordinator instead of one global counter, then mints codes from that local range with zero further coordination until it runs out. The durable write itself happens asynchronously: the API responds with the minted code immediately and queues the actual persistence.

Client ──▶ API ──▶ Range Allocator (hands out ID ranges per node)
        └▶ API mints code locally, responds immediately
                └▶ Write Queue ──▶ Persistence Worker ──▶ Sharded Store

Tradeoffs

• Pro: ID minting scales linearly with the number of API nodes, since each one works out of its own local range almost all of the time.
• Pro: Client-perceived latency drops to “however long it takes to mint a local ID,” since the durable write happens after the response.
• Con: Introduces a small eventual-consistency window — a just-minted code may not be queryable by Redirection until the async write lands.
• Con: A node that crashes mid-range abandons its unused IDs permanently — an acceptable cost given how enormous the keyspace is (62⁷ ≈ 3.5 trillion codes at 7 characters).

Tech Choices

• Base62 encoding — a compact, URL-safe alphabet that packs the most entropy per character, so 6–7 characters covers billions of links.
• PostgreSQL / a sharded wide-column store — durable mapping storage.
• Redis — backing store for the pre-generated key pool and the range-allocator’s counters.
• Key Generation Service — isolates “give me a unique code” from the write path itself.

How to Vocalize This in an Interview

Start from base62(auto-increment) — it’s the fastest way to show you understand why short codes need an encoding scheme at all. Let the interviewer’s “these are guessable” or “what if two servers write at once?” push you toward the key-generation service. Only bring up range allocation once they push further with “isn’t the key-gen service now your bottleneck?”