Katkat
Back

Design a Distributed URL Shortener for Very High Redirect Traffic

Uber FreightSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSystem Design

Last updated

A system design interview question asking you to design a distributed URL shortener. It tests API design, unique short-code and distributed ID generation, collision handling, storage and sharding, caching for very high redirect traffic, availability, fault tolerance, and link expiration.

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.

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?

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.

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?

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

Hints

Hint 1

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.

Hint 2

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.

Hint 3

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.

Hint 4

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.

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?