Worked design — URL shortener

1# Scenario A — moderate product (interview default)2new_links_per_day = 100_000_000 / 365          # ~3e5 writes/day if 100M/year3write_qps = 3e5 / 86400                       # ~3–4 QPS avg; peak ~20 QPS4redirects_per_day = 50_000_000                # example5read_qps = redirects_per_day / 86400          # ~600 avg → peak ~2–3K6# ID space: 7-char base62 = 62^7 ≈ 3.5e12 — huge vs 1e8 links/year7# Storage: ~200B/row × 1e8/year ≈ tens of GB/year raw — single DB fine early8# Decision: ID space is not the bottleneck; read QPS + cache is.910# Scenario B — bit.ly-class (secondary-cited / heuristic — label it)11# ~10B redirects/day → ~115k RPS avg → ~500k+ peak with spike factor12# 99% cache hit → origin sees ~1% → still large; edge cache mandatory13# 1B links × 200B = 200GB working set class → multi-node Redis/Memcached14# Write 1B links/day → ~11.5k write QPS avg → sharded metadata store1516# Numbers → decisions: analytics never on 302 path; shard when write QPS17# exceeds one primary; CDN/edge for viral codes.

1POST /api/v1/links2  Headers: Idempotency-Key, Authorization?3  Body: { long_url, custom_alias?, expires_at? }4  → 201 { code, short_url }56GET /{code} → 302 Location: long_url  (or 301 if permanent + cacheable intentionally)7DELETE /api/v1/links/{code}8GET /api/v1/links/{code}/stats → aggregates (async path)910links(11  code PK,              -- base62 or custom12  long_url,13  owner_id NULL,14  created_at,15  expires_at NULL,16  is_custom BOOL17)18clicks(short_code, ts, ip_hash, ua, country, referer)  -- partition by day/code; async only

1ALPHABET = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"23def base62_encode(n: int, width: int = 7) -> str:4	out = []5	while n:6		n, r = divmod(n, 62)7		out.append(ALPHABET[r])8	s = "".join(reversed(out)) or "0"9	return s.rjust(width, "0")[-width:]1011# Counter service hands out [start, end) ranges per instance — no central lock per request.1213ID STRATEGY TRADEOFF14Approach              Pros                         Cons                    Pick when15--------------------  ---------------------------  ---------------------  --------------------16MD5/SHA truncate      simple                        collisions, retries    internal tooling17Base62 counter        monotonic, compact            hot row if unsharded   low-write sortable18Snowflake             distributed, time order       NTP/config care        multi-DC high QPS19UUID v7               no coord, sortable            longer keys            modern internal IDs20Random base62+unique  simple ops                    retries under load     many interviews

1def redirect(code: str):2	row = cache.get(code)3	if row is None:4		row = db.get_link(code)  # primary or read replica OK if create→redirect lag rare5		if row is None:6			return 4047		cache.set(code, row, ttl=3600)8	if row.expired():9		return 41010	enqueue_click(code)       # async; never block on analytics DB11	return 302, row.long_url

1REDIRECT CACHING MATRIX2Layer            What to cache              TTL mindset3---------------  -------------------------  --------------------------4Browser          optional for 301           long if permanent5CDN edge         public non-auth codes      short (30–300s) + purge API6App Redis        code → long_url            minutes–hours; delete on edit7Local process    ultra-hot codes            seconds; single-flight fill89Never cache personalized analytics pages the same way as 302 Location.

1# ID space with region nibble (sketch)2# [timestamp | region | worker | sequence] → base623# Guarantees no cross-region counter collision without a global lock4# Custom aliases still need a global uniqueness check (harder problem)

1SHORTENER DECISION LOG (write on board)2Assumption              Number (heuristic)     Decision3---------------------  ---------------------  --------------------------4Creates/day            3e5                    single primary OK early5Redirects/day          5e7                    cache-aside mandatory6Peak redirect RPS      ~3k (×5)               few app nodes + Redis7Key length             base62×7               decades of headroom8Viral code share       10–50% of QPS          CDN + local cache9Analytics volume       = redirects            async only; never 302 path10Custom alias rate      low but abusive        policy + unique + reserved1112Rejected: UUID short links; sync malware scan on redirect; global lock IDs.

1MODERATE PRODUCT (heuristic)2creates/day 3e5 → write QPS ~3–4 avg, ~20 peak3redirects/day 5e7 → read QPS ~600 avg, ~3k peak4row size ~200B → storage tens of GB/year — single DB OK early5base62 len 7 → 62^7 ≈ 3.5e12 codes — space not the bottleneck6THEREFORE: cache redirects; keep metadata SQL/primary simple; async clicks78BITLY-CLASS ESCALATION (secondary/heuristic — label it)9redirects/day 1e10 → ~1e5 RPS avg → peak much higher10cache hit 99% still leaves large origin QPS without edge11metadata shards + multi-node cache + CDN required12analytics warehouse path mandatory1314ID PICKER15low write + simple → random base62 + unique retry16high write multi-DC → Snowflake / range counters17custom alias → separate uniqueness + reserved words1819HOT PATH RULES201) 302 decision uses cache/DB only212) enqueue click never blocks response223) single-flight on hot miss234) disable flag for malware must reach edge fast245) 301 only if permanent + purge story exists2526FAILURE DRILLS27cache stampede, counter service down, alias race 409,28analytics lag, DB outage serve hot from cache, abuse flood