System Requirements

Functional:

To shorten the URL given, a long URL should return a short URL.
To redirect a given short URL, the system should redirect to the original URL.
Expiration functionality: The system should support setting a TTL for short URL expiration.
Alias capability (optional): Have the capability to choose a short URL code by the user.

Non-Functional Requirements

1. Low Query Latency:

The system should resolve a short URL and redirect the user to the original URL with minimal delay (typically <100 ms). This is important because URL shorteners are user-facing and delays degrade user experience.

Achieved by using CDN for edge caching, in-memory cache (Redis) for fast lookups, and efficient key-value database access.

2. Horizontal Scalability:

The system must handle increasing traffic (both reads and writes) and growing data volume over time. Since the system is read-heavy and may handle tens of thousands of requests per second, it should scale horizontally.

Achieved by using stateless services, load balancers, distributed NoSQL databases, and caching layers.

3. High Availability:

The system should be highly available so that short URLs are always accessible, even during failures.

Achieved by deploying services across multiple availability zones, using replication in databases, and failover mechanisms.

4. Fault Tolerance:

The system should continue functioning even if some components fail (e.g., server crash, database node failure).

Achieved by redundancy, retries, replication, and fallback mechanisms such as serving from cache when database is unavailable.

5. Efficient Storage of URL Mappings:

The system should store billions of URL mappings efficiently without excessive storage overhead.

Achieved by using compact data models, short encoded keys (Base62), and NoSQL databases optimized for large-scale storage.

Capacity Estimation

Traffic Estimation

Write Requests

Assume a mid-size URL shortener generates:

Write QPS = 200 URL creations/sec

Daily URL creations

200 * 86,400 seconds

= 17,280,000

≈ 17M new URLs/day

Monthly URL creations

17M * 30

≈ 510M URLs/month

Read Requests

Assume read : write ratio = 100 : 1

Read QPS

200 * 100

= 20,000 redirects/sec

Daily redirect requests

20,000 * 86,400

= 1,728,000,000

≈ 1.7B redirects/day

Peak Traffic

Assume 10x traffic spike

Peak Writes

10 * 200

= 2,000 writes/sec

Peak Reads

10 * 20,000

= 200,000 reads/sec

Storage Estimation

Short URL = 7 bytes

Long URL = 100 bytes

Created Timestamp = 10 bytes

Expiration Timestamp = 10 bytes

UserId (optional) = 20 bytes

Click Count = 8 bytes

Total per record

7 + 100 + 10 + 10 + 20 + 8

= 155 bytes

≈ 160 bytes

Daily Storage

17M URLs * 160 bytes

= 2,720,000,000 bytes

≈ 2.7 GB/day

Monthly Storage

2.7 GB * 30

≈ 81 GB/month

Yearly Storage

81 GB * 12

≈ 972 GB

≈ 1 TB/year

Twenty-year Storage

1 TB * 20

= 20 TB

Replication Factor = 3

Actual storage required

3 * 20 TB

= 60 TB

Bandwidth Estimation

Write Request

Request Size = 500 bytes

Response Size = 200 bytes

Total per write request = 700 bytes

Write QPS = 200

Peak Write QPS = 2000

Average write bandwidth

200 * 700

= 140,000 bytes/sec

≈ 137 KB/sec

≈ 0.13 MB/sec

Peak write bandwidth

2000 * 700

= 1,400,000 bytes/sec

≈ 1.34 MB/sec

Read Request (Redirect)

Total per redirect (request + response)

≈ 1 KB

Read QPS = 20,000

Peak Read QPS = 200,000

Average read bandwidth

20,000 * 1 KB

= 20,000 KB/sec

≈ 19.5 MB/sec

Peak read bandwidth

200,000 * 1 KB

= 200,000 KB/sec

≈ 195 MB/sec

Total Bandwidth

Average bandwidth

Write ≈ 0.13 MB/sec

Read ≈ 19.5 MB/sec

--------------------------------

Total ≈ 19.6 MB/sec

Peak bandwidth

Write ≈ 1.34 MB/sec

Read ≈ 195 MB/sec

--------------------------------

Total ≈ 196 MB/sec

Cache Size

The access pattern is highly skewed.

A small fraction of URLs (viral links, popular content) generate most of the redirect traffic.

Using the 80/20 rule:

20% of URLs generate 80% of traffic.

So cache the 20% of the most frequently accessed URLs.

Daily URLs created ≈ 17M

0.2 * 17M

= 3.4M hot URLs per day

Instead of caching the entire historical dataset, we cache recently active URLs.

Assume we cache the last 30 days of hot URLs.

Total cached URLs

3.4M * 30

= 102M URLs

Assume each cache entry stores:

Short URL

Long URL

Metadata

Average entry size ≈ 256 bytes

Total cache memory required

102M * 256 bytes

= 26,112,000,000 bytes

≈ 26 GB

Accounting for Redis overhead, replication, and future traffic growth:

Recommended cache cluster size

≈ 80 GB – 120 GB

Submissions

Displaying Solutions with Scores Ranging from 1 to 10