URL Shortener: Deep Dives

Level: Mid-level

The ID must have two properties: global uniqueness (no two URLs share a code) and shortness (compact enough to be useful as a short URL). These properties are in tension — longer IDs are easier to make unique; shorter IDs risk collisions.

The fundamental approach: generate a unique integer, then encode it into a compact string. Let's evaluate the integer generation options:

Option 1: Hash Functions (MD5 / SHA-256)

Hash the original URL to produce a fixed-length digest, then truncate to the desired length.

Problem: Truncation dramatically increases collision probability. Even with collision detection and retry logic, the write path becomes: hash → check DB → collision? → re-hash with salt → check again. Under load, this creates hot-path database reads on every write.

Collision Math: Birthday Paradox

The birthday paradox tells us collisions appear much sooner than expected. For a hash space of size N, the probability of at least one collision after k insertions is approximately:

$P(\text{collision}) \approx 1 - e^{-k^2 / 2N}$

For 6 hex characters (N = 16⁶ = 16,777,216):

• After 1,000 URLs: P ≈ 3%
• After 4,800 URLs: P ≈ 50%
• After 10,000 URLs: P ≈ 95%

For 6 Base62 characters (N = 62⁶ = 56,800,235,584):

• After 100,000 URLs: P ≈ 8%
• After 280,000 URLs: P ≈ 50%
• After 1,000,000 URLs: P ≈ 99.98%

Even with the larger Base62 space, a collision becomes more likely than not after about 280,000 URLs — under 7 hours of traffic at 1M new URLs per day. Hash-based IDs need collision detection from day one.

Option 2: UUID (v4 Random / v1 Timestamp)

Problem: 36 characters defeats the purpose of URL shortening. Even Base62-encoding a UUIDv4 produces ~22 characters. UUIDs solve uniqueness but fail the shortness requirement.

Option 3: Snowflake IDs (Twitter-style)

Structure: [timestamp: 41 bits][machine_id: 10 bits][sequence: 12 bits] = 64-bit integer.

Problem: Base62 encoding of a 64-bit integer produces ~11 characters. Still too long for a "short" URL. We could truncate, but that reintroduces collision risk.

Option 4: Machine ID + Sequence Number (Recommended)

Assign each server a unique 1-character prefix. Each server maintains an auto-incrementing counter. The ID is: MachinePrefix + SequenceNumber.

With 1 character for machine ID (62 options using Base62) and 5 characters for sequence (62⁵ = 916M per machine):

Advantages over alternatives:

The Machine ID + Sequence approach produces the shortest IDs with guaranteed uniqueness and no runtime coordination between servers. The only coordination point is machine ID assignment — a one-time setup operation when adding servers.

Handling Server Restarts and Sequence Recovery

If a server crashes and restarts, it must not reuse sequence numbers. Three approaches:

1. Persistent checkpoint (recommended): Write the current sequence to disk every N IDs (e.g., every 1,000). On restart, resume from the last checkpoint + 1,000 (skip the gap to avoid any overlap).

2. Database-backed sequence: Use a database counter (SELECT last_seq FROM sequences WHERE machine_id = 'A' FOR UPDATE). Reliable but adds a DB call to every write.

