Designing TinyURL

A shortener does one trivial thing: it turns a long URL into a short code and sends anyone who visits the code back to the URL. That is a hash table with a web server in front, and you could write it in an afternoon. What makes it worth a whole article is the ratio: a hundred reads for every write, billions of rows that are never read again, and a redirect that has to answer in single-digit milliseconds from anywhere on earth. Every decision here follows from those three facts.

The map

Read this first when short on time. Every branch is a section below.

What it must do, and at what size

The method from the previous article starts with requirements, so here they are, stated as verbs and exclusions before anything is drawn.

It must accept a long URL and return a short one, redirect a short code to its target, let a caller choose a custom alias, let a link expire or be deleted, and report how many times a link was followed. It must not edit a link's target after creation, serve as a general redirect manager with rules and A/B splits, or guarantee that a short code is secret. Those exclusions matter: an editable target forces cache invalidation on every write and version numbers on every row, and it is the single largest simplification available here.

The promises are lopsided. A redirect is on the critical path of somebody else's page load, so it wants a p99 under about 50 ms including the network, from any continent, at four or five nines of availability. Creating a link is a background action a human waits on, so 200 ms is generous. And consistency is asymmetric too: a link that is a second late becoming visible is fine, but a code that resolves to the wrong target is never fine.

Writes   10M/day   -> 10M / 86,400  ~= 115/s    -> peak ~350/s
Reads     1B/day   -> 1B  / 86,400  ~= 11.6k/s  -> peak ~35k/s
Ratio    ~100 reads per write                   -> cache-first design

Row      code 7 B + URL ~400 B + metadata ~90 B ~= 500 B
Storage  500 B x 10M/day = 5 GB/day -> 1.8 TB/year -> ~5.5 TB replicated x3
5 years  ~18 billion links, ~9 TB before replication

Hot set  top ~1% of links serve ~90% of redirects
         180M links x ~200 B cached ~= 36 GB     -> one modest Redis cluster

Three conclusions fall out before any component is chosen. The write rate is trivial — 350 writes per second is one database. The read rate is not trivial but is cache-shaped, because the same small set of links is followed over and over. And the dataset is large but cold: eighteen billion rows of which a few hundred million are ever touched again, which means the store must be cheap per row and fast on a single-key lookup, and nothing else.

flowchart TD
  B["browser follows a short link"] --> E["edge and regional cache"]
  E --> RS["redirect service, stateless"]
  RS --> KV[["mapping store, sharded by code"]]
  RS --> CL[["click log"]]
  CL --> SA["stream aggregation"]
  SA --> AN[["analytics store"]]
  AP["API client creates a link"] --> CS["create service"]
  CS --> RG["range service, once per million codes"]
  CS --> KV
  AN --> SP["stats endpoint"]

The API and the data model

Write the API first, because it fixes the contract, and then list the queries, because they decide the store.

POST   /links        { url, alias?, expires_at? }   -> 201 { code, short_url }
                     header: Idempotency-Key: 7f3a
GET    /{code}                                      -> 302 Location: <long url>
GET    /links/{code}                                -> 200 { url, created_at, expires_at }
GET    /links/{code}/stats?from=&to=                -> 200 { total, by_day[] }
DELETE /links/{code}                                -> 204
GET    /links?cursor=                               -> 200 { items[], next_cursor }

Two details on the create call. The idempotency key stops a retried request from minting a second code for the same intent; without it, a client that times out and retries gets two links and reports the wrong one. And creation returns 201 with the code in the body rather than redirecting, because the caller is a program, not a browser.

Now the access patterns, written as sentences, in order of how often they happen:

1. Given a code, get the target URL. Eleven thousand times a second. This is the only query that matters for the architecture.
2. Given a user, list their links, newest first. Rare, paginated, and tolerant of a hundred milliseconds.
3. Given a code and a date range, get click counts. Rare, aggregate-shaped, and a completely different workload from the first two.

