System requirements

Functional Requirements

Able to save new short URL

Able to access saved short URL

URLs live forever

Non-Functional Requirements

Numbers

100M new URLs per day -> 1k new URLs per sec

10B reads per day -> 100k URL reads per sec

~1KB per URL (very pessimistic/conservative)

100M new URL per day -> ~35B new URL per year

~35TB per year

API design

GET read(short_url) -> long_url

POST write(long_url) -> short_url

High-level design

Each app server will create a random 8 char base62 code whenever client tries to create short url. 8 char gives enough URLs to last >1k years. The app server will try to insert it into the DynamoDB which will fail if it already exists. In the unlikely event the short URL already exists, app server will retry random short URL creation

For hot URLs, we implement two levels of caching. There will be a distributed LRU Redis cache. Each server will also have a small LRU in-memory cache. This will protect Redis in the case of a super super hot URL.

Detailed component design

Database design

Store URL in DynamoDB table

short_url, long_url