URL Shortener: key generation, the read path and follow-ups

The design is fifteen minutes of work. The remaining half hour is the deep dives and follow-ups, and they are what the question is actually for.

This lesson takes the requirements, numbers and data model as given. It first chooses how to generate the short key — a choice decided by a collision probability you can compute in thirty seconds, which is why it rewards arithmetic over intuition. It then designs the read path, which is a different system from the write path and should be designed as one. It ends with the follow-ups: aliases, expiry, analytics, abuse and phishing.

Approach 1: hash and truncate

There are three approaches to generating the key. The first: hash the long URL (MD5, SHA-256 — any will do), take the first 7 base-62 characters of the result, and use that as the key.

• For: stateless, no coordination, and the same URL naturally produces the same key.
• Against: collisions. Two different URLs can produce the same 7 characters, and if you overwrite you have sent someone to the wrong site.

Compute the collision probability rather than asserting it. The key space is 62^7 ≈ 3.52 × 10^12. Over five years you store 1.825 × 10^11 keys. The load factor is:

1.825 × 10^11 ÷ 3.52 × 10^12 = 5.2%

So by year five, roughly one in twenty new keys collides with an existing one. That is not an edge case; it is a routine event happening about 50 times per second at peak. Every insert therefore needs a uniqueness constraint and a retry loop: on collision, append a salt to the URL, rehash, and try again. Retries are cheap at 5% and get more expensive as the table fills.

Note the counter-intuitive result the arithmetic gives you: even with 19× more key space than keys, collisions are common. The birthday-problem intuition — collisions arrive far earlier than a naive "space is much bigger than usage" reading suggests — is exactly what the calculation makes concrete.

Approach 2: base-62 encode a unique counter

Get a globally unique, monotonically increasing number from a distributed identifier generator (Section 9), and encode it in base 62.

• For: no collisions are possible, ever, because the input is unique by construction. No uniqueness check, no retry, one insert.
• Against: two real problems, listed below.

The two problems:

• Keys are sequential and therefore guessable — anyone can enumerate aB3xY7z, aB3xY80, and crawl every link in your system, including private ones. This is a genuine security issue for a link shortener, since links are frequently treated as secrets.
• Key length grows over time — early keys are short (c, d), later ones are seven characters. Cosmetic, and it means early keys are trivially guessable.

The fix for guessability: apply a reversible bijective transformation to the counter before encoding — a block cipher over the integer range, or multiplication by a large constant coprime to the space, modulo the space. The mapping stays one-to-one, so uniqueness is preserved, while consecutive counters produce unrelated-looking keys. This is the standard answer and it is worth knowing by name.

Approach 3: a key generation service with pre-generated keys

A separate service generates random unused keys ahead of time, stores them in a table of available keys, and hands out blocks of them to application servers on request.

• For: keys are random (not guessable) and collision-free (the service checked), and the application never does a uniqueness check at write time. Blocks mean one coordination call per few thousand links rather than per link.
• Against: a new service to run, and a state problem — a server that dies with an unused block leaks those keys, so keys must either be reclaimed or accepted as lost. It is also storage: pre-generating a billion 7-character keys is a few gigabytes, which is fine, but pre-generating the whole 3.5-trillion space is not.

The key recommendation

Base-62 encoding of a unique counter, with a bijective scramble. Collisions become impossible rather than merely unlikely, so the write path is one insert with no retry loop, and the scramble removes the guessability objection. State the alternative and the condition:

"If we could not run an identifier generator, I'd use the key generation service, because pre-checked random keys still avoid the collision retry. I'd avoid hash-and-truncate — at 5% load factor by year five, one in twenty inserts collides, so it turns every write into a check-and-retry."

The read path: cache-aside, with a hot set that fits

Three hundred thousand redirects a second, each of which must complete in a few milliseconds.

The redirect service checks the cache first; on a miss it reads the database and populates the cache with a time-to-live. Requirements and scale established the hot set is about 10 GB, which fits comfortably in memory.

The arithmetic that follows is what makes the design work:

At a 95% hit ratio: cache serves 285,000 reads/s, the database serves 15,000 reads/s.

At a 99% hit ratio, achievable because the hot set genuinely fits: the database serves 3,000 reads/s.

Fifteen thousand single-key lookups per second is comfortable for a sharded key-value store; three thousand is trivial. Without the cache it is 300,000, which is not.

TTL choice. URL mappings are immutable in the common case — a short key points at one long URL forever — so a long TTL is safe, say hours. The exception is deletion and expiry: a deleted link must stop redirecting, so a delete must also invalidate the cache key, and the TTL is the backstop if that invalidation is missed. State the window: "a deleted link could keep working for up to the TTL if the invalidation fails, so I would keep it at an hour rather than a day."

