Design exercise: URL shortener and key-value service

Generated by Claude (Fable 5.1) by hand, Scout learning center M4a on 2026-10-12, reviewed by a second reader (Claude Fable 5.1), Scout learning center M4b on 2026-10-12.

Concept: System design and architecture · also covers API design, Relational and non-relational data stores, Scaling · Part C (Design exercises) of the system design module · design exercise · version 2

On this page

A classic design exercise: a service that shortens URLs, redirects for years and counts clicks. The reference answer sizes the system from stated assumptions, chooses a random base-62 code, keeps the redirect path read-only and independent of the primary database, and counts clicks asynchronously. Converted by hand from the module outline's reference answer; every number and source is kept.

Attempt the design from the prompt, the constraints and the questions before reading the reference answer.

The prompt

Design a service that turns a long URL into a short one and redirects anyone who opens the short one. Links must keep working for years. Give the owner basic click counts.

Constraints and numbers

Functional

Create a short link (optionally with a custom alias and an expiry), redirect, show click totals per link.

Scale (assumption)

100 million new links per year; 100 redirects per write, so about 10 billion redirects per year; peak redirect rate 10x the average. Every number here is an assumption chosen for the exercise; a candidate derives the per-second rates, the storage and the cache size from them.

Targets and retention (assumption)

Redirect p99 under 50 ms from the service's side; 99.95 percent availability for redirects; link creation may be slower and less available. Links live 5 years by default.

Non-goals

A full analytics product, link previews, fraud detection beyond a block list.

Clarifying questions worth asking

  • Can two users shorten the same long URL and get different short codes? Yes; a short code identifies a link record, not a URL.
  • 301 or 302? 302, so that clicks are counted and the target can change; a 301 lets browsers cache the redirect and the counts stop. RFC 9110 defines the status semantics and RFC 9111 the caching.
  • Custom aliases? Yes, up to 32 characters, unique.
  • How exact must click counts be? Approximate within a minute is fine.
  • Multi-region? Readers everywhere; writers mostly one region.
  • Deletions? Owner can disable; disabled links return 410.

Reference answer

Requirements and estimates

Derived numbers

Writes: 100 million per year is about 3.2 per second average, 32 at peak. Reads: 10 billion per year is about 320 per second average, 3,200 at peak; a well-known-link spike could be 10x that for one key. All of this is arithmetic on the chosen scale.

Storage

A link record of about 500 bytes (short code, long URL up to 2 kB in rare cases, owner id, created, expires, flags) gives 50 GB per year, 250 GB over 5 years before indexes: one primary with replicas holds it; sharding is a choice, not a need, at this scale.

Cache and bandwidth

If 20 percent of links take 90 percent of reads (assumption), caching the hot 20 million records of one year at 600 bytes is 12 GB; a two-node cache holds it. Bandwidth is negligible (a redirect is a few hundred bytes).

High-level design

Container view

The redirect path is read-only and stateless: an edge that does not cache the 302, a redirect service, a cache in front of read replicas, and an asynchronous click log. Link creation is a separate API that writes to the primary and invalidates the cache. The two paths share the database and nothing else, which is what lets redirects stay up when creation cannot.

flowchart LR
  U[Browsers] -->|GET /code| E[Edge or CDN, no caching of 302]
  E --> R[Redirect service, stateless]
  R --> C[(Cache: code to long_url)]
  R -->|miss| P[(Primary DB, replicas for reads)]
  R -->|async| Q[[click events]]
  Q --> A[Aggregator]
  A --> S[(click counts by day)]
  O[Owners] --> W[Link API]
  W --> P
  W -->|invalidate| C
flowchart LR
  U[Browsers] -->|GET /code| E[Edge or CDN, no caching of 302]
  E --> R[Redirect service, stateless]
  R --> C[(Cache: code to long_url)]
  R -->|miss| P[(Primary DB, replicas for reads)]
  R -->|async| Q[[click events]]
  Q --> A[Aggregator]
  A --> S[(click counts by day)]
  O[Owners] --> W[Link API]
  W --> P
  W -->|invalidate| C

Boxes are containers; cylinders are stores; double brackets are queues or logs.

The data model

Entities

Link {code, long_url, owner_id, created_at, expires_at, state (active or disabled), custom (bool)}. ClickCount {code, day, count}.

API

POST /links {long_url, alias?, expires_at?} returns {code, short_url} (idempotency key supported); GET /{code} returns 302 to the long URL, or 404 or 410; GET /links/{code}/stats returns {total, by_day[]}; DELETE /links/{code} sets disabled.

