Designing URL Shortener

The whiteboard for this problem is in excalidraw/6. Designing URL Shortener.excalidraw. This file is the full write up of that board. It is the best problem to start with, because almost every other design in this folder reuses one idea from here.

1. Problem Statement

Design a URL shortener that turns a long URL into a short, human readable, pseudo random code. Visiting the short URL takes the user to the original site.

Why anyone wants this: long URLs are painful to share over SMS and social media, and short ones look better in print and in messages.

Scale to design for: about 100 million new URLs per month. Custom aliases are not supported for now.

2. Requirements

2.1 Functional Requirements

2.2 Non Functional Requirements

1. Redirect latency must be tiny. The redirect sits between a click and the destination page, so it must be a few milliseconds.
2. Read heavy. Reads outnumber writes by a large factor, so the read path gets the cache and the replicas.
3. No collisions, ever. Two different long URLs must never receive the same code.
4. Unguessable codes. Sequential codes let anyone scrape the whole database.
5. Highly available. A dead shortener breaks every link ever shared, which is far worse than a dead signup page.
6. Horizontally scalable. Code generation must not depend on one machine.

2.3 Out of Scope

Custom aliases, link editing, team accounts, malware scanning of destinations.

3. How to Shorten a URL

3.1 Approach 1: Hash the URL

Take SHA-256 of the long URL and use a prefix of the digest.

Problems:

• A full digest is 256 bits, which encoded is far too long to be a short URL. Even truncated to 16 characters it is not short.
• Truncation creates collisions, and two different URLs can land on the same prefix.
• The same long URL always produces the same code, so two different users shortening the same link share one code and therefore share analytics. That is not what either of them wants.

3.2 Approach 2: Use the Integer Id

If the row lands at id 1729, the short URL is url.sml/1729.

Very short, and guaranteed unique. But completely predictable. Anyone can walk 1, 2, 3 and scrape every link in the system, including private ones.

3.3 Approach 3: Custom Encoding

We cannot expose the integer directly, so we encode it into a string.

The character set is a-z plus A-Z plus 0-9, which is 26 + 26 + 10 = 62 characters. Six bits give us 2^6 = 64 slots, which is enough to hold 62 characters with two unused.

A plain mapping looks like this:

000000 -> a
000001 -> b
000010 -> c
000011 -> d

Worked example. Suppose the id assigned in the database is 79.

79 in binary            = 1001111
left pad to a multiple of 6 = 000001 001111
000001 -> b
001111 -> p
short URL = url.sml/bp

Still predictable, because the mapping is the obvious alphabetical one and ids are sequential. So we use a random mapping that only we know:

000000 -> q
000001 -> d
000010 -> e
000011 -> A

Now the code is much harder to guess from the outside. But someone firing back to back requests would collect consecutive ids, see the pattern in the output, and reverse engineer the mapping.

So the real fix is at the source: instead of picking sequential ids, pick random ones. That is the crux of the whole design. The encoding is just a way to turn an integer into characters. The unguessability comes from which integers we hand out.

4. Generating Unique Pseudo Random Ids

This is the interesting part of the problem.

Constraints:

• Going one by one is easy to predict.
• Generating a random integer and hoping is prone to collisions, and checking for a collision on every write is a read plus a write on the hot path.
• One machine must not own generation, because it would be both a bottleneck and a single point of failure.

Volume check:

100M per month / 30  = 3.3M per day
3.3M / 24            ~ 138K per hour
138K / 60            ~ 2.3K per minute

That is the average. Peak is considerably worse, so the design has to leave headroom.

The answer uses partitioning, sharding and transactions: a set of database backed ticket servers whose only job is to hand out one unique integer at a time, atomically.

4.1 Ticket Servers, Small Example

Take a range of 0 to 1000 and split it into four partitions:

current is the value that will be returned next from that partition.

Getting one integer:

1. The user asks for a short URL.
2. The API server picks a ticket server, at random.
3. The ticket server knows which range ids it owns, from configuration.
4. The API server, or the ticket server, selects one range at random.
5. It reads current for that range.
6. It increments current by one, as long as current is not equal to end.

All inside a transaction:

BEGIN;
SELECT current FROM ranges WHERE id = ? FOR UPDATE;
UPDATE ranges SET current = current + 1 WHERE id = ?;
COMMIT;

No matter how many requests hit the database at the same moment, there are no collisions, because the row lock serializes them. For example on range id 2, the next value becomes 251.

When a range is exhausted, meaning current has reached end, the server drops that range id from its in memory list and stops selecting it.

