URL Shortener Design

Tags

URL Shortener Design

System that maps short alphanumeric codes to long URLs, enabling redirect-based access and click analytics.

Clarify First

Before designing, lock these assumptions with the interviewer:

  1. Read:write ratio — URL shortener is read-heavy (~100:1); drives CDN and cache tier decisions. Every URL is written once, read hundreds of times.
  2. Do short URLs expire? — TTL on records adds an expires_at column and requires background deletion jobs; no expiry means simpler storage but unbounded growth.
  3. Custom aliases? — User-provided short codes (e.g., bit.ly/my-brand) require conflict detection; changes the ID generation path.
  4. Analytics depth? — Click count only vs geo/device/referrer breakdowns; click count fits in the URL record, detailed analytics requires a separate event store.
  5. Scale target? — Startup (1M DAU) vs Bitly-scale (300M DAU); different tiers, different sharding decisions.

Capacity Estimation

Derivation chain for a mid-tier URL shortener (2026):

Assumption: 100M DAU (mid-tier URL shortener, 2026 estimate)

Write path: 1 URL creation per 100 users per day = 1M new URLs/day
  write_QPS = 1M / 86_400 ≈ 12 write QPS

Read path: 100:1 read/write ratio
  read_QPS = 12 × 100 = 1,200 read QPS
  peak_read_QPS = 1,200 × 2 = 2,400 QPS (2x peak multiplier)

Storage (5-year horizon):
  record_size ≈ 500 bytes (short_url + long_url + metadata)
  daily_records = 1M
  5_year_records = 1M × 365 × 5 = 1.825B records
  storage = 1.825B × 500 bytes ≈ 900 GB ≈ 1 TB over 5 years
  → single-shard relational DB is sufficient at this scale
  → sharding required only if write_QPS exceeds ~10,000 (100× scale)

Cross-reference: Capacity-Estimation for the shared DAU-to-QPS-to-storage methodology.

Conclusion: At 12 write QPS and 2,400 read QPS, a single-shard relational database handles writes. The read path is the target for caching and CDN optimisation, not the write path.

Central Technical Problem

Collision-free short code generation at write time without a sequential ID source.

Two approaches address this:

Approach 1: Hash-then-truncate

  • Compute MD5 or SHA-256 of the long URL.
  • Truncate to 6-7 base62 characters.
  • Collision risk is on truncation, not on the full hash. Two different URLs can truncate to the same 6-character prefix.
  • Mitigation: retry loop (generate next 6 chars from the hash) or bloom filter pre-check before writing.

Approach 2: Auto-increment ID + base62 encode

  • Database auto-increment provides a globally unique integer.
  • Encode the integer in base62 to get a 6-character short code.
  • No collision possible — uniqueness is guaranteed by the auto-increment.
  • Risk: sequential IDs are guessable (enumeration attack). Mitigation: apply a random salt or use Snowflake-style distributed counter to remove sequential predictability.

Base62 encoding math

  • Alphabet: [0-9A-Za-z] — 62 characters
  • 6 characters: 62^6 = ~56.8 billion combinations — sufficient for 1.825B records over 5 years
  • 7 characters: 62^7 = ~3.5 trillion — sufficient for Bitly-scale (300M DAU)
  • At 1M writes/day for 5 years: 1.825B IDs needed — 6-char base62 has a 31× safety margin

301 vs 302 redirect tradeoff

Response CodeBrowser Caches?Analytics ImpactUse When
301 Moved PermanentlyYes — browser skips server on repeat visitsBreaks click count after first visit (clicks never reach server)Analytics not required; CDN/cache offload is priority
302 Found (Temporary)No — every click hits the serverEvery click is intercepted and countableAnalytics required; accept the per-click server load

Decision rule: Use 302 if click analytics are required. Use 301 if analytics are not needed and minimising server load is the priority.

Component Design

