Loading...
1. Shorten URL: Given a long URL, the system generates a unique, shorter URL (e.g., https://short.url/7bXk9L).
2. Redirect URL: When a user accesses a short URL, the system redirects them to the original long URL with minimal latency.
3. Custom Aliases: Users can optionally provide a custom short code (e.g., https://short.url/my-custom-link).
4. Link Expiration (TTL): Users can optionally set an expiration time for short URLs. Once expired, the link should no longer redirect.
Optional / Advanced Requirements
1. Basic Analytics: Track usage metrics (click counts, referrer headers, geo-location, timestamp).
2. Rate Limiting: Prevent spamming and misuse of the shortening endpoint.
1. High Availability: Redirection must be highly available (99.99% uptime). Users should never get a 500 error on link redirection.
2. Low Latency: Link redirection must be extremely fast (≤50 ms for 99th percentile).
3. Scalability: System should easily handle high read-to-write traffic spikes.
4. Uniqueness: Short codes must be unique—two different long URLs should never map to the same active short code.
5. Durable & Predictable: Short links must not be guessable sequentially (prevents scraping/enumeration attacks).
EAssumptions
1. Read-to-Write Ratio: 100:1(Read-heavy application).
2. New URLs generated (Writes): 100 million per day (10 8 URLs/day).
3.URL Redirects (Reads): 10 billion per day (10 10 reads/day).
4. Retention: System will store URLs for 5 years by default.
QPS (Queries Per Second)
Write QPS:
100,000,000/86,400 sec≈1,160 write requests/sec
Peak Write QPS (2×): ∼2,300 QPS
Read QPS:10,000,000,000/86,400 sec≈116,000 read requests/sec
Peak Read QPS (2×): ∼230,000 QPS∼230,000 QPS
Storage Requirements
Average record size:
short_code: 7 bytes
long_url: 500 bytes
created_at: 8 bytes
expires_at: 8 bytes
user_id / metadata: 30 bytes
Total size per record: ≈500 bytes
Daily Storage: 100M×500 bytes=50 GB/day
5-Year Storage: 50 GB/day×365×5≈91.25 TB
Memory / Cache Estimation
Applying the 80/20 Rule (20% of URLs generate 80% of read traffic):
Daily Read Volume: 10 billion requests.
20% of requests to cache: 2 billion URLs daily.
Cache Memory Required: 2 billion×500 bytes=1 TB of RAM across cluster.
1. Create Short URL
POST /api/v1/shorten
Content-Type: application/json
{
"long_url": "https://www.example.com/long/path/article?id=12345",
"custom_alias": "my-custom-link", // Optional
"expire_in_days": 30 // Optional
}
Response (201 Created):
{
"short_url": "https://short.url/my-custom-link",
"long_url": "https://www.example.com/long/path/article?id=12345",
"expires_at": "2026-09-04T10:00:00Z"
}
2. Redirect Short URL
GET /{short_code}
Response:
HTTP 302 Found (Temporary Redirect) with header Location: https://www.example.com/...
Note: 302 is preferred over 301 (Permanent Redirect) if you want to capture analytics for every click. 301 causes browsers to cache the redirect locally, bypassing your server.
Describe the overall system architecture. Identify the main components needed to solve the problem end-to-end. Use the diagramming tool to create a block diagram.
Database Choice: NoSQL (Key-Value / Wide-Column Store)
Justification:
Pattern: Simple key-value lookups by short_code.
No Complex Joins: Transactions across tables are not needed.
High Scalability: Distributed NoSQL databases like Amazon DynamoDB, Apache Cassandra, or MongoDB can easily scale horizontally to handle 100k+ read QPS and multi-terabyte storage.
Schema: urls Table
Column Name Data Type Primary Key / Index Description
short_code VARCHAR(16) Partition Key Base62 encoded key (e.g. aB3x9L)
long_url VARCHAR(2048) None Original target URL
user_id VARCHAR(64) Secondary Index Owner ID (optional)
created_at TIMESTAMP None Creation timestamp
expires_at TIMESTAMP Secondary Index Expiration time
1. Hash-Based (MD5/SHA256):Take MD5(long_url), base62 encode first 7 characters.
2. Drawback: Collisions can occur. Resolving collisions requires database lookups, adding latency.
Key Generation Service (KGS) (Recommended):
1. A dedicated service pre-generates 7-character Base62 keys in advance and stores them in a key table (used_keys vs unused_keys).
2. When a write request arrives, the app server fetches an already available key from KGS memory instantly.
3. Concurrency control: KGS loads blocks of pre-generated keys (e.g., 5,000 keys) directly into app server memory buffer to avoid DB locks during generation.
** Caching Strategy
1. Use Redis / Memcached in front of the NoSQL database.
2. Cache Eviction Policy: LRU (Least Recently Used).
3. Read Flow:
Check Redis for short_code.
If present (Cache Hit), increment async metrics and return HTTP 302.
If missing (Cache Miss), read from NoSQL database, populate Redis, return HTTP 302.
** Expiration Cleanup (TTL)
1. Avoid querying the database periodically to remove expired links.
2. Lazy Deletion: When a user clicks an expired link, verify expires_at > NOW(). If expired, delete the key from cache and DB, return HTTP 404 Not Found.
3. Background Worker: A scheduled cron job (e.g., during low-traffic hours) batch scans DB partitions to reclaim storage.