Dashboard/System design/35. Design a URL Shortening Service/TinyURL

SYSTEM DESIGN · LESSON 35 OF 52 · 15 MIN VIDEO · 1 TOPICS

Design a URL Shortening Service/TinyURL

Module Progress (0 / 1 Lessons Completed)0%
System design Track (0 / 52 Modules) · Overall 0/80 (0%)0%
⌁

Narrated HD Video Lesson (15 min) · Pro

Lesson Overview + Section #01 + RESHADED Checklist + Quiz #1 are unlocked free below (no login required). Unlock all 80 HD video lessons and deep-dive sections — or watch our two free sample video lessons first.

SYSTEM DESIGN VIDEO LESSON & GUIDE

Design a URL Shortening Service/TinyURL

Designing a URL shortening service like TinyURL or Bitly means building an ultra-reliable, globally distributed lookup table that resolves short 6-character aliases to long destination URLs in single-digit milliseconds. At 200,000,000 new links per month (77 writes/sec) and a 100:1 read-to-write ratio (7,700 redirects/sec, 667,000,000 clicks/day, 12,000,000,000 links = 6 TB over 5 years), raw disk capacity is modest, but availability is existential—any outage breaks millions of embedded links across the internet simultaneously. L4–L6 interviewers focus on Base58 key-space math, coordination-free ZooKeeper range allocation, bijective counter scrambling against enumeration, HTTP 301 vs. 302 semantics, and race-free custom aliases.

WHAT YOU WILL MASTER IN THIS LESSON
  • Calculate 5-year storage (12B links * 500 B = 6 TB), 80/20 Pareto cache memory (67 GB), QPS (77 writes/s, 7,700 reads/s), and Base58 key length (58^6 ≈ 38.07B keys).
  • Design REST APIs and NoSQL schemas weighing HTTP 301 (browser-cached permanent redirect) against HTTP 302 (analytics-preserving temporary redirect).
  • Eliminate database collision checks on the write path using ZooKeeper-allocated 1,000,000-ID counter blocks, Base58 encoding, and bijective modular counter scrambling.
  • Guarantee sub-millisecond redirects, race-free custom aliases (>= 7 chars via conditional inserts), lazy + batch expiration, and multi-region availability across consistent-hashed KV shards.
SYSTEMATIC INTERVIEW CHECKLIST · RESHADED + 45-MIN CLOCK

8-Step RESHADED Execution Checklist

Follow this exact sequence from the Intro narration on every system design prompt so you never miss requirements, math, contracts, or the 13-minute deep dive.

0 / 8 Checked
INTERVIEWER SCORECARD · WHAT MAKES A STRONG HIRE?

5 Signals Bar Raisers Grade (L4 vs. L5 Senior vs. L6 Staff)

Senior (L5 / E5 / Senior SDE) Bar — Autonomous Pacing, Depth & Proactive Trade-Offs: Owns the 45-minute clock without prompting, derives every component quantitatively, surfaces failure modes (hot shards, stampedes, dual writes) BEFORE being asked, and defends consistency vs. latency trade-offs.
1. Scoping
✓ STRONG HIRE SIGNAL

Clarifies users, read/write skew, p99 latency, consistency bounds, and explicit non-goals in minutes 2–8.

✗ NO-HIRE RED FLAG

Jumps straight into drawing load balancers and microservices at minute 2 without asking a single question.

2. Right-Sized Design
✓ STRONG HIRE SIGNAL

Starts with the simplest working architecture justified by the math (e.g., 1 NVMe SQL primary + replicas + Redis for 40 writes/s & 3 TB).

✗ NO-HIRE RED FLAG

Recites a memorized Kafka + multi-DC Cassandra diagram that contradicts their own traffic calculations.

3. Technical Depth
✓ STRONG HIRE SIGNAL

Drives deep into 1–2 hard bottlenecks (partition keys, hot-key mitigation, transactional outbox, KV-cache batching) at minute 27.