The short code

7 characters of a 62-character alphabet gives 62^7, about 3.5 trillion codes; 100 million per year uses a vanishing fraction, so collisions are a non-issue if codes are random. Two sound options: (a) a random 7-character code, insert with a uniqueness constraint, retry on the rare collision; (b) a time-ordered 64-bit id (the Snowflake layout: timestamp, worker id, sequence) encoded in base 62, which yields 11 characters and is guessable in sequence. The answer takes (a): shorter, not enumerable, and the database does the uniqueness check it has to do anyway for custom aliases.

The core flow, step by step

Redirect, create and disable, in the order a request sees them.

  1. Redirect: look up the code in the cache; on a miss read a replica, fill the cache with a TTL plus jitter, and cache negative results for a short time so a storm of bad codes does not reach the database (the Builders' Library caching article covers negative caching).
  2. Emit a click event asynchronously: fire and forget onto a log; losing a fraction of events is accepted by the approximate-count requirement.
  3. Return 302 with Cache-Control: no-store so browsers and the CDN do not cache the hop.
  4. Create: validate the URL (scheme, block list), insert with the idempotency key, return the code.
  5. Disable: update state, delete the cache entry; replicas lag a little and the cache entry is gone, so the next read may serve a stale active link for the replica lag window; acceptable and stated.

Scaling and the bottleneck

Keeping redirects fast and available when the database is not

Redirects need the cache and the replicas, not the primary. Replicas in two zones, cache in two zones, the redirect service stateless behind a balancer (the SRE book's datacenter load balancing chapter). If the primary is down, creation fails and redirects continue: the availability target applies to redirects only, and the design makes that true by construction. The cache is not a source of truth: a cold cache after a restart means the replicas take the full read load for a while, so they are sized for it (3,200 reads per second at peak is well within one replica's reach on an indexed key lookup; the sizing is stated, not assumed).

Counting clicks without slowing redirects

The redirect path never writes to the database. Events go to a log (a partitioned log or a queue, the queues and streams lesson); an aggregator sums per code per minute and upserts daily counts. Duplicates from at-least-once delivery are tolerated because counts are approximate; if exactness were required, the event would carry a unique id and the aggregator would dedupe within a window. The hot link case (one code at 30,000 reads per second) is a cache hit, costs nothing on the database, and produces a hot partition in the log only if the partition key is the code; partition by a hash of code plus a random suffix for the aggregator's benefit.

Cost per billion redirects

A billion redirects is about five weeks of traffic at the stated scale (10 billion per year). The variable cost per redirect is small: one cache read, a response of a few hundred bytes and a click event of about 100 bytes (assumption), so a billion redirects move about 300 GB out and write about 100 GB of events. The cost is dominated by the fixed fleet, which is sized for the 3,200 per second peak whether or not the traffic arrives: at an assumed 2,000 dollars per month for the redirect nodes, the two cache nodes and the replicas (assumption, chosen to make the arithmetic concrete), the fixed cost is about 2,400 dollars per billion redirects, against tens of dollars of egress and event storage at an assumed 0.05 dollars per GB (assumption). The lever is therefore the peak-to-average ratio the fleet is sized for, not per-request efficiency, and the number falls as volume grows.

Failure modes and what degrades

Each row names the failure, what the user sees, and what the design does about it.

FailureEffectMitigation
Cache node downmisses go to replicastwo cache nodes, replicas sized for cold cache
Primary downno creation, redirects finereplicas serve reads; promote a replica; owners see a clear error
Replica lag after disablestale active for secondscache invalidation plus accepted lag; disabled links are rare
Code collisioninsert failsretry with a new random code (probability negligible)
Malicious targetsreputationalblock list at creation, re-scan on report, 410 on disable
Click log backlogcounts delayedcounts are approximate; alert on consumer lag

Trade-offs and the alternative not taken

The decisions a reviewer reads first, with the option the answer did not pick.

DecisionOptionsChosenWhy
Redirect status301 (cacheable) versus 302 (counted, changeable)302 with no-storecounts and ability to disable outweigh one saved round trip
Code schemerandom base-62 versus time-ordered idrandom 7-charshorter, not enumerable, uniqueness check needed anyway
Countingsynchronous increment versus async eventsasync events, approximatekeeps the redirect path read-only
Storageone relational primary versus sharded from day oneone primary, replicas250 GB in 5 years does not justify shards; sharding plan is written down

What changes at 10x

At a billion links per year

At a billion links per year the table grows 500 GB per year: partition by code hash across a few shards (the replication and partitioning lesson), keep the cache strategy, move old counts to cold storage. Multi-region readers get regional caches and read replicas; writes stay in one region because a link is created once and read everywhere (the geo distribution lesson). Custom domains add a host lookup before the code lookup.

Migrating the id scheme

The id scheme changes when the random 7-character space gets crowded by a billion links per year (62^7 is 3.5 trillion, so collisions are still rare, but the retry rate becomes measurable) or when a product need appears, such as codes that sort by creation time for the aggregator or a longer code for a separate namespace. Existing codes must keep resolving for their 5-year life, so the migration is additive, never a rewrite: the new scheme is distinguishable from the old by length or by a reserved first character, the redirect service resolves both (the lookup table does not change, since the code is the key either way), new links are issued in the new scheme behind a flag, and old codes are never touched. The risk is in clients and the CDN that assume a fixed code length, so the format rule is published and exercised with synthetic codes before the flag flips, and the flag flips back if the error rate moves. A time-ordered scheme (the Snowflake layout) brings the enumerability problem the answer avoided, so a migration to it also needs a per-link random component or an access check on the stats endpoint.

Self-check rubric

Read, not scored: find the level your answer reached.

L1, mid-level: applies

  • A correct API with 302 semantics, and a code scheme with the collision argument.
  • A cache in front of a database, with click counting off the hot path.
  • The storage estimate (50 GB per year, 250 GB over 5 years) derived from the stated assumptions.

L2, senior: chooses with numbers and defends

  • Redirects independent of the primary; negative caching and TTL jitter; replica lag after a disable stated, not hidden.
  • The hot-link case handled as a cache hit, with the log partition key chosen so one code does not make a hot partition.
  • The 10x sharding plan with a shard key, and custom alias uniqueness handled by the same constraint as random codes.

L3, staff: sets the constraint and judges

  • The question whether 301 is acceptable for some customers, and the product consequence of the answer.
  • Abuse and takedown as a design input (block list, re-scan, 410), and cost per billion redirects.
  • Multi-region read placement, and what the service must never do: log full URLs with tokens in query strings.

The 45-minute interview frame

  • 0:00 to 0:05 Requirements: ask the six clarifying questions above, state the non-goals, and say the numbers aloud: 3,200 redirects per second at peak, 32 writes per second at peak, 250 GB in 5 years, a 12 GB hot cache.
  • 0:05 to 0:10 Entities and API: the Link and ClickCount records, the four endpoints, and the 302 with no-store decision stated as a product decision you are making on purpose.
  • 0:10 to 0:20 High-level design with the container diagram: the read-only redirect path (edge, service, cache, replicas, click log) separate from the creation path (API, primary, invalidation). Explain the random 7-character code and why it beats a time-ordered id here.
  • 0:20 to 0:40 Two deep dives: availability of redirects when the primary or the cache is down (replicas in two zones, cold-cache sizing, the primary off the read path), then click counting without slowing redirects (async events, approximate counts, the hot-link partition key).
  • 0:40 to 0:45 Failure modes from the table, the 10x plan (code-hash sharding, regional caches, writes in one region), and the L3 sentence: the interesting decision is 302 versus 301, and it is a product decision.

The design-doc frame

  • Context and scope. Who creates links, who follows them, the retention promise (5 years) and the exact click-count expectation.
  • Goals and non-goals. Redirect latency and availability as the goals; creation availability explicitly lower; analytics, previews and fraud detection as non-goals.
  • Design. This answer fills it: the container diagram, the data model, the code scheme, the redirect and creation flows.
  • Alternatives considered. The code scheme (random versus time-ordered) and the counting method (synchronous versus asynchronous), with the trade-off table.
  • Cross-cutting concerns. Abuse (block list, takedown), privacy (never log full URLs with query-string tokens), observability (cache hit ratio, replica lag, click-log consumer lag), cost per billion redirects.
  • Review questions the doc must answer. What a user sees in the replica lag window after a disable, and how the replicas behave under a cold cache.

Depth notes

  • L1. A correct single-region design with an id scheme, a cache and redirect semantics.
  • L2. Sharded storage, hot-key handling, analytics without slowing redirects, cost.
  • L3. Abuse, custom domains, multi-region reads, migration of the id scheme.

Sources

  • Latency, throughput and back-of-envelope numbers sd-numbers planned
  • Storage engines and indexes sd-storage-engines planned
  • Replication and partitioning sd-replication-partitioning planned
  • Caching sd-caching planned
  • API design sd-api-design planned
  • Data modelling across stores sd-data-modelling planned