Design a Distributed URL Shortener for Very High Redirect Traffic

Design a distributed URL shortening service. A user submits a long URL and receives a short URL; anyone who opens the short URL is redirected to the original. Discuss the overall distributed architecture and how it runs at scale. The interviewer expected all of the following to be covered: the shortening API, the redirect API, unique short-code generation, database and storage, caching, distributed ID generation, read and write scalability, handling very high redirect traffic, availability and fault tolerance, URL expiration, collision handling, and database partitioning or sharding. The parts below group these topics. ### Clarifying Questions - How many new short URLs per day and how many redirects per second at peak should the design support? Size everything from these numbers. - Can users choose a custom alias instead of a generated code? - If the same long URL is shortened twice, should it get the same short code? - What is the expiration policy: no expiry, a default lifetime, or a lifetime chosen per URL? - Should the service record click analytics? - Must short codes be hard to guess or enumerate? ### Part 1 — Shortening and redirect APIs Define the API that creates a short URL and the redirect API. Specify requests, responses, status codes and error cases. ```hint What the status code controls The status code of the redirect response decides whether browsers and intermediaries may cache it. Consider what that means for analytics, for expiration, and for the load on your servers. ``` #### What This Part Should Cover - The create request and response, including optional alias and expiry - The choice of redirect status code and its consequences - Input validation, error responses and abuse protection ### Part 2 — Short codes, distributed ID generation and collisions How are unique short codes generated across many servers, how short can they be, and how are collisions handled? ```hint Derive or assign Compare deriving a code from the long URL with assigning each new URL a unique number and encoding it. Ask which approach can produce two equal codes, and what coordination across servers each one needs. ``` #### What This Part Should Cover - Code length derived from the expected key space - A distributed ID scheme, its coordination cost and its failure modes - Detecting and resolving collisions, including those involving custom aliases ### Part 3 — Storage, caching, sharding and very high redirect traffic Choose the database and data model, describe the caching layers, explain how reads and writes scale and how the system absorbs very high redirect traffic, and describe how the data is partitioned. ```hint Count the layers Redirects usually far outnumber creations and follow a very skewed popularity curve. Think about how many layers could answer a redirect before the request ever reaches the database. ``` #### What This Part Should Cover - The data model and the choice of storage technology - Caching layers, including hot keys and lookups of codes that do not exist - The partition key, resharding, and how reads and writes scale independently ### Part 4 — Availability, fault tolerance and expiration How does the service stay available when a server, a cache node, a database node or a whole region fails? How do URLs expire? ```hint Decide what must survive Separate what must keep working during a failure from what may degrade, and design expiration so that no cached redirect outlives its link. ``` #### What This Part Should Cover - Replication, failover and multi-region operation - Graceful degradation, keeping redirects up when other functions fail - How expiration is enforced, how expired data is cleaned up, and whether codes are reused ### What a Strong Answer Covers - Requirements and back-of-envelope numbers that drive code length, storage size and cache size - A coherent design in which ID generation, partitioning and caching fit together - Explicit trade-offs, such as hashing versus counters, permanent versus temporary redirects, and relational versus key-value storage - Failure modes, and how the redirect path survives each of them - Monitoring and abuse protection ### Follow-up Questions - How would you add per-link click analytics without slowing down redirects? - A single link goes viral and receives a large share of all traffic. What happens at each layer? - How would you stop the service from being used to spread phishing or malware links? - How would you migrate to a new sharding scheme with no downtime?