Video summary

Beginner System Design Interview: Design Bitly w/ a Ex-Meta Staff Engineer

Main summary

Key takeaways

Technology

Video purpose / audience

  • Beginner-friendly system design walkthrough of the classic interview question: “Design a URL shortener (like Bitly)”.
  • The speaker (Evan) slows down the process and explains concepts typically assumed in advanced system design interviews.

Suggested interview framework (technology/process)

  1. Define requirements
    • Functional: core features users need.
    • Non-functional: qualities like latency, scalability, durability, security, fault tolerance, and CAP theorem decisions.
  2. Outline core entities (high-level tables/collections).
  3. Design the user-facing API contract (endpoints mapped 1:1 to functional requirements).
  4. High-level design (whiteboard): draw a simple working system that satisfies functional requirements first.
  5. Deep dives: revisit each non-functional requirement one-by-one, evolving the design until all requirements are met.

The speaker argues that up-front back-of-the-envelope math is often unhelpful if it doesn’t directly change a decision; instead, do calculations when they inform architecture choices.

Functional requirements for the URL shortener

  • Create: users can create a short URL from a long/original URL.
  • Redirect: users can access the short URL and be redirected to the original URL.

Optional features added to the design

  • Custom alias: user-provided short code (e.g., “Evan”), producing bit.ly/Evan if it doesn’t already exist.
  • Expiration time: short links can expire; redirects after expiry return an error.

Non-functional requirements discussed (and decisions)

  • Low latency on redirects
    • Target: ~200 ms as a human-perceived “real-time” bound.
  • Scale
    • Example target: 100M DAU and 1B total URLs.
    • Redirect traffic estimate leads to around 100K–10K–100K req/s peak range (speaker uses exponent-based math intuition).
  • Uniqueness of short codes
    • Must avoid collisions to prevent incorrect redirects.
  • CAP theorem
    • Decision for URL shortening: prioritize high availability over strong consistency.
    • Use eventual consistency rather than strong read-after-write consistency.
    • Rationale: brief inconsistency can be handled with user-facing retry/error (“still saving—try again”) and isn’t catastrophic like banking/ticketing.

API design (endpoint mapping to requirements)

Create shortened URL

  • Example REST-ish: POST /urls
  • Returns the short URL and includes:
    • the original URL
    • optional custom alias
    • optional expiration time

Redirect

  • Example REST-ish: GET /{shortCode}
  • The server looks up the original URL and responds with an HTTP redirect.

Redirect choice: 302 vs 301 (feature/analytics trade-off)

  • 302 (temporary redirect)
    • Browser goes back to your service each time → better for logging/analytics/monitoring and detecting breakage.
  • 301 (permanent redirect)
    • Can be cached by clients/DNS → reduces hits to your service but reduces visibility and may make debugging harder.
  • Speaker’s rationale in this interview: choose 302.

High-level design (baseline system)

  • Client → primary backend server → database
  • After POST /urls:
    • Backend generates a short code, stores a mapping in a URL table.
    • The table conceptually includes:
      • short URL/code
      • long/original URL
      • creation time
      • user id
      • (optionally) custom alias, expiration time
  • For GET /{shortCode}:
    • Backend queries DB by short code and issues 302 redirect to the original URL.
  • Notes: the baseline initially “black-boxes” the short-code generation complexity, then revisits it in deep dive.

Deep dive #1: generating unique short codes (collision/uniqueness)

The speaker evaluates several strategies:

  1. Prefix-based (bad)
    • Taking the first 5–7 chars of the long URL causes many collisions → many-to-one mapping.
  2. Random number generator + Base62 encoding
    • Encode a random integer in Base62 (0-9, A-Z, a-z).
    • Produces short codes (e.g., ~6 chars).
    • Collision risk is analyzed via the birthday paradox.
    • Mitigation option:
      • Check DB for collision (read first; insert only if not present).
  3. Hash long URL → Base62 + slice
    • Deterministic hashing (MD5/Murmur/sha variants) and take prefix.
    • Collision probability behaves similarly to random approach; DB collision check still recommended.
  4. Sequential counter + Base62 encoding (no collisions, but predictability risk)
    • Use an incrementing counter, Base62 encode it to produce unique codes.
    • Pros: guaranteed uniqueness; avoids collision checks.
    • Cons: predictable (scraping/enumeration risk).
    • Mitigations:
      • rate limiting
      • product warning (“don’t shorten private URLs”)
      • bijective/obfuscation function (example mentioned: SquidsDog) to map sequential numbers to Bitly-like codes non-incrementally.

Deep dive #2: low latency on redirects

To reduce redirect lookup time:

  • Database indexing
    • Use the short code as a primary key → DB automatically builds an index (example: PostgreSQL uses B-tree).
    • Optional secondary indexes (hash indexing) discussed but stated as often unnecessary in practice.
  • Caching
    • Use a read-through LRU cache (examples: Redis/memcache).
    • Key: short code → Value: long/original URL
    • On cache miss: fetch from DB, populate cache.
    • Hot URLs remain cached; cold URLs are evicted.

CDN option (trade-off)

  • CDN edge caches redirect responses closer to users.
  • Drawback: may bypass backend routing and reduce monitoring/logging visibility—mirrors the 301 caching/visibility trade-off.

Deep dive #3: scalability to 100M DAU and 1B URLs

  • Compute redirect QPS estimate:
    • 100M/day DAU assuming ~1 redirect per user → estimate leads to ~10K–100K requests/sec peak.
  • Scaling approach:
    • Horizontal scaling preferred (add more instances).
    • Reads vastly outnumber writes, so the architecture evolves into microservices:
      • Read service: handles redirects (high QPS)
      • Write service: handles URL creation (lower QPS)
      • API Gateway routes requests to the right service based on endpoint.

Scaling short-code counters safely

  • Problem: multiple write service instances need a global shared counter.
  • Solution:
    • Move counter to a global counter store such as Redis, using atomic increment operations.
  • Optimization idea:
    • Pre-fetch a batch of counter values (e.g., next 1000) to reduce network overhead; unused values can be lost without harming correctness.

Deep dive #4: database sizing and sharding

  • Rough sizing:
    • The table row estimated up to ~500 bytes.
    • For 1B rows → about 500 GB, described as manageable for modern storage.
  • Primary concern becomes read throughput, mitigated via Redis cache.
  • Sharding discussed as an option:
    • If needed, shard by short code.
    • Example idea: distribute by hash(shortCode) mod N.
  • Conclusion in the worked example: a single DB may suffice.

Deep dive #5: high availability (fault tolerance)

  • Auto-scaling improves availability for read/write services.

Redis availability

  • Down-time isn’t ideal because it provides global counter increments.
  • Suggested mitigations:
    • HA configuration
    • snapshots of counter/state

Database HA

  • Replicas and periodic snapshots (example: snapshot to S3-like object storage and restore).
  • If the primary DB fails, restore from snapshot/replica.

Outcome / review conclusion

The design is considered complete once it satisfies:

  • All functional requirements: create, redirect, optional alias, optional expiration
  • All non-functional requirements: low latency, scale, uniqueness, availability/consistency choice

Main speaker(s) / sources

  • Evan (co-founder of Hello Interview, former Meta staff engineer) — primary narrator and system design presenter.
  • Mentions Stefan (co-founder of Hello Interview) in context of tuning guided practice feedback.

Original video