URL Shortener

1. Requirements

Functional:

1. shorten(longURL, customAlias?, ttl?) → short URL.
2. redirect(shortKey) → HTTP redirect to long URL.
3. Custom aliases (first-come-first-served, validation + reservation).
4. Optional expiry (TTL); expired keys return 404/410.
5. Basic analytics: click count + rough geo/device breakdown per key.
6. Rate-limited public API with per-user quota.

Non-functional:

Out of scope:

• Full web-analytics suite (no funnels, no real-time dashboards).
• Malware/phishing scanning beyond a pluggable hook.
• URL preview pages.

2. Capacity Estimation

Assumptions: 100M new URLs/month; read:write ≈ 10:1; avg stored record ≈ 500 B (keys, URL ~200 B avg, timestamps, counters); retain 10 years; peak = 5× avg.

3. API Design

POST /api/v1/shorten
Content-Type: application/json
Idempotency-Key: <uuid>

{ "long_url": "https://example.com/a/very/long/path?q=1",
  "custom_alias": "my-link",      // optional
  "ttl_seconds": 2592000 }        // optional

201 Created
{ "short_url": "https://t.ly/aZ3kP9q",
  "short_key": "aZ3kP9q",
  "expires_at": "2026-10-15T00:00:00Z" }

• Same (longURL, user) re-shortened → return existing key (hash-lookup) instead of minting duplicates.
• Pagination/cursors unnecessary (single-key lookups only).

4. Data Model & Storage

CREATE TABLE url_mapping (
  id          BIGINT PRIMARY KEY,          -- from KGS, base62(id) = short_key source
  short_key   CHAR(8) NOT NULL UNIQUE,     -- hash-shard key; indexed
  long_url    TEXT NOT NULL,
  long_hash   CHAR(40) NOT NULL,           -- SHA-1(long_url) for dedup lookup, indexed
  owner_id    BIGINT NULL,
  created_at  TIMESTAMP NOT NULL,
  expires_at  TIMESTAMP NULL,              -- NULL = permanent (301-eligible)
  INDEX (expires_at)                       -- janitor sweep for expiry
) ENGINE=InnoDB;

• Shard by hash(short_key) mod N — uniform, and lookups are always point queries so no range-scan penalty. Rebalance via Rebalancing Partitions (consistent hashing when N grows).
• Authoritative store is the RDBMS with Single Leader Replication per shard; Redis is pure cache (cache-aside).

5. High-Level Design

Write path: client → LB → API servers → (dedup check by long_hash) → KGS range allocator → insert into hash-shard → warm cache. Read path: client → CDN/edge (301s only) → LB → API → Redis → DB shard on miss → async click event to Kafka.

• Load balancer / gateway: TLS termination, per-IP throttling, routes 301-cacheable traffic hints.
• App tier (stateless): shorten + redirect logic; holds an in-memory KGS range (see §6.1).
• KGS (Key Generation Service): hands out disjoint numeric ranges from an auto-increment table; base62-encoded into short keys.
• Cache: Redis LRU, TTL = min(key TTL, 24 h); negative caching for 404s (60 s) to absorb scan attacks.
• Primary store: hash-sharded MySQL; each shard single-leader + 2 replicas.
• Async path: redirect emits fire-and-forget click event → Kafka → Flink/Spark → ClickHouse; counters never block redirects.

6. Deep Dives

6.1 Key generation: counter vs hash vs KGS

KGS detail: one tiny MySQL table with next_id; each app host requests a range (e.g. 10k IDs) via UPDATE kgs SET next_id = next_id + 10000 (atomic) and mints from memory until the range is 80% consumed, then prefetches. At ~200 keys/s peak, a 10k range lasts ~50 s per host — DB load is ~1 QPS. Run active-standby KGS behind a lock from Coordination Services (ZooKeeper/etcd lease); standby takes over the same table, so no ID reuse. Unused IDs on crash are simply skipped — with 3.5T of keyspace, waste is irrelevant.

6.2 301 vs 302, TTL and custom aliases

• 301 Permanent: browser + CDN cache it → kills repeat origin traffic. Only for expires_at IS NULL and analytics-off links. Downside: owner can't change analytics/expiry later; bad actors harder to revoke (need cache purge + key tombstone).
• 302 Found: every click hits origin → enables counting + expiry enforcement. Cost: full read QPS. Default for TTL links and tracked links.
• Rule: permanent + untracked → 301; anything with TTL/analytics/owner-editable → 302. Say this sentence in the interview.
• Custom aliases: separate reservation path — INSERT ... ON CONFLICT DO NOTHING on short_key; 409 if taken. Validate charset/length + reserved-word blocklist (api, admin, stats). Alias claims bypass KGS.

6.3 Cache + analytics without per-click DB writes

• Redis holds {short_key → (long_url, expires_at, redirect_type)}; cache-aside with TTL jitter to avoid stampedes; singleflight (request coalescing) on miss so a viral key causes 1 DB read, not 2,000.
• Clicks: redirect path does kafka.send(click) fire-and-forget with a bounded in-memory drop counter (shed load before slowing redirects). Stream job aggregates per (key, minute) → ClickHouse; owner stats API reads ClickHouse. click_count in MySQL updated hourly by batch — never per click.
• Expiry janitor: hourly scan on expires_at index → tombstone + async CDN/cache purge; 410 for 7 days, then 404.

7. Bottlenecks, Trade-offs & Monitoring

First bottleneck at 10x: a single Redis (hot-key skew on viral links) → Redis Cluster with replicas + client-side local LRU (Caffeine, 10k entries) in front; next is KGS range-DB failover time → prefetch earlier (50% watermark) + longer ranges.

Interview one-liners

• Q: Why not auto-increment in MySQL directly? / A: Single-writer bottleneck and SPOF at scale; KGS amortises coordination to one DB op per 10k keys.
• Q: 301 or 302? / A: 301 only for permanent untracked links (cacheable); everything with TTL or analytics is 302 so origin enforces and counts.
• Q: How do you shard? / A: Hash of short_key — point lookups only, so hash sharding gives perfect spread with no range-scan cost.

Related

• Partitioning — hash-shard choice
• Rebalancing Partitions — growing shard count
• cache-aside and Cache Patterns and Eviction — hot-key cache
• Single Leader Replication — per-shard durability
• Coordination Services — KGS failover lease
• Stream Processing — click aggregation pipeline
• Rate Limiter case — throttling the shorten API