Design a URL shortener: uniqueness, fast redirects and safe revocation
Start with the difference between a public alias and an authorization token, then follow one alias from creation through caching, deletion and analytics. These are proposed interview choices, not TinyURL implementation claims.
1. Ask what a short link must guarantee
Before drawing a key generator, I would clarify whether these are public marketing links or private document links. A short URL is a locator, not permission to read its destination. I will solve public links and keep the destination responsible for authorization.
| Candidate asks | Illustrative interviewer reply | Design consequence |
|---|---|---|
| Which actions are required? | Create, redirect, custom alias, expire and delete. | Management writes and latency-sensitive redirects need separate paths. |
| Can owners edit the destination? | No; delete and create another alias. | Immutable destinations simplify caching; status and expiry still change. |
| What is the workload? | 100 million creations per 30 days; 100 redirects per creation. | Size read traffic independently from stored mappings. |
| How long do links live? | Up to five years, with optional earlier expiry. | Retention is distinct from cache TTL; never silently recycle old aliases. |
| How quickly must deletion take effect? | Within 60 seconds; emergency abuse blocks sooner where reachable. | Bound positive cache TTL and distribute invalidations; no absolute global instant promise. |
| What analytics are needed? | Approximate clicks by day and country. | Keep tracking asynchronous and disclose bot, cache and event-loss limitations. |
| Are private or unguessable links required? | Public links only. | Randomness reduces predictability but cannot replace access control. |
2. Agree behavior before selecting infrastructure
My core invariant is one committed destination per alias. I prioritize existing redirects during a create-service outage, but I will not serve an expired cache entry just to improve availability. I propose the following targets for discussion; they are not measured production guarantees.
| Requirement | Agreed target or scope | Design implication |
|---|---|---|
| Create and manage | Authenticated owners; unique custom aliases; 201 after durable commit. | Conditional insert and ownership checks on every management request. |
| Redirect | p99 under 100 ms at service edge; 99.99% monthly availability target. | Cache popular mappings, isolate management resources and measure origin misses separately. |
| Deletion and expiry | Cache lifetime at most 60 seconds and never beyond expiresAt. | On expired cache entry, revalidate; unavailable origin can produce 503. |
| Safety | Only http/https destinations; bounded URL length; abuse reporting. | Validate scheme/host syntax; isolate any preview or malware-scanning fetcher from internal networks. |
| Outside first scope | No editable destinations, private-link ACL system or exact billing analytics. | Avoid promising cache invalidation or event accuracy that the baseline does not provide. |
3. Keep one capacity ledger
I use decimal units and 30-day months throughout. Daily and peak traffic are different quantities: a 10x peak assumption sizes capacity but does not multiply five-year storage by ten. The service redirects; it does not proxy the destination page.
| Quantity | Calculation | Interpretation |
|---|---|---|
| Creates | 100M / 2,592,000 seconds = 38.6/s average; 386/s at 10x. | Uniqueness writes are modest compared with redirect reads. |
| Redirects | 10B / 2,592,000 = 3,858/s average; 38,580/s at 10x. | A 95% cache-hit assumption leaves 193/s average origin lookups; validate skew. |
| Mappings | 100M × 60 months × 500 bytes = 3 TB logical. | Three copies = 9 TB before indexes, backups and allocator overhead. |
| Redirect bytes | 10B × 200 bytes / 30 = 66.7 GB/day. | Illustrative headers only, excluding TLS and destination content. |
| Analytics | 333.3M clicks/day × 100 bytes = 33.3 GB/day. | Thirty days = 1 TB raw before replication; retention policy matters. |
| Alias space | 62^8 = 218,340,105,584,896 possible aliases. | At 6B retained aliases, occupancy is about 0.00275%; still use insert-if-absent, never assume no collision. |
4. Define authoritative data and cache versions
I partition lookup records by a hash of the alias and keep a separate owner index for management. The alias record is authoritative. A deletion writes a versioned tombstone before invalidation; cache contents never establish ownership.
| Record and key | Fields / invariant | Access pattern |
|---|---|---|
| Link(alias) | ownerId, destination, createdAt, expiresAt, status, version. Alias cannot be reassigned. | Point lookup for redirect; conditional insert for allocation. |
| CreateRequest(ownerId, key) | payloadHash and resulting alias, stored atomically with mapping or in the same durable transaction. | Replay the same result; reject a reused key with a different payload. |
| OwnerLinks(ownerId, createdAt, alias) | Derived listing index with stable cursor. | Listing lag is acceptable; mutations verify the primary Link owner. |
| Cache(alias) | destination, status, version, expiresAt and cache-valid-until. | TTL is min(60 seconds, remaining link lifetime); do not extend on a stale read. |
| Click(eventId) | alias, time bucket, coarse location, bot classification. | Append asynchronously; limit personal data and deduplicate within the analytics retention window. |
5. Specify errors and uncertain outcomes
A client timeout does not tell us whether creation committed. I therefore return the original alias when the same authenticated owner retries the same idempotency key. Custom aliases are validated against reserved names before the uniqueness check.
| Operation | Contract | Failure or retry behavior |
|---|---|---|
| POST /links | Body: destination, optional alias and expiresAt; Idempotency-Key header. Return 201 with alias and management URL. | 409 for occupied custom alias or changed payload under the same key; generated alias collisions retry internally with a bound. |
| GET /{alias} | 302 with Location for a live mapping; explicit Cache-Control consistent with the 60-second revocation contract. | 404 for unknown, 410 for expired/deleted where disclosure is acceptable; 503 when safe validation is unavailable. |
| DELETE /links/{alias} | Owner-authenticated, version-aware tombstone write. | Idempotent for already-deleted records; unauthorized callers receive a non-disclosing error. |
| GET /links?cursor=... | Owner-scoped management list. Cursor binds owner and ordering. | A stale list may show a deleted item; clicking it consults current primary state. |
6. Draw a minimal write and redirect architecture
I start with stateless creation and redirect services, a durable mapping store and a shared cache. The architecture does not need a separate key-generation service at 386 peak creates per second. Analytics is intentionally outside the redirect critical path.
7. Narrate creation and the collision race
Suppose two workers choose the same alias. Both may observe it as absent, so a separate read-then-write is not sufficient. Only one conditional insert can win. I treat generation as optimistic allocation and let the durable uniqueness constraint arbitrate.
Validate the request
Authenticate owner, apply creation quota, reject unsupported schemes and oversized values. Any server-side URL fetch runs in an isolated worker with redirect and private-address defenses.
Resolve idempotency
Look up owner plus key; a matching payload returns the committed result. Concurrent identical requests serialize through a unique request key in the write transaction.
Allocate and commit
Generate a cryptographically random Base62 alias or use the requested alias. Insert mapping and request result atomically. On random collision generate another alias; on custom collision return 409.
Return after durability
Return 201 only after the declared replicated commit. Do not return a cache-only alias. If the response is lost, a retry resolves the stored result.
Publish status changes
For deletion, persist a higher version/tombstone and invalidation intent together. Retain alias ownership history so an old link cannot later point at a different customer.
8. Trace redirect, expiry and invalidation races
On GET I validate the alias, then look up a live cache record. I compare its logical expiry as well as cache expiry before redirecting. A cache miss reads authoritative state, fills the cache with a bounded TTL and returns 302. Brief negative caching prevents random-alias attacks from hitting storage on every request.
Protect the cache fill
A database read may race with deletion. Versioned invalidations prevent an older fill from overwriting a newer tombstone where both are observed. Anchor cache-valid-until to the authoritative read start, not a delayed fill time, so a late response cannot create a fresh 60-second stale window. The maximum TTL remains the fallback bound when an invalidation is lost, subject to the declared clock-skew tolerance.
Avoid stampedes
Coalesce concurrent fills per alias, jitter TTLs without exceeding the revocation bound, and limit origin concurrency. Do not turn cache failure into an unbounded database flood.
Record clicks separately
Enqueue a best-effort event with a unique event ID. Count accepted analytic events, not an invented exact count of humans. Browser or intermediary caching can bypass the service.
Respect deletion limits
Already-open destinations and a redirect previously returned to a browser cannot be revoked. Emergency blocking reduces future redirects but does not claw back destination data.
9. Compare alternatives at the actual bottleneck
I would measure hot-alias frequency before adding database shards. One viral link creates read skew, not millions of distinct writes. Replicating its immutable destination in cache is more effective than repeatedly repartitioning the primary store.
| Decision | Chosen baseline | Alternative and trade-off |
|---|---|---|
| Alias allocation | Random alias plus atomic uniqueness. | Range allocation removes most collision retries but needs range ownership; predictable IDs require a separate non-security obfuscation decision. |
| Redirect status | 302 with explicit bounded caching. | Long-lived 301 caching reduces origin reads but weakens deletion and analytics visibility. |
| Regional operation | Regional caches with a home write authority per alias shard. | Active-active custom-alias allocation needs a global uniqueness protocol or region-specific namespaces. |
| Hot links | L1 copies with the same expiry cap and request coalescing. | Longer stale serving helps uptime but violates the agreed revocation bound. |
10. Explain recovery without overstating guarantees
I alert on redirect p99, origin miss rate, creation conflicts, stale-version fills and invalidation lag. Synthetic checks create, resolve, expire and delete a link so a green cache metric cannot hide a broken lifecycle.
| Failure | Detection | Recovery and remaining limitation |
|---|---|---|
| Create response lost | Client timeout; request key exists. | Return stored alias on retry; do not create another mapping. |
| Cache unavailable | Connection failures and rising origin concurrency. | Bound database fallback, shed abusive traffic; expired cached links are not served indefinitely. |
| Invalidation lost | Version lag or synthetic deletion still redirects. | Retry delivery; TTL bounds ordinary stale behavior to the agreed limit. |
| Clock skew | Expiry checks disagree across nodes. | Synchronize clocks and monitor skew; conservative expiry margins trade a little availability for earlier denial. |
| Storage failover | Leader unavailable or commit outcome uncertain. | Redirect from unexpired caches; writes wait for safe authority, then retry idempotently. |
| Phishing campaign | Abuse reports and creation spikes. | Quarantine links, invalidate reachable caches, isolate scanners; random aliases do not make destinations safe. |
11. Close with invariants and answered challenges
I have one durable alias owner, bounded redirect staleness and asynchronous approximate analytics. I would spend the remaining interview time on uniqueness or revocation, depending on which matters most to your use case.
The key trade-off is not SQL versus NoSQL by itself. It is whether the chosen store can enforce uniqueness and commit the idempotency result together, while the read path meets a clearly stated freshness bound.
Technical references
Primary references explain underlying mechanisms. Workloads and architecture choices above remain proposed interview assumptions.