Design a URL Shortener (TinyURL / bit.ly)

TL;DR. A URL shortener is a read-heavy caching problem disguised as a storage problem. The 100:1 redirect-to-create ratio means you design the read path first: layered caches (CDN edge, in-process LRU, Redis) absorb 100K+ QPS while DynamoDB sees only misses. Pre-allocated batch IDs eliminate per-write coordination. A buffered Kafka pipeline decouples analytics from the redirect hot path. Bitly serves billions of redirects per month at 99.99% uptime^[1] using exactly this shape.

Learning Objectives#

After this module, you will be able to:

• Estimate capacity for a URL shortener at 10M creates/day and 1B redirects/day
• Compare four code-generation strategies and justify pre-allocated batches as the default
• Design a layered cache topology with singleflight to defend against cache stampedes
• Decouple analytics from the redirect hot path using buffered Kafka producers
• Justify the redirect-code choice (302, or 301 with a short Cache-Control) for analytics-bearing shorteners
• Integrate abuse scanning without blocking the redirect path

Intuition#

You run a coat-check counter at a concert venue. A guest hands you a coat (long URL), you hand back a numbered ticket (short code). When they return with the ticket, you find their coat and hand it back (redirect). Simple.

Three problems make this hard at scale. First, 100 guests arrive per minute but 10,000 guests per minute come back to retrieve coats. Your retrieval path is 100x hotter than your storage path. You need runners, a sorted rack, and a front-desk cache of the most popular coats. Second, you cannot pause to think of a ticket number. You pre-tear a roll of numbered tickets so handing one out takes zero thought. Third, your boss wants to know which coats get retrieved most often, but counting must never slow down the handoff. You jot a tally mark on a notepad and reconcile later.

That is a URL shortener. The coat rack is DynamoDB. The runners are Redis. The pre-torn tickets are batch-allocated IDs. The notepad is a Kafka buffer. The naive approach (one Postgres row, one server, synchronous analytics) handles 10 users fine. At 10 million writes per day and 1 billion reads per day, it collapses because the read path saturates a single database, the write path blocks on a global counter, and synchronous analytics doubles redirect latency.

The one insight that unlocks the design: treat the read path as a CDN problem, not a database problem. The mapping is immutable once created. Cache it aggressively at every tier.

Requirements#

Clarifying Questions#

• Q: Authenticated users only, or anonymous? Assume: Both. Anonymous creates with aggressive rate limits (10/min); registered users get quotas (10K/day).

• Q: Do we need click analytics? Assume: Yes. Per-link click counts, geo breakdown, referrer, and user-agent. Dashboard latency can be minutes behind real-time.

• Q: Custom aliases (vanity URLs)? Assume: Yes for paid users. Must be globally unique with a conditional write.

• Q: Multi-region required? Assume: Yes. Active-active reads across 3 regions. Writes route to nearest region with async replication.

• Q: What is the SLA target? Assume: 99.99% read availability, 99.9% write availability, p99 < 50 ms globally on redirect.

• Q: Link expiration? Assume: Optional TTL. Default is permanent. Expired links return 410 Gone.

Functional Requirements#

• Create a short URL from a long URL and return the short code.
• Redirect GET requests on the short code to the original URL via HTTP 302.
• Support optional custom aliases with uniqueness enforcement.
• Record click events for analytics (geo, referrer, user-agent).
• Allow link deletion and optional TTL-based expiration.
• Block or warn on malicious destination URLs.

Non-Functional Requirements#

• Load: 10M writes/day (~115 write QPS avg, ~350 peak), 1B reads/day (~11,500 read QPS avg, ~100K peak).
• Latency: p50 < 10 ms, p99 < 50 ms on redirect globally.
• Availability: 99.99% read path, 99.9% write path.
• Consistency: eventual for cross-region reads (1-5s lag); strong for custom-alias uniqueness.
• Durability: once published, a short code mapping must never change or disappear without explicit deletion.

Capacity Estimation#

Key ratios:

• Read:write = 100:1. This ratio drives every architectural decision.
• Cache hit rate target: 95%+. At 95% hit rate on 100K peak QPS, DynamoDB sees only 5K reads/sec, well within burst capacity.
• Code space: 7-char base62 = 62^7 = 3.52 trillion slots^[2]. At 10M/day, that is ~965 years of headroom.
• Bandwidth: 100K req/sec x ~1 KB response (headers + 302) = ~100 MB/s egress at peak.

API and Data Model#

API Design#

POST /v1/urls
  Authorization: Bearer <token>
  Idempotency-Key: <uuid>
  Body: { "long_url": "https://...", "custom_alias": "my-brand", "expires_at": "2027-01-01T00:00:00Z" }
  Returns: 201 { "short_code": "dX3kq8", "short_url": "https://sho.rt/dX3kq8", "created_at": "..." }
  Errors: 409 alias conflict, 429 rate limited, 400 invalid URL