4.2 Why This Looks Random

Randomness comes from three layers of choice:

1. Pick one ticket server at random.
2. Pick one range on that server at random.
3. Take the next value from that range.

Within a single range the order is sequential, but consecutive requests almost never come from the same range, so the observed sequence of ids jumps around. Combined with the secret six bit character map, the codes are hard to guess and hard to reverse engineer.

4.3 Range Math

How long does the id space last?

32 bit ids:  2^32  ~ 4 billion
4 billion / 100M per month = 40 months ~ 3 years

Three years is not enough, so go to 64 bits:

2^64 ~ 1.84 x 10^19
1.84 x 10^19 / 10^8 per month = 1.84 x 10^11 months
                              ~ 1.53 x 10^10 years

Fifteen billion years, so we are completely safe on space. But a 64 bit number encodes to about 11 characters, which is longer than we want.

So bound the code length instead. Say the code should be at least 3 and at most 8 characters:

min length 3 = 3 x 6 = 18 bits, 2^18  = 262,144
max length 8 = 8 x 6 = 48 bits, 2^48  ~ 2.81 x 10^14

Start ids at 100,000 rather than 0, so every code is at least 3 characters long and we never emit a one character link.

Now size the ranges. If each range should last about a year:

100M per month x 12 = 1200M = 1.2 x 10^9 ids per range

total ranges = 2.81 x 10^14 / 1.2 x 10^9 ~ 2.3 x 10^5

Which is a couple of hundred thousand ranges, each holding 1.2 billion ids. The board rounds this to roughly half a million ranges. The exact count is not the point, the point is that it is a fixed, precomputable table:

range 1: 100,000        to 1,200,000,000
range 2: 1,200,000,000  to 2,400,000,000
range 3: 2,400,000,000  to 3,600,000,000
...

We create these rows up front. On each request we pick one range at random and take one integer out of it. If one ticket database becomes a bottleneck, spin up another one and move some ranges to it, then let the API server pick a ticket server at random.

5. Storage

We store the mapping between the short code and the actual URL.

The important property: the short code is not derived from the URL. It comes from the ticket server, so the URL row is a plain key value entry.

short_code | url | metadata

Sizing it:

short_code   ~   8 B
url          ~ 120 B
per row      ~ 128 B

100M rows x 128 B = 12.8 GB per month

Storage is not the concern at this size, and a single node could hold years of it. We shard for request throughput, not for space, and because the access pattern is purely key based we shard on short_code.

Any key value store works, and so does a relational database with sharding. The lookup is always the same query:

SELECT * FROM urls WHERE short_code = ?;

6. Redirect Flow

When someone visits url.sml/bp:

1. The request reaches an API server.
2. The server looks up the short code, cache first, then the shard.
3. Before responding it emits an analytics event.
4. It returns a redirect with the original URL.

The analytics event carries the short code plus everything the request already tells us: user agent, referrer, IP derived location, operating system, device type. It goes onto Kafka and the response goes out immediately. Nothing about recording a click should slow down a redirect.

6.1 Which Redirect Status

The board uses 301 for speed. In practice, if analytics matter, 302 is the safer default, and 301 is the right pick only for links whose destination will never change. Say which one you chose and why.

7. Caching

Newly published URLs are far more likely to be clicked. A link shared this morning gets thousands of hits today and almost none next year. That is a textbook case for a cache, to cut database load and improve latency.

So we cache the short codes that are new or popular.

Because the mapping is immutable once created, invalidation is almost never needed. That is what makes this cache easy, unlike the product catalog cache in the ecommerce problem where prices change.

8. API Design

8.1 Public

Create:

{
  "longUrl": "https://example.com/a/very/long/path?with=query&and=more",
  "expiresAt": "2026-12-31T00:00:00Z"
}

Response 201 Created:

{
  "shortCode": "bp7Kx",
  "shortUrl": "https://url.sml/bp7Kx",
  "longUrl": "https://example.com/a/very/long/path?with=query&and=more",
  "createdAt": "2026-08-19T10:31:00Z",
  "expiresAt": "2026-12-31T00:00:00Z"
}

Redirect:

GET /bp7Kx
302 Found
Location: https://example.com/a/very/long/path?with=query&and=more
Cache-Control: private, max-age=0

Stats:

{
  "shortCode": "bp7Kx",
  "totalClicks": 18422,
  "uniqueVisitors": 12103,
  "byDay": [{ "date": "2026-08-18", "clicks": 3120 }],
  "byCountry": [{ "country": "IN", "clicks": 9021 }],
  "byDevice": [{ "device": "mobile", "clicks": 14002 }],
  "byReferrer": [{ "referrer": "twitter.com", "clicks": 5510 }]
}