The first pattern is a pure key lookup with no joins, no ranges and no ordering, which is the definition of a key-value workload. The second is a range scan by owner, which is a secondary index. The third is an aggregation over events, which belongs in an analytical store entirely — as the analytics article argues, mixing it into the transactional store is how the redirect path gets slow.

links                              (partition key: code)
  code         string   7 chars, base62
  long_url     string   up to 2,048 bytes
  owner_id     string   null for anonymous links
  created_at   timestamp
  expires_at   timestamp | null      -- store TTL uses this
  alias        bool     true if user-chosen

links_by_owner                     (partition key: owner_id, sort: created_at desc)
  owner_id, created_at, code       -- a second table, not an index on the hot one

The row is immutable after creation, which is the property the whole design leans on. An immutable mapping can be cached forever, replicated to every region without conflict resolution, and served from a stale replica without being wrong. That one decision, taken in the requirements, is worth more than any optimisation later.

Generating the short code

The code is the product, so it is worth being precise about it. It should be short, URL-safe, unambiguous to read aloud, and impossible to collide.

Base62 — 0-9a-zA-Z — is the standard alphabet: it is URL-safe without escaping and denser than hex. The length follows from the keyspace:

Seven is the answer, and the reason six is wrong is subtler than exhaustion: long before a keyspace is full, random generation into it starts colliding, because by the birthday bound collisions become common at around the square root of the space. Six characters means collisions at a few hundred thousand links, which is nothing.

Now, where does the number behind the code come from? Four approaches, and the trade is always coordination against collisions.

flowchart TD
  S["need a new code"] --> Q{Coordination allowed?}
  Q -- no --> H["hash the URL, take 7 chars"]
  H --> C{Collision?}
  C -- yes --> H2["rehash with a salt"]
  C -- no --> D["write the row"]
  Q -- yes --> R["claim a range of 1,000,000 ids"]
  R --> L["encode the next id in base62"]
  L --> D

Counter ranges win on simplicity, and the gaps left by dying instances are irrelevant against a trillion-code space. The one thing they do badly is hide the sequence: 000001A, 000001B, 000001C is an invitation to walk the entire dataset. Fix it by scrambling the id before encoding, with a reversible permutation such as multiplying by a large odd constant modulo 62⁷ and taking the result, or by XOR-folding a per-range secret into it. The codes stay unique and collision-free, but consecutive ids land far apart.

sequenceDiagram
  autonumber
  participant C as Client
  participant A as API instance
  participant Z as Range service
  participant D as Store
  C->>A: POST /links, url and Idempotency-Key 7f3a
  A->>D: has key 7f3a been seen?
  D-->>A: no
  Note over A: local block 41,000,000 to 41,999,999 has ids left
  A->>A: take next id, scramble, encode as base62
  A->>D: conditional put, code must not exist
  D-->>A: created
  A-->>C: 201 with the short URL
  Note over A,Z: when the block empties, claim the next one from the range service

Custom aliases live in the same keyspace and break its tidiness: they are user-chosen, must be unique, and must never collide with a generated code. Two rules keep it manageable. Require aliases to be at least eight characters or to contain a character the generator never emits, so the two spaces cannot overlap. And take the uniqueness check as a conditional write on the same table, so two people racing for the same alias resolve at the store rather than in application code.

Base62

Positional encoding over 0-9a-zA-Z. Seven characters address 3.52 trillion values in a URL-safe form with no escaping.

Birthday bound

Random values start colliding at roughly the square root of the keyspace, which is why a keyspace must be far larger than the number of items you expect.

Range allocation

Handing a server a block of ids it may use without further coordination. Trades id gaps for the removal of a bottleneck.

Storing the mapping

The store has to do one thing well — return a 500-byte row given a 7-character key — at eleven thousand reads a second, over several terabytes, cheaply.

Sharding is by hash of the code, which is already uniformly distributed, so there is no hot-shard problem and no skew to engineer around — a rare luxury that exists only because the key is generated rather than natural. Replication factor three, with reads allowed from any replica: the row is immutable, so a replica that is a second behind cannot return a wrong answer, only a not-found for a link created moments ago. That is worth a sentence in the design, because it is the reason this system can be eventually consistent without being incorrect.

