Design a URL Shortener (Long URL to Short URL)

Follow the six steps from Lesson 00: clarify, estimate, API, data, core design, scale and failure.

Words you need first

• URL is the full web address of a page, such as https://example.com/very/long/path?x=1. A short URL is a tiny address that sends the visitor to the long one.
• Redirect is an answer from a server that says "the page you want is at another address, go there". The browser then goes there by itself.
• Code (also called a short code or key) is the last part of the short URL, such as Xk3p9Qa in https://sho.rt/Xk3p9Qa.
• Encoding means writing the same value with a different set of symbols. For example, the number 125 can be written in base 10 as 125 or in base 62 as 21.
• Hash function is a function that turns any input into a fixed-size result. The same input always gives the same result, but you cannot go back from the result to the input. MD5 is an old hash function that gives a 128-bit result (32 hex characters). It is fine for making codes. It is not safe for security.

1. Requirements

Functional (what the system does)

• Create a short link for a long URL. Optional extras: a custom alias (a name the user picks) and an expiry date.
• When someone opens a short link, the system redirects them to the long URL.
• Optional: count clicks for each link. Users can list or delete their links.

Non-functional (how well it must work)

• Redirects are fast (tens of milliseconds) and almost always available (availability is the share of time the service works), because every click needs them.
• Read-heavy: assume people open links about 100 times more often than they create them.
• Short codes must be unique. Two links must not get the same code.
• Durability (saved data stays saved): a link must never disappear without anyone knowing.
• Protection from abuse (spam, phishing, scraping).

2. Estimates

100M new links / month           → ~40 writes/s (peak ~200)Read:write 100:1                 → ~4,000 reads/s (peak ~20,000)Keep 5 years: 6 billion links × ~500 B → ~3 TBHot-set cache (20% of daily URLs) → ~10 GB: fits in one Redis node                                   (Redis is a fast in-memory data store used as a cache)

How long should the code be? Base62 means 62 possible characters per position: the digits and the letters (0-9a-zA-Z). With Base62, 7 characters give 62⁷ ≈ 3.5 trillion possible codes. That is far more than 6 billion links (about 0.17% used). 6 characters give about 56.8 billion codes. That is also enough, but it leaves less room to grow. 7 is the usual answer.

3. API

POST /v1/linksAuthorization: Bearer …Content-Type: application/json{ "url": "https://example.com/some/very/long/path?x=1", "alias": "launch-2026", "expiresAt": "2027-01-01T00:00:00Z" }→ 201 CreatedLocation: /v1/links/Xk3p9Qa{ "code": "Xk3p9Qa", "shortUrl": "https://sho.rt/Xk3p9Qa", "longUrl": "…", "expiresAt": "…" }# Errors (HTTP status codes): 400/422 invalid URL, 409 conflict (alias already taken), 429 too many requests (rate limited)GET /Xk3p9Qa→ 302 FoundLocation: https://example.com/some/very/long/path?x=1# 404 Not Found (unknown code), 410 Gone (expired or removed on purpose)

Notes:

• Accept only http and https URLs.
• The create endpoint needs a login and is rate-limited. A rate limiter is a part that limits how many requests one caller can send in a period of time. See Lesson 02.
• The redirect endpoint is public and used a lot. Keep it as small and simple as you can.

4. Data model

CREATE TABLE links (  code        varchar(16)  PRIMARY KEY,         -- the short code; the hot lookup key  long_url    text         NOT NULL,  user_id     uuid,  created_at  timestamptz  NOT NULL DEFAULT now(),  expires_at  timestamptz,  is_active   boolean      NOT NULL DEFAULT true);CREATE INDEX links_user_created ON links (user_id, created_at DESC);

The main question the system asks is: "what is the long URL for this code?" This is a plain key-value read: you give a key and get one value back. A primary key is a column whose value is different in every row, and PostgreSQL builds an index for it (a sorted list that finds a row fast, like the index of a book). So this lookup is fast at this size.

If the load grows, you have two options. You can move the same model to a key-value store such as DynamoDB (partition key = code). Or you can shard it. Sharding means splitting the data over several databases, and a hash of the code decides which database holds each row.

Click events go to a separate store where you only add new rows (an append-only store, so nothing is edited). See the analytics section.

5. The core problem: generating unique short codes

There are four common ways to do it.

Option A: hash the URL, encode, truncate

code = base62(md5(longUrl + salt)).slice(0, 7)

Here the hash function is MD5 (see "Words you need first"). Truncating means you keep only the first 7 characters of the result. salt is an extra value mixed into the input, so the result changes.

