System requirements

Functional:

• should be able to create shortened URLs
• reduce longer URL
• smallest length posisble
• collect click metrics to be later used for the longer URL as well
• stay permanent

Non-Functional:

• should always be up and running
• should be fast
• replicate the functionality of the longer URL (i.e. calling other service APIs)

Capacity estimation

Estimating that the system would be a lot more of read than write. We would only write once to create the URL but mostly read a lot more. so it would be read heavy.

If there are 10 million of shortened URLs created in a month then its about, 10 urls created per second.

Assuming 200:1 read write, that would mean its about 2000 redirections per second.

If we want to store it for a given time (let's say 50 years) then we would need a DB to be long lasting. lets say a URL is about 500bytes, and we are creating 10 million URLs a month, that;s about 120 million URLs a year, and we want it to last for 50 years so that;s about 120*50= 600 million urls

600 million * 500 byte, is somewhere around 30 TB.

We also need to consider caching memory. if we use 80:20 rule for caching, then for 2000 requests/redirects per second, we have that for a day is about 180 million requests a day and if we cache 20% of these then we would need memory of about 0.2*180*500 or so GB of memory for caching.

API design

• /create:
  • will create the shorter URL by taking longer URL in the request body and return 200OK if successful or return error if not.
• /get:
  • gets the shorter URL for the longer URL from the DB and return 200OK or not.
• /delete:
  • delete the short URL if no longer needed.

Database design

• we would need relational DB like Mysql or postgres.

DB1:

• stores info about the URL itself. it will have the following columns: shortURL, corresponding longURL and the id is the primary ID of the user or service that requested the shortening, and datetime of when the URL was created.

DB2:

• stores info about the user/service that is requesting the shortening. the columns are ID (primary ID of the user/service). name, email, etc.

High-level design

on a high level we will have client and database.

the client has two functions:

• to request a short URL:
  • the client gets back the short URL for the long url
  • hits a webserver
  • in the backend there will be logic/code called to shorten the URL and store in the DB
• to access the URL.
  • the client is redirected to the long URL when accessing the shortURL.
  • hits a webserver
  • in the backend there will be logic/code called to get the long URL from the short URL from the DB and hit that URL instead.

In order to avoid latency if multiple requests are coming, then we need to add load balancers in front of the webserver and perhaps increase the webservers and also partition the DBs so that balanced requests are managed accordingly. (for example if they are coming from different locations then they go to the server closest to their region and hits the right DB partition).

We could also allow caching so that some of the long URLs can be cached and dont have to hit the DB often to reduce latency.

Request flows

• to request a short URL:
  • the client gets back the short URL for the long url
  • hits a webserver
  • in the backend there will be logic/code called to shorten the URL and store in the DB
• to access the URL.
  • the client is redirected to the long URL when accessing the shortURL.
  • hits a webserver
  • in the backend there will be logic/code called to get the long URL from the short URL from the DB and hit that URL instead.

Detailed component design

The main crux would be the shortening algorithm. We would have to use URL encoding to shorten the URL and have some kind of key that would map to the longer URL. Also we need to decide how many characters we want in our short URL. If we have more characters in our shortURL then we can have more variations of different URLs that we can generate for different long URLs (if we use base 62 URLs and want 7 characters then that's 62^7).

For simplicity sake we can have our algorithm just choose 7 characters at random. First we check if the long URL exists in the DB or not. if it does then return the short one. If not then we will generate a short one and see if that exists in the DB or not. but this can take a while if we want to keep retrying. if not then we would need some kind of basic conversion rules such that if the long url is of certain length and has certain characters then the corresponding short URL will be encoded in a certain way. May be some kind of a counter?

Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...

Failure scenarios/bottlenecks

A bottleneck could be when using RDBMs for bigger number of URLs. it may not be very scalable and we would need a NOSQL type solution for it.

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?