System requirements

Functional:

1) /v1/get

body:

{

"url": "https://longurl.example"

}

Response:

{

"url": "https://cut.example/$RandomPart$"

}

2) listen for shortURL:

a) find correcspondig URL

b) 301 redirect to found URL

3) TTL of shorten URL - max 1y

4) Statistics - out of scope

Non-Functional:

301 redirect should work for less then 1 second

System should be able to work with millon users daily

and generate 5 million URLS/day

New short URL should be generated faster then 1 second

Capacity estimation

let's assume we need 5kb per URL (5k symbols length)

5 000000 * 5 = 25 000000 / 1024 = 24 414 MB/day

Let's round it to 25 GB per day of storage.

We will have 1 year maximum retention policy, so for 1 year it will be maximum of

365*25 = 9125 GB. Let's round it to 10 TB/year

API design

1) /v1/getShortURL

body:

{

"url": "https://longurl.example"

}

Response:

{

"url": "https://cut.example/$RandomPart$"

}

2) /v1/getFullURL

the opposite from getShortURL

Database design

We will work with NoSQL DB type with following schema:

key: our generated post slash part of shorturl

value:

url: "full_url",

valid_until: "maxvaliddate"

High-level design

We should have:

1) API-server

2) DB with shorten URLS

3) Webserver to surve 301 redirects from shorten URLs to Full ones and to consume API service to generate shorten urls for users

4) DB with some meta info?

5) Shortener - component that is being called from api server that will generate shortURL

6) DB with pregenerated short URL

hashmap

key: url

value: true - occupied, false - free

7) batch job that will scan DB with shorten urls and find outdated ones and delete it from there and add back to DB with pregerated short URLS

Request flows

1) from web ui, user paste long url. UI use API-server /getShortenURL,

Meanwhile API service is requesting shortener to generate new short URL

Shortener response to api-server, api-server returns response back to UI, UI is showin response to user

2) Next request flow is the same, but instead UI user could use prgrammatic access with API

Detailed component design

How shortener should generate short random part of the our URL unique per 2 billions URL (maximum esitated for the year)?

We will use pregenerated nosql db for this: number 6 from our high-level design.

We will pre-generate 2billion random strings.

We can use combinatoric forumula x^y=maximum_variants

where X - maximum variants of value per place in number

y - number of places in number

e.g.:

"123" if we know that on each place of this number could be 0-9 (10 digits) and we have 3 place, then 10^3 = 10000 maxim possible combination.

let's assume that we will use

all latin symbols, how much of them? approx 25

+ 2 small and caps registry - it will be 50.

now we can add some special sybols, e.g it will be 70.

now we need to understand to which power we should get 70 to reach 2billons+

root 70 power of 2billions

70^x=2,000,000,000

x=5

so our random part of the url could be only 5 symbols.e.g

https://myservice.example/Ad$.a

We can partition our main DB with urls by hasha on shorten url (they are unique) module N (number of node)

Trade offs/Tech choices

Failure scenarios/bottlenecks

If our db with pregenerated (free) postfix will be unavaiable for some reason we won't be able to short new urls, but we still can service already existing ones.

Let's assume that multi datacenter is our of scope with consensus algorithms

Future improvements

Support multiDC with consensus algorithms