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 reddis 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.

Detailed component design

So my redis cache would use a least recently used algorithm so that urls that are most used are pulled instantly. Since urls won't be shared amongst users anyways, using LFU doesn't make as much sense here.

The no sql database can hold userdata as well so we can denormalize the dataset to give us access to more elements. the nosql db can be scaled horizontally as the number of requests increase.

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 are not tracking used hashes, so how can we generate new ones every time.

If the hashes run out, we are simply returning the long url making it redudant.

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

Future improvements

Need to have a time based algorithm generate the hashes so that we can ensure hashes are not already used. We we go to update our database with a new hash, if it already exists then we need to create a new hash and then update that.

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