System requirements

Functional:

1. Able to generate a short url with given long url
2. Able to redirect to long url with given short url

Non-Functional:

1. Availability: should be able to generate short url and get long url with minimal downtown
2. Low latency

Capacity estimation

Assume:

10 millions write requests per day

50 millions read requests per day

write qps = 10 * 1e6 / 24 / 60 / 60 = 10 * 1e6 / 1e5 = 100 qps

read qps = 500 qps

Data size:

Assume the average length of a long url is 30 characters (30 bytes)

And short url: 6 characters

Total = 10 * 1e6 * 36 bytes/day = 300 millions bytes = 360 mb per day

1 year = 365 days = 365 * 360 = 130 GB/year

API design

POST /api/url/{long_url}

response:

status_code = 200

{

long_url,

shourt_url,

create_at

}

GET /api/url/{short_url}

response:

status_code = 302

{

short_url,

long_url,

request_at

}

Database design

1. based on the estimation, 130GB / year, pick MongoDB/NoSQL as the option for the scaling in the future

Table:

long_to_short:

{

long_url: text

short_url: varchar

}

short_to_long:

{

short_url: varchar

long_url: text

}

High-level design

Request flows

1. generate short url
2. client -> load balancer -> service -> generate short url -> DB
3. fetch long url and redirect
4. client -> click short url -> service
5. if {shor_url: long_url} can be found in cache -> return
6. if not: fetch from DB
7. redirect the client to the long url

Detailed component design

url component:

1. Choose Redis as the cache tool, cache the {short_url: long_url} key-value pairs to reduce the fetching time
2. in the URL service, the main job is for the short url generation
3. Every request to generate a short url, it generates the short url with 6 characters randomly (256 options for each characters)
4. check if the new short url in the cache or db or not
5. if it is there already => repeat step a to generate a new url

Trade offs/Tech choices

For database, here I choose NoSQL for the ease of future scaling. The trade off here is the time to generate the new short url, if the db grow larger and larger, it might take more time to generate a new url (since it has to check there is no duplication).

Another choice we could do is using relational database, and utilize the primary key with hashing function for the short url generation

Failure scenarios/bottlenecks

The bottlenecks will be the short url generation while the system grow larger and larger to avoid duplicate url generation

Future improvements