OpenAI Interview: Design a URL Shortener

Part of the OpenAI system design question bank. The question is representative of the round. The analysis and solution are this site's own.

Problem statement

A user submits a long URL and gets back something like https://sho.rt/aZ3k9Qx. Anyone who opens it is redirected to the original. The owner sees click counts. The idea is simple, and senior loops grade the depth: key generation at scale, a global redirect path that is fast and cheap, analytics that never slow redirects, and abuse controls.

Clarifying questions

• Scale? For practice: 100 million new links a day, 100 reads per write.
• Key length? As short as practical. Derive it from the numbers.
• Custom aliases? Yes, optional.
• Expiry? Optional per link.
• Analytics? Click counts by day, country, and referrer, delayed by a minute is fine.
• Can links change after creation? The destination does not change; links can be disabled.
• Private links? Some links point to private documents, so keys should not be guessable.

What makes a shortener hard

Nothing is hard at small scale. At scale, three things are.

Key generation must produce billions of unique, short keys at thousands per second, across many servers, without a central bottleneck and without collisions.

The redirect path carries almost all the traffic, from everywhere in the world. Every millisecond added to it is added to every click, and every database read on it costs money at 100,000 reads per second.

And a public shortener attracts abuse: phishing and malware links hide behind short URLs, and scanners enumerate keys looking for private content.

So the driving tension is read latency and cost versus the bookkeeping the business needs: analytics, abuse checks, and link management must happen without touching the redirect's hot path.

flowchart LR
  U([User clicks short link]):::user --> EDGE[Edge / CDN region]:::svc
  EDGE --> C[(Regional cache)]:::store
  C -->|miss| KV[(Key-value store replica)]:::store
  EDGE -->|302 Location| U
  EDGE -.click event.-> LOG[[Click stream]]:::svc
  classDef user fill:#e6efec,stroke:#315e55,color:#171717;
  classDef svc fill:#f4f1e8,stroke:#315e55,color:#171717;
  classDef store fill:#fdf3dc,stroke:#c4492d,color:#171717;

Key idea. Make the redirect a cache lookup near the user. Everything else, including analytics and abuse checks, happens off that path.

Key concepts

Base-62 encoding

Digits, lowercase, and uppercase letters give 62 symbols. A number written in base 62 is short: 7 characters cover 62^7, about 3.5 trillion values.

Counter ranges

A coordinator hands each application server a block of IDs, such as 10,000 at a time. Servers generate keys from their block with no coordination per request, and ask for a new block when it runs out.

301 and 302

A 301 redirect is permanent: browsers and proxies may cache it and skip your server next time. A 302 is temporary: every click comes back to you.

Hot keys

Link popularity is extremely skewed: a few links get most clicks. Caching those few serves most traffic.

Key idea. Base 62 for short keys, counter ranges for scale without coordination, 302 for control and analytics, and a cache for the skew.

1. Requirements

Before reading on. List requirements, then derive the key length from the numbers before choosing a scheme.

1.1 Functional requirements

• Create a short link for a long URL, with an optional custom alias and expiry.
• Redirect a short link to its destination.
• Show the owner click analytics.
• Disable a link (owner or trust-and-safety).

1.2 Non-functional requirements

• Redirect latency under 50 ms at p95 worldwide, excluding the destination.
• Availability of redirects: 99.99% or better; links in documents must keep working.
• Durability: a created link never disappears unless disabled.
• Uniqueness: no two links share a key.
• Unguessable keys for links that may point to private content.

1.3 The constraint versus the property

Redirect availability is the property. Short links live in documents, emails, and printed material for years. Read volume is the constraint. At 116,000 redirects per second on average, the redirect path decides cost and latency.

1. Back-of-the-envelope estimation

• Writes: 100 M links a day / 86,400 ≈ 1,160 per second.
• Reads: 100 × writes ≈ 116,000 per second on average; peaks several times higher.
• Links over five years: 100 M × 365 × 5 = 182.5 billion.
• Key length: 62^6 ≈ 57 billion is too few; 62^7 ≈ 3.5 trillion covers five years with room to spare. 7 characters.
• Storage: 182.5 B × 500 bytes (URL, key, owner, timestamps) ≈ 91 TB over five years, before replication.
• Cache: if the top 1% of links get most clicks, and 1% of the last year's links is about 365 million entries at 500 bytes, that is about 180 GB of cache across a region; a smaller slice of the hottest links captures most hits.
• Click events: 116,000 per second × 200 bytes ≈ 23 MB/s into the analytics stream, about 2 TB a day.

Key idea. 1,160 writes and 116,000 reads per second, 7-character keys, 91 TB over five years, and a click stream bigger than the link data itself.

1. API design

Before reading on. The same long URL is shortened twice by different users. Should they get the same key?

Usually no. Different owners want their own analytics and the ability to disable their own link. Returning the same key for the same URL makes sense only per owner, as a convenience.

POST /v1/links
  {long_url, custom_alias?, expires_at?}
  -> 201 {key, short_url: "https://sho.rt/aZ3k9Qx"}
  -> 409 alias taken
  -> 422 URL blocked by safety checks

