URL Shortener

"Design a URL shortener like bit.ly or TinyURL: users submit a long URL and get a short one; anybody who opens the short URL is redirected to the original."

The URL shortener is the "hello world" of system design interviews, and it is usually the first problem you get as a junior or the warm-up in a senior loop. It looks trivial — a key-value lookup — and that is exactly the trap: the interviewer wants to see whether you drive the conversation (requirements, numbers, API, data, design, deep dives) instead of jumping to "use a hash". It exercises three ideas you will reuse in almost every other case: unique ID generation, read-heavy caching, and taking side work (analytics) off the critical path.

BoxOffice uses one too: the SMS that says "your tickets for Saturday" carries a short link such as https://bx.example/aB3x9Kq, because an SMS has 160 characters and a signed ticket URL has 300.

1. Clarify the requirements

Even for a "simple" problem, spend 3–5 minutes here (interview framework). The requirements decide whether codes may be predictable, whether analytics must be exact, and whether the same long URL always gets the same code.

Functional requirements

1. Shorten: given a long URL, return a short URL with a unique code (e.g. 7 characters).
2. Redirect: GET /{code} sends the browser to the long URL.
3. Custom alias (optional): the user chooses the code (/boxoffice-rock-in-rio).
4. Expiration (optional): links can expire at a given date.
5. Click statistics: number of clicks per link, per day, per country.

Non-functional requirements

Out of scope (say it explicitly)

User accounts and link editing UI, billing, QR-code rendering, A/B testing of destinations. They are features on top of the same core.

2. Back-of-the-envelope estimates

State the assumptions, then compute. All numbers are illustrative — open the Source tab, change one and recompute.

# URL shortener: assumptions (illustrative)
new_per_month = 100_000_000   # new short links per month
read_write    = 100           # redirects per created link
peak_factor   = 3             # peak / average traffic
years         = 5             # retention
record_b      = 500           # code + long URL + metadata, bytes
hot_fraction  = 0.2           # share of a day's redirects worth caching (80/20 rule)
click_b       = 200           # one click event (code, time, country, referrer)

write_qps  = new_per_month / (30 * 86_400)
read_qps   = write_qps * read_write
peak_read  = read_qps * peak_factor
records    = new_per_month * 12 * years
storage_tb = records * record_b / 1e12
codes_7    = 62 ** 7
used_pct   = records / codes_7 * 100
cache_gb   = read_qps * 86_400 * hot_fraction * record_b / 1e9
clicks_gb  = read_qps * 86_400 * click_b / 1e9

rows = [
    ("write_qps", write_qps, "req/s"), ("read_qps", read_qps, "req/s"),
    ("peak_read", peak_read, "req/s"), ("records", records, "links"),
    ("storage_tb", storage_tb, "TB"), ("codes_7", codes_7, "codes"),
    ("used_pct", used_pct, "%"), ("cache_gb", cache_gb, "GB"),
    ("clicks_gb", clicks_gb, "GB/day"),
]
print("| quantity | value | unit |\n|---|---:|---|")
for name, value, unit in rows:
    v = f"{value:,.0f}" if abs(value) >= 100 else f"{value:,.2f}"
    print(f"| `{name}` | {v} | {unit} |")

What the numbers tell us:

• ~40 writes/s and ~4 k redirects/s (peak ~12 k/s): a single database could take the writes; the reads are what we design for. ⇒ cache in front of the store, stateless app servers behind a load balancer.
• 6 billion links, ~3 TB in 5 years: too much for comfort on one node with replicas and indexes, trivial for a partitioned key-value store. The access pattern is a single-key lookup, so a KV store (DynamoDB, Cassandra) or a sharded SQL table both work.
• 7 base62 characters = 3.5 trillion codes; we use 0.17% of them in 5 years. Short codes are not the scarce resource — uniqueness without coordination is the design problem.
• The hot set is ~33 GB: it fits in the RAM of one or two cache nodes. With a Zipf-like popularity (a few links get most clicks), the hit ratio will be high.
• Click events are ~67 GB/day — more than the links themselves. ⇒ they go to a stream and an analytics store, never to the main table.

