URL Shortener

Clarify the requirements before you draw a box

Start by separating what the system must do from how well it must do it. The functional surface is small. First, create a short code for a long URL. Second, redirect a short code to its long URL with an HTTP 3xx. Third, optionally accept a custom alias chosen by the user. That is the entire feature set; resist the urge to invent more.

The non-functional requirements are where this problem lives, and they are the things the simulator scores. The workload is read-heavy at about 100 to 1, so the redirect path must be low-latency and the write path can be comparatively slow and simple. Availability is paramount: the redirect path has to stay up even when the datastore does not, which is the precise failure the gym injects. Codes must be short and unique. Concretely, the scenario pins these to measurable targets: redirects succeed at least 99% of the time (weight 4), sustained p99 latency stays at or below 110 ms (weight 2), served throughput holds at or above 4,000 rps through the 3x surge (weight 2), and the provisioned footprint stays at or under six instances (weight 1).

A strong candidate also names what is explicitly out of scope and confirms it with the interviewer rather than silently assuming. Click analytics, link expiration, user accounts, and abuse or malware filtering are all reasonable follow-ups, but none of them change the core architecture, so park them. The one scope question that does change the design is whether a freshly created code must be resolvable immediately, which is a read-your-writes concern we handle on the write path.

• Functional: create code from long URL, redirect code to URL, optional custom alias.
• Non-functional and graded: availability >= 99% (w4), sustained p99 <= 110 ms (w2), throughput >= 4,000 rps through a 3x surge (w2), footprint <= 6 (w1).
• Read:write is roughly 100:1, so optimize the read path relentlessly and keep the write path simple.
• Defer analytics, expiry, accounts, and abuse filtering; they do not move the core design.

Back-of-the-envelope: size everything before you commit

Anchor on the scenario load. Reads are 4,000 redirects per second sustained, peaking at 12,000 rps when a link goes viral (a 3x surge). At a 100:1 read-to-write ratio, that is 40 creates per second. Per day this is roughly 346 million redirects and 3.46 million new links. These numbers tell you immediately that the read path is the engineering problem and the write path is almost an afterthought at 40 writes per second.

Storage is tiny by modern standards. Each record is a short code (about 7 bytes), the long URL (around 100 to 200 bytes), plus a little metadata such as creation time and owner, so budget roughly 500 bytes per row. At 40 writes per second you accumulate about 3.46 million rows per day, 1.26 billion per year, and about 6.3 billion rows over five years, which is about 3.15 TB. That comfortably fits in a single managed key-value store or a sharded relational database; you are not storage-bound, you are throughput-and-availability bound.

Key space confirms a short base-62 code is more than enough. Base-62 (a to z, A to Z, 0 to 9) gives 62^6, about 56.8 billion, six-character codes and 62^7, about 3.5 trillion, seven-character codes. At ~1.26 billion new links a year, six characters already covers more than four decades of growth; seven gives you generous headroom and makes codes harder to enumerate, so standardize on seven. Finally, the hot working set is far smaller than total storage. Link popularity is heavily skewed (Zipfian), so the top one to ten million links absorb the vast majority of traffic. One million hot links at 500 bytes is 500 MB and ten million is 5 GB, both of which sit in a single Redis-class node. A redirect response is just headers (a few hundred bytes; budget ~500 B), so even at the 12,000 rps peak you are pushing only about 6 MB/s, roughly 48 Mbps, almost all of it from the edge.

• Reads: 4,000 rps sustained, 12,000 rps peak. Writes: ~40 rps. Daily: ~346M reads, ~3.46M writes.
• Storage: ~500 B/row, ~3.15 TB over five years — fits one managed KV cluster.
• Key space: 62^7 ~= 3.5 trillion codes; seven base-62 chars is ample, six already covers ~45 years.
• Hot set: top ~1-10M links = 0.5-5 GB, fits one cache node; peak egress ~48 Mbps, mostly from the edge.

High-level architecture and why each component earns its place

The reference topology is a single read pipeline: visitors hit an edge CDN, misses fall through to a small fleet of stateless Redirect API replicas behind a load balancer, those check an in-memory hot-link cache, and only a cache miss touches the key-value store that is the source of truth. The write path is a separate, low-traffic Create API that allocates a code, writes the mapping to the KV store, and warms the cache. The simulator requires four roles to be present (client, service, cache, db) and lets you add a CDN, which you should, because the edge is what makes a datastore outage a non-event. Note that the gym scores only this hot read path; the Create API and key-generation service are real but low-traffic, so they sit off to the side and outside the footprint budget.