GET /:key
  -> 302 Location: <long_url>      Cache-Control: private, max-age=0
  -> 404 unknown key
  -> 410 disabled or expired

GET    /v1/links/:key/stats?from=&to=   (owner)  -> clicks by day, country, referrer
PATCH  /v1/links/:key  {disabled: true}           (owner)

1. Data model

links (key PRIMARY KEY, long_url, owner_id, created_at, expires_at, status)
      -- key-value store, partitioned by key, replicated to every region
owner_links (owner_id, created_at, key)          -- "my links" list
id_blocks   (range_start, range_end, server_id, allocated_at)
clicks_by_day (key, day, country, referrer_domain, count)   -- analytics store

The redirect path touches only links, by exact key. No joins, no range queries, which is why a key-value store fits.

1. High-level design

5.1 One server and one SQL table

A single server writes rows with an auto-increment ID, converts the ID to base 62 for the key, and redirects by lookup. It works up to one machine's limits, and the auto-increment counter makes keys sequential and guessable.

5.2 Fix 1: counter ranges for key generation

Many API servers each hold a block of IDs from a coordinator, a small strongly consistent service. They generate keys locally from the block.

flowchart LR
  COORD[(Range coordinator)]:::new -->|block 50,000,000-50,009,999| A1[API server 1]:::svc
  COORD -->|block 50,010,000-50,019,999| A2[API server 2]:::svc
  A1 -->|next id -> permute -> base62| K1[key]:::store
  classDef svc fill:#f4f1e8,stroke:#315e55,color:#171717;
  classDef store fill:#fdf3dc,stroke:#c4492d,color:#171717;
  classDef new fill:#ffffff,stroke:#c4492d,stroke-width:2px,stroke-dasharray:5 3,color:#171717;

5.3 Fix 2: a distributed key-value store

Store links in a key-value store partitioned by key and replicated across regions. Reads by key are single-digit milliseconds.

5.4 Fix 3: regional caches at the edge

Redirects are served in the user's region: an edge server checks an in-memory cache, then the regional replica. Most clicks never leave the region, and most hit the cache.

5.5 Fix 4: analytics off the hot path

The redirect emits a click event to a stream and returns immediately. A stream processor aggregates counts.

5.6 Fix 5: abuse controls

New URLs are checked against malware and phishing lists before a key is returned, and popular links are rescanned.

5.7 The composed design

sequenceDiagram
  autonumber
  actor Cr as Creator
  participant API as API server
  participant S as Safety check
  participant KV as Key-value store
  actor V as Visitor
  participant E as Edge server
  participant C as Regional cache
  participant ST as Click stream
  Cr->>API: POST /links {long_url}
  API->>S: check URL
  S-->>API: ok
  API->>API: id from local block, permute, base62
  API->>KV: put key -> long_url (if absent)
  API-->>Cr: short_url
  V->>E: GET /aZ3k9Qx
  E->>C: get key
  alt hit
    C-->>E: long_url
  else miss
    E->>KV: get key (regional replica)
    E->>C: fill
  end
  E-->>V: 302 Location
  E--)ST: click event (async)

Key idea. Blocks of IDs for keys, a replicated key-value store for links, edge caches for redirects, a stream for clicks, and safety checks at creation.

1. Deep dives

6.1 Key generation compared

Before reading on. Compare four ways to generate keys. Which would you pick, and what changes if keys must be unguessable?

Counter ranges are the strongest default for throughput. For unguessable keys, pass each counter value through a reversible permutation, a keyed block cipher over the ID space, before encoding. Keys stay unique, because the permutation is one-to-one, and consecutive IDs produce unrelated keys. Or use random keys with a conditional insert: at 182 billion links out of 3.5 trillion possible, the space is about 5% full after five years, so about 1 insert in 20 collides and retries once, which is cheap.

Custom aliases share the key space. Insert them with the same conditional put; a taken alias returns 409. Reserve words such as api, admin, and login.

6.2 Storage and replication

The access pattern is a single-key read and a single-key write with a uniqueness check. A distributed key-value store fits: partition by key hash, replicate within each region for durability, and replicate asynchronously to other regions for local reads.

Creation writes to the key's home region with a conditional put, so uniqueness is enforced in one place. Other regions receive the link within a second or so. A visitor in another region who clicks a brand-new link before it replicates gets a cache miss and a local miss; fall back to reading the home region before returning 404. That fallback covers the first second of a link's life.

6.3 The redirect path

Before reading on. 301 or 302? Defend your choice.

A 301 is permanent. Browsers cache it, often indefinitely, so later clicks from that browser go straight to the destination without contacting you. That saves load. It also means you lose the click in analytics, and you can never redirect that browser differently, even if you disable the link because it turned malicious.

A 302 comes back every time. You pay for every click, and you keep analytics and control. Most commercial shorteners use 302 for that reason. Add Cache-Control: private, max-age=0 so shared caches do not store it either.

Latency: serve redirects from edge servers in many regions, each with an in-memory cache of hot keys and a nearby key-value replica. A cache hit answers in a millisecond or two plus the network round trip to the edge.

6.4 Caching hot links

