Design TinyURL

Turn long URLs into short links and redirect visitors fast, at billions of redirects a day, with optional custom aliases and expiry.

We are building a URL shortener: a service that maps a long URL to a 7-character code on a short domain (sho.rt/aZ3kQ9x) and redirects anyone who visits the code, with optional custom aliases and expiry.

Clarifying questions worth asking up front: Can the same long URL get different codes for different users? (Yes; dedupe only per user and request.) Are links editable after creation? (Destination no, expiry yes.) Do we need click analytics? (Yes, counts within a minute; not on the redirect path.) 301 or 302? (Decided below.)

Functional requirements

• create(long_url, alias?, expires_at?) → short_url. Random code if no alias is given.
• Custom aliases: 4–32 chars of [A-Za-z0-9_-], first come first served, reserved words blocked.
• GET /{code} redirects to the long URL; unknown code → 404, expired or disabled → 410 Gone.
• Owners can list their links, change expiry, disable a link, and see click counts.

Non-functional requirements

• Redirect p99 under 20 ms at the edge, under 50 ms on a cache miss. Redirects matter far more than creates.
• 99.99% availability for redirects. A brief create outage is acceptable; a redirect outage breaks every link ever shared.
• A code, once issued, never points at a different URL. No collisions, ever.
• Codes are not guessable in sequence (no enumerating everyone's links).
• Read-your-writes for the creator: a link works the moment the API returns it.

Back-of-the-envelope estimation

• Writes: 100M new links/day ≈ 1,200/s average, 5K/s peak.
• Reads: 100:1 read/write → 10B redirects/day ≈ 115K/s average, ~500K/s peak, with single viral links at 50K/s.
• Storage: one row ≈ 500 B (URL averages 200 B plus metadata and index overhead). 100M/day × 365 × 5 years ≈ 180B rows ≈ 90 TB before replication.
• Code space: base62, 7 chars = 62^7 ≈ 3.5 trillion. 180B is 5% of it, so random codes rarely collide (see deep dive).
• Cache: redirects follow a power law; the hottest 20% of links (about 20M live in a day) take most traffic. 20M × 500 B ≈ 10 GB, which fits in one Redis cluster with room to spare.
• Click events: 10B/day × 100 B ≈ 1 TB/day into the log, compacted to per-link-per-minute counters.

POST /v1/links                         Idempotency-Key: <uuid>
  { "long_url": "https://...", "alias": "launch", "expires_at": "2027-01-01T00:00:00Z" }
  201 { "code": "launch", "short_url": "https://sho.rt/launch", "expires_at": "...", "created_at": "..." }
  409 { "error": "alias_taken" }   422 { "error": "invalid_url" | "blocked_domain" | "reserved_alias" }

GET /{code}
  302 Location: https://...   Cache-Control: private, max-age=0   (or 301, see trade-offs)
  404 not found   410 expired/disabled   429 abusive client

GET    /v1/links?cursor=...&limit=50    → { "links": [...], "next_cursor": "..." }
GET    /v1/links/{code}                 → link metadata + { "clicks_total", "clicks_24h" }
PATCH  /v1/links/{code}  { "expires_at": ..., "disabled": true }
GET    /v1/links/{code}/stats?from=&to=&bucket=hour → [{ "t": ..., "clicks": n, "top_referrers": [...] }]

Creates are authenticated (API key or session) and rate limited per account. The same Idempotency-Key within 24 h returns the original response, so a retried POST never mints two codes. Stats are eventually consistent (about a minute behind); the contract says so.

Links store: DynamoDB or Cassandra, partitioned by code. Every access on the hot path is a single-key lookup, data grows to ~90 TB, and there are no cross-row transactions. A conditional put ("insert if not exists") gives collision-proof creates.

links_by_owner is written from the links change stream, so it can lag by a second; the list page tolerates that. Native TTL deletes expired rows a grace period after expires_at (see 410 below). Raw click events go to Kafka and then to S3/a columnar store, never to the links table.

Redis cache: l:{code} → {long_url, expires_at, status}, TTL 24 h with jitter; neg:{code} → empty marker, TTL 60 s.

flowchart LR
  U[Visitor] --> CDN[CDN edge]
  CDN --> RS[Redirect service]
  RS --> RC[(Redis cache)]
  RS --> DB[(Links store)]
  RS -. click event .-> K[Kafka]
  K --> AGG[Stream aggregator]
  AGG --> CC[(Click counts)]
  A[Creator] --> API[Link API]
  API --> KG[Code generator]
  API --> DB
  API --> SAFE[URL safety check]
  DB -. change stream .-> OWN[(Links by owner)]

1. Create. The API validates and normalizes the URL, checks it against a malware/phishing list, and looks up the idempotency key. For a random code it draws 7 base62 chars from a CSPRNG and does PutItem(code) if attribute_not_exists(code); on conflict it draws again (expected retries ≈ 0.05). For an alias the same conditional put either wins or returns 409. It stores the idempotency record and returns 201. The write goes to the leader/quorum, so the creator's first click hits a committed row.
2. Redirect. The CDN serves the 302 for hot codes when we allow a short edge TTL. On a miss, the redirect service reads l:{code} from Redis; on a cache miss it reads the links store, fills Redis (cache-aside), and returns 302, or 404 (writing a negative entry) or 410. It emits the click event fire-and-forget to a local buffer that ships to Kafka.
3. Routing. Both the cache and the store are hash-partitioned on code. Redis uses consistent hashing (16,384 slots); the store routes by partition key. Any redirect node can serve any code; nodes are stateless behind an L4 load balancer.
4. Analytics. The aggregator rolls events into per-minute counts per code and updates click_counts; the stats endpoint reads those.
5. Failure. Redis down → redirects fall through to the store, protected by request coalescing and a concurrency cap; the store down → keep serving from Redis and the CDN, which hold most live traffic; Kafka down → the local buffer drops oldest events after it fills, and redirects never wait.

Short-code generation.

At 180B of 3.5T used, a random draw collides with probability ~5%; the conditional put catches it and we redraw, so expected attempts are 1.05 and three misses in a row is about 1 in 8,000. If utilization ever passes ~30%, move to 8 characters (218T space) for new codes. The range-lease scheme is the answer if the interviewer forbids the read-before-write: shuffle the counter with a format-preserving cipher (e.g. a Feistel network over the 62^7 domain) so codes look random but stay unique without a check.

Sharding, routing, and viral hot keys. Partitioning by code spreads load evenly because codes are random, so no shard owns a "popular range". The problem is one code at 50K/s: a single Redis shard handles ~100K simple ops/s, but a few viral links on the same shard saturate it. Defenses in order: (1) CDN caching of the redirect itself for 30–60 s absorbs most of it at the edge; (2) a small in-process LRU in each redirect node (10K entries, 5 s TTL) turns 50K/s into one Redis read per node per 5 s; (3) for detected hot keys, replicate the cache entry to l:{code}#0..7 and read a random suffix. The store never sees hot keys after the cache warms, but request coalescing (one in-flight load per code per node) stops a cache-expiry stampede from reaching it.

Cache-aside, TTL, and invalidation. Links are almost immutable, which makes caching easy: the destination never changes, so only status and expires_at can go stale. Rules: cache TTL is min(24 h, expires_at − now) with ±10% jitter, so an expiring link drops out of cache on time without a purge. On PATCH (disable or new expiry) the API writes the store, then deletes l:{code} and issues a CDN purge; a disabled phishing link stops resolving within seconds at the origin and within the purge time at the edge. Negative entries (neg:{code}, 60 s) stop scanners hammering the store with random codes, and must be deleted on create, which is why the create path also does a cache delete for its new code. Miss path: Redis timeout of 5 ms, then read the store with a 30 ms timeout; if both fail, return 503 rather than a wrong 404.

Expiry and 410 Gone. Return 410 for a link that existed and expired or was disabled, and 404 for one that never existed: clients and crawlers treat 410 as permanent and drop it. Keep expired rows (tombstoned) for a grace period of 1 year before TTL deletion, and do not reissue that code during the grace period, or an old printed link would silently point somewhere new. Custom aliases are never recycled at all.

Async click analytics. The redirect handler appends {code, ts, referrer, country, ua_class} to an in-memory ring buffer and returns; a background thread batches to Kafka every 50 ms. Kafka is partitioned by code, so a stream job (Flink) keeps per-code minute counters and writes them every minute, with exactly-once via checkpoints. Viral codes make one Kafka partition hot; pre-aggregate in the redirect node (count per code per second) before sending. Losing a few seconds of clicks during a node crash is acceptable and stated in the contract.

• 302 vs 301. A 301 is cached by browsers forever, which removes load but makes clicks invisible and a disabled link keeps redirecting on that browser. Use 302 by default; offer 301 only for links without analytics or expiry.
• Random codes with a check vs pre-allocated ranges. Random codes need no coordination but cost a conditional write per create; ranges skip the check but add a lease service and a cipher to keep codes unguessable.
• NoSQL key-value vs relational. DynamoDB/Cassandra scale writes and storage without manual sharding but give up ad hoc queries and cross-table transactions; the owner index is built asynchronously and lags.
• CDN-cached redirects cut origin load by 90%+ but delay a disable by the edge TTL and hide some clicks from origin logs unless the CDN ships its own logs.
• Read replicas for the redirect path add capacity but can serve a stale "not found" for a brand-new link; so on a replica miss, retry once against the leader (or read at quorum) before returning 404, and never write a negative cache entry from a replica miss.
• Fire-and-forget clicks keep redirects fast at the cost of losing a small fraction of events on crashes.
• Abuse controls (URL blocklists, per-account create limits, reserved paths like api, admin, login, static) add latency to creates and false positives, but a shortener without them becomes a phishing service and gets its domain blocklisted.

Mid-level (L4)

• Clear API, base62 math showing 7 characters is enough, and a key-value table keyed by code.
• Cache in front of the database for redirects, with a reason the read:write ratio justifies it.
• Handles custom aliases with a uniqueness check and knows 301 vs 302.

Senior (L5)

• Compares code-generation schemes with collision probability and guessability, and makes creates idempotent.
• Cache-aside with TTL tied to expiry, negative caching, stampede protection, and 404 vs 410.
• Keeps analytics off the redirect path with a queue and stream aggregation; sizes storage and cache from numbers.

Staff (L6+)

• Plans for viral hot keys across CDN, local cache, and key replication, and for the failure of each tier.
• Treats the never-repoint guarantee and code reuse after expiry as product and security decisions.
• Addresses abuse (phishing, scanners, reserved paths), domain reputation, staleness with replicas, and multi-region reads with a single-writer rule for creates.