URL Shortener

URL Shortener

System Design series #1 (EP22). Topic skill: skills/url-shortener/. Design a TinyURL / bit.ly at scale, from requirement to operation.

1. The problem and why it is deceptive

The product fits in one sentence: take a long URL, return a short URL, redirect the user to the original. That is exactly why it is a great interview trap. Underneath sit almost every core system design theme: read-heavy load, unique key generation, cache, partitioning, consistency, abuse, analytics, multi-region, cost, and architecture evolution.

The single most important framing: there are two very different flows.

• Create: moderate write. One link is created once.
• Resolve: huge read, latency-critical. That one link may be read millions of times.

Design the architecture around redirect. Everything else bends to it. Anyone who starts drawing Kafka in the first three minutes is answering the wrong question. Product and priority first, technology second.

2. Requirements

Functional: long URL to unique short URL; resolve short to redirect; optional expiry; custom alias; basic analytics (click, timestamp, user agent, referer, approximate country); disable/ban malicious links.

Non-functional, in priority order:

1. Redirect availability. If create fails for a few seconds it is bad; if redirect fails the product dies.
2. Low redirect latency, tens of ms on cache hit.
3. Durability, once a code is issued, the mapping must never vanish.
4. Horizontal read scale.
5. Security / anti-abuse, this product becomes a phishing/malware/spam vector fast.
6. Observability and auditability.

Staff-level extras that separate a senior answer from a staff answer: TTL links, logical delete/tombstone, optional dedup, preview page for suspicious links, rate limit per account/IP/tenant, multi-tenant custom domains, and different SLAs for redirect vs analytics.

3. Scale sizing (back-of-envelope)

Assumptions: 100M new links/month, 3B redirects/month, read:write ~30:1, peak 5x average, 5-year retention.

Writes:  100M / 2.6M s  ~ 38 wps avg,   ~200 wps peak.   Trivial.
Reads:   3B   / 2.6M s  ~ 1157 rps avg, ~6k rps peak.    Comfortable.

But enterprise clients, a viral campaign, an event QR code, or global usage can push reads to tens or hundreds of thousands per second. Design to grow even if v1 is small.

Storage: ~1 KB/record (code 8-10 B, long URL ~500 B, metadata 100-200 B). 6B records over 5 years = ~6 TB raw, 15-25 TB with indexes, replication, and backup. The crucial distinction: hot data is small, total data is large. That drives heavy caching in front of durable, partitionable storage.

Analytics: 3B events/month. Never a synchronous counter on the transactional DB. Decouple it.

4. API

POST /v1/links   {long_url, custom_alias?, expires_at?, domain?, idempotency_key?}
              -> {short_url, code, created_at, expires_at}

GET /{code}   -> 301 if the mapping is immutable (lowest perceived latency on repeat)
                 302/307 if you want flexibility (avoids aggressive client caching when target
                 may change)

The 301-vs-302 choice is control vs efficiency. 301 is cached hard by clients and intermediaries, so repeat redirects are instant but you lose the ability to change or revoke cheaply. 302 keeps control at the cost of a server round trip each time. Product questions that change the architecture: can a link be edited after create? can an alias be reused after expiry? same long URL = same code or not? These drive idempotency, cache, and invalidation.

5. Data model

Two domains, deliberately separated.

Transactional links table

code PK, long_url, url_hash?, owner_id?, domain, created_at, expires_at?,
status(active|disabled|expired|banned), is_custom, redirect_type, metadata_json

Indexes: PK on code, (owner_id, created_at), expires_at if TTL cleanup is frequent, url_hash if dedup.

Analytics events (asynchronous, columnar / data lake / stream)

code, timestamp, ip_prefix or hashed IP, user_agent_hash, referer_domain, country, device_type

Never on the synchronous redirect path.

6. Theory, short-code generation

The classic interview core. Four approaches, with their failure modes.

A. Hash of the long URL, truncated, base62

Deterministic and trivially dedup-able, but truncation collides, the same input always yields the same code (bad when two users want distinct links for the same landing page), and the output is predictable and enumerable.

B. Sequential ID, base62 encoded

Simple, short, collision-free with a good generator. But a pure sequential ID is predictable: it leaks your total volume and is trivially scrapeable by incrementing.

C. Unique ID + reversible obfuscation, base62 ← recommended

Generate a 64-bit unique ID, pass it through a keyed bijection (a Feistel network or another bijective permutation), then base62-encode. The bijection preserves uniqueness (no collisions) while destroying predictability (you cannot guess neighbors without the key). Optional fixed-length pad.

Why a Feistel network? It is a construction (Horst Feistel, IBM, 1970s, the basis of DES) that turns any function into an invertible permutation over a fixed bit-width. For short codes it gives you a 1:1, reversible, key-dependent scramble of the ID space, uniqueness for free, unpredictability by construction. This is the standard "encrypt the counter" trick.

Base62 and code length

Base62 = [A-Za-z0-9]. Capacity: 62^7 ~ 3.5 trillion, 62^8 ~ 218 trillion. Seven characters fit most platforms; eight gives operational slack. Custom aliases bypass this entirely.