✗ NO-HIRE RED FLAG

Skims across 12 boxes at identical buzzword depth and runs out of time before the deep dive.

4. Explicit Trade-Offs
✓ STRONG HIRE SIGNAL

Uses 3-part reasoning: 'A queue here because SMTP spikes to 3 s; checkout stays <60 ms, and we accept eventual email delay + retry dedup.'

✗ NO-HIRE RED FLAG

Name-drops tools ('We put Kafka and ZooKeeper here') without stating the alternative or operational cost.

5. Communication
✓ STRONG HIRE SIGNAL

Thinks aloud every 30–45s, checks alignment at phase transitions, and treats 'What if X fails?' as a cue for where points are awarded.

✗ NO-HIRE RED FLAG

Goes silent for 5 minutes while drawing or defends a flawed assumption defensively when nudged.

ARCHITECTURE & DATA-FLOW SLIDES · SLIDE 1 OF 6Section 01: System Design: TinyURL
ARCHITECTURE / DATA FLOW DIAGRAM
writeCreatorhas a long linkreadBrowserclicks short linkkey → URLShortenershort key to long URLOriginal sitethe long URL
SECTION 01 OF 1

1. System Design: TinyURL

★ FREE PREVIEW
Key Takeaway: Lease non-overlapping 1,000,000-ID counter ranges via ZooKeeper, scramble each integer bijectively before 6-character Base58 encoding for zero-collision unguessable keys, and serve 100:1 redirects from a 67 GB LRU cache fronting consistent-hashed KV shards.
SECTION 01 DIAGRAMS · SLIDE 1 OF 6System Design: TinyURL
ARCHITECTURE / DATA FLOW DIAGRAM
writeCreatorhas a long linkreadBrowserclicks short linkkey → URLShortenershort key to long URLOriginal sitethe long URL

Requirements, Capacity Sizing & Base58 Key-Space Math

A URL shortener exposes two primary paths: shorten (persisting a long URL under a compact unique key, optionally supporting custom aliases, TTL expiration, and owner deletion) and redirect (resolving a short key via HTTP redirect). Non-functionally, the service demands >= 99.999% availability, < 10 ms server redirect latency, human-readable keys free of look-alike characters, and non-predictable URLs so attackers cannot enumerate private links sequentially. Assuming 200,000,000 new links/month (~2.6M s/month -> ~77 writes/sec), a 100:1 read-to-write ratio (~7,700 redirects/sec or ~667M clicks/day), and 5-year (60-month) retention (12,000,000,000 links * 500 B = 6 TB), caching the hottest 20% of daily traffic (80/20 Pareto rule) requires just 667M * 0.20 * 500 B ≈ 67 GB of RAM. Starting from 62 alphanumeric characters (0-9, a-z, A-Z) and removing 4 visually ambiguous glyphs (0, O, I, l) yields Base58: 6 characters provide 58^6 = 38,068,692,544 (~38.1B) unique keys—3.17x our 12B 5-year demand (58^7 ≈ 2.21 trillion offers 58x expansion if ever needed).

  • Functional Requirements: Generate unique short URLs, redirect short keys to target URLs, claim custom aliases (e.g., spring-sale), enforce link expiry timestamps, and authenticate link deletions.
  • Read-Dominated Footprint: 3.9 MB/s egress (7,700 * 500 B) and 67 GB hot working set mean 80–90%+ of redirects never touch disk.
Sizing DimensionDerivation FormulaCalculated ResultArchitectural Implication
Shorten Write QPS200,000,000 / 2,592,000 s~77 writes/sec avgLight write load, but concurrent servers still need lock-free unique keys
Redirect Read QPS77 writes/sec * 100~7,700 reads/sec (~667M/day)Sub-millisecond memory caching (Cache-Aside) shields storage shards
5-Year Total Storage200M/mo * 60 mo * 500 B12B links = 6 TB raw dataModest disk volume; shard across KV nodes primarily for IOPS and HA
Hot LRU Cache Memory667M/day * 20% * 500 B~67 GB RAMFits easily inside a single replicated Redis cluster (2–4 nodes)
Key Length (Base58)58^6 ([1-9A-HJ-NP-Za-km-z])~38.07 billion keys (58^7 ≈ 2.21T)6 chars minimizes URL length while giving 3.17x headroom over 12B links