GET /{short_code}
  Returns: 302 Found, Location: <long_url>, Cache-Control: private, max-age=0
           404 not found, 410 gone (expired)

GET /v1/urls/{short_code}/stats
  Returns: 200 { "clicks": 42000, "by_country": {...}, "by_day": [...] }

DELETE /v1/urls/{short_code}
  Returns: 204 No Content

Why 302 (or 301 with a short Cache-Control) and not an uncapped 301: browsers may cache a vanilla 301 indefinitely and never re-request^[3], which kills click analytics and delays revocation until each client's cache expires on its own schedule. A 302 response forces the client back to the server on every click. Bitly takes a different route: direct HTTP probes against bit.ly return HTTP/2 301 with Cache-Control: private, max-age=90, which accepts up to ~90 seconds of per-client analytics lag in exchange for browser-cache friendliness^[4]. Either pattern is defensible; a bare 301 without a short Cache-Control is not.

Data Model#

-- Primary store: DynamoDB Global Table
-- Partition key: short_code (hash-distributed)
-- No secondary indexes on the hot path

table url_mappings (
  short_code     String    -- partition key, 7-char base62
  long_url       String    -- the destination
  owner_id       String    -- nullable for anonymous creates
  created_at     Number    -- epoch ms
  expires_at     Number    -- nullable, epoch ms
  safety_status  String    -- "clean" | "warn" | "blocked"
)

-- Analytics store: ClickHouse
-- Partitioned by month, ordered by (short_code, event_time)

table click_events (
  event_time     DateTime
  short_code     String
  country        FixedString(2)
  referrer_host  String
  ua_family      LowCardinality(String)
)

DynamoDB Global Tables provide single-digit ms point reads, managed multi-region replication, and no joins on the hot path^[5]. Per-partition limits are 3,000 RCU and 1,000 WCU^[5:1], which is fine because 7-char base62 codes distribute uniformly across partitions.

ClickHouse's sparse primary index makes "last 30 days of clicks for this code" a contiguous range scan over a single disk segment^[6].

High-Level Architecture#

The redirect path is lean: CDN edge, gateway, redirect service, Redis, DynamoDB. Analytics and safety scanning hang off a Kafka bus so neither blocks a click.

Write path: Client sends POST to the API gateway. The create service calls the code generator (in-memory batch allocation, no RPC), writes to DynamoDB with a conditional put, warms Redis, and emits a url.created event to Kafka. The safety scanner consumer evaluates the destination URL against Google Web Risk asynchronously.

Read path: Client sends GET to the CDN edge. On cache hit (viral codes), the CDN returns 302 directly. On miss, the request falls through to the redirect service, which checks the in-process LRU, then Redis, then DynamoDB. The redirect service appends a click event to an in-process buffer (never blocks on Kafka).

Async path: Kafka consumers enrich click events (geo from IP, UA parsing) and batch-insert into ClickHouse. A separate consumer re-scans URLs for safety status changes.

Deep Dives#

Deep dive 1: ID generation strategies#

The code generator must produce globally unique, URL-safe, compact codes at 350 peak writes/sec with zero per-request coordination.

Option A: Hash truncation (MD5 prefix, base62-encoded). Deterministic, but collisions are guaranteed by the birthday paradox. With 6-char base62 (62^6 = 56.8B slots), collisions become likely at ~238,000 URLs^[7]. Also leaks information: anyone with the long URL can compute the code.

Option B: Auto-increment counter (Flickr ticket-server style^[8]). Zero collisions, compact codes. Flickr runs two MySQL servers with auto_increment_increment=2 and offsets 1/2 for HA. "In production since Friday the 13th, January 2006"^[8:1]. But the counter is a single-point bottleneck, and codes are enumerable.

Option C: Random + conditional write. Unguessable codes. At 18B existing codes in a 3.52T code space, collision probability per attempt is ~0.5%. Requires an extra DB round-trip per write.

Option D: Pre-allocated batches (the winner). A coordinator (ZooKeeper or a Postgres row) hands out ranges of 10,000 consecutive integer IDs to each create-service instance. The instance assigns IDs from its in-memory range with zero coordination per request. When the range runs low, it fetches another batch asynchronously.

This is the Instagram sharded-ID pattern^[9]: 41 bits of timestamp, 13 bits of shard ID, 10 bits of sequence, yielding 1,024 IDs per shard per millisecond without cross-shard coordination. Twitter's Snowflake uses the same principle at 64 bits^[10].

Each create-service instance holds a pre-allocated ID range in memory. The hot path requires zero network calls for ID generation; ZooKeeper is contacted only when the range runs low.

Why batches win: no per-request coordination, linear throughput scaling with instances, zero collisions by construction. If an instance crashes with 9,000 unused IDs, those are wasted. With 3.52 trillion slots, waste is irrelevant.