• Pro: no state and no coordination. The same URL always gives the same code, so duplicates are found for free.
• Con: cutting the hash short causes collisions. A collision is when two different URLs get the same code. You must check the database. If the code is taken, hash again with a counter or a different salt and retry.
• Con: the same long URL from two users gets one code. This is wrong if each user wants their own stats or expiry date.
• A well-known study guide, the system-design-primer, uses this idea in its Pastebin/Bit.ly exercise: MD5 over IP and timestamp, then Base62, then the first 7 characters. It is a good first answer if you also explain how you handle collisions. (MD5 is used here only to spread values. It is not used for security.)

Option B: random code with collision retry

Make 7 random Base62 characters. Insert them into the database with the code as the primary key. If the insert fails with a unique violation (the database refuses the row because the key already exists), make another code and try again. The code in the example below uses Prisma, an ORM (a library that lets you use a database from TypeScript code). Error code P2002 is Prisma's name for a unique violation. randomBase62(7) is assumed to pick each character with a secure random source such as crypto.randomInt(62). (Do not use byte % 62: it favours some characters.)

• Suppose 6 billion codes are already used out of a space of 3.5 trillion. Then the chance that a new random code is already taken is about 0.17%. Retries are rare (on average about 1.002 attempts, at the very end of the five years; earlier it is even less).
• Pro: simple, no central coordinator, and codes are hard to guess.
• Con: collisions become more common as the space fills up. When it is 50% full, half of the inserts need a retry. So watch how full the space is, and make the code longer before that happens. The database must enforce uniqueness (a primary key does this).