The datastore choice is a key-value store, and the rubric rewards it most because the access pattern is a pure point lookup by primary key (the short code), with no joins, no scans, and no traversal. DynamoDB, Cassandra, or even Redis-as-system-of-record all fit. A relational database with a unique index on the short code also works and is a perfectly defensible answer at small to medium scale, just with less headroom. A graph database is the wrong tool: there is no graph to traverse, only single-key gets.

Two design decisions follow directly from the read:write ratio. Because reads dominate 100:1, you put your money into caching and edge delivery rather than into a bigger database, and you keep the Redirect API stateless so you can scale it horizontally and tolerate the loss of any single instance. The write path stays deliberately boring: 40 writes per second never stresses anything, so its only real job is generating unique codes correctly and making a new code immediately resolvable.

• Edge CDN: serves the cacheable hot set without touching your origin.
• Redirect API (stateless service, replicated behind an LB): does the code-to-URL lookup and returns the redirect.
• Hot-link cache (in-memory, Redis-class): absorbs the CDN misses so the DB stays near-idle.
• Key-value store: source of truth for code-to-URL, sized for point lookups, not scans.
• Separate low-traffic Create API plus code generator on the write path (off the scored hot path).

Deep dive 1: generating short, unique codes

There are two good code-generation strategies and two traps. The strongest answer is to base-62-encode a globally increasing counter. It is compact and collision-free by construction, since every counter value is distinct, so you never pay for a uniqueness check or a retry. The downside is that sequential codes are guessable and enumerable, and they leak your growth rate, so an attacker can walk the namespace. The second good answer is to generate a random 6-to-8-character code and rely on a unique index to reject collisions, retrying on the rare clash. This yields unguessable codes at the cost of an occasional extra round trip; with a 7-character space of 3.5 trillion, the per-insert collision probability stays under a fraction of a percent even after you have stored billions of links.

The two traps are instructive. Taking a prefix of MD5(longUrl) feels clever but is strictly worse: hash prefixes still collide, so you still need collision handling and a uniqueness check, which means you gained nothing over plain random while adding the surprise that the same URL always maps to the same code (often undesirable). Using the full URL as the key defeats the entire purpose, because the code is no longer short. Avoid both.

The counter raises a real distributed-systems question: who owns the counter? A single auto-increment column is a write bottleneck and a single point of failure. The standard fix is a key-generation service that hands out ranges. Each Create API instance leases a block of, say, 1,000 counter values from a coordinator (a transactional row, ZooKeeper, or a dedicated KGS), then serves codes from that block in memory with zero coordination until it needs the next block. This removes per-write contention and survives instance death (you lose at most one unused block). For multi-region uniqueness, give each region a disjoint range or use a stride so regions never collide without talking to each other.

Two more details earn points. Custom aliases share the same namespace, so check them against the same unique index and reserve a prefix or separate namespace so a user-chosen alias can never collide with a generated code. And for read-your-writes: because a creator may immediately test their new link, write the mapping through to the cache at creation time (or read it from the primary, not a lagging replica) so the code resolves the instant it exists, despite the read path being eventually consistent everywhere else.

• Best: base-62 counter — compact, collision-free; downside is enumerable, guessable codes.
• Good: random 6-8 chars plus a unique index and retry — unguessable, occasional collision check.
• Avoid: hash-prefix (still collides, no gain) and full-URL-as-key (not short).
• Scale the counter with a key-generation service that leases ranges; use disjoint ranges per region.
• Custom aliases reuse the unique index; write-through the cache on create for read-your-writes.

Deep dive 2: surviving the read storm (the hard part of this problem)

This is what the scenario is really testing, because the chaos timeline takes the datastore down at second 14 — just as load climbs into the 3x peak at second 16 — and then has it limp back with an 8x latency spike at second 22. The only thing that turns those events into a shrug is a very high combined hit ratio in front of the database. The arithmetic is the whole game. If the CDN serves 92% of redirects at the edge and the in-memory cache serves 95% of what is left, then the fraction that reaches the datastore is (1 - 0.92) x (1 - 0.95) = 0.004, or 0.4%. Combined hit ratio is 99.6%. At the 12,000 rps peak, that is about 960 rps reaching the Redirect API and only about 48 rps reaching the database.