3. Time-based offset: On restart, set the sequence to (seconds since the service launched) × (the machine's maximum ID rate). As long as the machine never issues IDs faster than that rate, this is always past every ID already issued. It needs no persistent state, but it burns ID space quickly, so it only suits machines with a low maximum rate.

The checkpoint approach balances reliability with performance — you lose at most 1,000 IDs per crash (0.0001% of the per-machine capacity of 916M).

Pre-generating IDs in Bulk

Under sudden traffic spikes, generating IDs on-demand could introduce latency if the sequence checkpoint or encoding becomes a bottleneck. Pre-generating a batch of IDs eliminates this concern:

Trade-off: Pre-generation wastes IDs if the server crashes before using all buffered IDs. With a 10K buffer and 916M capacity per machine, this waste is negligible (0.001%).

Level: Mid-level

After generating a unique integer, we need to encode it into a compact, human-readable string. The encoding must balance shortness with usability — avoiding characters that are confusing to type or problematic in URLs.

Encoding Options Comparison

Why Base62?

Base62 is the optimal choice because:

1. No special characters — Base64's / splits a URL path, and + and = are often rewritten by encoders, so all three end up percent-encoded (%2F, %2B, %3D), defeating the purpose of shortening. URL-safe Base64 swaps them for - and _, but those are easy to lose when a link is underlined or wrapped at a line end, so shorteners usually stick to letters and digits
2. 6 characters suffice — 62⁶ = 56.8B provides 30× headroom over our 5-year requirement
3. Human-friendly — All characters are easily typeable on any keyboard
4. Case-sensitive by definition — URLs are case-sensitive after the domain, so a1B2c3 and A1b2C3 are different short codes

Why Not Base58? (Bitcoin's Choice)

Base58 removes visually ambiguous characters: 0 (zero) vs O (letter O), I (uppercase i) vs l (lowercase L). This is valuable for Bitcoin addresses that are manually transcribed.

For URLs, visual ambiguity matters less — users click links, they don't type them. The extra 4 characters (0, O, I, l) give us Base62's larger space (56.8B vs 38B for same length), reducing the likelihood of needing 7-character codes.

When to choose Base58: If your short URLs appear on billboards, business cards, or physical media where humans must type them. When to choose Base62: If URLs are primarily shared digitally (links, messages, emails).

Level: Senior

Request handlers are stateless HTTP servers — scaling them is trivial (add more instances behind the load balancer). The interesting scaling challenges are in the ID generator and the database.

Scaling the ID Generator

Each ID generator uses 1 character for machine ID, giving us 62 possible machines. Each machine generates up to 916M IDs. But how do we route requests to them?

Load balancing strategies:

• Random selection: Each request handler picks a random ID generator. Simplest, good load distribution.
• Least-loaded: Pick the generator with the shortest queue. Better under skewed load.
• Sticky routing: Route by client ID. Unnecessary (any generator works for any request).

Sharding the Database

At our estimates (12 writes/sec, about 1 TB over five years), one PostgreSQL primary with read replicas is enough: the cache absorbs most reads, and the writes are light. Sharding becomes necessary when the data or the write rate outgrows one primary, for example at 100× today's volume. When that happens, this design already has a natural shard key: the machine ID prefix in each short code serves double duty as the shard key. Each machine writes to its own database shard — the write paths are completely independent.

Shard key = Machine ID prefix in the short code.

When the machine with prefix a generates code a1B2c3, it writes to shard a. When the machine with prefix B generates B7x9pQ, it writes to shard B. No cross-shard coordination is needed for writes.

Write path: Completely parallel. Each machine writes to its own shard. No coordination, no locking, no cross-shard transactions. Adding a new machine = adding a new shard. Existing shards are unaffected.

Read path: On a cache miss, the redirect handler extracts the first character of the short code and routes to the correct shard. For example, a1B2c3 → shard a.

Why This Sharding Strategy Works

Scaling Request Handlers and ID Generators Independently

Should request handlers and ID generators be 1:1? No — they have different scaling profiles:

Request handlers are I/O-bound: handling HTTP connections, checking cache, holding sockets open. They need many instances for concurrency — often 10-50 instances for high traffic.

ID generators are CPU/IO-bound: generating IDs and writing to disk/DB. Each generator can handle thousands of IDs per second. At 12 QPS average, even a single generator has enormous headroom.

Typical ratio: 10-20 request handlers per ID generator.

Routing: Request handlers pick an ID generator using round-robin or least-loaded selection. Since any generator can serve any request, the routing doesn't need to be sticky.

Database Choice: DynamoDB vs Cassandra vs PostgreSQL

Recommended for this design: PostgreSQL. The tables, queries and replication in this lesson are PostgreSQL: one primary with read replicas carries today's load, and sharding by the code's prefix is the path when one primary is outgrown. DynamoDB is the strongest alternative for AWS teams that want no database operations: the access pattern (a key-value lookup by short code) fits it well, and it partitions data automatically, so no manual sharding is needed.

DynamoDB schema (the alternative):

Table: url_mappings
  Partition Key: short_code (String)
  Attributes: original_url (String), created_at (Number), is_active (Boolean)
  Read Capacity: On-demand (auto-scales)
  Write Capacity: On-demand

Level: Senior

Caching is the single most impactful design decision for a URL shortener. With a 100:1 read-write ratio, the difference between an 80% and a 95% cache hit rate is 20% vs 5% of redirects reaching the database: four times the database load.

Traffic Distribution: Zipf's Law

URL access follows a Zipfian distribution — a small fraction of URLs receive the vast majority of clicks. A typical shape:

• Top 1% of URLs → ~50% of all clicks
• Top 10% of URLs → ~90% of all clicks
• Bottom 50% of URLs → ~1% of clicks (many are clicked only once)

This is excellent for caching: a small cache capturing the top URLs handles most traffic.

Cache Sizing

At 1 GB (easily fits in a single Redis instance), we achieve ~93% hit rate, leaving only ~80 QPS hitting the database. This is well within a single database node's capacity.

Caching Strategies Compared

Recommended: Read-through + Write-through hybrid.

• Write path: When a new URL is created, write to both DB and cache (write-through). This ensures newly created URLs are immediately resolvable without a cache miss.
• Read path: On redirect, read from cache. On miss, the cache auto-fetches from DB (read-through).

Cache Stampede and Thundering Herd Prevention

Cache stampede: A popular URL's cache entry expires. 1,000 concurrent requests all experience a cache miss simultaneously. All 1,000 hit the database for the same URL. The database is overwhelmed.

Solution: Request coalescing (singleflight pattern)

With coalescing, 1,000 concurrent requests for the same expired key result in 1 database query instead of 1,000. The first request fetches from DB; the other 999 wait on the same Future.

Stale-while-revalidate: An alternative approach: serve the stale cached value immediately while refreshing in the background. This provides zero-latency cache misses at the cost of serving slightly stale data (acceptable for URL mappings that never change).

Multi-Tier Caching

For extreme scale (10B+ redirects/day), add a local in-process cache layer:

Tier 1: In-process LRU cache (each Redirect Handler instance)

• Size: 100 MB per instance (~200K URLs)
• Latency: < 0.1 ms (no network call)
• Hit rate: ~60% (top URLs accessed by this specific instance)

Tier 2: Redis cluster (shared)

• Size: 1-5 GB
• Latency: ~1 ms
• Hit rate: ~33% of all requests (93% cumulative with Tier 1)

Tier 3: Database

• Latency: ~5-10 ms
• Only ~7% of requests reach this tier

Level: Mid-level

The redirect status code determines browser behavior, caching semantics, and analytics accuracy. This seemingly small decision has significant downstream consequences.

Impact Analysis

When to Use Each

Use 302 (recommended for most URL shorteners):

• You need click analytics (the primary business model for many shorteners)
• You need ability to deactivate malicious URLs
• You want to A/B test destination URLs
• The redirect is for external/marketing links

Use 301 for specific cases:

• Internal tool links where analytics don't matter
• Links embedded in documentation that will never change
• When minimizing server load is critical and analytics are unnecessary

Hybrid Approach

A middle ground: use 302 with a Cache-Control header that allows short-term browser caching:

HTTP/1.1 302 Found
Location: https://example.com/destination
Cache-Control: private, max-age=300

This tells the browser: "Reuse this redirect for 5 minutes, then check back with us." Repeat clicks inside that window never reach the server, so you count at most one click per user per 5 minutes, and a deactivated link keeps working for that user until the cached copy expires. The longer the max-age, the bigger both effects: at max-age=86400, you count at most one click per user per day.

Level: Senior

URL shorteners are prime targets for abuse. Attackers use them to disguise phishing URLs, distribute malware, and bypass email security filters. If security vendors blocklist your domain, legitimate users lose access — a business-critical failure.

Defense Layers

Layer 1: Pre-creation scanning (synchronous)

Before storing a URL, check it against known malicious URL databases:

Layer 2: Post-creation batch scanning (asynchronous)

URLs can become malicious after creation (e.g., destination changes, new threat intelligence). A background scanner rechecks URLs periodically:

Layer 3: Enumeration prevention

Short codes like a00001, a00002, a00003 are sequential and predictable. An attacker can enumerate all URLs by incrementing the code. Mitigations:

• Randomize sequence within machine: Instead of strictly incrementing, use a permutation function that maps sequential integers to non-sequential outputs
• Rate limit redirect requests: Detect enumeration patterns (sequential codes from same IP)
• Don't expose creation-order information: Ensure short codes don't reveal when they were created

URL Deactivation and Takedown Process

When a malicious URL is detected:

1. Immediate: Set is_active = FALSE in the database
2. Cache invalidation: In every region's Redis, delete the cache entry (DEL url:{short_code}) and set a permanent block marker; tell every Redirect Handler to drop the link from its in-process cache (a pub/sub message)
3. Redirect behavior change: Return 410 Gone with a warning page instead of redirecting
4. Notification: Alert the URL creator (if authenticated) and the reporter (if user-reported)

The block holds even when caches are rebuilt: every database lookup reads only active rows (WHERE short_code = %s AND is_active), so a cold cache cannot bring a deactivated link back.

Time to deactivation target: < 5 minutes from detection to global cache purge. This limits the exposure window for phishing campaigns.

Level: Senior

A user in California creates a short URL. Seconds later, someone in Tokyo clicks it. The URL must resolve globally with minimal latency. This requires multi-region deployment with careful consistency trade-offs.

The Consistency Challenge

A newly created URL must be globally resolvable within seconds. But cross-region replication takes 100-300 ms. During this window, a request to the AP-EAST region returns 404 for a URL that exists in US-WEST.

Solution: Read-after-write consistency for creators

The creator's region has the URL immediately in cache. Other regions receive it within 300 ms via replication. For the rare case where someone clicks a URL within 300 ms of creation from a different region:

Fallback: Cross-region read on miss

The cross-region fallback adds 100-200 ms. For real links it triggers only in the first ~300 ms after creation, before the link reaches the local replica. But every code that does not exist at all — typos, bots, enumeration attempts — also falls through to the primary region, which is why step 4 caches the miss. It keeps that answer for only 5 seconds: codes are sequential, so a code probed just before it is created must still become visible within our 5-second target. Probing many different codes is the rate limiter's job (see the abuse deep dive).

Regional Cache Warming

For high-profile URLs (e.g., a marketing campaign shared on social media), pre-warm caches in all regions at creation time:

Level: Mid-level

At 1M URLs/day for 5 years, we accumulate 1.825B records (~1 TB). Without cleanup, storage grows indefinitely. But deleting URLs is dangerous — a "dead link" is worse than a "slightly slow link."

Our requirements say a short URL works forever, and expiration was out of scope. At about 1 TB, keeping every link is affordable, and the storage tiering below keeps it cheap. So expiring links is a product decision (for example for free-tier or never-used links), not a storage necessity. If the product decides to expire links, this is how to do it safely.

Expiration Policy

TTL-Based Cleanup

Storage Tiering

Key principle: Never delete a short code that might be embedded somewhere. Soft-delete, archive, and serve a "this link has expired" page instead of a 404: when a redirect finds no active link, check whether the code exists with is_active = FALSE, and if it does, show that page.