3. API

POST /v1/urls                          → 201 {code, shortUrl, expiresAt}
     {"longUrl": "https://boxoffice.example/events/42?utm_source=sms",
      "customAlias": null, "expiresAt": "2027-12-31T23:59:59Z"}
     (409 ALIAS_TAKEN, 422 INVALID_URL, 429 TOO_MANY_REQUESTS)

GET  /{code}                           → 302 Found, Location: <longUrl>
                                         (404 not found, 410 Gone when expired)

GET  /v1/urls/{code}/stats?from=…&to=… → 200 {clicks, byDay[], byCountry[]}
DELETE /v1/urls/{code}                 → 204   (owner only)

• Creation is authenticated (API key or user token) and rate limited per client — a shortener is a favorite tool of spammers.
• The redirect is public and does one thing: look up and answer. Everything else (counting, geo lookup, bot detection) happens asynchronously.

4. Data model

The core access pattern is code → longUrl, a point lookup by primary key, at thousands per second, over billions of rows. No joins, no range scans.

-- Logical model (a KV/wide-column table, or a sharded SQL table)
CREATE TABLE short_url (
    code        VARCHAR(16) PRIMARY KEY,   -- partition key
    long_url    TEXT        NOT NULL,
    owner_id    BIGINT,
    created_at  TIMESTAMP   NOT NULL,
    expires_at  TIMESTAMP
);

-- Only for the counter-based generator: one row per range allocation
CREATE TABLE id_range (
    name        VARCHAR(32) PRIMARY KEY,   -- 'short_url'
    next_start  BIGINT      NOT NULL
);

5. High-level design

flowchart LR
    u([Browser / app]) --> dns["DNS"]
    dns --> lb["Load balancer"]
    lb --> app["Shortener app<br/>(stateless, N replicas)"]
    app --> cache[("Cache<br/>hot codes")]
    app --> db[("NoSQL<br/>code → long_url")]
    app --> ids["ID allocator<br/>(ranges)"]
    app -. click event .-> k[["Kafka<br/>clicks"]]
    k --> agg["Analytics workers<br/>aggregate"]
    agg --> dwh[("Analytics store")]

The write path asks the ID allocator for a code (from a range already leased in memory — no network call most of the time), stores the row, and returns the short URL. The read path is shown below; notice that the click event is fired after the response and never waits.

sequenceDiagram
    autonumber
    participant B as Browser
    participant A as Shortener app
    participant C as Cache
    participant D as NoSQL
    participant K as Kafka
    B->>A: GET /aB3x9Kq
    A->>C: GET url:aB3x9Kq
    alt cache hit (most requests)
        C-->>A: long_url
    else cache miss
        C-->>A: nil
        A->>D: get(code = aB3x9Kq)
        D-->>A: long_url, expires_at
        A->>C: SET url:aB3x9Kq long_url EX 86400
    end
    A-->>B: 302 Location: long_url
    A-)K: click {code, ts, ip, user-agent}

6. Deep dives

6.1 Generating the code

This is the deep dive every interviewer expects. Four families, each with a different trade-off:

UPDATE id_range SET next_start = next_start + 10000
 WHERE name = 'short_url'
RETURNING next_start - 10000 AS block_start;

The base62 encoding itself is a few lines:

ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

def base62(n: int) -> str:
    s = ""
    while n > 0:
        n, r = divmod(n, 62)
        s = ALPHABET[r] + s
    return s or "0"

# 62**7 = 3_521_614_606_208 codes; base62(3_521_614_606_207) == "ZZZZZZZ"

Recommendation for the interview: counter with range allocation + scrambling for generated codes; a conditional insert (IF NOT EXISTS) for custom aliases. Mention hashing and why you did not choose it (collisions, shared stats).

6.2 The redirect: 301 or 302, and caching

Most commercial shorteners answer 302 (or 301 with a short Cache-Control: max-age) because analytics and the ability to disable a malicious link are part of the product. Whatever you choose, say why (HTTP semantics).

Caching the lookup (cache-aside):