Now the failure becomes a non-event. When the datastore goes fully down, you only drop the 0.4% of traffic that would have missed both caches, so the instantaneous availability bottoms out at about 99.6% during the outage and the run-aggregate availability lands around 99.9% — comfortably above the 99% target — because the store is only dark for six of the thirty seconds. When the datastore instead slows down 8x, it is still up and easily handles those ~48 rps, so only that same 0.4% of requests feel the latency. The sustained (median) p99 the gym grades barely moves: it sits around 44 ms for the reference. That number is set by the hot path (edge to Redirect API to cache), which never pays a database round trip; the dead or slow store touches just the miss fraction, so it cannot move the median even though the instantaneous tail briefly rises during the spike. The surge behaves the same way: tripling load triples the absolute miss traffic from 16 rps to 48 rps at the database, which is still nothing. High hit ratio is what decouples your availability and latency from the health of your slowest, most failure-prone component.

This is also where the 301-versus-302 trade-off lives. A 301 (permanent) redirect is cacheable by browsers and CDNs, so repeat clicks and edge nodes answer without touching your origin — that is exactly what the CDN node with a 0.92 hit ratio models, and it is how you offload the read storm. The cost is that you give up a server-side touch per click, which makes per-click analytics and the ability to change or disable a link harder. A 302 (temporary) redirect is not cached by default, so every click reaches your service: great for analytics and link control, terrible for absorbing a viral spike. The interview-grade answer is to use 301 with a sensible Cache-Control TTL and accept sampled or asynchronous analytics, or, if you must keep 302 for control, to push the read-absorption into your own cache tier instead of the CDN. Either way, the combined hit ratio is the number that matters.

One real-world caveat the simulator abstracts away: a single viral link is a hot key, and in reality one cache key can saturate one shard even when the cluster has spare capacity. The mitigations are to lean on the CDN (which naturally shards the hot key across geographic points of presence), to add a tiny per-replica in-process LRU for the few hottest codes, and to replicate hot keys across cache nodes. The gym models the cache as one logical node with ample capacity, so there the hot-key risk shows up as the datastore-outage scenario rather than cache saturation, but you should name the hot-key problem in an interview.

• Combined hit ratio = 1 - (CDN miss x cache miss). At 0.92 and 0.95 that is 99.6%, so the DB sees ~0.4% of traffic.
• A DB outage drops only the miss fraction (instantaneous availability ~99.6%, run-aggregate ~99.9%); an 8x DB slowdown only slows that fraction, so sustained p99 stays ~44 ms.
• 301 is cacheable (offloads reads, weakens analytics); 302 hits you every click (keeps analytics, no edge offload).
• Hot single key: spread it across CDN POPs, add a per-replica local cache, and replicate the key.

Bottlenecks under load and how to scale them

Walk the path and find what breaks first. The Redirect API is stateless, so it scales horizontally: put replicas behind a load balancer and add instances until replica_count x per-instance_capacity comfortably exceeds the peak miss traffic. In the reference that is three replicas at 4,000 rps each (12,000 rps of capacity), which dwarfs the roughly 960 rps of CDN-miss traffic at peak — the extra headroom buys you redundancy so no single instance is a point of failure and a degraded CDN hit ratio cannot tip the tier over. The lesson the gym teaches with its starter (a 0.5 CDN hit ratio and only two replicas at 1,500 rps) is that a low edge hit ratio pushes thousands of rps onto an under-provisioned service: at the 3x peak the CDN forwards 6,000 rps into 3,000 rps of capacity, so the service drops half the surge.

The database is the classic single point of failure, and you protect it in layers: the cache and CDN keep it near-idle, read replicas absorb whatever reads still get through, and the write path of 40 rps never threatens it. When total storage or write throughput eventually grows past one node, shard the KV store by short code using consistent hashing; because every access is a point lookup on the code, the code is a perfect shard key and there are no cross-shard queries. Reads scale with replicas, writes scale with the key-generation ranges described earlier, and nothing requires a distributed transaction.

