Design a URL Shortener

Adapted from: Alex Xu, System Design Interview – An Insider's Guide (2020), Chapter 8 — rewritten and condensed for teaching.

Designing a URL shortener like TinyURL is a classic interview question. It's small enough to cover end to end in one session, and it draws on almost everything so far: estimation, caching, unique ID generation, and rate limiting.

What you'll be able to do after this lesson:

• Estimate QPS and storage for a URL shortener, and catch a classic estimation mistake.
• Design the two REST endpoints and choose between 301 and 302 redirects.
• Work out the shortest code length that fits the expected number of URLs.
• Compare hash + collision resolution with base-62 conversion and implement both.
• Build the full shorten and redirect flows with a database and a cache.

---

Step 1: Understand the Problem and Establish Scope

Candidate asks	Interviewer answers
How does it work?	https://www.systeminterview.com/q=chatsystem&c=loggedin&v=v3&l=long becomes an alias like https://tinyurl.com/y7keocwj. Clicking the alias redirects to the original
Traffic volume?	100 million URLs generated per day
How short?	As short as possible
Allowed characters?	0-9, a-z, A-Z
Can short URLs be deleted or updated?	No, to keep things simple

Use cases:

1. URL shortening: given a long URL, return a much shorter one.
2. URL redirecting: given a short URL, redirect to the original.
3. High availability, scalability, and fault tolerance.

Back-of-the-envelope estimation

Quantity	Calculation	Result
Writes per second	100 M ÷ 86,400 s	≈ 1,160
Reads per second	Assume a 10:1 read-to-write ratio: 1,160 × 10	≈ 11,600
Records over 10 years	100 M × 365 × 10	365 billion
Average URL length	Assumption	100 bytes
Storage over 10 years	365 B records × 100 bytes	36.5 TB

A classic estimation slip

The book's version of this calculation reads "365 billion × 100 bytes × 10 years = 365 TB." But the 365 billion already includes the 10 years (100 M/day × 365 days × 10 years), so multiplying by 10 again counts the time twice. The right answer is 36.5 TB. This is exactly why Lesson 2 says to label units at every step: "records" × "bytes/record" gives bytes, and no "years" factor is left to multiply by.

Walk through these numbers with the interviewer so you agree on them before designing.

---

Step 2: High-Level Design

API endpoints

Two REST-style endpoints are enough:

1. Shorten a URL

POST api/v1/data/shorten
  request body: { "longUrl": "<longURLString>" }
  returns:      shortURL

2. Redirect

GET api/v1/{shortUrl}
  returns: longURL, sent as an HTTP redirect

URL redirecting

When a browser requests a short URL, the server looks up the long URL and replies with a redirect status code and a Location header pointing at it:

sequenceDiagram
  participant B as Browser
  participant S as tinyurl server
  participant L as Long-URL server
  B->>S: GET https://tinyurl.com/zn9edcu
  S-->>B: 301 Moved Permanently<br/>Location: https://en.wikipedia.org/wiki/Systems_design
  B->>L: GET https://en.wikipedia.org/wiki/Systems_design
  L-->>B: 200 OK (page)

301 vs. 302

	301 Moved Permanently	302 Found (temporary)
Browser caches the redirect?	Yes: repeat visits go straight to the long URL	No: every visit goes through the shortener first
Load on the shortener	Lower: only the first request per browser	Higher: every click
Analytics (click counts, sources)	Hard: repeat clicks aren't seen	Easy: every click is observed
Pick it when…	Reducing server load matters most	Analytics matter

The simplest redirect implementation is a hash table of <shortURL, longURL> pairs:

longURL = hashTable.get(shortURL)
return redirect(longURL)

URL shortening

Short URLs look like www.tinyurl.com/{hashValue}. We need a function fx that maps each long URL to a hashValue with two properties:

• Each long URL maps to one hash value.
• Each hash value maps back to its long URL.

The deep dive designs fx.

Check: API and redirects

Quiz

301 or 302?

1 / 2

Marketing wants a dashboard showing every click on each short link, by time and referrer. Which redirect should the service return?

Pick an answer to see if you are right.

---

Step 3: Design Deep Dive

Data model

A hash table in memory is a good starting point, but memory is limited and expensive, and 36.5 TB won't fit. Store the mapping in a relational database instead:

Column	Type	Notes
id	bigint, primary key	Unique ID from the ID generator
shortURL	varchar(7)	The hash value (indexed)
longURL	varchar	The original URL (indexed, for de-duplication)

Hash value length

The code uses [0-9a-zA-Z]: 10 + 26 + 26 = 62 characters. We need the smallest n with 62ⁿ ≥ 365 billion.

n	Maximum number of URLs (62ⁿ)
1	62
2	3,844
3	238,328
4	14,776,336
5	916,132,832
6	56,800,235,584
7	3,521,614,606,208 ≈ 3.5 trillion
8	218,340,105,584,896

n = 6 gives about 56.8 billion, which is too few. n = 7 gives about 3.5 trillion, comfortably above 365 billion. So the hash value is 7 characters.

There are two ways to produce it.

Approach 1: Hash + collision resolution

Use a standard hash function and keep the first 7 characters. Even the shortest common hash is too long to use whole. For https://en.wikipedia.org/wiki/Systems_design:

Hash function	Hash value (hex)
CRC32	5cb54054
MD5	5a62509a84df9ee03fe1230b9df8b84e
SHA-1	0eeae7916c06853901d9ccbefbfcaf4de57ed85b

Truncating to 7 characters causes collisions: two different URLs can share a prefix. The fix is to append a predefined string to the URL and hash again, repeating until the code is free:

flowchart TB
  IN[longURL] --> H["hash → take first 7 chars"]
  H --> E{shortURL exists<br/>in DB?}
  E -- "yes, and for a different longURL<br/>(collision)" --> A["longURL + predefined string"] --> H
  E -- no --> SAVE[(Save to DB)]

This removes collisions, but it means a database lookup for every attempt. A Bloom filter in front of the database can answer "definitely not taken" without touching the database. (See Lesson 6's read path for how Bloom filters behave.)

Practice: hash + collision resolution

Implement shorten(long_url, db). db maps codes to long URLs.

1. Hash a candidate string (initially the long URL) with MD5 and take the first 7 hex characters.
2. If that code is not in db, store db[code] = long_url (the original URL, not the candidate) and return the code.
3. If it's already mapped to the same long_url, return it (the URL was shortened before).
4. Otherwise it's a collision: append "!" to the candidate and repeat.

Input: line 1 lists existing code=url pairs (it may be empty), and line 2 lists the URLs to shorten.

Approach 2: Base-62 conversion

Give each URL a unique integer ID and write that number in base 62, the same way you'd write it in base 10 or base 16, but with 62 digits:

0–9 → '0'–'9'     10–35 → 'a'–'z'     36–61 → 'A'–'Z'

Example: convert 11157 (base 10) to base 62 by repeated division:

Step	Division	Quotient	Remainder → digit
1	11157 ÷ 62	179	59 → X
2	179 ÷ 62	2	55 → T
3	2 ÷ 62	0	2 → 2

Read the remainders from bottom to top: 2TX. As a check, 2 × 62² + 55 × 62¹ + 59 × 62⁰ = 7,688 + 3,410 + 59 = 11,157. The short URL is https://tinyurl.com/2TX.

Practice: base-62 encode and decode

Implement encode(n) and decode(s) with the alphabet above. encode(0) returns '0'.

Comparing the two approaches

Hash + collision resolution	Base-62 conversion
Fixed code length (always 7)	Length grows with the ID (2TX is 3 characters, and IDs above 62⁷ − 1 need 8)
No unique ID generator needed	Depends on a unique ID generator
Collisions possible and must be resolved	No collisions, because IDs are unique
Can't predict the next code (it's a hash)	If IDs increase by 1, the next code is easy to guess, which is a security and privacy concern

Check: code length and approach

Quiz

Choosing a code scheme

1 / 3

A service expects 50 billion URLs ever. Using 62 characters, what is the shortest code length that fits?

Pick an answer to see if you are right.

---

URL shortening deep dive

Our design uses base-62 conversion:

flowchart TB
  IN["1. Input: longURL"] --> Q{"2. longURL in DB?"}
  Q -- "3. yes" --> RET["Return existing shortURL"]
  Q -- "4. no" --> ID["Generate unique ID<br/>(ID generator)"]
  ID --> B62["5. Convert ID to shortURL (base 62)"]
  B62 --> SAVE[("6. Save (id, shortURL, longURL)")]
  SAVE --> OUT[Return shortURL]

