URL Shortener (TinyURL / bit.ly)

Functional

• Given a long URL, return a short alias (e.g. sd.io/aB3xZ9).
• Visiting the alias redirects to the original URL.
• Optional: custom aliases, expiry, basic click analytics.
• Optional: user accounts to list and delete their links.

Non-functional

• Highly available: redirects must keep working even if link creation is degraded.
• Low latency on redirect (p99 < 50 ms from the edge, excluding client network).
• Aliases must be unique and hard to guess (not sequential).
• Read:write ratio is very skewed, roughly 100:1.
• Durability: a created link must never be lost.

Out of scope

• Malware/phishing detection, abuse rate limiting, link previews.

Assumptions

• 100M new URLs per month.
• 100:1 read:write ratio → 10B redirects per month.

Traffic

• Writes: 100M / (30 × 86,400 s) ≈ 40 writes/s.
• Reads: 40 × 100 ≈ 4,000 reads/s average; plan for 5–10× peak ≈ 40K reads/s.

Storage

• 100M/month × 12 × 5 years = 6B records.
• ~500 bytes per record (alias, long URL, owner, timestamps) → 6B × 500 B ≈ 3 TB over 5 years. Comfortably fits a single replicated database with modest sharding.

Key space

• Base62 (a–z, A–Z, 0–9). 6 chars = 62^6 ≈ 56.8B. 7 chars = 62^7 ≈ 3.5T. Use 7 to leave headroom.

Cache

• 80/20 rule: 20% of links serve 80% of traffic. Cache hot links: 20% × daily reads is wasteful; instead cache by access. Budget ≈ 0.2 × (4,000 × 86,400) × 500 B ≈ 35 GB/day of hot data. A few Redis nodes handle it.

Bandwidth

• Redirect responses are tiny (a 301/302 with a Location header), roughly 500 B. 4,000 r/s × 500 B ≈ 2 MB/s. Not a concern.

POST /v1/urls

• Body: { longUrl, customAlias?, expiresAt?, userId? }
• Returns 201 { shortUrl, alias, expiresAt }
• Errors: 400 invalid URL, 409 alias taken, 429 rate limited.

GET /{alias}

• Returns 301 or 302 with Location: longUrl.
• 404 if unknown, 410 if expired.

GET /v1/urls/{alias}/stats

• Returns { clicks, byDay[], topReferrers[] }. Analytics can be eventually consistent.

Notes

• Use an API key or JWT for creation so you can rate limit per user.
• Idempotency: the same user submitting the same long URL twice may return the existing alias.

Entity: url_mapping

• alias (PK, 7-char base62 string)
• long_url (text, up to 2 KB)
• user_id (nullable, indexed)
• created_at, expires_at
• click_count (counter, may live elsewhere)

Entity: user

• user_id (PK), email, api_key_hash, created_at

Storage choice

• The workload is a simple key → value lookup with no joins and a huge number of rows. A wide-column or key-value store (DynamoDB, Cassandra) scales horizontally with minimal operational effort.
• A relational DB (Postgres) also works at this size (3 TB) if sharded by alias prefix, and makes the "list my links" query easy.
• Either is defensible in the interview. State the reason for your pick: operational simplicity vs query flexibility.

Analytics

• Do not update click_count on the hot path with a synchronous DB write. Emit a click event to a queue and aggregate separately.

Why split read and write services?

• They scale independently: reads are 100× writes and are latency-sensitive. A bug deploy in creation should not take down redirects.

1. Key generation

• Option A: Hash the long URL (MD5/SHA-256), base62-encode, take the first 7 chars. Collisions are possible: on collision, re-hash with a salt or append a counter. Needs a DB check per write.
• Option B: Key Generation Service (KGS). Pre-generate random unique 7-char keys into a key table; services grab batches into memory. No collision checks on the write path. KGS is a single point of failure, so run it replicated with the "used" flag updated atomically.
• Option C: Distributed counter (e.g. Snowflake-style or ZooKeeper-allocated ranges) base62-encoded. Simple and unique, but sequential aliases are guessable, so apply a bijective scramble or mix in random bits.
• Recommended: B for simplicity under load, or C with range allocation if you already run a coordination service.

2. Redirect caching and cache invalidation

• Cache-aside with TTL. Hot keys get long TTLs. Deletions and expirations must invalidate the cache explicitly, otherwise a deleted link keeps redirecting until TTL.
• Use a CDN for the redirect itself only if you are fine with slow invalidation; most designs keep redirects at the application layer and use the CDN for static assets.

3. 301 vs 302

• 301 (permanent): browsers cache the redirect, so repeat visits never hit your servers. Cheaper, but you lose analytics and cannot change the target.
• 302 (temporary): every click hits your service. You get analytics and can update or expire links.
• Pick 302 if analytics matters (it usually does for the business), 301 if pure cost minimisation.

4. Expiry

• Lazy: check expires_at on read and return 410. Cheap.
• Active: a background job sweeps expired rows in batches to reclaim space and keys. Both together is the usual answer.

5. Availability of the redirect path

• Multi-AZ cache and DB replicas. Redirect service reads from replicas; eventual consistency of a few hundred ms after creation is acceptable (you can say "a just-created link may take a moment to work").

Summary of decisions

• 302 redirects for analytics at the cost of extra read traffic.
• KGS-style pre-generated keys to avoid collision checks on write.
• Key-value store sharded by alias; cache-aside Redis for hot reads.
• Async click events through a queue; analytics are eventually consistent.

What was given up

• Strong consistency between creation and first redirect.
• Simplicity of a single service (we split read/write).

With more time

• Rate limiting and abuse detection, custom domains, link previews, A/B testing of destinations.