API Specification, HTTP 301 vs. 302 Semantics & Data Model

Requests pass through an L7 Load Balancer enforcing per-api_key token-bucket rate limits onto stateless App Servers. When answering GET /{short_key}, returning HTTP 301 Moved Permanently instructs browsers to cache the mapping locally forever—minimizing server read load, but blinding the platform to repeat click analytics and preventing link destination/expiry enforcement. Returning HTTP 302 Found (temporary redirect) routes every click through TinyURL so click counters, referrer analytics, and link expirations remain accurate; at 7,700 RPS served from a 67 GB RAM cache, 302 overhead is trivial. Because every database read is an exact primary-key lookup (short_key -> long_url) with zero joins or relational scans across 12B rows, a horizontally partitioned Key-Value store (DynamoDB or Cassandra) cleanly outperforms manually sharded SQL.

Design ChoiceOption AOption BProduction Trade-Off & Verdict
Redirect Status Code301 Moved Permanently (Browser caches link indefinitely)302 Found (Every click hits shortener edge)Use 302 when click analytics, A/B routing, or instant expiry/deletion matter; 301 only for pure zero-analytics static links
Primary Storage EngineRelational SQL (PostgreSQL / MySQL)Distributed Key-Value Store (DynamoDB / Cassandra)Choose KV store: 100% point lookups by short_key with 0 joins; native consistent hashing scales past 12B rows effortlessly
// REST API Signatures
POST   /v1/urls             Headers: { "X-API-Key": "..." }
                            Body:    { "long_url": "https://...", "alias": "spring-sale", "expires_at": "2027-01-01T00:00:00Z" }
                            -> 201 Created { "short_url": "https://tinyurl.com/2t6V2H" }

GET    /{short_key}         -> 302 Found | Header: Location: https://...
                            -> 404 Not Found (if unknown, deleted, or now > expires_at)

DELETE /v1/urls/{short_key} Headers: { "X-API-Key": "..." } -> 200 OK (evicts cache + deletes DB row)

// Key-Value Schema
urls  (short_key PK, long_url, user_id, created_at, expires_at) -- Partitioned by hash(short_key)
users (user_id PK, name, email, api_key UNIQUE, created_at)     -- Account & rate-limit metadata

Collision-Free Range Counter, Base58 Encoding & Bijective Scrambling

How do dozens of stateless App Servers mint unique 6-character keys concurrently without database round-trips? Truncating MD5(long_url) to 6 characters suffers birthday-paradox collisions (requiring read-retry loops) and maps two users shortening the same URL to the identical key, breaking independent analytics and expiry. Generating 6 random Base58 characters also requires a SELECT-before-INSERT check whose collision rate climbs as billions of keys accumulate. Instead, a monotonic Counter encoded in Base58 is unique by construction: for example, dividing counter 1,234,567,890 repeatedly by 58 produces remainders [16, 1, 28, 5, 51, 1] (least- to most-significant), mapping to digits [1, 51, 5, 28, 1, 16] -> 2t6V2H in microseconds. To eliminate single-counter contention, a replicated ZooKeeper range service leases non-overlapping blocks of 1,000,000 integers to each app server in memory (lasting > 3.5 hours at 77 RPS; losing unused IDs on crash wastes < 0.003% of 38B keys). Finally, because consecutive counters (5,000,001..5,000,003) encode to predictable adjacent keys (11SdKv, 11SdKw, 11SdKx), each server applies a secret bijective permutation—such as a modular affine cipher (a * counter + b) mod 58^6 with gcd(a, 58^6) = 1 or a 36-bit Feistel cipher—before Base58 encoding, scattering consecutive counters to WSN88D, mV7zKz, 2XsrXm while preserving strict 1-to-1 uniqueness.

