Design a URL Shortener

The URL shortener is the most common warm-up question in system design interviews. It is small enough to finish in forty-five minutes and rich enough to expose how you think about identifiers, caching, read-heavy traffic and abuse. It also teaches a technique that large systems need everywhere: generating unique identifiers without creating a bottleneck.

This chapter follows the same shape as every problem breakdown in this track: understand the problem, set up the entities and API, build a high-level design one requirement at a time, then go deep on the parts an interviewer is most likely to probe, each with a weak, a solid and an excellent answer. It ends with what is expected at each seniority level.

1. Understanding the problem

A URL shortener maps a long URL to a short code and redirects visitors who use the short link. The product is trivial. The engineering is in doing it for billions of links, with redirects that feel instant and never break.

Functional requirements

Core requirements, the ones the design must satisfy:

1. A user submits a long URL and receives a short URL.
2. Anyone who opens the short URL is redirected to the original.

Often confirmed as in or out of scope, so ask:

• Custom aliases chosen by the user.
• Link expiry.
• Click analytics.
• Editing or deleting links.

Say which you will build first. A good opening is: "I will design creation and redirect, then treat aliases, expiry and analytics as extensions."

Non-functional requirements

These shape the architecture far more than the features do:

• Low latency redirects, in the tens of milliseconds, since a slow redirect makes every page that links to it slow.
• High availability. A dead short link breaks every document, message and page that contains it. Availability matters more than strict consistency here: if a freshly created link takes a second to become visible everywhere, nobody is harmed.
• Uniqueness. Two long URLs must never share a code.
• Scale. State a number. Assume 500 million new links a month, and 100 redirects for every link created.
• Guessability. For private or unlisted links, codes should not be predictable.

Estimation

Do the arithmetic aloud, and use it to decide the design.

Code length. A base-62 alphabet (digits, lowercase, uppercase) with 6 characters gives $62^6\approx 5.7\times 10^{10}$, which is just short of 60 billion. With 7 characters it gives $62^7\approx 3.5\times 10^{12}$, which is ample. Use 7 characters.

Conclusions the numbers support. Writes are trivial, so a single primary handles them for a long time. Reads are 100 times heavier, so the redirect path needs a cache and replicas. Thirty terabytes fits a sharded store comfortably and does not need an exotic one.

2. The set up

Core entities

• URL mapping: the short code, the long URL, creation time, optional expiry, owner.
• User: only if you support accounts and link management.

API

POST /v1/urls
  body: { "long_url": "https://example.com/very/long/path", "alias": "optional", "expires_at": "optional" }
  returns 201: { "short_url": "https://sho.rt/aZ3k9Qd" }

GET /{code}
  returns 302 with Location: https://example.com/very/long/path
  returns 404 for an unknown code, 410 for an expired one

Details that show experience: creation should accept an idempotency key so a retried request does not create two links, the API is versioned in the path, and creation is authenticated and rate limited while redirects are open to anyone.

Data model

One table, accessed almost entirely by primary key:

The dominant query is "get the long URL for this code". That points to a key-value store or a plain relational table with a primary-key index, and either is fine at this scale. Say that, and do not pretend the choice is hard.

3. High-level design

Build the design in the order of the requirements, so the interviewer can follow each addition.

Requirement 1 and 2 together

The first version has a client, a load balancer, stateless application servers and a database. The two flows:

Creating a link. The client sends the long URL. An app server generates a code, writes the mapping to the database and returns the short URL.

Redirecting. The client requests the short URL. An app server looks up the code and returns an HTTP redirect.

Now add the pieces the numbers justify:

• A cache in front of the database, because reads outnumber writes by a hundred to one and the traffic is skewed toward popular links.
• A key service to supply unique codes, because generating a unique code is the hard part and deserves its own component. The next section covers why.

How the redirect path behaves

The path that matters is the read. An app server first checks the cache. A hit returns the redirect immediately. A miss reads the database, fills the cache and then redirects. Click analytics, if you support them, are emitted as an event to a queue and processed later, so they never slow the redirect.

The cache should use a least-recently-used eviction policy, and a cached entry must never outlive the link's own expiry time, or an expired link would keep working.

301 or 302?

Both redirect. They differ in who remembers the result.

