System requirements

Functional:

To shorten a large url into a smaller one.

Non-Functional:

We want to optomize for latency as this service takes too long it makes it pointless.

Capacity estimation

Assuming the endpoint is hit 1 billion times a month this means roughly 33 million hits a day, which if we assume a day has roughly 100000 seconds, we are at 333 requests per second.

now it terms of database, assuming each link has a max expiration of 5 years, roughly 60 billion possibilities of urls. 12 billion a year or 60 billion every 5 years. Lets say we want to use A-Z, a-z and 0-9. so we are at 62 characters possible to use. We need roughly 6 characters to achieve this lets say 7 to be safe.

Each character takes roughly a byte but lets say we also want to store so metadata and we also have to store the long url.

so lets say 1kb per request. Which is a terabyte a month and 12 terabytes a year and 60 terabytes max storage.

API design

Define what APIs are expected from the system...

So we need a post request to create the url, we would pass something like https://tinyurl/create_url

with params: {

expiration,

date_created,

long_url,

user_id

} returning something like { short_url, url_id, expiration }

We would also want a way to fetch your specific url or all your urls associated with your user. These would be with get requests.

https://tinyurl/users/:id/:url_id for a specific url returning something like { short_url, url_id, expiration }

or https://tinyurl/users/:id/urls which returns a list of { short_url, url_id, expiration }

Database design

Since we are optimizing for read heavy low latency operations. We are not prioritizing consistency so we can use a no sql mongo database, that can we scaled horizontally.

we can have a url schema that holds user information as well.

High-level design

So we have a load balancer distributing the server load. We have a LRU cache based system used because using a LFU here won't necessarily work as we are not sharing urls since different users will want to have different expirary dates.

Request flows

When requesting the url: client hits load balancer. The load balancer directs the request to the correct server. We then check the redis cache to see if the url already exists for the user, if so we pull the value and respond to the client, if not we send a request to the database for the url.

When creating a url: client hits load balancer. The load balancer directs the request to the correct server. We then hit the url generator to get a url stored in its cache, and if the urls are finished we get a batch of urls from the url generator database. We return this to the server and then to the client.

Detailed component design

So my redis cache would use a least recently used algorithm so that urls that are most used are pulled instantly. We don't want to use LFU in case a famous person makes a url it could just sit there forever and not be used.

Our url generator can actually generate and store all of our urls in one shot and either systematically pull from a batch when it runs out or periodically make requests to increase its amount of urls it has.

Trade offs/Tech choices

We used a nosql db vs sql db because this is more read heavy than write heavy and i don't see an immediate use case for table joins etc.

Instead of the redis cache being updated as the requests come in. We can have some service workers that update the cache periodically to reduce server load.

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

We have a lot of single point of failures the way the system is drawn out.

Future improvements

Use multiple load load balancers, multiple servers, and backup our database periodically as well using service workers.