System Design: Design a URL Shortener

Interviewer

How would you generate the short URL aliases? We need to handle 100 million new URLs per month.

Candidate

At 100M URLs/month, we're looking at ~40 writes per second. We need a fast, collision-free generation method. I'd avoid hashing the original URL because of collisions. Instead, I'd use a distributed unique ID generator like Snowflake or pre-allocated token ranges from Zookeeper. Once we have a unique 64-bit integer ID, Base62 encode it. A 7-character string gives us 62^7 (~3.5 trillion) combinations - plenty for decades. Base62 also avoids special characters that might break URLs.

Interviewer

How would you handle redirect latency? We want the 99th percentile redirect to be under 10ms.

Candidate

For that latency target, reads must be in-memory. I'd put a Redis cache in front of the database, with an LRU eviction policy. Popular URLs stay hot in cache. For the database, I'd use a distributed key-value store like DynamoDB or Cassandra partitioned by the short code's first character. This gives us O(1) lookups and automatic sharding. For cold URLs (not in cache), we'd fall through to the database with a read-through cache pattern. A single DynamoDB partition can handle thousands of reads per second, so even cache misses should stay under 5ms.

Interviewer

What about custom short URLs that users want to choose?

Candidate

Custom URLs need a separate namespace. I'd store them in a distinct table with a unique constraint on the custom alias. On creation, we check the custom table first; if the alias is taken, return an error. If available, we insert the custom mapping and invalidate any overlapping auto-generated entry. We should also implement profanity filtering and allow only alphanumeric characters plus hyphens for custom aliases.