Staff framing

Centrally-coordinated unique ID by ranges (or decentralized with a uniqueness guarantee), reversible bijection to cut predictability, base62 encode, and validate uniqueness in storage as the last line of defense (a unique index catches the impossible).

7. Theory, unique ID generation

Approach	How	Trade-off
DB auto-increment	the database hands out the next integer	fine for MVP; central hotspot; blocks active multi-region
Snowflake-style	timestamp | worker id | local sequence in 64 bits	horizontal, roughly time-ordered, DB-independent; watch clock skew, worker-id coordination, bit layout
Range allocation	a service hands each instance a block of 1M IDs to consume locally	very simple, near-zero per-request coordination; wastes IDs on restart (usually fine), needs reliable refill

Twitter's Snowflake (2010) is the canonical 64-bit scheme: ~41 bits timestamp, ~10 bits machine, ~12 bits sequence. For a URL shortener, range allocation or snowflake both work well.

8. Create flow

1. Validate the URL (see below).
2. If custom alias, check availability and policy.
3. Generate the code.
4. Persist to the transactional DB.
5. Write-through to cache.
6. Return short_url.

URL validation is not cosmetic. Accept only http/https. Block SSRF targets: 127.0.0.1, 169.254.169.254 (cloud metadata), RFC1918 private ranges, internal hostnames. Canonicalize. Enforce a size limit. Handle punycode and suspicious characters. (SSRF, Server-Side Request Forgery, is the real risk: your validator fetching an attacker-supplied internal URL.)

Idempotency. Store the response per idempotency_key for a short window so a client retry after a timeout does not mint duplicate links.

Dedup, default no. Globally deduping by long URL breaks per-campaign and per-tenant analytics, leaks privacy (a user learns someone else already shortened a link), and blocks distinct links for the same landing page. If you want it, dedup only as an internal storage optimization, separating the logical link entity from the physical URL target.

9. Redirect flow (the heart)

sequenceDiagram
  Client->>Edge: GET /abc123X
  Edge->>Cache: lookup code
  alt cache hit
    Cache-->>Edge: target
  else miss
    Edge->>DB: read (replica), validate status + expiry
    DB-->>Edge: target
    Edge->>Cache: populate (TTL)
  end
  Edge-)Analytics: emit click event (async)
  Edge-->>Client: 301/302 Location

Loading

Negative caching. If someone hammers random codes, every miss hits the DB, a miss storm. Cache the "nonexistent" result for a short TTL (30-60s).

TTL choice. If the mapping is immutable, TTL can be hours and invalidation nearly disappears. If links can be disabled or edited, choose a short TTL, event-based invalidation, or split layers: keep the destination near-immutable (cached hard) and use a fast blacklist layer for urgent blocks.

10. Theory, cache and the read path

This is a textbook cache-heavy read path.

• L1 local in-process cache for extreme hot keys (small, short TTL).
• L2 distributed cache (Redis) shared across instances.
• DB as source of truth.

Hot key problem. A viral link concentrates load. Beyond a good cache, staff thinks about:

• Single-flight (request coalescing) on miss: if 1000 requests miss simultaneously, exactly one fetches the DB and the rest wait on its result. Without this, a cold hot-key causes a cache stampede (a.k.a. thundering herd / dog-piling) that can topple the DB.
• Refresh-ahead: refresh a hot entry before it expires so it never goes cold under load. The probabilistic variant (Vattani et al., Optimal Probabilistic Cache Stampede Prevention, 2015) refreshes early with a probability that rises as expiry approaches.
• Ensure the hot value fits in L1; limit concurrent refresh.

11. Theory, storage choice

The workload: PK lookup by code, few relations, moderate write, very high read, strong durability. SQL or a persistent KV both fit. What matters is efficient key lookup, mature replication, reliable backup/restore, and team familiarity.

Pragmatic pick: a mature relational database (Postgres) with partitioning when needed, read replicas, and heavy cache in front. Evolve to a Dynamo/Cassandra-style distributed KV only when scale truly forces it. The staff answer is the smallest system that holds the load with margin and evolves safely, not the most exotic technology. (Amazon Dynamo, DeCandia et al. 2007, is the reference for the distributed-KV end of that spectrum: consistent hashing, quorum reads/writes, eventual consistency.)

12. Partitioning

Partition by code or its internal ID.

• Hash partition: even distribution, good for random lookup; harder rebalancing, no time locality. Consistent hashing (Karger et al., 1997) minimizes the keys that move when you add or remove a node, the standard technique.
• Range partition by time/ID: good archive and lifecycle, good locality, but a monotonic ID creates a hot newest shard.

For redirect lookup, prefer hash or a pseudo-random distribution over the obfuscated ID. Analytics partitions differently (by time).

13. Consistency

• Strong consistency required: custom-alias uniqueness (unique index on (domain, code)), link persisted before the success response, critical admin status changes.
• Eventual consistency acceptable: analytics, cross-region DR replication, aggregated dashboards.

