Design a URL Shortening Service: Code Generation, Storage and Fast Redirects

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 interviewer expects you to drive the discussion from requirements to a design that holds up at large scale. The story gives no scale or feature details. For practice, assume the standard scope: creating short links and redirecting them are in scope, links may optionally expire, the service is public and read-heavy, and redirects must be fast and highly available. Treat custom aliases and click analytics as extensions to discuss if time allows. ### Constraints and Clarifications - Short codes must be unique: two different long URLs must never share a code. - Redirect latency and availability matter more than the latency of creating a link. - State your own scale assumptions and use them in your estimates. ### Clarifying Questions - What scale should I design for: links created per month and redirects per second? - Should shortening the same long URL twice return the same code or a new one? - Do links expire by default, and can their owners delete or edit them? - May codes be guessable or sequential, or must they be hard to enumerate? - Is click analytics needed, and how fresh must it be? ### Part 1 — Requirements, API and estimates Pin down the functional and non-functional requirements, define the public API, and estimate write and read rates, storage, and the length of the short code. ```hint Size the code from the count Work out how many links will exist over the service's lifetime, then choose an alphabet and a length that leave comfortable headroom. ``` #### What This Part Should Cover - Functional scope and non-functional priorities (read latency, availability, durability) - Create and redirect endpoints with request, response and status-code choices - Back-of-the-envelope rates, storage and code length - The redirect status code and what it implies for caching and analytics ### Part 2 — Generating short codes Compare ways of generating unique short codes and pick one. Explain how it stays collision-free while many application servers create links at the same time, and whether its codes can be guessed. ```hint Coordination cost Ask how much coordination between servers each scheme needs per link, and what happens when one of those servers restarts. ``` #### What This Part Should Cover - At least two schemes compared, such as hashing, counters and pre-generated keys - How uniqueness is guaranteed across servers - Code predictability and how to prevent enumeration if required - Handling of custom aliases and repeated long URLs ### Part 3 — Storage, caching and the redirect path Choose the data store and data model, describe the read and write paths, and explain how redirects stay fast and available under heavy, skewed traffic, including what happens when parts of the system fail. ```hint Most reads hit few links Consider how popularity is distributed across links and which layers could answer a redirect without touching the database. ``` #### What This Part Should Cover - A data model and store choice tied to the access pattern - Cache layers and their invalidation for expired or deleted links - Partitioning and replication for scale and availability - Failure handling and monitoring for the redirect path ### What a Strong Answer Covers - Requirements and estimates that drive later decisions instead of being forgotten - A code-generation scheme with a clear argument for uniqueness - A redirect path optimized for a read-heavy, skewed workload - Explicit trade-offs, such as permanent versus temporary redirects and relational versus key-value storage - Abuse and safety considerations for a public service ### Follow-up Questions - How would you add click analytics without slowing redirects down? - How do you stop the service from being used to spread malicious links? - How would you serve users in several regions with low redirect latency? - One link suddenly receives a huge share of all traffic. What happens in your design?