URL shortener

Turn long links into short codes and redirect people fast. The system is read-heavy: about 100 redirects for every new link. The real questions are how to generate unique codes and how to keep popular redirects in a cache (a fast in-memory copy of the data).

Design a URL shortener that handles 100 million new links a month and about 10,000 redirects a second at peak.

Requirements

Functional

  • Create a short link for a long URL. The response is a short code such as sk.in/aZ3k9Qx.
  • Visiting the short link redirects the browser to the long URL.
  • Optional custom alias (sk.in/diwali-sale) and optional expiry date.
  • Basic click analytics per link (counts by day, country and referrer), available within a few minutes.

Non-functional

  • Scale: 100 million new links a month (about 40 a second) and about 10,000 redirects a second at peak. Reads outnumber writes about 100 to 1.
  • Redirect latency: p99 under 50 ms at the server, meaning 99 out of 100 redirects finish within 50 milliseconds. The redirect sits in front of every click, so it must be fast.
  • Availability: 99.99% for redirects, because a dead short link breaks every campaign that printed it. Creating links can be 99.9%.
  • A code, once issued, never points anywhere else. Codes should not be easy to enumerate (guess one after another).
  • Analytics may lag by a few minutes. Eventual consistency (the numbers catch up a little later) is fine there.

Out of scope

  • User accounts, billing and link-management dashboards.
  • Malware and phishing scanning of target URLs (mention it, do not design it).
  • Editing where an existing code points.

Estimate

  • New links: 100M a month / 30 days ≈ 3.3M a day; 3.3M / 86,400 s ≈ 40 writes a second (peak maybe 3x, about 120).
  • Redirects: 100 reads per write → 40 x 100 = 4,000 a second on average; the prompt says about 10,000 a second at peak.
  • Storage per link: code + long URL + metadata ≈ 500 bytes. 100M x 500 B = 50 GB a month → 600 GB a year → 3 TB over 5 years; x3 replication ≈ 9 TB.
  • Code space: 5 years x 1.2B links a year = 6B links. Base62 with 6 characters gives 62^6 ≈ 57B, 7 characters gives 62^7 ≈ 3.5 trillion. Use 7: lots of headroom and sparse enough to resist guessing.
  • Cache: if about 20M distinct links are clicked on a busy day and the top 20% take most clicks, 4M x 500 B ≈ 2 GB. The whole hot set fits in RAM easily.
  • Database load after the cache: at a 95% hit ratio, 10,000 x 5% = 500 reads a second at peak, comfortable for a replicated store.
  • Bandwidth: 10,000 redirects x ~500 B ≈ 5 MB/s. Not a concern.

API

  • POST /v1/links {long_url, alias?, expires_at?} -> 201 {code, short_url} (409 if the alias is taken)
  • GET /{code} -> 302 Location: long_url (404 if unknown, 410 if expired)
  • GET /v1/links/{code} -> 200 {long_url, created_at, expires_at}
  • GET /v1/links/{code}/stats?from=&to= -> 200 {clicks_by_day[], top_countries[], top_referrers[]}
  • DELETE /v1/links/{code} -> 204 (owner only; the code is retired, never reused)

Data model

  • links(code PK, long_url, owner_id, created_at, expires_at, is_custom): key-value access by code only, so a replicated key-value store fits.
  • id_ranges(range_start PK, allocated_to, allocated_at): which block of the counter each service instance has leased.
  • click_events (stream): {code, ts, country, referrer, user_agent_class}, partitioned by code.
  • link_stats_daily(code, day, clicks, by_country map): written by the analytics worker; read by the stats API.

A request, step by step

  1. Create: the client sends a POST with a long URL. The link service takes the next number from the ID block it has leased (reserved for itself for a while), say 1,048,213.
  2. The service scrambles that number with a fixed reversible permutation, a reshuffle that can be undone. It encodes the result in base62 (the characters 0 to 9, a to z and A to Z) to 7 characters, then writes the row to the links store.
  3. Custom alias: the service does a conditional insert, which writes the row only if the code does not exist yet. If the code already exists, the API returns 409 (Conflict) and nothing is overwritten.
  4. Redirect: a request for GET /aZ3k9Qx reaches the load balancer, then any link-service instance. The instance checks Redis first. About 95% of the time the long URL is there, and the service answers with a 302 redirect in a millisecond or two.
  5. On a cache miss, the service reads the links store by partition key (the code). It fills the cache with a TTL (time to live: how long the entry stays before it is removed), capped by the link expiry, then redirects. Unknown codes are cached briefly as "not found", so a bot trying thousands of random codes does not reach the database.
  6. Every redirect also sends a small click event to Kafka (a durable message queue) without waiting for a reply. The aggregator rolls these events up into per-day counts in the stats store, a few minutes behind real time.
  7. When an instance uses up its 1,000 IDs, it leases the next block from the allocator. That is one atomic operation per 1,000 links, so the allocator sees well under one call a second.

Deep dives

Generating unique short codes

Weak: hash the URL and take the first 7 characters. Compute an MD5 or SHA hash of the long URL, encode it in base62 and cut it to 7 characters. It looks clever, but cutting the hash short causes collisions: two different URLs get the same code.

With 6 billion links in a space of 3.5 trillion codes, roughly 1 new link in 600 collides late in the system's life. So every write needs a check and a retry. Also, two users who shorten the same URL get the same code. That is a problem if they want separate analytics or expiry.

Good: one global counter, encoded in base62. A single database sequence gives unique numbers, so there are no collisions at all. But every create now waits on one row. Sequential codes are also guessable: anyone can try aZ3k9Qx, then aZ3k9Qy, and scrape all your links.