Crucially, hit ratio is the cheapest lever you have. In the gym's cost model, raising a cache or CDN hit ratio is free, while every service replica and every box adds to your footprint. So the correct scaling instinct is to spend hit ratio first — crank the edge and cache to absorb the storm — and add boxes only for redundancy and to cover the residual miss traffic. That ordering is what lets you hit ~99.9% availability and a sub-45 ms p99 while staying inside a lean budget.

• Redirect API: stateless, scale by replicas behind an LB; size for peak miss traffic plus redundancy.
• Database: shield with cache, CDN, and read replicas; shard by short code (consistent hashing) only when storage or writes outgrow one node.
• Write path: scale code generation with leased counter ranges, not a single auto-increment.
• Spend hit ratio before boxes — it is the cheapest and most effective lever.

Key trade-offs to state out loud

Interviewers reward candidates who name the forks in the road and pick a side with a reason. The code-generation fork is compactness and determinism versus unguessability: a base-62 counter is the tightest and collision-free but enumerable, while random-plus-unique-index is unguessable but needs a collision check. The storage fork is a key-value store (ideal for point lookups, scales horizontally) versus a relational database (fine at smaller scale, simpler operationally, with a unique index doing the work). The redirect-semantics fork is 301 versus 302, trading edge cacheability against per-click control and analytics.

There is also a deduplication fork worth a sentence: do you return the same code for the same long URL, or a fresh code each time? Deduplicating saves storage and is nice for idempotent creates, but it requires an index on the long URL (a large, awkward key) and prevents two owners from tracking the same destination separately, so most production shorteners simply mint a new code per create. Finally, consistency: the system is eventually consistent on reads by design (caches and replicas lag), which is fine for redirects, but the create path must offer read-your-writes via write-through caching or a primary read so a new link works immediately.

• Counter vs random code: compact and collision-free but enumerable, vs unguessable but needs a uniqueness check.
• KV store vs relational: horizontal point-lookups vs operational simplicity at smaller scale.
• 301 vs 302: edge cacheability and read offload vs per-click control and analytics.
• Dedup vs new-code-per-URL: storage savings and idempotency vs simplicity and independent ownership.
• Eventual consistency everywhere except a read-your-writes guarantee on the create path.

How this maps to the SysGym scorecard

The reference design you are graded against is the single read pipeline: visitors, an edge CDN at a 0.92 hit ratio, three Redirect API replicas at 4,000 rps each, a hot-link cache at a 0.95 hit ratio, and a key-value store. Those numbers are not arbitrary. The 0.92 and 0.95 hit ratios produce the 99.6% combined hit ratio that keeps the datastore at about 0.4% of traffic, which is what lets a full DB outage and an 8x slowdown pass the 99% availability and 110 ms p99 SLOs. The three service replicas give capacity and redundancy well beyond the roughly 960 rps of peak miss traffic. And the footprint lands exactly at the budget: one CDN plus three service replicas plus one cache plus one database equals six, matching the cost SLO of at most six. (The low-traffic Create API and KGS are not part of this scored graph.)

Contrast that with the starter you are handed: a 0.5 CDN hit ratio, a 0.7 cache hit ratio, and only two service replicas at 1,500 rps. That combined hit ratio is just 85%, so 15% of traffic reaches the database, and when the database fails during the surge you drop a large slice of all redirects, while the under-replicated service drops still more at peak — at the 3x peak the CDN alone forwards 6,000 rps into 3,000 rps of service capacity. The fix is almost free: push the CDN and cache hit ratios up (hit ratio costs nothing in the model) and add the third replica to spend your cost budget where it counts. The takeaway the gym is drilling is the same one you would give in an interview — for a read-heavy redirect service, a high combined edge-plus-cache hit ratio is the single most important design decision, because it is what makes the database optional on the hot path.

• Reference graph: CDN 0.92 hit, 3x Redirect API at 4,000 rps, cache 0.95 hit, KV store — footprint exactly 6.
• SLOs: availability >= 99% (weight 4), p99 <= 110 ms (weight 2), throughput >= 4,000 rps (weight 2), cost <= 6 (weight 1).
• Starter fails because an 85% combined hit ratio sends 15% of traffic to a database that the scenario then kills — and two 1,500-rps replicas can't absorb the surge.
• Winning move: max out hit ratios (free) first, then add a replica for headroom and redundancy.