Dinesh/ Blog
systems

Designing for Scale · URL Shortener

Identifier probability and redirect policy. A source-bounded lesson with worked reasoning, failure analysis and explicit runtime limitations.

9 min read
Checking device speech…
Lesson preparation & details

Level: advanced

Designing for scale · Lesson 4 of 20 ↗
Loading this browser’s progress…

By the end, you should be able to

  • Identifier probability and redirect policy
  • A malicious link is disabled at the database but still cached in browsers. What requirement was missing?

Bring with you

Sources checked: . A source check does not change the publication or update date.

Editorial review: · What review means

In this article · 12 sections

The problem this post solves

A shortener creates an alias for a destination and later redirects a caller using that alias. Define creation authorization, custom aliases, expiry, editing, abuse takedown, analytics and retention before calling every mapping immutable. A 10,000-requests/s workload does not by itself prove a single database inadequate; request cost, working set, replication and latency targets must be measured.

The central write invariant is one authoritative mapping per alias under the intended namespace. Retries of one creation request also need a defined identity so a client timeout does not create an unintended second alias. The read path needs a cache/revocation contract, not just “redirect as fast as possible.” These two requirements drive different mechanisms.

First principles

Base62 is an encoding, not a uniqueness algorithm. Choosing a random code creates a probability of collision; allocating a unique integer and encoding it preserves uniqueness only under the allocator's assumptions. For a namespace of size M and n independent uniform draws, the probability of at least one collision is approximately 1 - exp(-n(n-1)/(2M)) when the usual birthday approximation is appropriate. The chance the next draw collides with m occupied codes is m/M; these are different questions.

An atomic unique insert handles a collision without a separate read-before-write race. On conflict, compare the existing mapping or generate another candidate under a bounded policy. A preliminary SELECT followed by INSERT is not sufficient under concurrency. Randomness is not intrinsically too slow, and a central sequence is not intrinsically a bottleneck at every scale. Measure before adding a distributed allocator.

Capacity and constraints

Use a 30-day month for this scenario. One hundred million creations/month average about 38.58/s; ten billion redirects/month average about 3,858/s, a 100:1 ratio. Specify peak/skew separately. Seven Base62 characters yield exactly 62^7 = 3,521,614,606,208 possible strings. At 1.2 billion unique creations/year that is about 2,935 years of nominal sequential capacity, ignoring reserved values, abandoned ranges and policy changes. Capacity is not the same as collision probability for random draws.

For eight characters, 62^8 = 218,340,105,584,896. One million independent random draws have about a 0.229% chance of at least one collision by the birthday approximation. The next draw into one million occupied slots has collision probability only about 4.58e-9 under the uniform model. A uniqueness check and retry policy are still necessary. None of these figures proves a particular generator, entropy source or database throughput.

Architecture

The Read Path

The Read Path
Figure text equivalent — labels and relationships
  • Node “Client GET alias” (square).
  • Node “Edge policy and optional redirect cache” (square).
  • Node “Resolver with current expiry and abuse policy” (square).
  • Node “Bounded mapping cache” (square).
  • Node “Authoritative alias mapping” (cylinder).
  • Node “Location plus explicit cache policy” (square).
  • “Client GET alias” leads to “Edge policy and optional redirect cache”. Line: normal; ends: arrow point.
  • “Edge policy and optional redirect cache” leads to “Resolver with current expiry and abuse policy”. Line: normal; ends: arrow point.
  • “Resolver with current expiry and abuse policy” leads to “Bounded mapping cache”. Line: normal; ends: arrow point.
  • “Bounded mapping cache” leads to “Authoritative alias mapping”. Line: normal; ends: arrow point.
  • “Authoritative alias mapping” leads to “Bounded mapping cache”. Line: normal; ends: arrow point.
  • “Resolver with current expiry and abuse policy” leads to “Location plus explicit cache policy”. Line: normal; ends: arrow point.
  • “Location plus explicit cache policy” leads to “Client GET alias”. Line: normal; ends: arrow point.