8.2 Internal

{ "id": 8241194001, "rangeId": 7, "ticketServer": "ts-3" }

This endpoint is internal only. Exposing it publicly would let anyone drain the id space.

9. Data Model

Three stores, because there are three completely different access patterns: key value lookups, transactional counters, and analytics aggregation.

9.1 URL Store, Sharded Key Value

urls

Only ever queried by short_code, which is why this can be DynamoDB, Cassandra, or a sharded relational table without anyone noticing the difference.

9.2 Ticket Store, Relational and Transactional

ranges

This table must be relational. It needs row level locking and real transactions, which is exactly the guarantee that makes collisions impossible. It is also tiny, a few hundred thousand rows.

users

9.3 Analytics Store, Document or Search

clicks (MongoDB or Elasticsearch)

Unstructured and append only, and every query on it is an aggregation. Any store that is good at aggregation over semi structured data works here.

Two important choices:

• The stats store is sharded by the user who created the URL, not by short code, because the dashboards a user opens are aggregations across all of their links.
• Aggregation results are rendered through Grafana or Kibana rather than a custom reporting service, which is free functionality.

9.4 Relationships

In words:

• One user creates many URLs, one URL has at most one owner. Anonymous links have none.
• One URL receives many clicks, one click belongs to one URL.
• One range issues ids for many URLs, one URL's id came from exactly one range. This is a logical relationship, not an enforced foreign key, because the two live in different stores.
• One user owns the analytics for many click records, which is why the click store is sharded by owner.

Note there is no foreign key from clicks back to urls. They are in separate databases, and the join is done at query time by short code. Cross store foreign keys are a wish, not a constraint.

10. Key Flows

10.1 Creating a Short URL

10.2 Following a Short URL

The click event is emitted before the response is written but never waited on. If Kafka is unavailable we lose a click record, and losing a click record is much better than failing a redirect.

11. Deep Dives

11.1 Why Not Just Check for Collisions

The obvious alternative to ticket servers is to generate a random code and check whether it exists. That turns every write into a read plus a write, and as the table fills the retry rate climbs. Under concurrency two requests can both read "free" and both insert, so you need a unique constraint and a retry loop anyway.

Ticket servers move the uniqueness guarantee to a single row lock on a tiny table, and the write path never checks for existence at all.

11.2 Why the Encoding Map Is Secret

The secret six bit map is not real security, it is friction. Anyone who can create links and observe the codes can start reconstructing it. What actually protects the keyspace is the random range selection, because the ids handed out are spread across a space of 10^14. Enumerating that space is not practical whatever the encoding is.

Treat the secret map as defense in depth and never as the reason a private link is private.

11.3 Expiry and Cleanup

Expiry is checked at read time, before the redirect, so an expired link returns 404 immediately even if a cleanup job has not run. A daily job then deletes rows past their expiry and purges the matching cache keys. Read time check for correctness, background job for space.

11.4 Analytics Volume

Clicks are the highest volume data in this system by far. At a 50 to 1 read to write ratio, 100 million links a month means around 5 billion click events a month. Two consequences:

1. Never write clicks synchronously in the redirect path.
2. Roll up aggressively. Keep raw events for a few weeks for drill down, keep per day per country per device rollups forever, and archive raw events to object storage after that.

12. Failure Handling

Notice the split: creation can fail loudly, redirects must not. Existing links are the product, new links are a feature.

13. Tradeoffs

14. Exercise

From the board, three things worth building:

• Implement the encoding scheme, integer to string, with a custom map, both encode and decode.
• Explore which analytics can be captured during a short URL hit, and how.
• Explore exactly how analytics data gets shared back to the link owner.

15. Interview Talking Points

• Walk all three shortening approaches and reject the first two with concrete reasons. The reason hashing fails is not only length, it is that two users shortening the same URL would share analytics.
• Say the key sentence plainly: unguessability comes from which integers we hand out, not from the encoding.
• Explain ticket servers with the small 0 to 1000 table. It makes the idea obvious in about thirty seconds.
• Show the transaction. Row level locking is the whole reason collisions are impossible.
• Do the range arithmetic out loud. Bounding code length to 3 through 8 characters, then sizing ranges to last a year, is what turns a vague idea into a table you can create.
• Do the storage math and then say storage is not the concern, throughput is.
• State the 301 versus 302 tradeoff explicitly. It is the fastest way to show you thought about analytics rather than just latency.