Design a URL Shortener

Problem Statement#

"Design a URL shortener like Bitly. Given a long URL, return a shortened URL and when someone visits the shortened URL it redirect them to the original URL."

That's it, and the rest is yours to figure out.

Requirements Gathering#

This is where the interview actually begins. One should always start the interview by asking clarifying questions and collecting the requirements.

Here's how a typical conversation in an interview may look like:

Candidate: "What scale are we designing for? How many URLs will the system hold in total? Can you throw some light on it?"

Interviewer: "Assume about 1 billion shortened URLs over the lifetime of the system(assume 10 years), and around 100 million monthly active users clicking links."

Candidate: "So you mean more reads than writes? Thats realistic tbh since people click short links far more often than they create them."

Interviewer: "Yes. Assume 1000 reads for every write. Sounds good?"

Candidate: "Yup. Do users get to pick a custom alias, like sho.rt/diwali-sale, or is an auto-generated code enough?"

Interviewer: "Support both: auto-generated by default, optionally custom alias, we'll discuss this later if we have some time left."

Candidate: "Just to clarify, one long url can be mapped to multiple shortened urls but vice versa is not allowed?"

Long url - https://intervueclub.com/problems/databases/design-a-url-shortener

its corresponding short urls - sho.rt/123, sho.rt/bitly1, ... (one to many mapping)

essentially, one shortened url always maps to only one (unique) long url. (one to one mapping)

Interviewer: "Correct. Appreciate you clarifying this."

Candidate: "Thanks. Do we need to support short URL expiry? or expire never by default?"

Interviewer: "Yes, never expire by default, but allow an optional expiry."

Candidate: "Okay. Do we also need click analytics, like simply counting how many people clicked each link?"

Interviewer: "No, keep analytics out of scope. Just shorten and redirect but keep in mind that this requirement might come up soon so design the system accordingly, scalable!"

Candidate: "How fast should a redirect be? According to me, it should happen in realtime, < 200ms, and also it should be highly available."

Interviewer: "Redirects should feel instant, Correct. And the service should basically always be up: 99.99% availability. Also, you picked availability and didn't talk about consistency, rationale?"

Candidate: "Since long url to shortened url mappings are immutable, that means serving stale data across different nodes only ever means hasn't appeared yet, and never a wrong value. The worst case is a just-created link that isn't visible for a few ms of replication lag, hence, 404."

Interviewer: "Sounds good to me!"

Candidate: "One last thing, some out of scope are like user accounts, dashboards, spam detection?"

Interviewer: "Correct, all out of scope."

Functional and Non-Functional Requirements#

Functional Requirements#

1. A user submits a long URL and gets back a short one (e.g. sho.rt/1club)
2. Visiting a short URL redirects to the original long URL
3. Optional custom alias instead of an auto-generated code
4. Optional expiry per URL (default: never)

Non-Functional Requirements#

Out of scope: Click analytics, user accounts and auth, spam detection, link-management dashboards

Capacity Estimates#

Do this math out loud in the interview. It takes two minutes and it justifies every decision that follows.

How many writes and reads per second?

Writes:  1B URLs over ~10 years
         = 1,000,000,000 ÷ (10 × 365 × 86,400 sec)  ≈ 3 new URLs/sec  → ~3 QPS

Reads:   ~1000× writes  ≈ 3,000 redirects/sec  → ~3,000 QPS  (maybe ~10k QPS at peak)

Pause on that first number. Three writes per second, about 3 QPS. Any database on a laptop can do that. The write path is not the challenge here; the read path is where all the traffic goes.

How much storage?

1B rows × ~500 bytes per row (URL + code + timestamps)  ≈ 500 GB

500 GB fits comfortably on one Postgres instance. No sharding, no exotic databases. Saying this out loud is a green flag; juniors who reach for sharding at 500 GB are overcomplicating.

How long must the short code be? We'll use base62, the 62 URL-safe characters 0-9, a-z, A-Z. Each extra character multiplies the number of possible codes by 62:

So 6 characters is enough. (If the interviewer bumps the scale to hundreds of billions of URLs, 7 characters cover it: 62⁷ ≈ 3.5 trillion. Same math, one more character.)

The two takeaways that shape everything: this is a read-heavy system, and 6 characters of base62 comfortably covers the keyspace.

High-Level Design#

Don't draw the final architecture on the board straight away. Start with the simplest design that works, and let the problems you discover pull the extra pieces in. That's exactly how we'll build it here.

Version 1: the simplest thing that works#

One app server, one database. Two endpoints. (The diagram says PostgreSQL, but don't stress about the database choice yet; we'll justify it properly in the Data Model section. At this stage, any database works.)

The write path, when a user submits a long URL:

1. Client calls POST /urls with the long URL
2. The app server generates a short code (how? great question, we'll solve it in a moment)
3. Store the row (short_code, original_url) in the database
4. Return sho.rt/4c92

The read path, when someone clicks a short link:

1. Client requests GET /4c92
2. The app server looks up 4c92 in the database
3. Found → respond with an HTTP redirect to the original URL
4. Not found → 404

This design genuinely works. If the interviewer said "10 users", you'd be done. But at our scale it has three open problems, and each one is a deep dive:

1. How do we generate short codes that never repeat? Step 2 above is hand-waving, and this is the heart of the problem.
2. Which redirect do we return? HTTP gives you two choices (301 and 302) and they behave very differently.
3. How do we keep redirects fast at 3,000 QPS? A naive database lookup won't stay under 100ms forever.

We'll fix these one at a time, and the final diagram will fall out at the end.

Deep Dives#

1. Generating the Short Code#

The short code must be unique (two URLs must never share a code), short (6 characters), and URL-safe. Where does it come from? Let's try the obvious ideas first and see why they fail. This is exactly the discussion the interviewer wants to have.

Hash the long URLSituational

Instead, one can run the long URL through a hash function like SHA-256 or MD5, then keep only the first 6 characters as the code. These hash functions take a string input and returns a fixed size hex which is unique and deterministic.

Notice the problem already: every one of these is far longer than 6 characters, so we have to chop it down, and that's where things break.

Here's the catch. 6 characters give us about 62⁶ ≈ 56 billion possible codes, plenty for our 1 billion URLs. But having enough codes doesn't mean each URL lands on its own code. Hashing scatters URLs randomly across that space, so two different URLs can still produce the same 6 characters. That's a collision, and you can't know a code is already taken until you check the database.

So on every single write you'd have to: compute the code, check the DB, and if it's taken, tweak the input and try again. That's the same check-and-retry loop we were trying to avoid.

And the odds only get worse over time: with a code space of size |S| and n codes already used, the chance the next code collides is n / |S|. Every URL you add makes the next collision more likely. In fact the first collision shows up far earlier than intuition says, this is the birthday problem (in a room of just 23 people, two probably share a birthday, even though there are 365 days). Same math here: collisions start around √(62⁶) ≈ 240,000 URLs, not billions.

Can hashing be made to work? Yes, with extra machinery like a bloom filter (a small in-memory check for "have I definitely never used this code?") to skip most DB lookups. Mentioning that shows depth. But it's effort spent making collisions survivable, when the counter approach below makes them impossible in the first place.

Counter + base62Recommended

Keep a counter. Every new URL gets the next number (1, 2, 3, and so on), and the short code is just that number written in base62.

Think of a token counter at a bank: every customer gets the next token number, and no two customers can ever hold the same token. That's the whole trick. Every number is unique, so every code is unique, and collisions are impossible by design. The write path is one insert, with no check-and-retry, ever.

What is base62, exactly? It's just counting with 62 symbols (0-9, a-z, A-Z) instead of 10, the same way hexadecimal counts with 16. Any number maps to a unique short string, and 62 symbols pack big numbers into few characters:

ID 125            → base62 → "21"       (2 × 62 + 1 = 125)
ID 1,000,000      → base62 → "4c92"     (4 chars)
ID 1,000,000,000  → base62 → "15FTGg"   (6 chars — the billionth URL still fits!)

Where does the counter live? If we run multiple app servers (we will, for availability), each keeping its own counter in memory, server A and server B would both hand out "1042". The counter must be shared. The standard answer: Redis. Redis is single-threaded and its INCR command is atomic, so even if a thousand requests arrive at once, each gets a different number, guaranteed. At our ~3 QPS of writes, one small Redis instance doesn't even notice the load.

2. Redirect Strategy: 301 vs 302#

Our read path says "respond with an HTTP redirect", but HTTP gives you two kinds, and interviewers specifically probe this because it looks trivial and isn't.

• 301 Moved Permanently tells the browser "this mapping will never change, remember it."
• 302 Found (temporary) tells the browser "go there this time, but ask me again next time."

The difference shows up on the second click:

Decision: 302. Our requirements include optional expiry, and once a browser caches a 301, that link works forever on that device, no matter what your database says. 302 keeps you in control: you can expire a link, fix a wrong destination, or delete spam, and it takes effect on the very next click. The extra server load is the price, and the next deep dive makes that load cheap. (Bonus: if the product ever adds click analytics, 302 means every click still reaches you. With 301 that data is gone.)

3. Making Redirects Fast#

At ~3,000 QPS of redirects, the read path is where all the pressure is. Two fixes, in order of importance.

Fix 1: an index on short_code. Without an index, the database answers "which row has code 4c92?" by scanning rows until it finds a match, like finding a name in a phonebook by reading every page from page 1. Across a billion rows, that's seconds per lookup. An index (Postgres uses a B-tree) is the phonebook's alphabetical ordering: the database jumps almost directly to the row, in a few milliseconds. Declaring short_code as UNIQUE gives us this index for free, and enforces uniqueness as a bonus safety net.

Honest note: an indexed lookup at 3,000 QPS is already within reach of a single beefy Postgres instance. The index alone nearly meets our 100ms target. So why go further?

Fix 2: a Redis cache for hot links. Link traffic is very skewed: a small fraction of links (the viral ones) get most of the clicks, while most links are rarely visited. Repeatedly asking Postgres for the same viral link is wasted work. So we put Redis in front, using the cache-aside pattern on short_code → original_url:

A cache hit is an in-memory lookup, well under a millisecond, and with hot links absorbing most traffic, roughly 80%+ of reads never touch Postgres at all. The settings, and why:

• Eviction: LRU (least-recently-used): when the cache is full, drop the link nobody clicked recently. For URL traffic, "recently clicked" is a good proxy for "will be clicked again".
• TTL: ~1 day is plenty; LRU handles the rest. If a URL has an expiry, cap the TTL at that.
• Safety: because we chose 302 (not 301), a stale cache entry costs at most one extra DB read, and can never permanently serve a wrong redirect.

4. Custom Aliases#

Auto-generated codes can't collide (the counter guarantees it). Custom aliases can: two users both want sho.rt/sale. Handle it at the database, not in application code:

• Insert relying on the unique constraint on short_code; a duplicate insert fails, which the API surfaces as 409 Conflict, "alias already taken." Checking with a SELECT first is a race condition: two users can both pass the check, then both insert. The constraint is what makes it correct under concurrency.
• Validate the alias before touching the DB: 3-20 characters, letters/digits/hyphens only, and reject reserved words (api, admin, login).

Putting It All Together#

Each deep dive added one piece for one reason. Here's the final design:

• Write: INCR the Redis counter → base62-encode → insert into Postgres → return the short URL.
• Read: check the Redis cache → hit: 302 immediately; miss: indexed Postgres lookup, backfill the cache, 302.
• One Postgres instance holds all 500 GB; a read replica adds availability, not necessity.

Notice what we didn't need: no sharding, no message queues, no dedicated ID service. At 1B URLs the simple version of every component is enough, and being able to say why is worth more in the interview than drawing extra boxes.

Data Model#

Which database, and why?#

We've been drawing PostgreSQL in every diagram without justifying it, and an interviewer will ask. Reason from what the system actually needs, not from buzzwords:

• The access pattern is dead simple. One table. Write a row once, then read it by short_code forever. No joins, no complex queries, no updates in the hot path. This is essentially a key → value lookup.
• The data is small. ~500 GB and ~3 QPS of writes: everything fits comfortably on one machine, so "which database scales better?" isn't even the right question here.
• We do want two things SQL gives us for free. A unique constraint on short_code (it does double duty: the index that makes redirects fast, and the race-free guard for custom aliases), and durable, transactional writes so a "success" response means the link is really saved.

The honest answer, and a strong one in the interview, is that almost any datastore works at this scale: Postgres, MySQL, even a key-value store like DynamoDB. When every option works, pick the boring, familiar one you can operate well. We pick Postgres: mature, reliable, and the unique constraint maps exactly to our correctness needs.

When would NoSQL (DynamoDB, Cassandra) earn its place? When the data no longer fits one machine or the write volume is far beyond one node, since those systems partition data across machines automatically. Neither is true at 500 GB and 3 QPS. Saying "NoSQL because it scales" without checking the numbers is a classic red flag; saying "any database works here, and here's why I pick Postgres" is a green one.

Schema#

-- URLs (Postgres; write-once, read-by-code)
urls (
  id            BIGINT PRIMARY KEY,      -- the counter value (pre-base62)
  short_code    VARCHAR(8) UNIQUE NOT NULL,
  original_url  TEXT NOT NULL,
  created_at    TIMESTAMPTZ DEFAULT NOW(),
  expires_at    TIMESTAMPTZ              -- nullable = never expires
)
-- Index: short_code (unique B-tree) — the redirect read path
-- Index: expires_at (partial, WHERE expires_at IS NOT NULL) — cleanup job

-- Redis:
--   url:counter          → the global counter (INCR)
--   cache: short_code    → original_url, LRU eviction + ~1 day TTL

short_code is VARCHAR(8), not VARCHAR(255), because a tight, fixed-width unique index keeps lookups fast. One table is genuinely all this system needs.

API Design#

POST /api/v1/urls
─────────────────────────────────────────────
Request:
  {
    "original_url": "https://flipkart.com/very/long/path?with=params",
    "custom_alias": "diwali-sale",   // optional, 3-20 chars, [a-zA-Z0-9-]
    "expires_in_days": 30            // optional, null = never
  }
Response 201:
  {
    "short_code": "4c92",
    "short_url": "https://sho.rt/4c92",
    "original_url": "https://flipkart.com/...",
    "expires_at": "2026-08-02T10:00:00Z"
  }
Errors: 400 invalid URL/alias · 409 alias taken · 429 rate limited

GET /:short_code
─────────────────────────────────────────────
Response 302:
  Location: https://flipkart.com/very/long/path?with=params
Errors: 404 not found · 410 expired

Note: the creation endpoint must be rate-limited (per-IP), since an open shortener is a spam magnet. See Design a Rate Limiter.

Failure Scenarios and Edge Cases#

Code#

Base62 Encode + Shorten (Redis Counter) and Resolve (Cache-Aside)#

public class UrlShortener {
    private static final String B62 =
        "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    private final RedisClient redis;   // counter + cache
    private final UrlRepository db;

    static String base62(long n) {
        if (n == 0) return "0";
        StringBuilder sb = new StringBuilder();
        while (n > 0) { sb.append(B62.charAt((int)(n % 62))); n /= 62; }
        return sb.reverse().toString();
    }

    public String shorten(String url, String customAlias, Instant expiresAt) {
        if (customAlias != null) {
            // Unique constraint makes this race-free; duplicate → 409.
            db.insert(customAlias, url, expiresAt);   // throws on conflict
            return customAlias;
        }
        long id = redis.incr("url:counter");  // atomic — no two calls share a number
        String code = base62(id);             // unique by construction, no collision check
        db.insert(id, code, url, expiresAt);
        return code;
    }

    public String resolve(String code) {
        String url = redis.get(code);         // cache-aside hot path
        if (url != null) return url;          // hit → 302 upstream
        Url row = db.findByCode(code);        // miss → indexed lookup
        if (row == null || row.isExpired()) return null;   // 404 / 410 upstream
        redis.setEx(code, row.url(), Duration.ofDays(1));  // backfill
        return row.url();
    }
}

Trade-off Summary#

Follow-up Questions#

Basic

Q: Why a counter and not just hashing the URL?

A truncated hash maps infinitely many URLs into only 62⁶ codes, so two different URLs can collide, and since you can't know in advance whether a code is taken, every write needs a collision check from day one, plus a retry when one hits. A counter gives every URL a distinct number, so codes are unique by construction: one insert, no checking, ever.

Q: Why 302 and not 301?

A 301 is cached by the browser, so after the first click that browser never asks you again, and you can't expire, fix, or delete the link on that device anymore. A 302 routes every click through your servers, keeping you in control. The extra load is handled by the cache.

Q: Why 6 characters? Could we use fewer?

62⁵ ≈ 916 million, just short of our 1 billion URLs. 62⁶ ≈ 56.8 billion, about 56× headroom. So 6 is the minimum safe length at this scale. (Small IDs naturally produce even shorter codes early on: ID 125 is just 21.)

Q: Is a single Postgres instance really enough?

Yes. Check the numbers. ~3 QPS of writes is nothing; ~3,000 QPS of reads against a unique index is well within one instance's capability, and the cache absorbs most of those anyway. Storage is ~500 GB. Add a read replica for availability, not for load. Sharding at this scale is a red flag, not a green one.

Q: What happens if two people shorten the same long URL?

Simplest and correct: they get two different codes, since the counter doesn't care about the URL's content. Deduplicating (returning the same code for the same URL) is a possible optimization, but it needs an index on the long URL and breaks per-user features like separate expiry. Say "two codes, and here's why that's fine."

Minute-by-Minute Interview Playbook#

0 to 5 min: Requirements Ask the questions above. Total URLs, the read:write ratio, custom aliases, and expiry all shape the design; get analytics explicitly declared out of scope. Write FR/NFR on the board.

5 to 8 min: Capacity estimates Do the math out loud. Three numbers carry the interview: ~3 QPS of writes (writes are trivial), ~3,000 QPS of reads (optimize the read path), and 62⁶ ≈ 56.8B (6-character codes). Land the punchline: 500 GB fits one Postgres.

8 to 15 min: HLD Draw the v1 skeleton (Client, App Server, Database, two endpoints) and walk both flows. Explicitly flag "how do I generate the code?" as the open question. Get the interviewer's buy-in before going deep.

15 to 35 min: Deep dives Lead with code generation: walk prefix → random → hash → counter, saying why each fails, then base62 and the Redis counter. Then 301 vs 302 (a known signal, so tie it to expiry and control). Then the read path: index first, cache second. Redraw the final diagram.

35 to 45 min: Failures and wrap-up Cache down (DB absorbs it at this scale), counter failover (gaps are harmless), viral link. Summarize in one sentence: "Counter + base62 for collision-free codes, 302 so we keep control, and an index plus cache-aside so redirects stay under 100ms."

Green flags

• Estimates before choosing anything, and notices writes are only ~3 QPS
• Says "500 GB fits one Postgres" instead of reflexively sharding
• Walks the failed code-generation options before landing on counter + base62
• Knows the 301 vs 302 trade-off cold and ties it to expiry/control
• Mentions the index before the cache, the right order of fixes

Red flags

• Draws Kafka, sharding, or five databases for 3 QPS
• "NoSQL because it scales", with no numbers to back it up
• Uses MD5/hash truncation without addressing collisions
• Picks 301 "because the mapping is permanent" without seeing the loss of control
• Checks alias availability with a SELECT instead of a unique constraint
• Never mentions caching despite a 1000:1 read ratio

Further Reading#