System design deep dive · HLD
Design a URL Shortener (bit.ly / TinyURL): full high-level design.
Requirements, back-of-envelope capacity estimation, a high-level design diagram, a deeper deployment architecture diagram, sequence diagrams for the write and read paths, and an entity-relationship diagram for the data model - with the reasoning an interviewer expects behind every box and arrow.
1. Clarify requirements before drawing any box
A strong system design answer starts by pinning down scope out loud. For a URL shortener, that means separating what the system must do from how well it must do it, and stating the scale assumptions that every later diagram depends on.
Functional requirements
Non-functional requirements
2. Back-of-the-envelope capacity estimation
These numbers decide almost everything downstream: whether a single relational database instance is enough, whether the cache needs to be a cluster, and how many bits the short code needs.
| Metric | Assumption | Resulting estimate |
|---|---|---|
| New URLs (writes) | 500 million / month | ~193 writes/sec average, ~1,500 writes/sec peak |
| Redirects (reads) | 100:1 read:write ratio | ~19,300 reads/sec average, ~150,000 reads/sec peak |
| Storage per record | ~500 bytes/row (URL + metadata + indexes) | 500M/mo × 5 years × 500B ≈ 15 TB raw |
| Short code space | Base62 alphabet, 7 characters | 62^7 ≈ 3.5 trillion codes - enough for decades of growth |
| Cache size for 80/20 hot set | 20% of monthly URLs get 80% of reads | ~100M hot entries × ~200 bytes ≈ 20 GB - fits a Redis cluster |
3. High-level design (HLD)
The HLD names the major components and the one-directional data flow between them, without committing yet to specific infrastructure, regions, or replica counts - that level of detail belongs in the architecture diagram in the next section.
What each box owns
Shorten service (write path)
Accepts a long URL, asks the ID generator for a globally unique numeric ID, encodes that ID as a Base62 short code, writes the mapping to the database, and returns the short code to the caller. It is deliberately kept separate from the redirect service so a slow or overloaded write path never adds latency to reads.
Redirect service (read path)
Looks up the short code in the cache first; on a hit, it issues the HTTP redirect immediately. On a miss, it reads from the database, populates the cache, then redirects. It also publishes a lightweight "click happened" event to the message queue and returns to the caller without waiting for that event to be processed - the click log must never block the redirect.
ID generator
Produces globally unique, roughly time-ordered 64-bit IDs (a Snowflake-style generator: timestamp + worker ID + sequence number) so that no two Shorten service instances can ever hand out the same short code, without needing a single centralized auto-increment counter that would become a bottleneck and a single point of failure.
Cache, database, and the analytics side path
Redis holds the hot 20% of mappings that serve 80% of redirects. The primary database is the source of truth and is sharded once volume outgrows a single instance. Click events flow through a queue into a separate analytics store so that reporting workloads (aggregation queries, dashboards) never compete for resources with the latency-sensitive redirect path.
4. Detailed architecture diagram
The architecture diagram takes every HLD box and answers "how is this actually deployed?" - replica counts, sharding, regions, and the specific technology choice, which is what an interviewer is checking for once they've accepted the high-level shape.
| Decision | Choice | Reasoning |
|---|---|---|
| Multi-region | Active-active, two regions | Redirects must survive a full region outage; Redis pub/sub propagates cache invalidation cross-region within milliseconds. |
| Database sharding key | Hash of the short code | Even distribution regardless of URL popularity; the short code is known on every read, so no secondary lookup is needed to find the shard. |
| ID generation | Snowflake-style workers, not DB auto-increment | Removes a single centralized counter as a bottleneck and single point of failure; IDs stay roughly time-ordered for index locality. |
| Analytics isolation | Separate Kafka topic + column store | A slow analytics query or a backlog in the stream workers must never add latency to the redirect path. |
5. Sequence diagrams for the two critical flows
A sequence diagram is where an interviewer checks whether you actually understand call order, what is synchronous versus fire-and-forget, and where a cache miss changes the path.
5.1 Create short URL (write path)
Step 4 happens entirely inside the Shorten service and touches no network call, which is why encoding is cheap. Step 7 is deliberately drawn as a dashed, non-blocking arrow: warming the cache on write is an optimization, not a correctness requirement, so the client response in step 8 does not wait for it.
5.2 Redirect (read path, with cache miss)
On a cache hit, steps 3-6 collapse into a single cache read and the response returns in well under 10ms. Step 7 is drawn the same way as the write path's async cache warm - the click event is published but never awaited, which is the specific design choice that keeps the redirect's p99 latency independent of however busy the analytics pipeline is.
6. Entity-relationship (ER) diagram and schema
The data model has to answer three questions: what is the primary lookup key, how are clicks recorded without write-amplifying the hot table, and how does a user's link list get retrieved without a full table scan.
Key modeling decisions
| Storage choice | Use when | Watch out for |
|---|---|---|
| Relational (Postgres/MySQL), sharded | You want strong uniqueness constraints on short_code and straightforward joins for the owner dashboard. | Cross-shard joins and resharding are operationally heavier than a key-value store. |
| Key-value (DynamoDB/Cassandra) | Access pattern is purely "get long_url by short_code" at very high scale. | Uniqueness on short_code must be enforced at the application layer via conditional writes. |
7. Deep dives interviewers actually probe
How is the short code generated - hash vs counter?
Two viable approaches: (1) hash the long URL (MD5/SHA-256), take the first 7 characters of a Base62 encoding of the hash, and retry on collision; or (2) generate a globally unique numeric ID first (via the Snowflake-style ID generator) and Base62-encode that ID directly, which has zero collision probability by construction. The design above uses option 2 because it avoids collision-retry loops entirely and keeps write latency predictable under load.
// Base62 encoding of a unique numeric id - no collisions possible
static final String ALPHABET = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
String encode(long id) {
StringBuilder sb = new StringBuilder();
while (id > 0) { sb.append(ALPHABET.charAt((int)(id % 62))); id /= 62; }
return sb.reverse().toString();
}Why 301 vs 302 redirect, and does it matter for analytics?
A 301 (permanent) redirect lets browsers cache the mapping locally, which reduces load on the redirect service but means the click never reaches the server again on a repeat visit from the same browser - breaking click analytics. A 302 (temporary) redirect is used instead specifically so every click is observable server-side, trading a small amount of avoidable redirect traffic for accurate analytics, which matches the functional requirement that owners can see click counts.
How do you prevent abuse - someone shortening millions of spam URLs?
Rate limiting at the API gateway keyed on API key or IP (token bucket, e.g. 100 shortens/hour for anonymous users), CAPTCHA on the anonymous web form past a threshold, and an async URL-safety check (a call to a phishing/malware-list service) that can retroactively deactivate a short code without blocking the synchronous create path.
How does cache invalidation work when a link is deleted or edited?
Deletes and edits are rare compared to reads, so the database write path also issues a cache DEL for that key (or publishes an invalidation event on Redis pub/sub that all regional cache nodes subscribe to), rather than trying to update the cached value in place - deleting and letting the next read repopulate the cache is simpler and avoids partial-update bugs.
What is the single biggest bottleneck as this scales 10x?
Not the redirect path - cache hit rate keeps that cheap and horizontally scalable by adding Redirect service replicas and Redis shards. The real bottleneck becomes the database's write throughput once organic growth in URL creation outpaces a single shard's IOPS, which is solved by adding more shards on the existing hash-of-short-code scheme - a decision made easy specifically because the sharding key was chosen up front to require no resharding migration of existing data ranges.
Post a Comment
Add