On a miss, read the authoritative mapping, verify validity/expiry and populate a cache entry with the relevant version and bounded lifetime. A cache hit still costs lookup/network work; it is not instant. Coalesce concurrent misses for a hot alias, limit concurrent origin reads and bound response time. Edits and takedowns require an invalidation/expiry strategy that covers each cache layer. A redirect already cached in a browser may bypass later origin checks.

Redirect status and caching are related but distinct. RFC 9110 defines 301/308 as permanent and 302/307 as temporary redirects. 307/308 preserve the request method; 301/302 permit historical POST-to-GET behavior. A simple GET-only shortener can reject unsupported methods explicitly. RFC 9111 makes cacheability depend on status and response/request directives: a 302 can be cacheable with appropriate explicit policy, so it does not force every click through the origin. 301/308 may be heuristically cacheable, but “every browser will always cache” is also too strong.

Choose freshness and permanence from the revocation requirement, then select Cache-Control and status accordingly. Origin logs cannot count requests that never reached the origin. Even no-store cannot establish “every human click counted” because clients can block requests, fail, prefetch or be bots. Define what analytics measures—resolver requests, edge requests, or a downstream action—and label its limits.

The Write Path: Generating the Identifier

Hash and truncate: deterministic hashing can nominate the same alias for the same chosen canonical input, but truncation can collide across different inputs. URL normalization is a product policy: case-sensitive paths or semantically significant query parameters must not be merged casually. A collision strategy might salt and retry or ask for a different custom alias. A cryptographic hash's properties do not survive arbitrary shortening as collision-free uniqueness, and a read-before-every-write is not required when the sink enforces uniqueness.

Database sequence: allocate an integer and encode it. With alphabet 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, integer 1000 encodes as g8 because 1000 = 16 × 62 + 8; a different alphabet changes the text. Sequences may have gaps, which usually do not matter for aliases. Benchmark contention and failover rather than assuming one counter must fail at forty writes per second. Sequential aliases are enumerable and are not an authorization secret.

Random code: use an appropriate random source, insert atomically, and retry on a true alias conflict. Scope identity and compare payloads. Do not catch every database error as “collision”: unavailability or invalid input needs a different response. A random-looking URL still needs access control if the destination/mapping is intended to be private.

Preallocated ranges: a durable allocator reserves disjoint half-open ranges such as [1,000,000, 2,000,000) and [2,000,000, 3,000,000). Half-open boundaries avoid assigning the shared endpoint twice. An API process allocates locally from its owned range and requests another block when needed. The coordinator is used less often, not eliminated; allocation retries, persistence and restore must never accidentally reuse a block.

The Scaled Architecture

The Scaled Architecture
Figure text equivalent — labels and relationships
  • Node “Create request with stable operation ID” (square).
  • Node “API worker” (square).
  • Node “Local unused portion of owned range” (square).
  • Node “Durable disjoint range allocator” (square).
  • Node “Atomic unique alias insert” (square).
  • Node “Mapping and creation identity” (cylinder).
  • Node “Conflict or retry reconciliation” (square).
  • “Create request with stable operation ID” leads to “API worker”. Line: normal; ends: arrow point.
  • “API worker” leads to “Local unused portion of owned range”. Line: normal; ends: arrow point.
  • “Local unused portion of owned range” leads to “Durable disjoint range allocator”: Refill when needed. Line: dotted; ends: arrow point.
  • “API worker” leads to “Atomic unique alias insert”. Line: normal; ends: arrow point.
  • “Atomic unique alias insert” leads to “Mapping and creation identity”. Line: normal; ends: arrow point.
  • “Atomic unique alias insert” leads to “Conflict or retry reconciliation”. Line: normal; ends: arrow point.

Wasting an unused tail after a process crash can be safer than reclaiming a range that an old owner might still use. Restoring the allocator from an old backup while newer aliases exist can repeat IDs; a correct restore procedure must preserve allocation history or fence/reconcile before resuming. With block size 10,000, allocation traffic is roughly one request per 10,000 successful local IDs in the idealized case, plus retry/refill overhead. This does not remove mapping-store writes, all contention or coordination-service outages.

