Url Shortener
IntermediateOverview
A URL shortener converts a long URL into a short, unique alias and redirects any request for that alias back to the original URL. The design is read-heavy and latency-sensitive, since a shortened link may be resolved millions of times after it is created once.
Functional Requirements
- Create a short alias for a given long URL, optionally accepting a user-supplied custom alias.
- Redirect a request for a short alias to the original long URL with an HTTP redirect.
- Support an optional expiration time after which an alias stops resolving.
- Collect basic analytics per alias, such as click count and referrer.
Non-Functional Requirements
- High availability: the redirect path must stay up even if the creation path degrades.
- Low latency: redirects should resolve in well under 100 ms at p99.
- Aliases must be unique and effectively non-guessable to discourage enumeration.
- Durable storage: a created mapping must not be lost.
Capacity Estimation
Assume 100M new URLs per day and a read-heavy 100:1 read-to-write ratio, retained for 5 years.
- QPS:
- Writes: 100M / 86,400 s ~ 1,160 writes/sec.
- Reads: 100 x 100M = 10B/day -> 10B / 86,400 s ~ 115,000 reads/sec.
- Storage: each record (short code, long URL, owner, timestamps, metadata) ~ 500 bytes. Per day: 100M x 500 B = 50 GB/day. Over 5 years: 50 GB x 365 x 5 ~ 91 TB.
- Bandwidth:
- Write ingress: 1,160/s x 500 B ~ 0.58 MB/s.
- Read egress (redirect responses ~ 500 B): 115,000/s x 500 B ~ 57.5 MB/s.
Key-space check: base62 over 7 characters yields 62&sup7; ~ 3.5 trillion aliases, enough for ~96 years at 100M/day.
High-Level Architecture
The architecture splits into a Write API for creating short links and a highly optimized Read API for resolving them. A standalone Key Generation Service runs in the background, pre-generating unique short keys to guarantee fast, collision-free writes. The read path heavily utilizes an in-memory cache (Redis) to serve the 115k QPS of redirects with sub-millisecond latency.
Data Model
| Entity | Fields / Schema | Storage Choice |
|---|---|---|
| url_mapping | short_code (PK), long_url, user_id, created_at, expires_at | Key-value / wide-column store (DynamoDB or Cassandra), partitioned by short_code |
| click_event | short_code, ts, referrer, country | Append-only analytics store (column-oriented) |
| user | user_id (PK), email, plan | Relational store |
Detailed Design
Alias Generation
There are two viable approaches for generating short codes:
- Hash and Encode: Hash the long URL (e.g., MD5) and take a base62-encoded prefix. If there's a collision in the DB, append a salt and re-hash. Problem: Collisions slow down the write path significantly at scale.
- Key Generation Service (KGS): A dedicated background service pre-computes a massive pool of unique base62 keys and stores them in a DB. When the API needs a key, it simply pops one off the pre-generated list. This removes generation and collision-checking from the request path entirely, making writes O(1) and ultra-fast. This is the preferred approach.
Redirect Path (The Read Layer)
On a resolve request, the Read Service checks the cache first. On a hit it returns a 301 or 302 immediately; on a miss it reads the key-value store, populates the cache, then redirects. Because the workload is overwhelmingly reads of a small hot set of links (Pareto principle), a cache-aside layer absorbs the vast majority of traffic.
301 vs 302 Redirects
A 301 (Permanent Redirect) tells the browser to cache the result indefinitely. This reduces server load but makes tracking analytics impossible because the browser bypasses the server on future clicks. A 302 (Found / Temporary Redirect) forces the browser to hit the shortener server every time, which is required if the business model relies on detailed click analytics.
Bottlenecks & Solutions
The Key Generation Service (KGS) handing out keys one-by-one is a bottleneck. To fix this, the KGS doesn't give out single keys to the API servers; it gives out 'chunks' of 1,000 keys at a time. The API server keeps this chunk in its local memory and uses them. If the API server crashes, those 1,000 unused keys are lost forever, but with 3.5 trillion possible combinations, we don't care.