Great: counter ranges plus a scramble. An allocator hands each service instance a block of 1,000 numbers. The allocator can be etcd, ZooKeeper or one database row updated atomically. The instance issues numbers from memory, so at 40 creates a second the allocator sees about one call every 25 seconds.

Before encoding, pass the number through a fixed reversible permutation, such as a small Feistel cipher over the 62^7 space. Consecutive numbers then give codes that look unrelated, still with zero collisions. Custom aliases live in the same table and use insert-if-absent (write only if the code is free).

Trade-off: if an instance crashes, the unused part of its block is lost. With 3.5 trillion codes, that waste does not matter. In return, you need no collision checks, and there is no hot row (a single row that every request must update).

Making redirects fast and cheap

Redirects are 99% of traffic, so this path decides both cost and latency.

Weak: read the database on every click. A big replicated store can do 10,000 lookups a second. But you pay for a cluster sized for the peak. Your p99 latency (the time within which 99 out of 100 requests finish) also suffers from every slow disk read.

Good: cache-aside in Redis. In cache-aside, the service checks the cache first and loads from the database only on a miss. The hot set is about 2 GB, so a small replicated Redis holds it. At a 95% hit ratio, the database sees about 500 reads a second at peak.

Also cache negative results (unknown codes) for a minute. Then scans of random codes do not fall through to the database.

Great: cache, the right status code, and the edge. Use 302 (temporary redirect), not 301 (permanent redirect). Browsers cache a 301 forever. That saves you load, but you never see repeat clicks and you can never expire the link.

Some campaign links are about to go viral, such as a festival sale SMS sent to millions. For those, let a CDN cache the 302 for a short time, say 60 seconds. A CDN (content delivery network) is a set of servers near users that cache responses. The origin, meaning your own servers, then barely notices the spike.

Trade-off: every layer of caching makes analytics and expiry a little less exact. With a 60-second TTL (time to live) at the edge, an expired link might still redirect for a minute. Clicks served at the edge must be counted from CDN logs instead of your own events.

Counting clicks without slowing the redirect

Weak: increment a counter in the links table on every redirect. Each click becomes a write to the same row. A viral link turns into a hot row that slows down its own redirects. Analytics now sits on the critical path, the steps that every request must wait for.

Good: fire-and-forget events to a queue. Fire-and-forget means the service sends the event and does not wait for a reply. The service publishes {code, ts, country, referrer} to Kafka, partitioned by code, and returns the 302 at once. Workers aggregate the events into per-minute and per-day counts.

If the queue is briefly unavailable, the service drops the event or buffers a little in memory. It never fails the redirect because of analytics.

Great: aggregate before you store. Workers keep small in-memory counters per code per minute. They flush these rollups (totals already added up) to a column store such as ClickHouse. A column store is built for queries like "clicks by day by country". Raw events are kept for a few days in case you need to reprocess them, then they expire.

Trade-off: you give up exact real-time counts. They lag a few minutes, and a crash may lose a few seconds of events. In return, the redirect path never waits on analytics. For billing-grade counts, make the consumer idempotent (handling the same event twice has the same effect as once) and keep raw events longer.

What breaks

  • The Redis cluster loses a node: cache misses jump, and the links store suddenly sees thousands of reads a second. The hit-ratio and database-latency alerts catch it. To degrade safely, serve from the remaining replicas and rate-limit cache refills, so a sudden rush of identical reads does not overload the store.
  • The ID allocator is unavailable: instances keep issuing from their current blocks of 1,000 IDs. With 4 instances sharing 40 creates a second, that gives about a minute and a half of headroom. So lease the next block early, or use bigger blocks. Creating links fails only when the blocks run out; redirects are unaffected.
  • A viral link creates a hot key on one cache shard (one server in the cache cluster), and you see one shard at high CPU. Fix it by caching that code inside each service instance for a few seconds, or by letting the CDN serve it.
  • Kafka is down: click events are dropped or buffered briefly, and redirects keep working. Analytics show a gap, visible as a dip in event throughput.
  • Abuse: bots create millions of spam links. Rate-limit creates per user and per IP address. Scan target URLs asynchronously (in the background), so bad links can be disabled.

What each level is expected to cover

Mid level: A Mid candidate should get the read-to-write ratio and the rates right: about 40 creates and 4,000 to 10,000 redirects a second. They should pick 7-character base62 codes with a sound way to keep them unique. They should put a cache in front of a replicated store behind a load balancer, and return a sensible redirect status.

Senior: A Senior candidate also explains why counter ranges beat hashing, and makes codes hard to enumerate. They argue 302 versus 301 in terms of analytics and expiry, and keep analytics off the redirect path with a queue. They plan for hot keys and cache failure, and say how expired links and abuse are handled.

Common mistakes

  • Designing for writes when the system is 99% reads, and never putting a cache on the redirect path.
  • Hashing and truncating the URL without saying how collisions are detected and retried.
  • Sequential codes from a public counter, so anyone can enumerate every link.
  • Using 301 without realising that browsers cache it forever, which breaks expiry and analytics.
  • Updating a click counter in the main table on every redirect, which creates hot rows (rows so busy that writes queue up behind each other).
  • Choosing a relational database with joins "because it is safer", when the only access pattern is lookup by code.

Follow-up questions

  • How would you support custom aliases without two users getting the same one?
  • A single link gets 50,000 clicks a second during an IPL final. What breaks first, and what do you change?
  • How do you expire links, and what does a visitor see after expiry?
  • How would you stop the service being used to spread phishing links?
  • How would you run this in two regions, and where would the ID allocator live?

Lessons behind this answer