Keep a final uniqueness constraint even with ranges as a defense against allocator bugs and custom aliases sharing the namespace. Return the committed creation result for a retry of the same operation identity. “Collision impossible” is conditional on disjoint durable allocation, correct encoding and no reuse; it is not an unconditional consequence of naming ZooKeeper.

Runnable collision-boundary fixture

This standard-library SQLite example uses deterministic candidates so the collision case is reproducible. It is not a production generator or a concurrent-service benchmark. The existing alias remains unchanged; the retry inserts a different candidate without a preliminary lookup.

import sqlite3
 
con = sqlite3.connect(":memory:")
try:
    con.execute("CREATE TABLE aliases (code TEXT PRIMARY KEY NOT NULL, destination TEXT NOT NULL)")
    con.execute("INSERT INTO aliases VALUES (?, ?)", ("abc", "https://example.com/old"))
    con.commit()
    chosen = None
    for candidate in ["abc", "abd"]:
        with con:
            cursor = con.execute(
                "INSERT INTO aliases VALUES (?, ?) ON CONFLICT(code) DO NOTHING",
                (candidate, "https://example.com/new"),
            )
        if cursor.rowcount == 1:
            chosen = candidate
            break
    assert chosen == "abd"
    assert con.execute("SELECT destination FROM aliases WHERE code=?", ("abc",)).fetchone()[0] == "https://example.com/old"
    assert con.execute("SELECT COUNT(*) FROM aliases").fetchone()[0] == 2
    print("conflict retained abc; accepted abd")
finally:
    con.close()

Failure modes

Random invalid-code scans: a short negative-cache TTL helps repeated misses for the same alias. An attacker generating distinct codes can still cause cache/origin work and fill a negative cache. Bound its admission/size, validate code syntax early, rate-limit appropriately and protect origin concurrency. Caching 404s alone is not complete denial-of-service protection.

A negative cache hides a new alias: invalidate the negative entry on successful creation or choose a bounded staleness policy. Otherwise a creation succeeds but immediate lookup can still return the earlier absence.

A takedown reaches only the database: stale CDN or browser redirects may continue sending users to the destination. Define revocation time and cache lifetimes before choosing permanent redirects; a safety interstitial or short-lived resolution may be justified by the abuse model.

Arbitrary destination schemes: validate and allow the intended destination schemes, enforce creation/abuse controls, and avoid turning preview/fetch functionality into unrestricted server- side requests. Merely storing a URL is different from fetching it from inside a private network.

Worked recovery exercise

An allocator hands worker A range [100,200). A uses 100 through 129, becomes unreachable, and a replacement starts. Is assigning [130,200) to the replacement safe? What if A later recovers?

Do not mistake silence for relinquished ownership

Not without a protocol proving the old owner cannot use that tail. A may resume and issue 130 at the same time. Reserve a new disjoint range, or use a properly fenced reclaim protocol and sink checks. Gaps are usually acceptable for aliases; duplicated mappings are not. Separately, a restored allocator must know every block already issued before accepting new allocations. The final unique insert rejects a duplicate but cannot by itself recover the intended owner or provide an acceptable user-visible retry policy.

What to carry forward

Distinguish namespace size, per-attempt collision probability, birthday probability and durable uniqueness. Choose caching from revocation and semantics rather than equating 302 with complete analytics. Ranges trade coordinator frequency for ownership/recovery responsibilities. The local SQLite collision test proves only its exact insertion behavior, not distributed allocation.

Sources and review boundary

Checked 2026-10-07: RFC 9110 (June 2022) for redirect status/method semantics; RFC 9111 (June 2022) for cacheability and freshness; PostgreSQL 16 constraints for uniqueness; and SQLite UPSERT documentation for explicit conflict-target behavior (access-dated). Namespace, probability and block-boundary calculations are independently checked teaching arithmetic. No HTTP server, CDN, random entropy source or distributed range allocator was deployed or benchmarked.

Pause / Recall / Apply

Can you explain it without the page?

Close the example. Reconstruct the core idea, then change one assumption. Mark complete when you’re ready; you can always undo it.

Stored in this browser only. No account, no sync. Clearing browser data removes your record.