[Client] --> [Load Balancer] --> [URL Shortener API] --> [Cache (Distributed-Cache)]
                                        |                        |
                                        v                        v
                                 [SQL Database]          [CDN (for redirect)]
                                 (short_url, long_url,
                                  created_at, expires_at,
                                  click_count)

Component responsibilities:

  • Load Balancer — distributes incoming read traffic across API server replicas; stateless API servers scale horizontally
  • URL Shortener API — handles URL creation (write path) and redirect lookup (read path); stateless; scales horizontally
  • Cache (Distributed-Cache) — cache-aside on the read path; caches (short_url → long_url) mappings; TTL aligned with URL expiry; reduces DB load on the 1,200 read QPS path
  • SQL Database — single source of truth for all URL records; relational handles TTL expiry queries and analytics aggregations efficiently at 12 write QPS
  • CDN — caches the 302 redirect response at edge nodes globally; reduces latency for international users; effective for popular short URLs with high repeat access

System Diagram

URL-Shortener-Design-diagram.excalidraw

Alternatives Considered

DecisionAlternative AAlternative BWhy Chosen Approach Wins
ID generation: auto-increment + base62Hash-then-truncateSnowflake distributed IDAuto-increment has no collision; simpler implementation; guessability mitigated with salt; preferred at sub-Bitly scale
Redirect: 302 Found301 Moved PermanentlyClient-side JS redirect302 enables server-side click interception; 301 breaks analytics after first visit; JS redirect adds latency
Storage: relational DBNoSQL key-value (DynamoDB)NoSQL document storeRelational handles TTL expiry queries and analytics aggregations at 12 write QPS; NoSQL wins only at 10,000+ write QPS
Read scaling: CDNNo CDN (all reads to cache)Cache onlyCDN reduces latency for global users; popular URLs benefit from edge caching; cache tier handles long-tail reads

Likely Follow-Up Questions

  1. How do you handle expired URLs? — Background TTL job deletes records past expires_at; alternatively, a lazy deletion strategy marks records as expired on first miss and deletes in a batch cleanup.
  2. How do you prevent enumeration attacks on sequential IDs? — Apply a random salt before base62 encoding, or use a Snowflake-style ID that embeds a timestamp and sequence rather than a simple counter.
  3. What changes at Bitly-scale (300M DAU)? — write_QPS grows to 36 (still manageable), but read_QPS grows to 360,000 (3x peak = 720K). A 7-char base62 code is required. Sharding the DB becomes necessary. CDN becomes critical to absorb the read load.
  4. How do you implement real-time click analytics? — Write click events to a stream (Kafka topic); a downstream analytics worker aggregates per-short-URL counts and stores projections in a read-optimised store. This separates the write-heavy click stream from the URL record itself.
  5. How would you add custom alias support? — Add an alias column with a unique constraint; on creation, check for conflict and return 409 if the alias is already taken; custom aliases share the same redirect path as generated codes.
  6. What if the same long URL is shortened multiple times? — Either generate a new short code each time (simpler, wastes space) or de-duplicate by hashing the long URL and checking for an existing record (requires a unique index on the long URL hash).

Existing Pattern Connections

Design DecisionExisting PatternRelationship
Short code generation via distributed counterConsistent-HashingIf using distributed ID generation across nodes, consistent hashing assigns ID ranges to nodes without coordination bottleneck
Cache tier for long URL lookupDistributed-CacheCache-aside strategy: check cache first, fall back to DB, populate cache on miss; eviction on URL expiry
Read scaling via CDN edgeContent-Delivery-Network302 redirects served from CDN edge; CDN caches (short_url → long_url) mapping for the read-heavy path
Click analytics as separate projectionCQRS-PatternClick events are writes to an append-only event log; analytics queries read from a separate aggregated projection — command and query separation
URL expiry triggering cleanupDomain-EventsURL expiry publishes a URLExpired domain event; background cleanup worker subscribes and deletes the record

Linked mentions