1. A long URL comes in.
2. Check whether it's already in the database.
3. If it is, return the existing short URL. Don't create duplicates.
4. Otherwise, get a new unique ID from the unique ID generator.
5. Convert the ID to a short URL with base 62.
6. Save a new row with the ID, short URL, and long URL.

Worked example:

id	shortURL	longURL
2009215674938	zn9edcu	https://en.wikipedia.org/wiki/Systems_design

The ID generator returns 2009215674938, which base 62 converts to zn9edcu. Generating globally unique IDs in a distributed system is exactly the problem Lesson 7 solved.

URL redirecting deep dive

Reads outnumber writes about 10 to 1, so the <shortURL, longURL> mapping is cached:

flowchart LR
  U["User clicks<br/>tinyurl.com/zn9edcu"] --> LB[Load balancer] --> WS[Web servers]
  WS -- "3. hit" --> C[(Cache)]
  WS -- "4. miss" --> DB[(Database)]
  DB -- "fill cache" --> C
  WS -- "5. redirect to longURL" --> U

1. A user clicks https://tinyurl.com/zn9edcu.
2. The load balancer forwards the request to a web server.
3. If the short URL is in the cache, return the long URL immediately.
4. Otherwise, fetch it from the database and fill the cache. If it isn't in the database either, the code is invalid, so return 404.
5. Return the long URL to the user as a redirect.

Practice: the full service

Build a URLShortener that combines both flows. The encode function is provided.

• shorten(long_url): if the long URL was already shortened, return its existing code. Otherwise take self.next_id, increment it, encode it in base 62, and store the mapping in self.db.
• resolve(code): return (long_url, 'cache') on a cache hit. On a cache miss with a database hit, fill the cache and return (long_url, 'db'). Otherwise return (None, 'missing').

Input: line 1 is the starting ID, and each following line is shorten <url> or get <code>.

Notice the last test: 1C and 1c are different codes. Base 62 depends on case, so any layer that lower-cases paths (some proxies and CDNs do) would break links.

Check: flows

Quiz

Shorten and redirect flows

1 / 2

Order the URL shortening flow for a new long URL (top = first):

OrderDrag the handle to rearrange — top should be first.

1. ⋮⋮1Convert the ID to a short URL with base 62
2. ⋮⋮2Get a new unique ID from the ID generator
3. ⋮⋮3Receive the long URL
4. ⋮⋮4Save (id, shortURL, longURL) and return the short URL
5. ⋮⋮5Check whether the long URL is already in the database

Drag items into the correct order (or use ↑↓), then check.

---

Step 4: Wrap Up

We covered the API design, data model, hash function choices, and the shortening and redirecting flows. Extra talking points:

• Rate limiter. Malicious users could flood the shortening endpoint. Throttle by IP or other rules, as in Lesson 4.
• Web server scaling. The web tier is stateless, so add or remove servers freely.
• Database scaling. Use replication for read throughput and sharding for size. Sharding by short URL keeps redirect lookups on a single shard.
• Analytics. How many people click each link, and when? Pair this with 302 redirects so clicks are visible.
• Availability, consistency, and reliability: the foundations from Lesson 1.

---

Key Takeaways

• About 1,160 writes/s and 11,600 reads/s. 365 billion URLs over 10 years at 100 bytes each is 36.5 TB, not 365 TB.
• 301 reduces load but hides repeat clicks. 302 costs more requests but enables analytics.
• 62ⁿ ≥ 365 billion gives n = 7 (about 3.5 trillion codes).
• Hash + collision resolution gives fixed-length codes but needs existence checks, ideally behind a Bloom filter. Base 62 of a unique ID never collides but can be guessable if IDs are sequential.
• Shortening: dedupe → ID → base 62 → save. Redirecting: cache → DB → 404.

Previous lesson: Design a Unique ID Generator.

Next lesson: Design a Web Crawler — the crawl pipeline, a polite and prioritized URL frontier, robots.txt, and defending against duplicates and spider traps.

---

Reference Materials

1. A RESTful Tutorial
2. Bloom filter — Wikipedia