--- title: "Design a URL Shortener: the Four-Move Answer, and the 301 vs 302 Trap" description: "'Design a URL shortener' is the classic system-design warm-up, and most candidates answer the wrong question. The interviewer is not testing your hash function — they want a data-store choice, defended. Here is the whole answer in four moves: base62-encode a hash into a short code, store code → URL as one key and one value in a KV store, handle collisions with a retry or a monotonic counter, and serve the redirect. Then the follow-up that separates a rehearsed answer from a real one: a 301 is cached by the browser, so your click counter flatlines and you can never repoint the link. A 302 costs a request per click — and that request is the product." keywords: "design a url shortener, url shortener system design, base62 encoding, 301 vs 302 redirect, hash collision handling, key value store, Redis, DynamoDB, system design interview, tinyurl system design, http redirect caching" created_at: "2026-08-19T20:45:00" post_type: "anonym_post" content_type: "technical_article" --- ![Banner](./banner.webp)
Prefer to watch? ▶ The 83-second version ✈ Telegram
*"Design a URL shortener."* It is the classic system-design warm-up — the question they open with because it sounds small enough to be friendly. It is also the one most candidates answer badly, because they answer the wrong question. They start hashing. They compare MD5 to SHA-256. They talk about truncating a digest. And the interviewer waits, because **hashing a string is not an engineering decision**. It is a library call. What is actually being marked is a **data-store choice, defended** — and then whether you know what the last step of the request costs you. Here is the whole answer, in the order one link actually lives. --- ## 1. Make the short code Hash the long URL into a number, then write that number in **base62** — the digits `0-9`, plus `a-z`, plus `A-Z`. Why base62 and not base10? Because the alphabet size is what buys you a short code. With ten symbols you need eleven characters to address a trillion links. With sixty-two you need seven: ``` 62^7 = 3,521,614,606,208 ≈ 3.5 trillion codes 10^7 = 10,000,000 ≈ 10 million codes ``` Same seven characters, five orders of magnitude more address space. That is the entire trick, and it is worth being able to say out loud. ```python import hashlib ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" def base62(n: int) -> str: if n == 0: return ALPHABET[0] out = [] while n: n, rem = divmod(n, 62) out.append(ALPHABET[rem]) return "".join(reversed(out)) def short_code(url: str, length: int = 7) -> str: digest = hashlib.sha256(url.encode()).digest() n = int.from_bytes(digest[:8], "big") # take 64 bits of it return base62(n)[:length] ``` Why not base64, which is shorter still? Because `+` and `/` are not URL-safe and the `=` padding is noise. Base62 is the sweet spot: every symbol survives a URL, a QR code, a browser address bar, and being read out loud over a phone. --- ## 2. Store the mapping ``` "aB9dK2" → https://example.com/some/very/long/path?utm_source=… ``` That is one key and one value. There is no join. No range scan. No ordering, no secondary index, no `WHERE` clause with three conditions. The access pattern is **exactly a hash-map get**, and it never becomes anything else. So: a **key-value store** — Redis, DynamoDB, or a single table where the code *is* the primary key — and not a relational table you filter. Every redirect on the hot path becomes one primary-key lookup. The value is small, the popular links are a tiny fraction of the corpus, and so the working set fits comfortably in memory, which is why a shortener can serve enormous read volume off modest hardware. This is the part of the answer that is actually being graded. Not "I would use Redis" — anyone can say that — but *"the access pattern is a single-key get with no secondary queries, so a KV store is the right shape and a relational table would be paying for indexes and a query planner I never use."* State the access pattern, then let the store fall out of it. That ordering is the signal. Note the asymmetry, too: writes are rare (someone creates a link once) and reads are enormous (everyone who sees it clicks). A read-heavy, single-key workload is close to the friendliest thing you can hand a cache. --- ## 3. Handle collisions Two different long URLs can hash to the same short code. If you just write it, the second one **silently overwrites the first** — and someone's link now points at a stranger's page. That is worth saying precisely, because it is what makes collisions interesting here: the failure is not a crash and not an error log. It is a **wrong redirect**, in production, that nobody notices until a customer complains that their campaign link opens someone else's site. Two ways out. **Retry.** Do a conditional write — `SETNX` in Redis, a unique constraint in Postgres, `attribute_not_exists` in DynamoDB. If the key is already taken, re-hash with a salt (or take the next slice of the digest) and try again. ```python for attempt in range(5): code = short_code(url + ("" if attempt == 0 else f"#{attempt}")) if kv.set(code, url, nx=True): # write only if the key is free return code raise CapacityError("code space too full") ``` Simple, and it keeps codes unguessable. The cost: the expected number of retries climbs as the code space fills — this is the birthday problem, and it is fine at millions of links and unpleasant at a saturated keyspace. **Counter.** Skip hashing entirely. Hand out a monotonically increasing ID — a database sequence, or ranges pre-allocated to each node so the counter is not a global bottleneck — and base62-encode *that*. A counter **cannot** collide, by construction. You have replaced a probabilistic problem with an arithmetic one. The cost is that codes become sequential, and therefore enumerable: `aB9dK1`, `aB9dK2`, `aB9dK3`. Anyone can walk your entire link set and read every destination people have shortened. If that matters, run the ID through a bijective scramble (a Feistel network, or multiply by a constant coprime with the keyspace) before encoding — you keep "cannot collide" and lose "can be guessed". Saying *"either, and here is the trade"* is a stronger answer than picking one and defending it to the death. --- ## 4. Serve the redirect — and the trap A `GET /aB9dK2` looks up the code and answers with a redirect: a status code plus a `Location` header pointing at the long URL. Which status code? This is the follow-up, and it is the part that separates a rehearsed answer from a real one. **`301 Moved Permanently` is cached by the browser.** The first click hits your server. Every click after that is resolved out of the browser's own cache — and out of any CDN or proxy in between — and never reaches you at all. Two consequences, both bad if you did not choose them deliberately: 1. **Your click counter flatlines.** The analytics the entire product is usually sold on stop moving, and the numbers look like the link simply died. 2. **You can no longer change where the link points.** The browser is not asking any more. A mis-typed destination is now permanent for every person who has already clicked it. **`302 Found` costs you a request on every single click.** That request is not overhead — it *is* the product, if you sell click analytics, expiring links, or editable destinations. You are being paid for exactly the thing the 301 optimises away.
301 Moved Permanently302 Found
Cached by browser / CDNYes, aggressivelyNo (by default)
Requests hitting your serverThe first one, then near zeroEvery click
Click analyticsBroken after the first hitComplete
Can you repoint the link later?Not for cached clientsYes, instantly
Can you expire the link?Not reliablyYes
Infra loadVery low — the edge absorbs itScales with clicks
SEO link equityPassed to the destinationWeaker signal
Reach for it whenThe mapping is permanent and you want the traffic goneYou need to count, expire, or edit
So: **301** when the mapping is genuinely permanent and you *want* browsers and CDNs to absorb the traffic — and you are happy to give up the count. **302** when you need to see every click. Most commercial shorteners serve a 302 for precisely this reason, which is a nice thing to be able to point out. --- ## Where this shows up in an LLM stack The same three moves reappear, unchanged, the moment you put a cache in front of a model — which is why this question is not as dated as it looks. **Hash the input, store one key and one value.** A prompt cache is `sha256(model + params + prompt) → response`: one primary-key lookup on the hot path, no joins, no ordering. Exactly the shortener's access pattern, and the same conclusion falls out — a KV store, not a table you query. **The collision failure mode is identical, and worse.** If two different prompts map to the same cache key, the second caller is served the first caller's answer. In a shortener that is an embarrassing redirect; in a multi-tenant LLM service it is a data leak between customers. This is why cache keys hash the *full* request — model, temperature, system prompt, tools, tenant id — and not just the user's text. Truncating the digest to save bytes is exactly the "shorter code, denser keyspace" trade from move 1, with a much sharper downside. **And the 301/302 tension is the caching tension.** A cached response is free and instantly stale; an uncached one costs a full generation and is always current. "Do I want the edge to absorb this, or do I need to see and control every request?" is the same question in both systems — only the price of a miss changes. --- ## The verdict The whole answer fits in four lines, and if you can say these four and defend the middle two, you have answered the question that was actually asked: > - **base62** → the short code, because 62 symbols instead of 10 turns 7 characters into trillions of links > - **KV store** → code in, long URL out; one key, one value, one lookup, no query planner > - **counter** → no collisions by construction, at the price of guessable codes (or retry-on-conflict, at the price of a filling keyspace) > - **302** → keeps your analytics, at the price of a request per click The deeper habit this question is testing is smaller than it looks: **name the access pattern before you name the technology.** "One key, one value, read-heavy, no secondary queries" is a sentence that chooses the database for you. Candidates who lead with the store and justify it afterwards sound like they are reciting; candidates who lead with the pattern sound like they have run one. And then there is the last step, which almost nobody volunteers — that a status code is a caching decision, and a caching decision is a product decision. If the interviewer has to ask *"301 or 302?"*, you have already left the interesting half of the answer on the table. --- **Want the short version?** The [83-second breakdown is here](https://youtube.com/shorts/tW15Xwes890) — all four moves and the redirect trap, drawn by hand.