• A 301 (moved permanently) is cached by browsers, so repeat visits never reach your servers. That means less load and lower latency, but you cannot count those visits and you cannot change the destination for those users.
• A 302 (found, temporary) goes through you every time. You keep analytics and control, and you pay for the extra traffic.

If analytics or editable destinations matter, choose 302 and say why. If the links are permanent and cost is the concern, 301 is defensible. State the trade-off either way.

4. Potential deep dives

An interviewer who is satisfied with the high-level design will probe one or two of these. Each follows the same pattern: the challenge, then a weak solution, a solid solution and an excellent one, with the reasoning that separates them.

Deep dive 1: How do you generate unique short codes?

The challenge. Every new link needs a code that is unique, short and, for private links, hard to guess. With 190 writes per second and several app servers, two servers must never issue the same code.

Weak: hash the long URL and take the first 7 characters. Hashing is stateless and gives the same code for the same URL. But truncating a hash makes collisions inevitable once the table is large. To handle them you must check the database and retry with a salt, and a check-then-insert has a race condition unless a unique constraint settles it. It also makes two users who submit the same URL share one code, which breaks per-user ownership and analytics.

Solid: a global counter encoded in base 62. A single counter assigns the next number to each link, and the number is converted to base 62. No collisions, and the codes are as short as possible. Two problems: the counter is a single point of failure and a write bottleneck, and sequential codes are guessable, so anyone can walk the whole space and read other people's links. You can improve on both by encoding a permuted or encrypted value of the counter, and by running the counter on a replicated, consensus-backed store. It works, but it keeps a central dependency on the write path.

Excellent: pre-allocated key ranges from a key service. A small replicated key service hands out blocks of unused keys. Each app server claims a block, say a thousand keys, and serves creation requests from memory. When the block runs low it claims another.

Why this is better:

• No per-request coordination. The write path touches the key service once per thousand links, not once per link.
• No collision check, because a block is claimed exactly once, inside one transaction.
• Unguessable. Keys can be generated randomly and stored as unused, so consecutive links get unrelated codes.
• Failure is cheap. If a server crashes with half a block unused, those keys are lost. With 3.5 trillion codes available, losing a few thousand is irrelevant.

The cost: a key service to build and run, and a requirement that claiming a block is atomic. Say both.

A variant worth knowing is the Snowflake-style identifier, used when you need roughly time-ordered unique 64-bit numbers with no central coordination:

| 1 bit unused | 41 bits timestamp (ms) | 10 bits machine id | 12 bits sequence |

Each machine can issue $2^{12}=4096$ identifiers per millisecond, and 41 bits of milliseconds last about 69 years. The failure mode to mention is a clock that steps backwards, which can produce duplicates unless the generator refuses to issue until time catches up. The resulting numbers are 64-bit, so their base-62 form is longer than 7 characters, which is why the key service is a better fit here.

Custom aliases. A user-chosen alias must be unique and must not clash with generated codes. Enforce uniqueness with a constraint and return a conflict error, and keep generated codes and aliases in separate length ranges so they cannot collide.

Deep dive 2: How do you keep redirects fast at 40,000 requests per second?

The challenge. The database cannot take 40,000 reads per second comfortably, and a redirect that waits on it will be slow.

Weak: put more hardware behind the database. Scaling up buys time, but it is expensive, has a ceiling and leaves latency unchanged.

Solid: a cache in front of the database. Traffic is heavily skewed: a small fraction of links gets most of the clicks. An in-memory cache of the hot set absorbs most reads. Use cache-aside with a least-recently-used policy, and size it from the numbers. If the hot set is 20 percent of a day's links, a cache of that size catches roughly 80 percent or more of requests. Add read replicas for the misses.

Excellent: layered caching including the edge. Layer the defences:

1. A CDN or edge function caches redirect responses near the user, which cuts latency worldwide and removes most traffic before it reaches your region. This works best with a 301 or a short-lived cached 302.
2. A distributed cache for the long tail the edge misses.
3. Read replicas behind the cache.
4. A small in-process cache on each app server for extremely hot keys, so a viral link does not overload one cache node.

