Design a URL Shortener

Design a URL shortening service similar to bit.ly that generates short aliases for long URLs and redirects users to the original destination.

Functional Requirements

• Generate a unique short URL for any given long URL
• Redirect users from the short URL to the original URL
• Allow custom short URLs (optional)
• Track click analytics (count, referrer, location)
• URLs should expire after a configurable period

Non-Functional Requirements

• High availability (99.9% uptime)
• Low latency redirects (< 100ms)
• Handle 100M+ URLs and 10K requests/second
• Shortened URLs should be as short as possible

Questions to Consider

• How will you generate unique short codes without collisions?
• What data store is best suited for high-read workloads?
• How will you handle the 301 vs 302 redirect trade-off?