fullstack · advanced · 10d
URL shortener at scale
Build a URL shortener that survives real traffic — then run it: deploy it, watch it, and work the incident when one hot link melts your cache.
Deliverable
A deployed redirect service with an indexed store, a read-through cache, a CI/CD pipeline, RED dashboards with SLOs, and a written post-mortem of a cache-stampede incident.
Milestones
0/8 · 0%- 01Frame the system: scale, SLOs, non-goals
Before any code, size the problem. A shortener is overwhelmingly reads (redirects) over writes (creates) — often 100:1 or worse — so the redirect path is what your design must protect. Do the back-of-envelope math (target QPS, link count, storage, cache working set), then write down SLOs (e.g. p99 redirect < 50 ms, availability 99.9%) and explicit non-goals so you do not gold-plate the create path.
Definition of done- You have numbers: target redirect QPS, create QPS, total links, bytes per link, and the resulting storage and cache-memory estimates.
- You wrote 2–3 SLOs for the redirect path and at least two explicit non-goals.
- 02Design the API, the schema, and the short code
Decide how short codes are generated and stored. A monotonic counter + base62 gives dense, collision-free codes but leaks volume and ordering; random/hashed codes hide that but need a uniqueness check and retry on collision. Pick one and justify it, then design the table and the single index the redirect lookup will ride, and choose where the cache and CDN sit.
Definition of done- Your API contract covers create and resolve, and you can state the collision behaviour of your code-generation choice.
- The schema has exactly the index the redirect query needs, and you justified it against the leading-column rule.
- 03Build the redirect hot path
Implement create and resolve for real. The resolve path is the hot path: it must be a single indexed lookup returning a 301/302, with the request lifecycle (accept → route → handle → serialize) kept lean. Measure a cold (uncached) redirect end to end so you know the latency you are about to cache away.
Definition of done- A redirect resolves via one indexed query (you confirmed it with EXPLAIN, not a sequential scan).
- You recorded the cold redirect p50/p99 with no cache, as your baseline.
- 04Cache the reads, protect the writes
Put a read-through cache in front of resolve and make create safe. The cache turns the hot path from a DB query into a memory hit, but introduces invalidation and a future stampede risk you will pay for later. On the write side, make create idempotent and rate-limit abusive creation so a script can't exhaust your code space or your database.
Definition of done- Cached redirects show a clear p99 drop versus the cold baseline, and you can explain your invalidation rule.
- Create is idempotent for the same input and rate-limited per client, with a 429 + Retry-After on abuse.
- 05Test it: unit, integration, contract, load
Build the test pyramid for the service. Unit-test the code generation and refill/limit math, integration-test the resolve path against a real Postgres + cache, contract-test the API so clients don't break on a change, and load-test the redirect path to find where p99 degrades. The load test is what makes the next two milestones honest.
Definition of done- Unit, integration, and contract tests run green in one command, and a flaky test is quarantined, not retried-until-green.
- A load test reports the redirect QPS at which p99 crosses your SLO.
- 06Deploy it: container, pipeline, rollout
Ship it through a pipeline, not by hand. Containerize with a lean image, wire a CI/CD pipeline that runs the tests as gates before build, roll out with a strategy that can fail safely (canary or blue-green), put redirects behind a CDN/load balancer, and keep secrets out of the image. A bad rollout should be reversible in seconds, not a redeploy.
Definition of done- A push runs tests → builds the image → deploys via the pipeline, and you can roll back without rebuilding.
- Secrets are injected at deploy, not baked into the image, and redirects are served behind a CDN or load balancer.
- 07Observe it: RED, traces, SLOs
Make the running system legible. Emit RED metrics (rate, errors, duration) on the redirect path, structured logs you can actually query, and traces propagated across the cache and DB hops so a slow redirect points at the slow span. Turn your SLOs into dashboards and an error budget, so you find the incident before your users tweet it.
Definition of done- A dashboard shows redirect rate, error rate, and p50/p99 duration, tied to your SLOs and error budget.
- A trace for one slow redirect shows the cache and DB spans, so you can localize latency without guessing.
- 08Survive a cache stampede, then write the post-mortem
A popular link's cache entry expires under peak traffic; thousands of concurrent misses hit Postgres at once, p99 redirect latency spikes, and the origin saturates. Detect it from your own metrics, mitigate it live, find the root cause, and write the post-mortem. The mechanism that saves you is request coalescing (single-flight) plus a probabilistic early refresh — not just a longer TTL, which only moves the cliff.
Definition of done- You reproduced the stampede with a load test (N concurrent misses on one hot key) and captured the p99 spike and origin QPS on your dashboard.
- You mitigated it with single-flight (one origin fetch per key) plus early-refresh jitter, and showed p99 returning to SLO.
- Your post-mortem names the trigger, the contributing factors, the blast radius, the fix, and one prevention that is not 'raise the TTL'.
Feeds fromSelf-review
Paste your post-mortem's root cause and the prevention item; a senior reviewer checks it names the stampede mechanism (coalescing / early refresh), not just the symptom (high latency).
Starter
- README.md
- src/shortener.ts
- test/shortener.test.ts
Unzip, implement the stubs, then run the tests until they pass: bun test
Rubric
| Junior | Mid | Senior | |
|---|---|---|---|
| Codec correctness | Implements encodeBase62/decodeBase62 that round-trips for small values; may miss edge cases like n=0 or single-digit base62. | Full round-trip for all non-negative integers including 0 and large values; correct charset order (no leading-zero ambiguity from using '0' as the first symbol). | Can articulate why the charset order matters for URL safety, why base62 beats base64 for short codes in URLs, and what the max code length is for a given counter ceiling (e.g., 62^6 ≈ 56 billion links before 6-char codes overflow). |
| Collision and expiry handling | Counter increments per create; resolve returns null for unknown codes. TTL comparison may be off-by-one or use >= instead of >. | Deterministic unique code generation with no collision by construction; TTL correctly distinguishes unknown (never existed) from expired (once existed); createdAt stored at create time, not resolve time. | Reasons about the coordination cost of a shared counter in a distributed system (single point, requires atomic increment or a flake-ID strategy), the lookup-before-insert cost of random code generation, and when each approach's tradeoffs favour it (write-heavy vs. anonymity vs. predictability). |
| Read-path scaling | Understands that redirect is the hot path and that a cache helps; uses 301 by default without considering its implications. | Explains that 301 is browser/CDN-cached permanently (fast but hard to revoke) while 302 is re-fetched every time (controllable but slower at scale); picks the right one for each use case and can justify it. | Identifies the cache-stampede risk on hot codes (many concurrent misses on expiry), proposes single-flight (request coalescing) and probabilistic early refresh as mitigations — not just a longer TTL. Discusses CDN edge caching of 301s as a zero-backend-cost path and the blast-radius of a misconfigured permanent redirect. |
Reference walkthrough (spoiler)
301 vs 302: permanence, cacheability, and revocability. A 301 is cached permanently by browsers and CDNs — the redirect happens client-side on repeat visits with zero backend traffic. That is the ideal outcome for a shortener's read path. The cost: you cannot change the destination or disable the link for any client that has already cached it. A 302 is re-fetched every time, so you keep full control (useful for A/B landing pages, expirable links, or analytics that must count every hit). Choose 301 for stable public links; choose 302 when you need runtime control.
Counter vs. random code generation. A monotonic counter + base62 gives dense, collision-free codes with O(1) generation and no uniqueness check needed — but it leaks creation volume and ordering (code 'c' was created before 'd'). Random or hashed codes hide that information but require a uniqueness check (lookup-before-insert) and a retry on collision. At low collision probability (e.g., 8 random chars from base62 = 62^8 ≈ 218 trillion combinations) retries are rare, but you pay one read per write. In a distributed system a shared counter becomes a coordination bottleneck; alternatives include per-node counter ranges, Snowflake-style IDs (timestamp + node id + sequence), or UUIDs truncated to base62.
Cache stampede on a hot code. When a popular link's cache entry expires, many concurrent requests all miss the cache simultaneously and fan out to the database. The origin receives a spike proportional to concurrent traffic, not to the steady-state RPS. Two standard mitigations: (1) single-flight / request coalescing — only one goroutine/thread fetches from the DB while the rest wait on that single in-flight fetch; (2) probabilistic early refresh (XFetch) — with some probability proportional to remaining TTL, the first request to evaluate the probability check triggers a background refresh before expiry, so the cache never actually goes cold under traffic. A longer TTL defers the problem but does not eliminate it.
Why base62 and not base64 for URL codes. Base64 uses '+', '/', and sometimes '=' — characters that must be percent-encoded in URL path segments, which makes codes longer and harder to read. Base62 (a–z, A–Z, 0–9) is URL-safe with no reserved characters. The information density loss is small: a 6-char base62 code encodes log2(62^6) ≈ 35.7 bits vs. base64's ≈ 36 bits — negligible. Charset ordering matters: if '0' is the first character, encodeBase62(0) = '0' and single-char codes collide with numeric-looking strings. Starting the charset with lowercase letters avoids that and produces more readable codes.
Redirect type as a design decision at create time vs. per-link. Storing the redirect type per link (not just per shortener instance) enables mixed policies in one service: permanent short codes (301) for stable campaigns and ephemeral tracking links (302) for A/B tests coexist in the same store. The resolution path always reads the stored type, so clients get exactly what was contracted at creation. Changing from 301 to 302 for an already-distributed code is impossible to revoke from browser caches — treat redirect type as immutable once set.
Make it senior
- Go multi-region: serve redirects read-local and reason explicitly about the create-path consistency trade-off.
- Add a click-analytics pipeline (events → queue → rollups) that never adds latency to the redirect path.
- Support custom domains with automated TLS issuance and per-tenant isolation.
- Detect and throttle abusive create and redirect patterns without hurting legitimate traffic bursts.