Walkthrough 1 — Design a URL Shortener (TinyURL)

The brief

Build a URL shortener like TinyURL or Bit.ly. User submits a long URL; gets a short URL back. Visiting short URL redirects to long URL.

Step 1: Clarify requirements

In an interview, ask:

Read:write ratio? (Typically 100:1 — many more redirects than creations.)
Custom slugs allowed? (Vanity URLs.)
Expiration? (Auto-delete after N days?)
Analytics? (Click count, geo, referrer.)
Auth? (Anyone can shorten, or only logged-in users?)

Assume for this design:

100M new URLs/month.
100:1 read:write ratio.
7-char short URL.
No expiration.
Basic click count analytics.

Step 2: Capacity estimation

100M URLs/month × 12 months × 5 years = 6B URLs total in 5 years.

Storage per URL: ~500 bytes (long URL + short slug + metadata) → 3TB total.

Throughput:

Writes: 100M / (30 × 86400) = ~40 writes/sec average. Peak: 200/sec.
Reads: 40 × 100 = 4000 reads/sec average. Peak: 20000/sec.

Bandwidth: redirects are tiny (HTTP 301 with new URL); not a concern.

Step 3: High-level design

[Client]
   ↓
[Load Balancer]
   ↓
[Web Service (stateless, many instances)]
   ↓                              ↓
[Cache (Redis)]              [Database]
   ↓
   (cache miss)
   ↓
[Database lookup]

Step 4: Short URL generation

Two main approaches:

Approach A: Hash-based

Hash the long URL (MD5/SHA), take first 7 chars (base62).

Pros: deterministic; same long URL → same short URL. Cons: collisions need handling (rare with 7 chars × 62 alphabet = 3.5T possibilities, but still).

Approach B: Counter-based

Auto-increment ID → encode to base62 → 7-char string.

def encode(n):
    chars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
    result = ""
    while n > 0:
        result = chars[n % 62] + result
        n //= 62
    return result.zfill(7)

ID 1 → "0000001"; ID 62 → "0000010"; etc.

Pros: no collisions; sequential. Cons: predictable (people can iterate URLs). Mitigate with random offset.

Distributed counter

Single counter = bottleneck. Options:

Ranges: each web server reserves a batch of IDs (e.g., 1000) and serves from it; refresh from DB when exhausted.
Snowflake-style: timestamp + datacenter_id + worker_id + sequence.
UUID: simpler but longer (16 chars base62, not 7).

For 7-char short URLs, range-based counter is most common.

Step 5: Database

Schema:

CREATE TABLE urls (
    short_code VARCHAR(7) PRIMARY KEY,
    long_url TEXT NOT NULL,
    created_at TIMESTAMP DEFAULT NOW(),
    click_count BIGINT DEFAULT 0,
    user_id BIGINT NULL
);

CREATE INDEX idx_user_id ON urls(user_id);

For 6B rows: sharded relational DB OR NoSQL.

Postgres sharded by hash(short_code): works.
DynamoDB: scales horizontally; perfect for KV access pattern.
Cassandra: also fits.

Choose by team familiarity; DynamoDB is the cleanest fit for the access pattern.

Step 6: Cache

Redis caches short_code → long_url:

4000 reads/sec average; 80% hit rate → 800 DB reads/sec (manageable).
TTL: a day or week; popular URLs stay cached.
LRU eviction.

Working set: top 10% of URLs likely account for 90% of traffic. 600M URLs × 500 bytes / 10 = 30GB cache. Doable with Redis Cluster.

Step 7: Redirect flow

GET /aB3xY9z
  → Web service
    → Cache.get("aB3xY9z")  → hit: return 301
    → Cache miss: DB.get("aB3xY9z")
      → Cache.set("aB3xY9z", long_url, ttl=86400)
      → Return 301 to long_url
    → Async: increment click_count (write to queue, batch update)

301 (Permanent Redirect) preferred over 302 (Temporary) for SEO and caching by browsers.

Step 8: Analytics (click counts)

Naive: increment counter on every redirect → write-heavy bottleneck.

Better:

Web service writes click event to Kafka.
Worker batches and updates DB every minute or hour.
Or use a separate analytics DB (ClickHouse).

For real-time click counts: Redis counter that periodically syncs to DB.

Step 9: Custom slugs

User picks "my-cool-link" instead of auto-generated.

Check uniqueness: SELECT 1 FROM urls WHERE short_code = ?.
If unique, insert with that code.
Length constraint: 3-20 chars.

Step 10: Scaling

Bottlenecks as traffic grows:

DB writes: sharding + async batched analytics.
Cache misses: tune TTL; bigger cache cluster.
Hot keys: a viral URL gets 10K req/sec on one cache key. Solutions: replicate the hot key across multiple cache nodes; CDN cache the redirect response.

Common follow-up questions

What if a URL is malicious? Blacklist; integrate with Google SafeBrowsing.
Expiration? Add expires_at column; periodic cleanup job.
Authorization on custom slugs? Reserve some keywords; rate-limit creations per user.
A/B testing on URLs? Add variant field; redirect based on coin flip.

Self-rubric

Clarified requirements (read:write ratio, custom slugs, etc.)
Estimated capacity (storage, QPS)
Designed short-code generation (hash vs counter; trade-offs)
Chose DB and explained why (DynamoDB, Postgres sharded, etc.)
Added cache layer with policy
Handled analytics (async, not in critical path)
Identified bottlenecks at scale (hot keys)
Drew the system diagram

Deliverables

Architecture diagram (on paper or whiteboard tool).
1-page design doc covering steps 1-10.
Pseudocode for encode(id) and get_url(short_code).

Assignment Instructions