Designing a URL Shortening Service like TinyURL

1. Requirements and Goals

Functional:

• Given a long URL, generate a short, unique alias (short link).
• When users access a short link, redirect them to the original URL.
• Optionally support custom aliases and expiration times.
• Expose analytics (click count) and deletion.

Non-functional:

• High availability is critical — if the service is down, every published short link breaks.
• Low latency: redirects should be sub-100 ms.
• Short links should not be guessable.

2. Capacity Estimation

Assume 500M new URLs/month and a 100:1 read:write ratio.

3. API Design

• POST /shorten → { original_url, custom_alias?, expiration? } returns { short_url, created_at, expires_at? }.
• GET /{short_key} → 301 redirect to original_url (or 404/410).
• GET /analytics/{short_key} → click count, unique visitors, referrers.
• DELETE /{short_key} → remove mapping (owner only).

4. Data Model

One table/collection urls:

Which store? Billions of tiny rows, pure key–value access by short_key, no joins, no cross-row transactions — a key-value / wide-column store (DynamoDB, Cassandra) fits naturally and shards by key without ceremony. Partitioned Postgres/MySQL is perfectly fine at lower volume (tens of millions of links, one team, one region); the access pattern is what decides, not fashion — nothing here uses the relational features you would be paying for.

5. High-level Design

6. Detailed Design: Key Generation

Two common strategies:

• Hash + collision check: MD5/base62 of the long URL. Risk: same hash for different URLs; must check and retry with a salt.
• Dedicated key service (KGS): A pre-generated pool of unique base62 keys in a range. Each app server reserves a batch, eliminating collisions at write time.

For 7-character base62 keys, the space is 62^7 ≈ 3.5 trillion, enough for the estimated 30 billion records with room to spare.

KGS concurrency, range caching, and crash recovery

If every shorten call hits the database for the next free key, the KGS becomes the write bottleneck. The production pattern:

1. Range lease. A KGS instance atomically claims a block of unused keys from a coordination store (e.g. ZooKeeper, etcd, or a single-row CAS on a key_counter table): KGS-1 gets [1_000_000, 1_010_000), KGS-2 gets [1_010_000, 1_020_000). No two instances receive overlapping ranges.
2. In-memory cache. The KGS (or each app server that received a sub-range) holds the remaining keys in RAM and hands them out with no DB round-trip per write. When the local buffer is low, it claims the next range.
3. Crash recovery. If KGS-1 dies with keys still in its RAM cache, that residual range is discarded, never reused. The huge key space (62⁷ ≈ 3.5 trillion; even 6 characters gives ~57 billion) makes a few thousand lost keys acceptable; reusing a range risks two URLs mapping to the same short code.

Unguessability. A naive counter (or sequential range) hands out enumerable keys — an attacker who sees abc123x can walk the neighbouring codes and harvest other people's links, violating the not-guessable NFR. Close the gap at issue time: pre-generate the key pool and hand keys out in random order, or run the counter through a keyed bijection (e.g. a Feistel permutation over the 62⁷ space) so consecutive counter values map to scattered, unpredictable codes. Range leasing still works unchanged — the ranges are over counter values, not over the issued codes.

ZooKeeper (or equivalent) is only for range coordination — the critical path of redirect still goes cache → DB, not through ZK.

7. Example Request Trace

8. Trade-offs

• Hash-based keys are deterministic and cache-friendly, but require collision handling.
• Pre-generated keys avoid collisions but need a coordination service and can waste unused keys.
• Write-back cache lowers redirect latency but may lose analytics events on failure; use a durable message queue for analytics.
• Custom aliases improve UX but increase collision risk and require reservation logic.

9. Takeaways

• URL shortening is read-heavy; optimize the redirect path with caching and 301 responses.
• Use a large, collision-resistant key space (base62 with 7+ characters).
• Separate analytics ingestion from the critical redirect path to keep latency low.
• Prefer 301 for stable links so browsers/CDNs cache the mapping and cut repeat load — but return 302 when you need to count every click, because aggressive 301 caching hides per-hit analytics (see the trade-off below).

Re-authored and RESHADED for the Knowledge Guide. Replaces raster diagrams with a hand-authored SVG flow and adds a concrete request trace.

Named bottlenecks, the 301-vs-302 trade-off, and when not to build this

301 vs 302: 301 permanent → browsers/CDNs cache aggressively (good for stable links; bad if you need click analytics on every hit). 302 temporary → more origin hits, better counting.

When not custom shortener: low volume internal tools — use managed bitly-class or even DB sequence + base62 without distributed design.

Drill ladder

1. L1: 7-char base62 space size?
2. L2: Why not MD5 of URL as key alone?
3. L3: Design counter service without single SPOF.
4. L4: Analytics pipeline: redirect path must stay <50 ms — how?