Deep dive 2: Read path at 100K QPS#

The redirect path must serve 100K peak QPS at p99 < 50 ms globally. A single database cannot do this. The solution is a four-tier cache:

Cloudflare reports that less than 0.03% of Workers KV keys account for nearly half of all KV requests, and their in-memory cache resolves these hottest keys in under 1 ms^[11]. That hot-key concentration matches URL shortener traffic perfectly.

The stampede problem: a hot cache key expires, 10,000 clients miss simultaneously, all 10,000 queries hit DynamoDB for the same key. DynamoDB's per-partition limit is 3,000 RCU^[5:2]. One viral code can saturate a partition.

Defense: request coalescing (singleflight). Only one in-flight DB lookup per key per redirect-service instance. All other callers subscribe to the same in-flight future. Go's golang.org/x/sync/singleflight implements this in a single file (~200 lines)^[12]. Discord uses the same pattern in their Rust data services layer, collapsing thousands of concurrent reads into one DB call^[13].

A miss at any tier falls through to the next. The singleflight gate before DynamoDB collapses concurrent misses on the same key into one DB call.

Additional defenses: stale-while-revalidate (serve expired value while refreshing in background), pre-warming (seed cache on create with long TTL), negative caching (cache 404s for 60s to block random-code scanners).

Deep dive 3: Async analytics pipeline#

The redirect must never block on analytics. Every millisecond added to the redirect path is a direct SLO violation.

The redirect service appends a click event to an in-process ring buffer and flushes to Kafka every 100 ms or 1,000 events, whichever comes first. If the buffer is full, the event is dropped. Analytics can tolerate small loss (typically < 0.1%); the redirect cannot tolerate blocking.

Kafka sizing: 100K events/sec (peak) x 200 B/event = 20 MB/s. With 30 partitions (< 1 MB/s each) and 7-day retention, the cluster holds ~12 TB. A 3-broker cluster with 3x replication handles this comfortably.

Consumer pipeline: Analytics workers consume batches, enrich (geo from MaxMind IP, UA parsing), and batch-insert into ClickHouse (10K rows per insert). ClickHouse's SummingMergeTree materialized views pre-aggregate daily counts at insert time so dashboard reads never scan raw events^[6:1].

The redirect returns before any analytics I/O. Kafka is a replay log: if ClickHouse ingestion fails, events re-ingest without loss.

Why not write directly to ClickHouse? ClickHouse is optimized for batch inserts, not low-latency single-row writes. A synchronous insert from the redirect handler would couple redirect latency to OLAP store health. Under partial ClickHouse degradation, redirects would time out.

Real-World Example#

Bitly processes billions of clicks per month^[14] across more than 190 countries, serving more than half of the Fortune 500 as enterprise customers^[1:1]. The redirect path targets 99.99% uptime^[1:2].

Abuse detection pipeline. Bitly's Trust and Safety system has three stages that never touch the redirect hot path^[4:1]:

1. Crawl. On create ("encoding" in Bitly's terminology), a Crawler fetches the destination URL and extracts metadata: page title, redirect chains, SSL certificate, hosting provider.
2. Classify. The Threat Detection Service evaluates metadata against Google Web Risk's database of over 1 million known-bad URLs^[15]. Web Risk scans over 10 billion URLs daily and returns a confidence score (low to extremely high)^[15:1].
3. Enforce. The Abuse API is the single source of truth. On every redirect ("decoding"), the cached record includes safety status. Flagged URLs show an interstitial warning; hard-blocked URLs return a block page. The flag lives in the cached record, so enforcement adds zero latency.

Re-scanning. A rolling Kafka consumer re-evaluates existing URLs because a benign page today can become a phishing page tomorrow^[4:2]. This is why the safety scanner is a consumer, not a synchronous gate.

Twitter t.co takes a different approach: every URL in every tweet is wrapped automatically with no opt-out^[16]. The fixed 23-character length for HTTPS links^[17] decouples link length from the character budget. Twitter's Snowflake^[10:1] provides uncoordinated ID generation at tens of thousands of IDs per second, and t.co likely uses this or a similar scheme.

Google goo.gl shutdown. Google's URL shortener stopped accepting new URLs in 2018 and began displaying interstitials in 2024. Their own data: "more than 99% of [goo.gl URLs] had no activity in the last month"^[18], yet the remaining links were embedded in "countless documents, videos, posts and more"^[18:1]. Google later revised their approach in August 2025, preserving actively-used links while deactivating only those with no recent activity^[18:2]. The lesson: a shortener makes a long-term durability promise. Breaking it has cascading costs for every artifact that embedded the link.

Trade-offs#

The single biggest trade-off: 302 vs 301. Serving 302 means every click hits the server, which costs compute and adds latency but gives exact analytics and immediate revocation. Serving 301 with a default Cache-Control means browsers may cache the redirect indefinitely, so returning users never come back to the origin; analytics decay and revocation takes weeks. The middle path is what Bitly actually runs in production: 301 with Cache-Control: private, max-age=90 (verified by direct HTTP probe against bit.ly at time of writing), which keeps the first-click hit on the server while letting browsers cache the redirect for a short, bounded window. Pick 302 when you want every click counted and you control the whole path; pick 301-with-short-Cache-Control when you want browser-cache friendliness and can tolerate ~max-age seconds of analytics lag and revocation delay.

Scaling and Failure Modes#

At 10x load (100M writes/day, 10B reads/day, 1M peak read QPS):

• Redis memory grows to 90 GB per region. Shard across more nodes; Redis Cluster handles this natively.
• DynamoDB hot partitions: a celebrity tweet sends one code viral. The cache tier absorbs most traffic, but leakage can hit the 3,000 RCU cap^[5:3]. Mitigation: write-sharding (replicate the hot key across N partition-key variants, round-robin reads).
• Kafka partition count increases to 300 to maintain < 1 MB/s per partition.

At 100x load (1B writes/day, 100B reads/day):

• Storage reaches petabyte scale. DynamoDB still handles it, but cost may justify migrating to self-hosted ScyllaDB. Discord proved this at trillions of messages: p99 reads dropped from 40-125 ms (Cassandra) to 15 ms (ScyllaDB) on 72 nodes instead of 177^[13:2].
• The CDN becomes the primary read path. DynamoDB becomes origin-only, hit on < 1% of requests.

At 1000x load: the architecture shifts to CDN-first with edge compute (Cloudflare Workers) resolving most redirects without ever hitting origin infrastructure.

Failure modes:

• Regional outage: GeoDNS routes traffic to surviving regions. DynamoDB Global Tables provide RPO < 1s for committed writes. URLs created in the failed region during the last replication window may 404 briefly in other regions until replication catches up.
• Redis cluster failure: redirect service falls through to DynamoDB directly. Latency increases from ~2 ms to ~8 ms. Singleflight prevents stampede. The CDN absorbs viral traffic regardless.
• Kafka broker failure: the in-process ring buffer continues accepting events. If all brokers are down for > buffer capacity (~10 seconds at peak), events are dropped. Analytics tolerates this; redirects are unaffected.

Common Pitfalls#

Follow-up Questions#

Exercise#

Exercise 1: Custom-alias collision handling#

A premium user requests sho.rt/my-brand. Another user already owns that alias. Design the flow that handles: (1) the conditional write detecting the collision, (2) the response to the second user, (3) caching negative lookups so popular alias checks do not hammer the DB, and (4) a reservation system that holds an alias for 5 minutes during checkout.

Key Takeaways#

• Read-heavy caching problem. Design the redirect path first; the create path is trivial at 350 peak QPS.
• Pre-allocated batch IDs. Eliminate per-write coordination. 7-char base62 gives ~965 years of headroom at 10M/day.
• Layered caching + singleflight. CDN, in-process LRU, Redis, then DynamoDB. Singleflight collapses stampedes into one DB call.
• 302, or 301 with a short Cache-Control. A bare 301 is cached by browsers indefinitely and breaks analytics. 302 costs one RTT per click for exact analytics; Bitly's 301+max-age=90 is the middle ground.
• Async analytics via Kafka. The redirect handler never blocks on analytics I/O. Tolerate < 0.1% event loss.
• Abuse scanning is not optional. Shorteners obscure destinations. Integrate Google Web Risk from day one.

Further Reading#

• Bitly Trust and Safety: An Overview of Our Abuse System. The closest thing to a public architecture post Bitly publishes; describes Crawler, Threat Detection Service, and Abuse API end-to-end.
• How Discord Stores Trillions of Messages. The canonical reference for hot-partition cascades and request coalescing via a Rust data-services tier.
• Announcing Snowflake (Twitter, 2010). The original 64-bit uncoordinated ID scheme that inspired batch allocation patterns everywhere.
• Sharding and IDs at Instagram. The 41+13+10 bit layout in PL/PGSQL, complete with runnable code.
• Ticket Servers: Distributed Unique Primary Keys on the Cheap (Flickr, 2010). The REPLACE INTO + odd/even offset HA pattern.
• We made Workers KV up to 3x faster (Cloudflare, 2024). Tiered cache architecture and hot-key concentration data (0.03% of keys = ~50% of requests).
• Designing robust and predictable APIs with idempotency (Stripe, 2017). Idempotency keys, exponential backoff, and thundering-herd mitigation.
• Google URL Shortener links will no longer be available (2024). The interstitial rollout and the cost of breaking link durability.

Flashcards#

References#