Popularity is heavily skewed. A viral link can get tens of thousands of clicks per second. An in-process cache on each edge server, backed by a regional cache cluster, absorbs it. A least-recently-used policy with a size limit works well.

Two cases need care. Negative caching: scanners request random keys; cache "not found" for a short time so they do not hammer the store. Disabling: when a link is disabled, publish an invalidation to every region so caches drop it at once, not after a time-to-live. For a malicious link, minutes matter.

6.5 Analytics

Never write to a database per click. The edge server emits a small event (key, timestamp, country from IP, referrer domain, a hash of the user agent) to a stream and returns the redirect. A stream processor aggregates counts per key per minute and writes them to an analytics store that answers "clicks per day by country." Delays of a minute are invisible to users.

Deduplicate obvious bots by user agent and rate, and exclude them from counts. Do not store raw IP addresses longer than needed.

6.6 Abuse

• At creation: check the destination against malware and phishing lists; block known-bad domains; rate limit creation per account and per IP.
• After creation: rescan links that suddenly become popular, since attackers create clean links and swap destinations on their own server later.
• Disable fast: trust-and-safety can disable a key, which invalidates caches globally and returns 410 with a warning page.
• Enumeration: unguessable keys, rate limits per IP on 404s, and no sequential structure.

6.7 Key generation, in code

Before reading on. Write a function that turns a counter value into an unguessable 7-character key, and show it cannot collide.

import hashlib, hmac

ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
SPACE = 62 ** 7                       # about 3.5 trillion keys

def to_base62(n: int, width: int = 7) -> str:
    chars = []
    for _ in range(width):
        n, r = divmod(n, 62)
        chars.append(ALPHABET[r])
    return "".join(reversed(chars))

def feistel_permute(n: int, secret: bytes, rounds: int = 4) -> int:
    # Balanced Feistel network over a power-of-two domain, then cycle-walk into SPACE.
    bits = (SPACE - 1).bit_length()
    half = (bits + 1) // 2
    mask = (1 << half) - 1
    while True:
        left, right = n >> half, n & mask
        for i in range(rounds):
            f = int.from_bytes(hmac.new(secret, bytes([i]) + right.to_bytes(8, "big"),
                                        hashlib.sha256).digest()[:8], "big") & mask
            left, right = right, left ^ f
        n = (left << half) | right
        if n < SPACE:                  # cycle-walk until inside the key space
            return n

def key_for(counter: int, secret: bytes) -> str:
    return to_base62(feistel_permute(counter, secret))

A Feistel network is a permutation: each round is reversible, so distinct inputs give distinct outputs. Cycle-walking keeps outputs inside the key space while staying one-to-one. So distinct counters give distinct keys, with no collision check, and consecutive counters give unrelated keys. Keep the secret in a secrets manager; if it leaks, keys become predictable again, but never duplicated.

6.8 Worked cost of the redirect path

For practice: 116,000 redirects per second on average. With a 95% cache hit rate at the edge, the key-value store sees about 5,800 reads per second across all regions, a small cluster. Without the cache, it would see all 116,000. The cache costs a few hundred gigabytes of memory per region; the savings are most of the storage tier's read capacity and a few milliseconds per click.

The click stream is the larger cost: about 2 TB a day. Aggregate within minutes and keep raw events for a short window, such as 7 days, for abuse investigation; after that, only aggregates.

1. Variants

7.1 Editable destinations

Some products let owners change the destination. Then 302 is mandatory, caches need invalidation on edit, and the destination history should be kept for abuse review.

7.2 Pastebin

Store text instead of a URL. Content goes to object storage; the key-value store holds a pointer. Reads serve content from a CDN.

7.3 Enterprise branded domains

Customers use their own domain, such as go.company.com. Keys are scoped per domain; the key-value key becomes (domain, key).

7.4 At ten times the traffic

At a million redirects per second, nothing structural changes: more edge servers, bigger caches, more stream partitions. Key space is the thing to recheck: 1 billion new links a day for five years is 1.8 trillion, about half of 62^7. Move to 8-character keys before the space is half full, so random-key collisions and permutation cycle-walking stay cheap.

1. The transferable pattern

A URL shortener is a globally replicated key-value lookup with an asynchronous side channel. The same shape serves feature flags, configuration lookups, and session stores: make the hot read a local cache hit, keep writes rare and conditional, and move every piece of bookkeeping to a stream.

Review: the 30-second answer

• Numbers first. 1,160 writes and 116,000 reads per second; 182 billion links in five years; 7 base-62 characters.
• Counter ranges, permuted, or random keys. No coordination per write; unguessable when needed.
• Key-value store, replicated to regions. Conditional put in the home region; fallback read for brand-new links.
• 302 from edge caches. Control and analytics; negative caching; global invalidation on disable.
• Clicks to a stream; abuse checks at creation and on popularity.

Quiz

Sources and further reading

• RFC 9110: HTTP Semantics, redirection 3xx defines 301 and 302 behavior and caching.
• Google Safe Browsing describes an API for checking URLs against malware and phishing lists.
• Format-preserving encryption covers keyed permutations over a fixed-size ID space.
• The same read-heavy, cache-first thinking applies to nearby places search.