Read-after-write. If a user creates a link and immediately clicks it, they expect it to work, even if a read replica has not caught up. Resolve via region-sticky reads for a few seconds, write-through cache (the cleanest, the redirect reads the cache the create just wrote), or a fallback to primary when the replica lags.

14. Multi-region

Separate create and resolve.

• Resolve is read-dominant and cacheable, push to edge and multiple regions, stateless regional service with a strong regional cache.
• Create can start single-writer per primary region, which simplifies alias uniqueness and ID generation.

Evolution: (1) one create region, many redirect regions with replica + cache; (2) multi-region create with per-region ID ranges/namespaces; (3) sophisticated active-active only if the business demands it. Avoid premature active-active.

15. Analytics without hurting redirect

Redirect is path A. Analytics is path B. Never tightly couple them.

Redirect responds fast; the click event goes to a queue or log; consumers aggregate counters per minute/hour/day/country/device/referer; dashboards query a separate analytical store. If the queue dies: best-effort (drop analytics, keep redirect), short local buffer with retry, or sampling under degradation. Always preserve redirect first. Retention tiers: raw 30 days, hourly aggregate 1 year, daily aggregate 5 years. For unique-visitor counts at this volume, HyperLogLog (Flajolet et al., 2007) estimates cardinality in kilobytes instead of storing every ID.

16. Security and anti-abuse

Risks: phishing, malware distribution, spam, link enumeration, open-redirect abuse, SSRF during validation. Controls: rate limit per IP/token/tenant/suspicious ASN, domain reputation at create time, safe-browsing checks (sync or async by risk), fast link disable, preview interstitial for suspicious links, progressive friction/CAPTCHA, stronger auth for high-volume accounts.

Anti-enumeration: obfuscation + adequate code length + rate limit on the resolve endpoint + scan-pattern monitoring. Privacy: minimize, truncate, or short-window-hash IPs.

17. Lifecycle and custom alias

Expiry: persist expires_at, validate at read time (do not rely only on an offline cleanup job, an expired link could otherwise survive in cache), evict on expiry, run an async cleanup job for archive/logical delete. Tombstone banned or removed links to prevent reuse and aid audit.

Custom alias needs strong consistency (unique index on (domain, code)), reserved words (admin, login, api), per-tenant policy, and no collision with internal routes. It is a minority of traffic but high value, so a stricter create flow is justified.

18. Observability

Metrics: create/resolve QPS, resolve p50/p95/p99, cache hit ratio per layer, errors by class, not-found rate, banned/expired access rate, create-to-first-resolve propagation time, analytics pipeline throughput and lag. Logs: sampled access logs, audit logs for admin operations, structured with correlation id. Tracing: full on create; sample on the hot resolve path. Alerts: cache-hit-ratio drop, p99 rise, redirect error over threshold, abnormal 404 growth (scan), analytics backlog growth.

19. Failure modes

Failure	Impact	Mitigation
Cache down	DB avalanche	rate limit + circuit breaker, L1 for hot keys, degrade analytics, shed suspicious traffic
DB degraded	misses and creates suffer	serve hot keys from cache, queue/retry creates, failover to promoted replica, protect alias ops
Region down	regional outage	DNS/anycast to another region, pre-warmed replicas/caches; create may pause, redirect must survive
Reputation system down	abuse risk	degraded mode with local rules, more friction for new users, later review of links from the window

20. Roadmap

1. MVP robust: one region, stateless API, Postgres primary + replica, Redis cache, range ID generator, analytics on a queue, basic offline dashboard.
2. Medium scale: L1 local cache, hot-key control, DB partitioning or distributed storage, multi-region redirect, maturer analytics, layered reputation.
3. Global scale: multi-region create with per-region ranges, tested automatic failover, per-tenant custom domains, premium branded links with per-client SLA, edge compute for some redirects.

21. Common mistakes

Start from technology not requirements; let analytics block the critical redirect path; truncated hash without discussing collision and predictability; ignore security and abuse; shard too early when relational + cache still holds; skip cache invalidation, expiry, and read-after-write; skip operations (metrics, failover, degradation).

References

• Martin Kleppmann, Designing Data-Intensive Applications, O'Reilly, 2017 (load params, consistency, replication, partitioning).
• DeCandia et al., Dynamo: Amazon's Highly Available Key-value Store, SOSP, 2007 (distributed KV, consistent hashing, eventual consistency).
• Karger et al., Consistent Hashing and Random Trees, STOC, 1997.
• Twitter Engineering, Announcing Snowflake, 2010 (distributed unique IDs).
• Horst Feistel, Cryptography and Computer Privacy, Scientific American, 1973 (Feistel networks).
• Flajolet et al., HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm, 2007.
• Vattani, Chierichetti, Lowenstein, Optimal Probabilistic Cache Stampede Prevention, VLDB, 2015.
• Michael Nygard, Release It!, 2nd ed., 2018 (circuit breaker, bulkhead, single-flight thinking).
• OWASP, Server-Side Request Forgery Prevention Cheat Sheet.