Also protect against a cache stampede: when a popular entry expires, thousands of requests miss at once. Randomise time-to-live values and coalesce concurrent misses so one request refills the entry while the others wait.

Deep dive 3: How do you scale storage and stay available?

The challenge. Thirty terabytes over ten years, with a requirement that redirects survive failures.

Weak: one large database server. Simple, but it is a single point of failure, and a restore from backup is a long outage.

Solid: a primary with replicas across zones. Writes go to the primary, which replicates to followers in other availability zones. If the primary fails, a follower is promoted. Replication is asynchronous, so a failover can lose the most recent writes, which for this product means a very recent link might need to be recreated. Say that you accept this because availability matters more than strict durability for the last second of writes.

Excellent: shard by a hash of the code, replicate each shard. When the data outgrows one machine, partition by a hash of the code. Because codes are effectively random, the hash spreads both data and load evenly, and the dominant query always includes the shard key, so no request touches more than one shard. Use consistent hashing so that adding a shard moves only a small fraction of the data. Each shard has its own replicas for read capacity and failover.

Keep the redirect path independent of the creation path, so a problem with the key service or a write failure never breaks the redirects of links that already exist.

Deep dive 4: Analytics, expiry and abuse

Click analytics. Weak: increment a counter in the database during the redirect. This puts a write on the hottest path and creates a contended row for popular links. Solid: emit a click event to a queue from the redirect handler and aggregate it asynchronously. Excellent: the same, plus batching and a stream aggregator that writes time-bucketed counts to an analytics store, so dashboards read pre-aggregated data. Accept that counts lag by seconds.

Expiry. Store the expiry time, check it on read and return 410 for an expired link. Delete expired rows with a background sweep rather than in one large operation, and make sure the cache respects the expiry.

Abuse. Short links hide their destinations, so they are used for phishing and malware. Reasonable controls: check submitted URLs against a malicious-link list, rate limit link creation per user and per address, support fast disabling of a code, and show a warning page for flagged destinations. Unguessable codes protect unlisted links, but never treat obscurity as access control for sensitive content.

5. What is expected at each level

Mid-level. A working design: a database keyed by code, a way to generate unique codes that you can defend, a cache, and an honest discussion of collisions or a single counter's limits. You should produce sensible estimates with a little guidance.

Senior. You drive the conversation. You recognise the key-generation problem without being asked, compare at least two approaches with their costs, size the cache and the database from your estimates, and discuss failure: what happens if the key service or a database primary dies. You know the 301 versus 302 trade-off.

Staff. You question the premise as well as answering it: how long must links live, what does deletion mean, how do you handle abuse at scale, what is the cost of the edge layer against the benefit. You discuss multi-region operation, evolve the design as requirements change in the interview, and keep the whole system simple enough to operate.

6. Interview questions and model answers

Q: How do you generate the short code? I would use pre-allocated key ranges from a small replicated key service. Each app server claims a block of keys and serves from memory, so there is no per-request coordination and no collision check. Hashing the URL is a simpler alternative, but it needs collision handling and breaks per-user ownership.

Q: How do you stop sequential codes being guessable? Draw keys from a randomly generated pool, or encode a permuted version of the counter, so consecutive creations give unrelated codes.

Q: Two users submit the same long URL. Do they get the same code? Usually not. Each submission is its own link, because owners, expiry and analytics are per link. If de-duplication is a requirement, I would look the URL up first, scoped to the user.

Q: What breaks first as traffic grows? Database read load on the redirect path. The cache is the first defence, then replicas and the edge. Writes stay modest for a long time, so sharding is a later step, by hash of the code.

Q: How do you count clicks without slowing redirects? Emit an event to a queue from the redirect handler and aggregate it asynchronously, accepting a delay of seconds.

Q: What if the key service is down? App servers keep creating links from their in-memory blocks until those run out, and existing redirects are unaffected because they do not touch the key service. I would size blocks so that a short outage is absorbed.

7. Common mistakes

• Using one auto-increment counter and ignoring both the bottleneck and guessability.
• Truncating a hash and never handling collisions.
• Writing analytics synchronously in the redirect path.
• Choosing 301 without noticing it removes analytics and editability.
• Forgetting expiry, abuse handling and cache invalidation.
• Sharding on a key that is not in the main query.