Eviction: least recently used, which matches the traffic pattern precisely — links go viral, then die.

The database choice

The access pattern is a single-key lookup at high volume with no joins, no range scans, and no multi-row transactions. That is the definition of a key-value workload, so a key-value or wide-column store partitioned on short_key is the natural fit, and it shards without effort because keys are independent.

A relational database is a defensible answer too — 91 TB across shards, single-row reads — but you are paying for joins and transactions you never use. Say the pattern, name both, and pick one with the reason.

CDN at the edge

Because a redirect response is tiny, cacheable, and needs no authentication, an edge cache can serve it entirely — turning a 130 ms transcontinental round trip into 15 ms.

The catch is the one from The API and data model: a redirect cached at the edge does not reach your servers, so it is not counted and cannot be revoked promptly. Options:

• Short edge TTL (say 60 seconds). Most of the benefit, bounded revocation delay, and click counts under-report by the number of repeat clicks inside 60 seconds.
• No edge caching for links needing per-click analytics; edge caching only for links marked as high-volume and analytics-exempt.

Recommendation: edge caching with a short TTL for the top links only, because the traffic distribution is so skewed that a small number of links carry most of the load, and those are exactly the ones where origin offload is worth an approximate click count.

Geographic distribution and failure

Run redirect services and cache replicas in each region, with the database replicated cross-region asynchronously. A newly created link may take a few hundred milliseconds to become readable in another region — a real staleness window, and an acceptable one for this product, since a link is rarely followed in the first second of its life. Say so rather than ignoring it.

If the database is unavailable, cached links keep redirecting — a large fraction of traffic continues working through a database outage. That is a genuinely good availability property and worth naming in the wrap-up.

Follow-up: custom aliases

A user asks for short.ly/summer-sale.

• Uniqueness across one namespace. Custom aliases and generated keys live in the same table and must not collide. With generated keys coming from a counter (the recommended key scheme above), a custom alias could land on a key the generator will later produce — so either reserve a separate character length or prefix for custom aliases, or check custom aliases against the same uniqueness constraint and let the generator retry on the rare clash.
• Length limits. A 40-character alias defeats the purpose; cap it.
• Reserved words and abuse. Block a list — admin, login, api, settings — anything that could be confused with your own routes, plus offensive terms and names that impersonate known brands. This is a moderation problem as much as an engineering one.
• Squatting. Popular aliases are claimed and hoarded. Real services handle this with account tiers and expiry on unused aliases, which is a product decision, not a technical one.

Expiry and cleanup

Two mechanisms, and you want both:

• Lazy deletion at read time. On lookup, check expires_at; if past, return 410 Gone and delete the cache entry. Costs nothing extra and handles the common case.
• A batch job. Scan for expired rows and delete them, to reclaim storage that lazy deletion never touches because nobody reads it. Run it against a follower and throttle it, so it does not compete with live traffic.

For a store with native time-to-live support, setting the TTL on the row lets the store do it. At 100 million rows a day, the storage reclaimed by expiry is the difference between 91 TB and something much smaller, so the job earns its keep.

Click analytics without slowing the redirect

The redirect must not wait for analytics. The pattern is fire-and-forget to a queue:

1. The redirect service issues the 302 immediately.
2. Asynchronously, it appends a click event — key, timestamp, coarse location, referrer, user-agent family — to a distributed log (Kafka is the common implementation).
3. A stream processor aggregates counts per key per time bucket and writes them to an analytics store.

At 300,000 redirects per second with ~200-byte events, that is 60 MB/s, or 5 TB a day of raw click events. That number is why the events go to a log with a retention window and get aggregated, rather than into the main database as rows. Section 23 (Design an Ad Click Event Aggregation) designs exactly this pipeline properly, including the "did we double-count?" problem.

The delivery guarantee is worth naming: fire-and-forget means at-most-once, so some clicks are lost during a failure. For analytics that is acceptable and should be said out loud. For billing it would not be, and Section 23 shows what changes.

Rate limiting and abuse

Limit link creation per account and per Internet Protocol address (Section 6). Without it, one script creates ten million links overnight, consuming key space and storage, and the service becomes a spam relay.

Malicious URLs

A shortener hides the destination, which makes it attractive for phishing. Three layers:

1. Check at creation against a threat-intelligence feed. Note that a URL can be benign at creation and malicious later, so this is necessary and not sufficient.
2. Rescan periodically, since the destination can change after the link is created.
3. Interstitial warning page for links flagged as suspicious, and immediate disabling for confirmed ones — which is possible only because The API and data model chose 302 over 301.

Add a status column (active, disabled, flagged) checked on the read path, and remember to invalidate the cache when it changes, or a disabled link keeps redirecting for the TTL.