-
Notifications
You must be signed in to change notification settings - Fork 0
URL Shortener
System Design series #1 (EP22). Topic skill:
skills/url-shortener/. Design a TinyURL / bit.ly at scale, from requirement to operation.
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.
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:
- Redirect availability. If create fails for a few seconds it is bad; if redirect fails the product dies.
- Low redirect latency — tens of ms on cache hit.
- Durability — once a code is issued, the mapping must never vanish.
- Horizontal read scale.
- Security / anti-abuse — this product becomes a phishing/malware/spam vector fast.
- 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.
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.
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.
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.
The classic interview core. Four approaches, with their failure modes.
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.
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.
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 = [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.
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).
| 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.
- Validate the URL (see below).
- If custom alias, check availability and policy.
- Generate the code.
- Persist to the transactional DB.
- Write-through to cache.
- 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.
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
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.
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.
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.)
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).
-
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.
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.
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.
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.
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.
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.
| 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 |
- MVP robust — one region, stateless API, Postgres primary + replica, Redis cache, range ID generator, analytics on a queue, basic offline dashboard.
- Medium scale — L1 local cache, hot-key control, DB partitioning or distributed storage, multi-region redirect, maturer analytics, layered reputation.
- 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.
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).
- 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.
The harness
- Harness Engineering
- References
- Guides
- Sensors
- Evals
- Pipeline and Stages
- Golden Path
- Agents
- Agent Pipelines
- Designer Skill
v5: autonomy
System design