async function createLink(longUrl: string, userId: string) {  for (let attempt = 0; attempt < 5; attempt++) {    const code = randomBase62(7);    try {      return await prisma.link.create({ data: { code, longUrl, userId } });    } catch (e) {      if (e instanceof Prisma.PrismaClientKnownRequestError && e.code === "P2002") continue; // unique violation → try again      throw e;    }  }  throw new Error("Could not allocate a unique code");}

Option C: a counter encoded in Base62

Keep one global counter, which is a number that goes up by one each time. The code is the counter value written in Base62 (counter 125 becomes 21, because 125 = 2 × 62 + 1). Every number is different, so every code is different. You do not need to handle collisions.

• Pro: zero collisions. Codes are as short as possible, because small numbers give short codes.
• Con: the counter is a shared point that every server must ask. It can become a bottleneck or a single point of failure (if it stops, everything stops). Ways to reduce this:
  • Use a database sequence (a built-in counter that hands out the next number safely, even when many requests ask at once).
  • Use Redis INCR (a command that adds 1 to a number and returns the new value as one step that cannot be interrupted).
  • Use range allocation. Each app server takes a block of numbers (say 100,000) from a coordinator. Then it hands them out itself, with no network call for each ID. If a server crashes, its unused numbers are lost. That is fine, because we have trillions.
• Con: codes are in order and easy to guess. Anyone can walk through the numbers and find other people's links. The fix is to scramble the counter before you encode it. Use a reversible mix, such as a Feistel network (a way to shuffle a number so that you can always undo the shuffle), or multiply by a large odd number that is not a multiple of 31 and then take the remainder after dividing by 62⁷ (modulo). Such a number shares no prime factor with 62⁷, so no two inputs give the same output. Then codes look random but are still unique. (This only hides the order. It is not strong secrecy.)

Option D: a key-generation service (KGS) with pre-generated keys

A separate service makes unique random codes ahead of time. It keeps them in two tables: unused and used. App servers take batches of unused keys into memory and use them one by one. The KGS marks them as "used".

• Pro: fast. There are no collisions when a request comes in, and the request path is short.
• Con: it is one more part to run. It can be a single point of failure (one part that stops everything if it fails), so run several copies. Keys held in the memory of a crashed server are lost (this is acceptable).

Comparison

A good answer to say: "At this size I would use random 7-character Base62 codes. If an insert hits a collision, I retry. It is simple, it keeps no state, and there is plenty of room. If I needed guaranteed uniqueness without retries, or shorter codes, I would use a scrambled counter with a range for each server. If collisions or delay became a problem at a much larger size, I would move to a key-generation service."

Why Base62, not Base64?

• Base64 is a way to write bytes using 64 safe text characters: A-Z a-z 0-9 + / (and = as padding at the end). In URLs, + and / have special meaning. / separates parts of a path. + can mean a space in a query string. So you must escape them (write them as %2B and %2F, a safe form). Base64url is a variant that uses - and _ instead and drops the padding. It is safe in URLs, but it still has punctuation.
• Base62 uses only 0-9 a-z A-Z. It is letters and digits only, safe in URLs, and easy to read out loud and copy. No escaping is needed.

Here is how to turn a number into Base62:

const ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";function toBase62(n) {  n = BigInt(n);  if (n === 0n) return ALPHABET[0];  let out = "";  while (n > 0n) {    out = ALPHABET[Number(n % 62n)] + out;    n /= 62n;  }  return out;}function fromBase62(s) {  let n = 0n;  for (const ch of s) n = n * 62n + BigInt(ALPHABET.indexOf(ch));  return n;}console.log(toBase62(125));            // 21console.log(fromBase62("21"));         // 125nconsole.log(toBase62(62n ** 7n - 1n)); // ZZZZZZZ   (the largest 7-character code)console.log(62n ** 7n);                // 3521614606208n  (about 3.5 trillion codes)

Check the numbers: 62⁷ = 3,521,614,606,208, and 62⁶ = 56,800,235,584.

The redirect: 301 or 302?

Both are HTTP status codes that tell the browser to go to another address. The difference is caching, which means the browser (or a server in the middle) remembers the answer and reuses it without asking again.

Answer: if you offer click analytics, expiry, editing or turning links off, use 302. You can also use 307, which keeps the request method the same. If links are permanent and you want the least load, use 301. Some services that need analytics use a 301 but add a short Cache-Control time (for example private, max-age=90), so the browser asks again soon. Either way, always set a clear Cache-Control header (a header that tells browsers and caches how long they may keep a response). Do not rely on defaults. See HTTP semantics.

app.get("/:code", async (req, res) => {  const target = await resolve(req.params.code);   // cache → DB  if (!target) return res.status(404).send("Not found");  if (target.gone) return res.status(410).send("Link expired");  recordClick(req, req.params.code);               // fire-and-forget, never awaited on the hot path  res.redirect(302, target.longUrl);});

Serving 100x more reads than writes

1. Cache-aside with Redis. A cache is a fast store that keeps answers you already looked up. "Cache-aside" means your code checks the cache first. If the answer is not there (a miss), it reads the database and saves the answer in the cache with a TTL (time to live: a time limit, after which the entry is removed). Most reads come from a few popular links (the 80/20 rule), so a cache of about 10 GB serves most reads.

// JSON turns Date into a string, so convert it back before comparing.function toTarget(v: { longUrl: string; isActive: boolean; expiresAt: string | Date | null }) {  const expired = v.expiresAt !== null && new Date(v.expiresAt) <= new Date();  return { longUrl: v.longUrl, gone: !v.isActive || expired };}async function resolve(code: string) {  const cached = await redis.get(`l:${code}`);  if (cached) { const v = JSON.parse(cached); return v && toTarget(v); }   // "null" is the negative-cache marker  const row = await prisma.link.findUnique({ where: { code } });  if (!row) { await redis.set(`l:${code}`, "null", "EX", 60); return null; }   // short negative cache vs. scanners  const value = { longUrl: row.longUrl, isActive: row.isActive, expiresAt: row.expiresAt };   // store the facts, decide "gone" on every read  const ttl = row.expiresAt ? Math.max(1, Math.min(3600, Math.floor((row.expiresAt.getTime() - Date.now()) / 1000))) : 3600;  await redis.set(`l:${code}`, JSON.stringify(value), "EX", ttl);   // never cache longer than the link lives  return toTarget(value);}

2. Read replicas. These are extra copies of the database that answer reads. The hot path (the code that runs on every request) rarely reaches the main database.
3. CDN or edge caching (a CDN is a network of servers around the world that keeps copies of responses close to users) for permanent links, if you use 301 or a Cache-Control header on 302s.
4. Keep the redirect path small. No login check, no heavy logging, no analytics that make the user wait.
5. Protect against cache stampedes and hot keys. A cache stampede is when many requests miss the cache at the same moment and all hit the database. A hot key is one entry that gets a huge number of requests, for example a viral link. To help: combine many misses for the same code into one database read, keep popular entries fresh, and copy hot keys to several cache nodes.
6. Negative caching. Also cache the answer "this code does not exist". This protects the database from scanners that try random codes.

Analytics without slowing the redirect

Never write a click row to the database inside the redirect request. Do this instead:

redirect handler ──(non-blocking)──▶ queue / log stream (Kafka, SQS, Kinesis)                                          (a queue holds messages until another program reads them)                                          │                                          ▼                              stream processor / batch job                                          │                       aggregates (per link, per day, per country) ──▶ analytics store (columnar DB / time-series)                       (columnar DB: stores each column together, fast for sums; time-series DB: built for values over time)

A raw event holds: code, timestamp, ip (hashed or truncated), user-agent, referrer. Add up the numbers later, in the background. The stats endpoint reads the totals. Remove obvious bots (programs, not people, that open links). If you need "unique clicks", remove repeats too. Think about privacy: hash or shorten IP addresses, and follow the rules of each region.

Custom aliases and expiry

• Custom alias:
  • Check the length and the characters.
  • Reject reserved words (api, admin, login, v1).
  • Check that the alias is free by using the same primary key. If it is taken, the insert fails with a unique violation, and you return 409.
  • Aliases and generated codes share one namespace (one set of names). So the same primary key catches a clash between a generated code and an alias, and the random-code retry handles it.
• Expiry:
  • Store expires_at. The redirect checks it. The cache value has it too, with a TTL no longer than the time the link has left.
  • A background job deletes or archives expired rows. It can also free the codes for reuse if you want.
  • Return 410 Gone for expired links, so search engines forget them.

Abuse prevention and security

• Check the destination. Allow only http and https. Set a maximum length. Normalise the URL (write it in one standard form). Check it against malware and phishing blocklists (lists of known bad sites, such as Google Safe Browsing) when the link is created. Phishing means a fake page that tricks people into giving away passwords. Check again from time to time, because a clean page can turn bad later.
• Rate limit creation per user, API key and IP address. For anonymous users, ask for a login or a CAPTCHA (a small test that a human can pass and a program cannot) (Lesson 02).
• Prevent SSRF if you ever fetch the destination (for example to show a preview or title). SSRF (Server-Side Request Forgery) means an attacker tricks your server into calling addresses inside your own network. Block private IP ranges, metadata endpoints, and redirects to them.
• Report-and-takedown flow. Have a way to turn a link off (is_active = false) that works at once. This is another reason to prefer 302.
• Enumeration (walking through codes one by one to find links). Codes in order let people scan for other users' links. Use random or scrambled codes. Remember that short links are not secret on their own. Do not put private content behind a short link with no login.
• Open redirect abuse. An open redirect is a service that sends visitors to any address a stranger gives it. A shortener is, by its nature, a redirector. Warn users about suspicious destinations, show a warning page for flagged domains, and keep watching.

Scaling the storage

At 3 TB and 20,000 reads per second, caches carry the reads. The write rate is small. If one main database is not enough:

• Shard by a hash of the code. Each lookup goes to exactly one shard. Use consistent hashing (a way to assign keys to servers so that adding a server moves only a small share of the keys) or a lookup service, so you can add shards without moving all the data.
• Or use a managed key-value store (DynamoDB, Cassandra) that shards for you.
• Keep the list of links per user (user_id, created_at) in a second index or table. Sharding by code does not help with that question.

Failure modes

• Redis is down: read from the database instead. It is slower but correct. Add rate limiting to protect the database from the extra load. You can also add a small cache inside each app process as a second layer.
• The main database is down: promote a replica to be the new main (this is called failover). Reads continue from replicas. Creating links fails for a short time, and clients retry. Creating is safe to repeat when you use a request ID or alias (this is called idempotent: doing it twice has the same result as doing it once).
• Duplicate create requests: use an idempotency key (a unique ID sent with the request), so a retry does not make a second code (Backend, Lesson 02).
• A whole region goes down: keep copies in several regions (a region is a group of data centres in one area). Route traffic with DNS (the system that turns a name like sho.rt into a server address) or at the edge.

Common mistakes

1. Hash-and-truncate with no collision handling.
2. Base64 codes with + and / in URLs.
3. 301 redirects when you need analytics or editing.
4. Writing analytics synchronously (the user waits for it) in the redirect path.
5. Sequential IDs that let anyone list all links.
6. No caching, so every redirect hits the database.
7. No abuse controls (phishing, spam creation, SSRF).
8. Forgetting expiry and turn-off behaviour (410).

Interview questions

Key takeaways

• Estimate first: ~40 writes/s, ~4,000 reads/s, ~3 TB. 7 Base62 characters (≈3.5 trillion) is plenty.
• Making codes: random + retry on a unique-key error (simple), a scrambled counter with ranges (no collisions), or a KGS (no work at request time). Hashing needs collision handling.
• Base62 is URL-safe and easy to read. Base64 is not.
• 302 for analytics and control, 301 for permanent links and less load.
• Cache a lot, keep the redirect path small, and record clicks in the background.
• Plan for expiry (410), abuse, guessing of codes, failures and sharding.

What's next

Lesson 02: Design a Rate Limiter. The shortener's create endpoint needs protection. Next: the algorithms, how to enforce limits across many servers, and the headers clients see.