Detailed Component Design

Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.

Load Balancer

Distributes incoming traffic across multiple stateless instances of the URL Shortening Service using round-robin or least-connections.
Horizontal scaling: Add more service instances behind the load balancer as traffic grows.
Read path (redirects) and write path (shorten) are handled by the same service pool, but can be routed separately via path-based rules if needed.

Redis

Redis handles read traffic for high frequency URLs
Use consistent hashing to spread URLs across instances
Eviction based on LRU, volatile-lru, based on TTL set to 24 hours

URL Shortening Service

Input: long URL
Output: short URL
First looks for a mapping for the long URL sent in the caching layers, to avoid attempting to map a popular URL
For new long URLs:
1. Generate short ID.
2. Attempt to insert into NoSQL DB (using shortId as primary key).
3. On collision (ID already exists): Generate the next ID and retry (1-2 times max). Probability is extremely low with 6-7+ character Base62 IDs.
4. Using UUIDv4 will help distribute the mapping evenly across the database shards

Redirect Service

Input: shortened URL ID
Output:
- Found: 302 and a redirect to the full URL
- Not found: Returns a 404
First checks the CDN for the mapping, then Redis, and finally the database
No mapping is found
- Return 404
If mapping is found in Cache
- Updates the last accessed timestamp and return redirect
If a mapping is not cached, but in DB
- Add it to the Redis cache and return redirect

Submissions

Displaying Solutions with Scores Ranging from 1 to 10