• Cache-aside with a TTL of hours: the mapping almost never changes, so staleness is not a problem; on delete or expiration, delete the key explicitly.
• Negative caching: cache "not found" for a short time (url:zzzzzzz → ∅, 60 s), otherwise a bot scanning random codes goes straight to the database.
• Zipf popularity: a viral link can receive thousands of clicks per second — a hot key on one cache shard. Mitigate with a small in-process cache (L1, a few seconds) on each app server in front of the shared cache.
• Expiration: check expires_at on every read (cached together with the URL) and answer 410 Gone; a background job deletes expired rows later.

6.3 Click analytics off the critical path

Counting clicks synchronously (UPDATE stats SET clicks = clicks + 1) would turn every read into a write on a hot row. Instead:

flowchart LR
    app["Shortener app"] -->|"fire-and-forget<br/>click event"| k[["Kafka topic clicks<br/>partitioned by code"]]
    k --> s["Stream aggregation<br/>1-min windows"]
    s --> olap[("Analytics store<br/>clicks per code/day/country")]
    k --> lake[("Object store<br/>raw events")]
    olap --> api["GET /stats"]

• The app produces the event after answering (or buffers it in memory and sends batches): the redirect does not depend on Kafka being healthy. If Kafka is down, drop or buffer — analytics may lose a few events; redirects must not fail (messaging semantics).
• A stream job aggregates per code per minute and writes counters to an analytics store; raw events land in object storage for later analysis.
• Unique visitors need a distinct count: use HyperLogLog (≈1–2% error, a few kB per counter) instead of storing every visitor ID.

7. Bottlenecks, failure modes and trade-offs

The trade-offs to say out loud: availability and latency over strict consistency for the redirect path (a link deleted a few seconds ago may still redirect from the cache), 302 over 301 because analytics and control matter, and counter ranges over hashing because uniqueness without collision retries is simpler to reason about.

8. Try it in the playground

The url-shortener scenario has the read path of this page: load balancer, app replicas, a cache in front of the store, and an event stream for clicks.

Open the full playground

9. Follow-up questions an interviewer asks

10. Self-assessment rubric

Related: Caching, Hands-on 5 (cache-aside and hit ratio), Messaging, interview practice problems.

How it connects

Which classes does this case test? Each branch is a class whose ideas the design relies on (blue), with the palette components where they show up (green):

flowchart LR
    CASE(["URL shortener"]) --> EST["Estimation<br/>reads ≫ writes, hot set"]:::tech
    CASE --> DIS["Distributed<br/>unique IDs: ranges, Snowflake"]:::tech
    CASE --> EDG["Edge<br/>DNS, LB, 301 vs 302"]:::tech
    CASE --> DB["Databases<br/>key-value: code → long URL"]:::tech
    CASE --> CAC["Caching<br/>cache-aside for hot codes"]:::tech
    CASE --> MSG["Messaging<br/>clicks as events"]:::tech
    EDG -.-> k1["dns · lb · app"]:::comp
    DB -.-> k2["nosql"]:::comp
    CAC -.-> k3["cache"]:::comp
    MSG -.-> k4["kafka · analytics"]:::comp
    classDef comp fill:#1e9e5a22,stroke:#1e9e5a
    classDef tech fill:#2f6fed22,stroke:#2f6fed

Classes it tests: Estimation — numbers · Distributed — time & clocks (unique IDs) · Edge — protocols (redirects) · Databases — models · Caching — patterns · Messaging — semantics. Palette components: dns · lb · app · cache · nosql · kafka · analytics · dwh. Scenarios: url-shortener, read-heavy-cache.

References

• XU, A. System Design Interview — An Insider's Guide, vol. 1, ch. 7 "Design a Unique ID Generator in Distributed Systems" and ch. 8 "Design a URL Shortener"¹.
• Twitter's Snowflake announcement and code².
• HTTP redirect semantics (301, 302, 307, 308)³.
• KLEPPMANN, M.; RICCOMINI, C. Designing Data-Intensive Applications, 2nd ed., chapters on partitioning and stream processing⁴.