Designing a URL Shortening Service

What you'll learn

• Problem Statement

  Design a service that creates short aliases for long URLs. Users submit a long URL and receive a short link (6-8 characters). When anyone clicks the short link, they're redirected to the original URL. The system must handle billions of U…

• Requirements

• Functional Requirements

  1. Given a URL, generate a shorter and unique alias (short link) 2. When users access a short link, redirect to the original URL 3. Users can optionally pick a custom short link (custom alias) 4. Links expire after a configurable timespan

• Non-Functional Requirements

  1. High availability — if the service is down, all short links break 2. Low latency — redirects must happen in real-time 3. Non-guessable — short links should not be predictable/sequential

• Extended Requirements

  1. Analytics — track how many times a redirection happened 2. REST API access for other services ---

• Design Considerations

  The system is read-heavy — for every URL creation, there are ~100 redirect requests. Key implications: - Optimize the read path aggressively (caching, fast lookups) - Write path can tolerate slightly more latency - Storage is modest (URL…

• Capacity Estimation

• Traffic

  | Metric | Calculation | Value | |--------|-------------|-------| | New URLs/month | Given | 500M | | Write QPS | 500M / (30 × 24 × 3600) | ~200/s | | Read:Write ratio | Given | 100:1 | | Read QPS | 200 × 100 | ~20,000/s |

• Storage (5 Years)

  | Metric | Calculation | Value | |--------|-------------|-------| | Total URLs in 5 years | 500M × 12 × 5 | 30 Billion | | Avg object size | ~500 bytes | | | Total storage | 30B × 500 bytes | 15 TB |

• Bandwidth

  | Direction | Calculation | Rate | |-----------|-------------|------| | Incoming (writes) | 200/s × 500 bytes | 100 KB/s | | Outgoing (reads) | 20K/s × 500 bytes | ~9 MB/s |

• Memory (Cache)

  | Metric | Calculation | Value | |--------|-------------|-------| | Daily requests | 20K/s × 86,400 | ~1.7 Billion | | Cache 20% of daily | 0.2 × 1.7B × 500 bytes | ~170 GB | Note: Many requests are for the same URL (duplicates), so actu…

• System APIs

  Abuse prevention: The apidevkey identifies and rate-limits each developer. Each key has a quota for: - Max URL creations per time period - Max redirections per time period - Configurable per developer tier ---

• Design Evolution & Trade-offs

  How this system grew from an MVP to what a production version looks like — and the choices you'd defend in an interview. A URL shortener is deceptively simple: it's really a distributed KV store with strong hot-key behavior on the read s…

• Stage 1 — MVP: One box, one database

  The simplest thing that could possibly work: a monolithic Flask/Express app in front of a single Postgres box, with a urls(shortkey PRIMARY KEY, longurl, createdat, expiresat) table. Writes hash the URL with MD5, take the first 6 base62…

• Stage 2 — Scale-out: Multiple pods behind a load balancer

  - API layer becomes stateless (no session state — the apidevkey is the whole session). - N replicas of the API pod sit behind an L7 load balancer (nginx / ALB). - Postgres is still single-node but now has one or two async read replicas.…

• Stage 3 — Bottleneck: Hot-key contention on ID generation

  Every write needs a globally unique 6-char base62 code, and every writer wants one right now. This is the classic distributed-uniqueness problem, and for URL shorteners it's the dominant write-path cost. Option comparison table. | Option…

• Stage 4 — Second bottleneck: Read fan-out to viral short codes

  A URL shortener is 100:1 read-to-write. Once ID generation is solved, the entire remaining scaling story is about serving reads — specifically, serving the same handful of viral short codes millions of times. The bad property is that rea…

• Stage 5 — Mature architecture

  Putting the pieces together. This is what a production URL shortener at ~20K reads/sec looks like — every element traces back to a specific bottleneck from stages 3 and 4. Eight core components, each earning its keep: - CDN edge — absorb…

• Cost vs Complexity — When to Pick What

  | Concern | MVP choice | Growth choice | Enterprise choice | |---------|-----------|---------------|-------------------| | Compute | Single VM (t3.medium) | K8s deployment (5–20 pods) | Multi-region K8s with global anycast | | Database |…

• Migration Path (MVP → Enterprise)

  The order matters. Some steps unlock others; some steps are traps if done too early. 1. Add Postgres read replicas. Zero write-side impact. Route only cold analytics queries first, then gradually shift redirect reads. Depends on nothing.…

• Database Design

• Schema

• Why NoSQL (Key-Value Store)?

  | Criterion | Assessment | |-----------|-----------| | Data volume | 30 billion records — needs horizontal scaling | | Record size | How KGS works: 1. Offline generation: KGS generates all possible 6-char base64 strings and stores them i…

• Approach C: Atomic Counter + Base62 (Alternative)

  A simpler alternative to KGS uses a centralized atomic counter: Base62 uses [a-zA-Z0-9] (not base64) because / is a URL path separator and + is interpreted as space in query strings. Advantages over KGS: - Zero collisions guaranteed (mon…

• Redirect Flow (Detailed)

• 301 vs 302: The Analytics Trade-off

  | HTTP Code | Browser Behavior | Server Impact | Use Case | |-----------|-----------------|---------------|----------| | 301 Moved Permanently | Browser caches redirect; future clicks never reach your server | Zero server load after firs…

• Data Partitioning

• Strategy A: Range-Based

  Partition by first character of the hash key: - Server 1: keys starting with A-F - Server 2: keys starting with G-L - ... Problem: Extremely unbalanced. Some letters appear far more frequently in base64-encoded keys.

• Strategy B: Hash-Based (Hash of Hash)

  Take hash(shortKey) % N to determine the partition. Problem: Adding a new server changes N, which reshuffles almost all keys across partitions.

• Strategy C: Consistent Hashing (Chosen)

  Advantages: - Adding a server: only ~1/N keys relocate - Removing a server: only that server's keys redistribute to next node - Virtual nodes: each physical server gets multiple positions on ring for even distribution ---

• Caching Strategy

• Architecture

• Configuration

  | Parameter | Value | Rationale | |-----------|-------|-----------| | Size | ~170 GB | 20% of daily unique requests × 500 bytes | | Policy | LRU | Evict least recently used URLs | | Data structure | Linked HashMap | O(1) get + O(1) evict…

• Cache Update Flow

  1. Cache miss occurs 2. Fetch from backend DB 3. Write to local cache 4. Broadcast update to all cache replicas 5. Replicas add entry (ignore if already present — handles race conditions)

• Layer 3: CDN/Edge Computing (Ultra-Low Latency)

  For the highest-traffic short URLs, deploy redirect logic at the edge: How it works: - Popular short codes are cached at geographically proximate edge PoPs (Points of Presence) - Requests for cached codes never reach the origin server -…

• Load Balancing

• Three Placement Points

• Algorithm Progression

  | Phase | Algorithm | Why | |-------|-----------|-----| | Start | Round Robin | Simple, no overhead, removes dead servers | | Growth | Weighted RR | Different server capacities | | Scale | Least Connections | Route to least loaded server…

• Link Expiration and Cleanup

• Lazy Cleanup (Primary)

  - On redirect: check ExpirationDate - If expired: return 410 Gone, async-delete from DB + cache - Pro: No background process needed; only processes URLs that are actually accessed

• Active Cleanup (Background)

  - Periodic sweep: scan for expired URLs - Remove from DB, evict from cache - Return expired keys back to unusedkeys pool (recycle) - Run during low-traffic hours to minimize DB load ---

• Analytics (Extended Feature)

  For each redirect, record: - Timestamp - Country/region (from IP geolocation) - Browser/device (from User-Agent) - Referrer Implementation: Log redirect events to an analytics pipeline (async, doesn't add latency to redirect). Aggregate…

• Security Considerations

  | Concern | Solution | |---------|----------| | Abuse (key exhaustion) | Rate limit per apidevkey | | Malicious redirects | URL validation, malware scanning on create | | Spam | Blacklist known spam domains | | Enumeration | Random keys…

• Complete Request Flow: URL Creation

  ---

• Summary: Why Each Decision Matters

  | Decision | What it Solves | |----------|---------------| | KGS (offline key gen) | Eliminates collisions, constant-time assignment | | 6-char base64 keys | 68.7B keys > 30B needed (5-year capacity) | | Batch key caching | App servers a…