The read path: where the system actually lives

Ninety-nine percent of the traffic is one request: GET /{code}, answered with a redirect. Everything about serving it is about not touching the store.

flowchart TD
  U["browser follows the short link"] --> E["edge point of presence"]
  E --> W["redirect worker, stateless"]
  W --> C["regional cache: code to URL"]
  C -- "hit, about 98%" --> R["302 to the target"]
  C -- "miss" --> K[["key-value store, sharded by code"]]
  K --> F["fill the cache, then redirect"]
  W --> Q[["click event to a log"]]

The cache is the whole trick, and it works because link popularity is Zipfian: a tiny fraction of links carry most traffic, and a link that has just been clicked is overwhelmingly likely to be clicked again. From the sizing above, caching the top one percent — 180 million entries at about 200 bytes of key, value and overhead — is roughly 36 GB, which is a handful of cache nodes and answers around 98 percent of requests. Doubling the cache buys perhaps one more point of hit rate; this is the shape of every Zipfian cache, and it is why the right size is found by measurement rather than by ambition.

Two mechanics matter more than the size. Negative caching: a code that does not exist must also be cached, briefly, or a scanning attacker turns every probe into a store read — the cheapest possible denial of service. And request coalescing: when a link goes viral, thousands of requests miss the cache in the same millisecond and all go to the store for the same key; the worker should let one through and have the others wait on its result.

The redirect status code is a product decision disguised as a technical one:

Since clicks are usually the product, 302 with an explicit short Cache-Control: private, max-age=0 is the answer. If analytics are not needed, 301 makes the system an order of magnitude cheaper, which is worth saying out loud rather than treating the choice as obvious.

Counting clicks without slowing the redirect

The one rule is that nothing on the analytics path may block the redirect. A counter incremented inline puts a write on the hot path for every read, turns the hottest links into the hottest write keys, and makes the redirect's availability depend on the analytics store.

flowchart TD
  W["redirect worker"] -->|"fire and forget"| L[["click log, partitioned by code"]]
  L --> S["stream job, one-minute windows"]
  S --> A[["per code per day counters"]]
  S --> H[["HyperLogLog sketch per code"]]
  A --> D["stats API and dashboard"]
  H --> D

The volume is real: a billion events a day at roughly 200 bytes each is about 200 GB of raw events a day. Three things keep that affordable. Aggregate early — a stream job rolls events into per-code per-day counters, and a billion events become a few tens of millions of counter updates. Sketch the expensive questions — unique visitors per link is a distinct-count, which is enormous to compute exactly and nearly free with a HyperLogLog sketch at about two percent error and twelve kilobytes per link. Expire the raw tier — keep raw events for a week for debugging and the aggregates forever.

Because the pipeline is at-least-once, an occasional duplicate click is counted twice. For a metric that exists to show a trend, that is the right trade against the cost of exactly-once counting; the messaging article covers why that cost is what it is.

Expiry, deletion and the cache that remembers

Links expire, get deleted, or are taken down for abuse. Each is easy in the store and awkward in the cache, and the awkwardness is the whole of this section.

In the store, expiry is a TTL on the row, which DynamoDB and Cassandra both reclaim in the background, and deletion is a tombstone that a later compaction removes. Neither costs anything on the read path. The problem is the copy of the row sitting in a cache in another continent, which knows nothing about either.

stateDiagram-v2
  [*] --> Active: created
  Active --> Expired: expires_at passes
  Active --> Deleted: owner deletes
  Active --> Blocked: abuse report upheld
  Expired --> [*]: reclaimed by TTL
  Deleted --> [*]: tombstone compacted
  Blocked --> Active: appeal upheld

