Design a URL shortener: short-code generation, fast redirects and scaling

Design a URL shortening service. A user submits a long URL and receives a short link; anyone who opens the short link is redirected to the original URL. The scale, the feature set and the retention policy were not given. Ask for them, or state your assumptions and the numbers you design for. ### Clarifying Questions - How many short links are created per day, and how many redirects per second must be served at peak? - Can users choose a custom alias? Do links expire, and can their owners edit or delete them? - If the same long URL is submitted twice, should it receive the same short code? - Are there limits on code length or allowed characters, or a requirement that codes not be guessable? - Do we need click analytics, and how fresh must they be? - Must redirects keep working while link creation is down? ### Part 1 — API and short-code generation Define the API, and explain how a new short code is generated so that two links never share a code. ```hint Uniqueness has to come from somewhere Compare deriving the code from the URL, drawing it at random, and deriving it from a counter. For each one, ask what happens when two servers create links at the same moment. ``` #### What This Part Should Cover - Create and redirect APIs, including error cases and custom aliases - Code length derived from the expected number of links and the character set - A generation scheme that is unique across servers, and how collisions are handled - Whether codes are predictable, and whether that matters ### Part 2 — The redirect path Make redirects fast and highly available at the expected read volume. ```hint Reads dominate Most short links are created once and opened many times, and a small share of links receive most of the clicks. Think about what that means for where the mapping should be cached. ``` #### What This Part Should Cover - The read path from request to redirect, with its caching layers - The choice of redirect status code, and its effect on caching and analytics - Unknown, expired and deleted codes, including caching of misses - Latency and availability targets ### Part 3 — Storage, scaling and operations Choose the data store and data model, and explain how the system scales and stays reliable as links accumulate. ```hint Let the lookup choose the key Every redirect is a lookup by code. Let that drive the data model and the way the data is partitioned. ``` #### What This Part Should Cover - The data model and the choice of store - Partitioning, replication and multiple regions - Expiry, deletion and the click analytics pipeline - Abuse: malicious links and limits on link creation ### What a Strong Answer Covers - Requirements and estimates first, with numbers that drive code length, storage and cache size - A collision-free generation scheme justified against the alternatives - A read path built for a read-heavy, skewed workload - Sound storage and partitioning, with failure handling - Operational concerns: expiry, analytics, abuse and observability ### Follow-up Questions - One link goes viral and receives a large share of all traffic. What happens in your system? - How would you count clicks per link accurately without slowing down redirects? - A short code is reported as a phishing link. How do you take it down everywhere quickly, including caches? - How would you serve redirects from several regions, and what happens when a link created in one region is opened in another a second later?