Design a URL Shortener
Problem
Design a service that turns a long URL into a short link such as sho.rt/aZ3kQ9. Anyone who opens the short link is redirected to the original URL. Users can optionally choose a custom alias and an expiration date, and link owners can see how many times a link was clicked. The service should handle 100 million new links per month and a much larger volume of redirects.
- What is the expected read to write ratio? Is 100 redirects per new link a reasonable assumption?
- How short must the code be, and which characters are allowed in it?
- Do links ever expire by default, or only when the owner sets an expiration?
- Can the same long URL map to multiple short codes, or should we return the existing code?
- How fresh must click analytics be? Is a delay of a few minutes acceptable?
- Do we need to block malicious or spam destinations?
Items in bold are existing requirements. The rest are suggestions. Confirm with the interviewer whether they are relevant first.
- Create a short link for a long URL, returning a unique short code.
- Redirect a short link to its original URL.
- Support an optional custom alias and an optional expiration time.
- Report click counts per link to the link owner.
- Let owners delete or disable a link they created.
- Reject destinations that appear on a malware or phishing blocklist.
Items in bold are existing requirements. The rest are suggestions. Confirm with the interviewer whether they are relevant first.
- Scale to 100 million new links per month (about 40 writes per second, peaking near 400).
- Redirects are read heavy: plan for roughly 4,000 redirects per second on average and 40,000 at peak.
- Redirect latency under 50 ms at p99, since a slow redirect delays every page load behind it.
- High availability for redirects (99.99%). Link creation can tolerate brief degradation.
- Short codes must be unique and must not be guessable in sequence.
- Store links for at least 5 years: about 6 billion links, or roughly 3 TB including metadata.
A stateless API tier writes links to a horizontally partitioned key-value store, keyed by short code, and serves redirects from a cache in front of that store. Short codes come from a pre-generated pool of unique IDs encoded in base62, which avoids collision checks on the write path. Click events are published to a stream and aggregated asynchronously, so analytics never slow down a redirect.
Loading diagram...
Create a link. The client sends POST /links with the long URL. The link service validates the URL against the blocklist, then takes the next short code from its local batch of keys leased from the key generation service (or checks that a custom alias is free with a conditional write). It writes code -> long URL, owner, expiry to the link store and returns the short URL.
Redirect. The browser requests GET /aZ3kQ9. The link service looks up the code in the redirect cache and, on a miss, reads the link store and populates the cache. If the link exists and has not expired, it responds with 302 Found and the destination in the Location header. It then publishes a click event to the stream without waiting for the result.
Analytics. The click aggregator consumes events in micro-batches, rolls them up into per-link counters by minute and by day, and writes them to the analytics store, which backs the owner's stats page.
Stateless HTTP service that creates links and serves redirects. Every instance holds a small in-memory batch of unused short codes so creating a link never waits on a remote call.
- Go or Java service behind an L7 load balancer, chosen for low per-request overhead on the hot redirect path.
- Containerized and autoscaled on request rate.
API
POST /linkswith{ longUrl, alias?, expiresAt? }returns{ code, shortUrl }.GET /:codereturns302with aLocationheader, or404if the link is missing or expired.DELETE /links/:codedisables a link (owner only).GET /links/:code/stats?from=&to=returns click counts.
Scalability
Instances are stateless, so the tier scales horizontally behind the load balancer. Redirects dominate traffic and are served almost entirely from cache, which keeps the per-instance work to one cache lookup and one asynchronous publish.
Tradeoffs
Respond with 302 rather than 301. A permanent 301 lets browsers cache the redirect and skip our servers, which reduces load but makes click counts undercount badly and prevents disabling a link later. Accurate analytics and revocability are product requirements, so 302 wins.
Pre-generates unique short codes and leases them to link service instances in batches, so link creation never has to detect collisions.
- Small service backed by a relational database table of unused keys.
- Base62 encoding (
[a-zA-Z0-9]) of 7 characters, giving 62^7, or about 3.5 trillion, codes.
Diagram
Loading diagram...
Data Model
unused_keys(code CHAR(7) PRIMARY KEY)used_keys(code CHAR(7) PRIMARY KEY, leased_at TIMESTAMP)
Scalability
Leasing 1,000 keys per request means even the 400 writes per second peak needs only a handful of lease calls per second. Each lease moves keys between tables in one transaction, so two instances never receive the same key.
Tradeoffs
The alternatives are hashing the long URL (for example, the first 7 characters of an MD5) or encoding an auto-increment counter. Hashing produces collisions that must be detected and retried on every write. A plain counter is simple but makes codes sequential and guessable, which leaks link volume and lets anyone enumerate links. Pre-generated random keys avoid both problems. The cost is that keys leased to an instance that crashes are lost, which is harmless given trillions of available codes.
In-memory cache of code -> long URL that absorbs the redirect traffic.
- Redis Cluster, or Memcached if no persistence or data structures are needed.
Scalability
Link popularity follows a power law, so caching the hottest 20% of recently used links serves the large majority of redirects. Use LRU eviction with a TTL capped at the link's expiration time, and shard the cluster by code.
Tradeoffs
Cache aside (read the store on a miss, then populate the cache) is preferred over write through, because most created links are rarely clicked and would waste cache memory. Deleting a link must also delete its cache entry so a disabled link stops redirecting immediately.
Durable storage for every link, keyed by short code.
- A distributed key-value or wide-column store such as DynamoDB or Cassandra.
Data Model
links:code(partition key),long_url,owner_id,created_at,expires_at,is_disabled.links_by_owner:owner_id(partition key),created_at(sort key),code, for the owner's dashboard.
Scalability
Partition by code. Random codes spread writes evenly across partitions with no hot spots. About 3 TB over 5 years fits comfortably in a modest cluster with three-way replication. Expired links are removed with the store's TTL feature.
Tradeoffs
Every access is a point lookup by code and there are no joins, so a key-value store fits better than a relational database, which would need manual sharding at this size. Custom aliases need a uniqueness check, which is done with a conditional put (insert only if the key does not exist) instead of a transaction.
Consumes click events and maintains per-link counters for the stats API.
- Kafka as the click event stream.
- A stream processor such as Flink, or a simple consumer group, writing to a columnar store like ClickHouse.
Data Model
click_counts(code, bucket_start, granularity, count)with minute buckets for recent data and day buckets for history.
Scalability
Partition the stream by code so each consumer owns a subset of links and can aggregate in memory before writing. At 40,000 clicks per second, one-minute micro-batches reduce writes to the analytics store by orders of magnitude.
Tradeoffs
Counting asynchronously means stats lag by a minute or two, which the owner dashboard accepts. Incrementing a counter in the link store on every redirect would add a write to the hot path and create hot partitions for viral links.