Three rules handle it. Give every cache entry a TTL, five to fifteen minutes, so the worst-case staleness is bounded even when an invalidation is lost — this is the safety net that makes the other two optional rather than critical. Publish invalidations on a topic that every cache tier subscribes to, so the common case is fast. And never reuse a code: an expired or deleted code is retired permanently, because handing it to a new link means the millions of places the old link was posted now point somewhere unexpected. The keyspace is large enough that retiring codes forever costs nothing.

When a code is gone, the answer is 404 or 410 with a page explaining it, not a redirect to a homepage. A wrong redirect is the one failure mode this system must never have.

Abuse: the part that is not about scale

A shortener hides the destination, which makes it useful for sharing and equally useful for phishing. Any design that ignores this is incomplete, because in practice abuse handling is most of the operational work.

On creation, check the target against a reputation service and a local block list, reject known-bad domains, and rate limit creation per account and per IP so a campaign cannot mint a hundred thousand links in an hour. Checking synchronously adds latency to a path that can afford it; the alternative is to accept the link and scan asynchronously, disabling it within seconds if it fails.

On redirect, re-check the target against the block list, because a domain that was clean at creation may be compromised a month later — this is why the block list is consulted at read time and not only at write time. For a target that has been flagged since, serve an interstitial warning rather than the redirect.

Against enumeration, the defence is the keyspace plus negative caching plus rate limiting per client on misses. A scanner is easy to spot because its miss rate is near 100 percent while a normal client's is near zero, which makes miss rate a better throttling signal than request rate — the reliability article covers the mechanics of the limiter itself.

Going global

Redirect latency is dominated by distance, so the service has to run near the user. The immutability of the mapping is what makes that easy.

Reads are trivial to distribute: an anycast address puts the user on the nearest point of presence, each region holds its own cache, and a miss falls back to a regional replica of the store. Because a row never changes after creation, a replica that is seconds behind can only be missing a very new link, never wrong about an old one — so cross-region replication can be asynchronous, which is what keeps it cheap and fast.

Writes are the part that needs a decision. Two workable answers: route every create to a single home region, accepting a hundred milliseconds of extra latency on a call that can afford it; or accept writes anywhere with a globally replicated store, which is fine for generated codes because ranges guarantee uniqueness without coordination. Custom aliases are the exception in both cases, since two regions can accept the same alias simultaneously — those need either the home region or a conditional write against a globally consistent store.

flowchart TD
  U["user in Frankfurt"] --> A["anycast, nearest point of presence"]
  A --> EC["EU cache"]
  EC -- "miss" --> ER["EU replica of the store"]
  ER -- "not found, very new link" --> HR["home region store"]
  W["create request"] --> HW["home region write"]
  HW --> ER
  HW --> AR["US and APAC replicas"]

When a region loses its store entirely, the right behaviour is to keep serving from cache and fail only on misses. A stale-but-correct redirect is strictly better than an error here, which is an explicit choice of availability over consistency — the correct one for this system, and the wrong one for a payment system.

What breaks first

The design is finished when the ladder of bottlenecks is known and the next rung is planned.

1. Cache memory. The first thing to run out. As the corpus grows, the hot set grows with it and the hit rate slides, which shows up as store load rather than as user-visible latency. Watch hit rate, not memory used.
2. Store read throughput. Once the hit rate slips, the store takes the difference — a drop from 98 to 95 percent hit rate more than doubles its load. Adding shards is the answer, and it is easy because the key is uniformly distributed.
3. The click pipeline. A billion events a day grows linearly with redirects and has none of the cache's leverage. It scales by adding partitions and consumers, and its lag is the metric to alert on.
4. The range service. Almost never: it is touched once per million codes. It is on the list only because it is the one component whose failure stops creation entirely, so it needs a replicated store and a large enough block size that a brief outage is invisible.

At ten times the traffic — ten billion redirects a day — the shape does not change. More edge locations rather than more origin capacity, more cache nodes with a smaller share of the keyspace each, more store shards, more click-log partitions. Nothing in this design has a step change in it, which is the real test of whether the shape was right.

Recap