Design a URL Shortener

Requirements

A URL shortener maps a long URL such as https://example.com/blog/2026/10/a-very-long-path?ref=newsletter to a short link like https://sho.rt/aZ3kP9q. Visiting the short link redirects to the original.

Functional

• Create a short link for a long URL (optionally with a custom alias).
• Redirect a short link to its original URL.
• Optional expiry time per link.
• Basic click analytics (count, referrer, country, device).
• Owners can delete their links.

Non-functional

• Read-heavy: redirects vastly outnumber creations (assume 100:1).
• Low latency: redirect p99 under ~50 ms server-side.
• High availability: a broken redirect breaks every page that embeds the link.
• Durability: a created link must never silently disappear.
• Unpredictable keys (nice to have): keys should not be trivially enumerable.

Capacity Estimates

Assume 100 M new links per day, a 100:1 read-to-write ratio, links kept for 5 years, and ~500 bytes per record.

The numbers tell you two things: storage is large but simple (key-value), and the read path must be served mostly from cache.

API Design

POST /api/v1/urls
  Body:     { "longUrl": "https://...", "customAlias": "optional", "expiresAt": "optional ISO-8601" }
  201:      { "key": "aZ3kP9q", "shortUrl": "https://sho.rt/aZ3kP9q" }
  409:      custom alias already taken

GET /{key}
  302:      Location: <longUrl>
  404:      unknown key
  410:      link expired or deleted

DELETE /api/v1/urls/{key}          (owner only, 204 No Content)

GET /api/v1/urls/{key}/stats?from=...&to=...
  200:      { "clicks": 1234, "byCountry": {...}, "byReferrer": {...} }

• Authenticate create/delete/stats with an API key or OAuth token; redirects are public.
• Rate limit POST per user and per IP to stop spam and key-space exhaustion.

Data Model

The access pattern is a single-key lookup, so a horizontally scalable key-value or wide-column store (DynamoDB, Cassandra, Bigtable) fits well. A sharded relational database also works.

CREATE TABLE urls (
  short_key   VARCHAR(10)  PRIMARY KEY,
  long_url    TEXT         NOT NULL,
  user_id     BIGINT,
  created_at  TIMESTAMP    NOT NULL,
  expires_at  TIMESTAMP,
  is_deleted  BOOLEAN      DEFAULT FALSE
);

CREATE TABLE users (
  user_id     BIGINT       PRIMARY KEY,
  email       VARCHAR(255) UNIQUE,
  api_key     VARCHAR(64)  UNIQUE,
  created_at  TIMESTAMP
);

High-Level Design

flowchart LR
  Client --> LB[Load Balancer]
  LB --> W[Write Service]
  LB --> R[Redirect Service]
  W --> KGS[Key Generation Service]
  W --> DB[(URL Store)]
  R --> C[(Redis Cache)]
  R --> DB
  R --> Q[[Click Event Queue]]
  Q --> A[Stream Aggregator]
  A --> OLAP[(Analytics Store)]

Write path: validate the URL → get a unique key → persist the record → return the short URL.

Read path: look up the key in cache → on miss read the DB and populate the cache → emit a click event asynchronously → return the redirect.

Separating read and write services lets each scale independently; the redirect fleet is roughly 100× larger.

Deep Dives

Key generation

This is the core of the interview. Three common approaches:

1. Counter + base62 encoding

• A global, increasing integer ID is encoded into base62 (0-9a-zA-Z).
• Guaranteed unique, no collision checks.
• A single counter is a bottleneck, so hand out ranges: each app server leases a block (e.g. 1 M IDs) from ZooKeeper or a "ticket" table and allocates locally.
• Downside: sequential keys are guessable. Mitigate by shuffling the ID through a reversible bijection (e.g. a Feistel cipher) before encoding.

2. Hash the long URL

• Compute MD5/SHA-256 of the URL, base62 encode, take the first 7 characters.
• The same URL naturally maps to the same key (free de-duplication).
• Truncation causes collisions: check the DB and, on conflict, append a salt and re-hash. This adds a read per write and complicates concurrency (use a conditional insert such as INSERT ... IF NOT EXISTS).

3. Pre-generated Key Generation Service (KGS)

• Offline, generate random unique 7-char keys and store them in an "unused keys" table.
• App servers fetch keys in batches into memory and hand them out with no coordination.
• Moving a batch to "used" atomically prevents two servers from getting the same key.
• If a server crashes, its in-memory keys are lost; with 3.5 trillion keys, that waste is acceptable.
• The KGS must be replicated so it is not a single point of failure.

Caching

• Cache-aside with Redis/Memcached, LRU eviction. Links follow a power-law: a small fraction gets most clicks.
• Long TTLs are safe because mappings are effectively immutable; invalidate on delete or expiry.
• Negative caching: cache "not found" briefly so scanners hitting random keys do not hammer the DB. A Bloom filter of existing keys is an alternative.
• Edge/CDN caching of redirects for viral links pushes latency below 10 ms.

Redirects: 301 vs 302

Use 302 (or 307) when analytics, expiry or editable destinations matter, which is most products. Use 301 when the link is permanent and you only care about minimizing load.

Analytics

• Never write analytics synchronously on the redirect path.
• The redirect service publishes a small event (key, timestamp, IP-derived country, user agent, referrer) to Kafka or Kinesis.
• A stream processor (Flink, Spark Streaming) aggregates per key per minute/hour and writes rollups to an OLAP store.
• Raw events land in object storage for reprocessing and ad-hoc queries.
• If the queue is unavailable, buffer locally and drop rather than fail the redirect: analytics is best-effort, redirects are not.

Scaling & Reliability

• Stateless services behind load balancers; autoscale the redirect tier on QPS.
• Shard the URL store by short_key using consistent hashing; random keys spread load evenly.
• Replicate each shard (e.g. 3 replicas, quorum reads/writes) and across regions for disaster recovery.
• Multi-region reads: links are write-once, so asynchronous cross-region replication with a short lag is acceptable; read-your-write for the creator can be handled by routing them to the home region briefly.
• Expiry cleanup: check expires_at lazily on read (return 410) and run a low-priority background job to purge expired rows and return keys to the pool if desired.
• Abuse protection: rate limit creation, scan destinations against malware/phishing lists, and support takedowns.
• Hot keys: a viral link can overload one cache shard; replicate hot keys across nodes or keep a small in-process cache on redirect servers.

Trade-offs

Interview Tips

• Start with numbers; they justify the cache-heavy read path and the 7-character key.
• Present all three key-generation options, then pick one and defend it.
• Explicitly discuss 301 vs 302; interviewers often probe it.
• Keep analytics off the critical path and say why.
• Mention collision handling and concurrency for custom aliases (conditional writes).
• Call out failure modes: KGS down, cache stampede on a viral link, region outage.
• Do not over-engineer the write path: ~1,200 writes/s is modest. The challenge is reads.