Walkthrough: URL Shortener (bit.ly / TinyURL)

1. Requirements#

Functional

• Given a long URL, return a short URL (7-char key); optional custom alias.
• Redirect short → long with 301 (permanent, cacheable) or 302 (temporary, lets us count clicks).
• Optional expiry; basic click analytics.

Non-functional

• Read-heavy: ~10:1 read:write (or 100:1); redirect p99 < 100 ms.
• 99.99% availability for redirects; shortening can tolerate brief degradation.
• Keys unguessable-ish; no collisions; scale to 10 years of data.

2. Estimates#

• Writes: 100M new URLs/day ÷ 86,400 s ≈ 1,160 writes/s (≈ 1.2k; peak 3x ≈ 3.5k).
• Reads: 10x → ≈ 11,600 reads/s (peak ≈ 35k).
• Storage: 100M/day × 365 × 10 yr = 365B records × ~100 bytes (key 7 + URL ~90 + metadata) ≈ 36.5 TB.
• Key space: base62 (a-z, A-Z, 0-9) with 7 chars = 62^7 ≈ 3.5 × 10^12 — enough for 365B.
• Bandwidth: reads 11,600/s × ~500 bytes (headers + Location) ≈ 6 MB/s; trivial.
• Cache: 80/20 rule → 20% of daily reads = 0.2 × 1B × 100 bytes ≈ 20 GB; fits in a Redis cluster.

3. API sketch#

POST /api/v1/urls          { longUrl, customAlias?, expiresAt? }  -> 201 { shortUrl, key }GET  /{key}                -> 301/302 Location: longUrl        (404 if missing, 410 if expired)DELETE /api/v1/urls/{key}  (owner only)GET  /api/v1/urls/{key}/stats -> { clicks, byDay... }

Idempotency-Key header on POST; API key auth + rate limit (token bucket at gateway).

4. Data model#

urls(  key        VARCHAR(7)  PRIMARY KEY,   -- base62  long_url   TEXT NOT NULL,  user_id    BIGINT NULL,  created_at TIMESTAMPTZ,  expires_at TIMESTAMPTZ NULL)INDEX urls(user_id, created_at)           -- "my links"clicks: append-only events in Kafka -> ClickHouse / Redshift for analytics (not in the hot path)

Store: Postgres sharded by key (hash) or DynamoDB/Cassandra with key as partition key. Hot path is pure key lookup, so a KV store is a natural fit.

5. High-level design#

client -> DNS -> CDN/edge (optional cache of 301s) -> L7 LB -> API gateway (auth, rate limit)                                                        |                       +---------------------+----------+------------------+                       v                     v                             v                [Redirect service]    [Shorten service]            [Analytics consumer]                       |                     |                             ^                  Redis cache  <--- fill --- |                             |                       |                     v                             |                  URL store (Postgres shards / DynamoDB) <-- key range from ID generator                       |------------------- click event ---> Kafka --------+

Redirect: check Redis → miss → DB → populate cache → 302 + async click event. Shorten: get unique ID → base62 encode → insert → return.

6. Deep dives#

Key generation

• Option A: hash (MD5/SHA-256) of long URL, take first 7 base62 chars → collisions need check-and-retry; same URL gives same key (dedupe).
• Option B: unique numeric ID (Snowflake or DB sequence) → base62 encode → no collisions, no DB check; keys are predictable (mitigate by salting/shuffling bits).
• Option C: pre-generated Key Generation Service (KGS) that hands out batches of unused random keys from its own DB; app servers cache a block of keys in memory. Pick B or C; say why: "No collision check on the write path."

301 vs 302

• 301 → browser caches, we lose click data but offload repeat traffic. 302 → every click hits us, we get analytics. Choose 302 if analytics matter; 301 if pure cost minimization.

Caching the redirect

• Cache-aside in Redis keyed by key, TTL ~24 h, LRU eviction; hit ratio should be high (Zipfian clicks). Negative-cache 404s briefly to blunt scanners. CDN can cache 301s at the edge for the hottest keys.

7. Bottlenecks & scaling#

• DB reads: cache handles most; add read replicas; KV store scales horizontally by key hash.
• DB writes: 1-4k/s fits one Postgres primary; shard by key hash when growth demands; consistent hashing if self-managed.
• Hot keys (viral link): cache absorbs; replicate the key across cache nodes or CDN edge.
• ID generator as SPOF: multiple Snowflake workers with distinct worker IDs; or KGS with two instances splitting key ranges.
• Abuse: rate limit per API key/IP; blocklist of malicious domains; CAPTCHA for anonymous shortening.
• Expiry: lazy delete on read + periodic cleanup job; TTL attribute in DynamoDB.
• Analytics off the hot path: emit event to Kafka, aggregate in ClickHouse; never count synchronously in the DB.

8. Words to say#

base62, 62^7 ≈ 3.5 trillion, read-heavy 10:1, cache-aside, Redis LRU, 301 vs 302, Snowflake ID, Key Generation Service, collision check, hash prefix, idempotency key, rate limiting at the gateway, hash-based sharding, consistent hashing, hot key, negative caching, CDN edge cache, lazy expiration, Kafka click stream, ClickHouse analytics, 99.99% on redirects.