Design a Distributed URL Shortener (TinyURL)

1. Problem Statement & Scope

System Mission

Design a highly scalable, fault-tolerant, low-latency URL Shortening service (similar to TinyURL or Bitly) that transforms long HTTP URLs into compact 7-character aliases, handles billions of redirects with sub-10ms latency, supports custom aliases, expiration TTLs, and real-time click analytics.

Functional Requirements

1. URL Shortening (POST /v1/urls): Given a long URL, generate a compact, unique 7-character alias (e.g. https://hi.link/aZ9k2Lq).
2. URL Redirection (GET /{short_code}): Given a short code, instantly redirect the client to the original long URL with minimum latency.
3. Custom Aliases & Expiration: Allow users to specify custom short aliases (e.g. https://hi.link/summit2026) and optional expiration timestamps (TTL).
4. Click Analytics: Asynchronously aggregate click metrics (total clicks, referrer, client country, timestamp).

Non-Functional Requirements (SLAs/SLOs)

• High Availability: $99.999\%$ uptime SLA for redirection lookups (Read Path is mission-critical).
• Ultra-Low Latency: P99 Read Redirection Latency $< 10\text{ ms}$; P99 Write Latency $< 50\text{ ms}$.
• Durability: $99.999999999\%$ (11 9s) zero URL mapping loss guarantee.
• Read-to-Write Ratio: Heavy read bias of $100:1$ (100 redirections per 1 new URL shortened).

---

2. Capacity & Scale Estimation

Traffic Calculations

• New URL Creation Rate (Writes):
  • 100 Million new URLs created per month.
  • Average Write QPS: $\text{Write QPS} = \frac{100,000,000}{30 \times 86,400} \approx \mathbf{38.6\text{ writes/sec}}$
  • Peak Write QPS ($5\times$ burst): $\mathbf{200\text{ writes/sec}}$.
• Redirection Traffic (Reads at 100:1 Ratio):
  • Average Read QPS: $\text{Read QPS} = 38.6 \times 100 \approx \mathbf{3,860\text{ reads/sec}}$
  • Peak Read QPS ($3\times$ burst): $\mathbf{11,580\text{ reads/sec}} \approx \mathbf{12,000\text{ QPS}}$.

Storage & Memory Estimation (10-Year Horizon)

• 10-Year URL Volume: $100\text{M URLs/month} \times 12\text{ months} \times 10\text{ years} = \mathbf{12\text{ Billion URLs}}$
• Record Size:
  • short_code: 7 Bytes.
  • long_url: 500 Bytes average.
  • user_id: 16 Bytes.
  • created_at / expires_at: 16 Bytes.
  • Metadata & Overhead: 61 Bytes.
  • Total per Record: $\approx 600\text{ Bytes}$.
• 10-Year Database Storage: $12 \times 10^9 \times 600\text{ Bytes} = \mathbf{7.2\text{ TB}}$
• 3-AZ Multi-Region Replicated Storage: $7.2\text{ TB} \times 3 = \mathbf{21.6\text{ TB}}$
• In-Memory Cache Sizing (80/20 Pareto Rule):
  • Daily active redirection requests: $3,860 \times 86,400 \approx 333\text{ Million requests/day}$.
  • $20\%$ of URLs generate $80\%$ of traffic. Even in the worst case where every hot request targets a distinct URL, the hot set is bounded by $333\text{M} \times 0.20 \approx 67\text{M}$ URLs: $\text{Hot Set Upper Bound} = 67\text{M URLs} \times 600\text{ Bytes} \approx \mathbf{40\text{ GB RAM}}$
  • Allocate an Amazon ElastiCache Redis Cluster with $64\text{ GB RAM}$ (easily caching 100% of daily hot URLs).

Base62 Encoding & Hash Space Math

A short code consisting of alphanumeric characters [0-9, a-z, A-Z] has a character alphabet size of:

$$\text{Base} = 10 + 26 + 26 = 62$$

For a 7-character string, the total unique URL capacity is:

$$62^7 = \mathbf{3,521,614,606,208} \approx \mathbf{3.52\text{ Trillion unique URLs}}$$

At $100\text{M}$ URLs/month, $3.52\text{ Trillion}$ provides over 2,900 years of collision-free namespace capacity.

---

3. AWS-First High-Level Architecture

Synthesizing vector architecture diagram...

Follow the two paths from the top. Reads (redirects): CloudFront answers most of them from its cache; a miss goes to the redirect Lambda, which checks Redis first (1) and DynamoDB only on a Redis miss (2), and every click is also sent asynchronously to Kinesis, so analytics never slow the redirect. Writes (new short links): the creator Lambda takes a block of 1,000 IDs from a DynamoDB atomic counter at once, then hands them out from memory, so it contacts the counter only once per 1,000 links; each ID is encoded into a short code and the mapping is saved to DynamoDB. In the "Asynchronous Click Stream Processing" panel, Firehose batches click events into Parquet files in S3 for Athena. Reads outnumber writes by about 100 to 1, so the design puts caches in front of reads and batching on writes.

Data Flow Walkthrough

1. Creation & Bijective Obfuscation: Client submits POST /v1/urls. URL Creator Lambda takes the next integer from its locally leased ID block (blocks of 1,000 are reserved with one DynamoDB ADD counter :1000 call, so the counter row sees $\approx 0.04$ writes/sec, not 38), applies a deterministic Feistel cipher permutation over the $62^7$ space to prevent sequential guessing, and converts the integer into a compact 7-character Base62 alias (hi.link/aZ9k2Lq).
2. Global Single-Table Persistence: The mapping is saved to Amazon DynamoDB Global Tables with primary key URL#<short_code> and optional TTL. Custom aliases use conditional expressions (attribute_not_exists(PK)) to guarantee uniqueness.
3. Multi-Tier Edge & Redis Redirection: Redirection queries (GET /{short_code}) resolve at CloudFront Edge caches ($P99 < 5\text{ ms}$). On edge miss, regional Lambda checks ElastiCache Redis cluster ($P99 < 1\text{ ms}$). On Redis miss, a single-flight mutex fetches from DynamoDB and backfills Redis.
4. Decoupled Asynchronous Analytics: The Redirect Lambda fires a non-blocking click event to Amazon Kinesis Data Streams and returns HTTP 302 immediately. Kinesis Data Firehose batches analytics into S3 Parquet lakes for ad-hoc SQL queries via Amazon Athena.

Concrete Step-by-Step Request Walkthrough: Tracing Redirection & Click Stream Ingestion

---

4. API Interface Design

1. Create Short URL

httpCopy
POST /v1/urls
Host: api.hi.link
Content-Type: application/json
Authorization: Bearer <jwt_token>

{
  "long_url": "https://www.amazon.com/dp/B08N5WRWNW?ref=my_campaign_summer_sale_2026_promo_code_xyz",
  "custom_alias": "summer-sale-2026",
  "ttl_seconds": 2592000
}

Response: 201 Created
{
  "short_code": "summer-sale-2026",
  "short_url": "https://hi.link/summer-sale-2026",
  "long_url": "https://www.amazon.com/dp/B08N5WRWNW?ref=my_campaign_summer_sale_2026_promo_code_xyz",
  "created_at": 1718000000,
  "expires_at": 1720592000
}

2. URL Redirection Endpoint

httpCopy
GET /{short_code}
Host: hi.link

Response: 302 Found (301 Moved Permanently only for immutable, analytics-free links)
Location: https://www.amazon.com/dp/B08N5WRWNW?ref=my_campaign_summer_sale_2026_promo_code_xyz
Cache-Control: public, max-age=0, s-maxage=86400, stale-while-revalidate=3600

max-age=0 keeps the browser from caching the redirect (so revocations take effect on the next click), while s-maxage=86400 lets CloudFront serve it from the edge. Edge hits never reach the origin, so click analytics for them come from CloudFront real-time logs streamed into the same Kinesis stream the Lambda writes to (Section 3, step 6).

3. Link Analytics

httpCopy
GET /v1/urls/{short_code}/stats?window=7d
Host: api.hi.link
Authorization: Bearer <jwt_token>

Response: 200 OK
{
  "short_code": "summer-sale-2026",
  "window": "7d",
  "total_clicks": 14290,
  "unique_visitors_approx": 11804,
  "top_referrers": [{"host": "t.co", "clicks": 6120}, {"host": "news.ycombinator.com", "clicks": 2210}],
  "top_countries": [{"country": "US", "clicks": 8010}, {"country": "DE", "clicks": 1330}],
  "updated_at": 1718003600
}

Served from the pre-aggregated click_stats table below (refreshed every 60 s by the stream aggregator), never from the raw event lake, so the request costs one DynamoDB read.

---

5. Data Models & Storage Architecture

DynamoDB Single-Table Schema (UrlShortenerTable)

• Primary Partition Key (PK): URL#<short_code>
• Primary Sort Key (SK): METADATA
• Global Secondary Index (GSI1): GSI1-PK: USER#<user_id>, GSI1-SK: CREATED#<created_at>

Redis Key Schema (ElastiCache)

Click Analytics Storage (Two Tiers)

---