Requirements

Functional

• Create a short URL from a given long URL (auto-generated alias, no custom aliases in v1)
• Redirect a short URL to its original long URL
• Links are permanent by default (optional TTL as a nice-to-have)

Non-Functional

• High availability — a redirect failure breaks every place the short link was posted
• Low redirect latency — user is waiting on a page load (target < 100 ms)
• Horizontal scalability — read-heavy (~100:1 read:write), traffic grows over time
• Durable storage — once a link is created it must never be lost

Capacity Estimation

Assumptions

• 100M new URLs/day, read:write ≈ 100:1
• Alias ~7 chars, long URL avg ~100 B, metadata ~50 B → ~500 B/record

Write / Read QPS

• Writes: 100M / 86,400 s ≈ ~1.2K writes/sec
• Reads: 100× → ≈ ~120K reads/sec (avg); peak ~2× to 3× → up to ~350K/sec

Storage over 5 years

• URLs = 100M × 365 × 5 ≈ 182.5B records
• Raw = 182.5B × 500 B ≈ ~90 TB
• With 3× replication ≈ ~270 TB

API Design

1. Create short URL (write path)

POST /api/v1/urls Content-Type: application/json{ "longUrl": "https://example.com/some/very/long/path" }

Response 201 Created:

{ "shortUrl": "https://tiny.url/aB3xK9z", "longUrl": "https://example.com/..." }

2. Redirect (read path)

GET /{shortCode}

Response 302 Found with Location: https://example.com/some/very/long/path

High-Level Design

Overview A read-heavy URL shortener with two independent paths — a write path that creates links and a hot read path that serves redirects — sitting behind a shared load balancer, backed by a partitioned key-value store with a Redis read cache.

Components

• Load Balancer / API Gateway — single entry point; terminates TLS, routes to the right service, spreads traffic across replicas for horizontal scale.
• Shortener Service (write path) — accepts the long URL, requests a unique code, writes code → longUrl, returns the short URL.
• ID Generation Service — issues guaranteed-unique 7-char codes via a counter + base62 with range allocation (each server grabs a block, so no per-request coordination and no collisions).
• Redirect Service (read path) — the hot path: looks up the code and returns 302 Found with the Location header. Kept separate from the write path so redirect spikes don't slow link creation.
• Cache (Redis) — short_code → long_url, LRU eviction, sitting in front of the DB. Serves popular codes from memory and shields the DB from the ~100:1 read load.
• Database — durable short_code → long_url store, partitioned by hash(short_code) so every lookup hits exactly one shard (even distribution, no scatter-gather).

Database Design

Table: url_mappings

(An internal id is optional — short_code is already unique and is what every read uses.)

Index strategy

• Primary key = short_code → every redirect is a single-key lookup, O(1), no table scan.
• Add a secondary index on user_id (if accounts exist) to list all links a user created.
• No index on long_url — redirects never query by it.

Partitioning

• Partition key = hash(short_code) → even traffic distribution (random codes → uniform) and each lookup hits exactly one shard, no scatter-gather. Avoid partitioning by long_url or created_at (scatters reads / creates hot shards).

Consistency

• Writes (create): strong consistency. A newly generated code must be durable and unique before the short URL is returned, or a user gets a link that 404s or collides.
• Reads (redirect): eventual consistency is fine. A brief replication lag only risks a transient 404, never data corruption. (Optional: read-your-writes on the creator's own redirects.)

Storage technology

• Key-value / wide-column store — DynamoDB or Cassandra — because the access pattern is pure single-key lookups at massive read scale. These give horizontal scale, partition-key lookups, strong-read option, and built-in TTL for expiring links.
• Why not SQL: Postgres/MySQL works early but single-node writes and ~120K reads/sec force manual sharding. Say "fine to start, hard to scale."
• 3× replication for durability — a lost mapping breaks every place that link was posted.

Detailed Component Design

1. ID Generation Service

How it works: A global counter encoded in base62 (62⁷ ≈ 3.5 trillion codes). To avoid a single hot counter, use range allocation — a coordinator hands each app server a block of IDs (e.g. 1M at a time); servers mint codes locally with no per-request coordination.

• Concurrency: Because each server owns a distinct range, two concurrent creates can never produce the same code — no collision possible, no collision-retry read on the hot path.
• Unpredictability: Sequential codes are enumerable (scrape /aaaaaab, /aaaaaac…). Mitigate by padding/obfuscating the counter (e.g. bit-shuffle or XOR with a secret), or switch to a pre-generated random pool (KGS) where codes are random by construction.
• Outage: If the coordinator dies, servers keep draining their local buffered range so creation continues; on partition, ranges are disjoint by design so a split-brain can't mint duplicates. Buffer size trades memory for outage tolerance.

2. Caching (the hot redirect path)

• Viral link: A single code hammered by millions gets served from Redis (hot cache) and/or a CDN at the edge, so neither the redirect service nor the DB is overwhelmed. Cache hit → 302 in a few ms.
• Miss / expiry: On a cache miss, the redirect service reads the mapping from the DB, serves the 302, and populates the cache for the next request.
• Invalidation: When a link is disabled/edited, purge it from both CDN and Redis so stale mappings don't keep redirecting.
• Eviction: LRU so hot codes stay resident and cold codes fall out; memory stays bounded.

3. Partitioning

• Single-shard lookup: Partition key = hash(short_code) → every redirect routes to exactly one shard, no scatter-gather, O(1).
• Even spread + hotspots: Random-ish codes hash uniformly, so traffic spreads evenly. A super-hot code can't overload one shard because requests are absorbed by Redis/CDN and read replicas before reaching the partition.

4. Rate Limiting (brief)

• Per-IP / per-token throttling at the edge so one abusive client can't mint millions of links; return 429 with Retry-After so clients back off.