Key Generation StrategyCollision RiskDB Round-Trips per WritePredictability & Duplicate-URL Behavior
Truncated Hash (MD5[:6])High (birthday paradox at ~200K keys)>= 2 on collision retrySame long_url collides across different users unless salted
Random 6-Char KeyGrows linearly as 12B / 38B fills (~31%)1–2 (put-if-absent retry loop)Unguessable, but suffers extra write latency as table fills
ZooKeeper Range + Scrambled Base580% (mathematically bijective)1 blind write (0 collision checks)Microsecond local generation, distinct per request, non-sequential (WSN88D, mV7zKz)
ALPHABET = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz" # 58 chars (no 0, O, I, l)
KEYSPACE = 58 ** 6         # 38,068,692,544
SECRET_A = 23_948_712_389  # Coprime with KEYSPACE: gcd(SECRET_A, 58**6) == 1
SECRET_B = 14_091_827_365

def encode_scrambled_base58(counter: int) -> str:
    permuted = (SECRET_A * counter + SECRET_B) % KEYSPACE
    chars = []
    for _ in range(6):
        permuted, rem = divmod(permuted, 58)
        chars.append(ALPHABET[rem])
    return "".join(reversed(chars))
Interview Signal: Security Boundary: Bijective scrambling defeats casual sequential enumeration (+1 stepping), but 58^6 (~35.6 bits of entropy) is not an access-control mechanism. Truly confidential documents must enforce authenticated authorization or use >= 128-bit (22+ char) capability tokens.

Cache-Aside Redirects, Custom Aliases, Lazy Expiry & Sharded HA

On GET /{short_key}, the App Server checks the 67 GB LRU Redis cluster first (Cache-Aside): cache hits return 302 Found in < 1 ms, while misses fetch from the KV store, populate Redis, and return. Because destination URLs are immutable after creation, cached entries never go stale—only DELETE calls must explicitly evict short_key from Redis. For Custom Aliases (e.g., spring-sale), the server executes an atomic conditional write (INSERT ... IF NOT EXISTS / DynamoDB attribute_not_exists(short_key)) so concurrent races resolve deterministically, and enforces len(alias) >= 7 while keeping generated keys strictly 6 characters so custom aliases can never collide with future counter blocks. Link Expiration combines Lazy Expiry on read (comparing now > expires_at at zero background cost and returning 404 Not Found) with an off-peak Cleanup Worker that batch-scans and purges expired rows to reclaim storage. Finally, the 6 TB KV store partitions keys via Consistent Hashing (hash(short_key) -> 1 shard per lookup) with multi-AZ and cross-region replicas so links resolve seamlessly even during a full data-center outage.

Non-Functional GoalPrimary MechanismEdge-Case Handling
Ultra-High AvailabilityStateless app tier + multi-AZ & cross-region KV shard replicasCache node failure degrades gracefully to KV shards; primary shard failure promotes replica
Low Latency (< 10 ms)67 GB LRU Cache-Aside + single-shard hash(short_key) routingViral link bursts stay 100% in Redis memory without touching disk
Collision-Free UniquenessZooKeeper 1M-ID disjoint blocks + >= 7-char custom alias conditional insertDisjoint lengths (6 vs. >= 7) prevent custom aliases from ever clashing with counters
Clean Storage LifecycleRead-time Lazy Expiry check + off-peak batch Cleanup Worker + DELETE cache invalidationExpired links stop redirecting at the exact millisecond of expires_at before batch GC runs
ACTIVE RECALL & TRADE-OFF PROBES

System Design Checkpoint Quizzes (1)

CHECKPOINT QUIZ #1

In "System Design: TinyURL" (Requirements, Capacity Sizing & Base58 Key-Space Math), how does a production-grade design handle "Redirect Read QPS" (Architectural Implication)?