Loading...
To shorten a large url into a smaller one.
We want to optomize for latency as this service takes too long it makes it pointless.
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.
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
eturning something like short_url, url_id, expiration. A successful write operation will return a 200 code and a failed one 404.
We would also want a way to fetch your specific url. These would be with get requests.
https://tinyurl/users/:id/:url_id for a specific url returning something like short_url, url_id, expiration
On successful url we will return a 302 redirect which redirects the user from the short url to the long url. Or we return a 404 error when something went wrong.
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.
To add future data that we might not need write now per schema. We can use denormalization to continue to have low latency for our reads.
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.
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.
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. We will use a write around cacheing as well so that we only add to the cache on writes so that we trade write latency for read latency.
We can implement sharding in our nosql database to improve latency.
We can use a SHA-256 based algo to actually generate the urls. Our url generator can actually generate and store all of our urls in in a seperate nosql database. We can also create a separate redis store that stores a batch of these urls based on alphabetical storing so that we reduce latency. Once a url is in the cache it is removed from the database. We can then have a background worker the periodically updates this cache once its empty, and also checks expiring urls to add more urls to the url database.
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.
Try to discuss as many failure scenarios/bottlenecks as possible.
Because we have a nosql database with sharding we have introduced eventual consistency which means if a famous person creates a url that gets a lot of hits, it can crash our server since that url won't exist instantly everywhere.
for the expiration of our generated urls have no system in place to remove them and add them back into the pile of unused urls.
We have a lot of single point of failures the way the system is drawn out.
To fix the issue of a famous person creating a url that needs to be available, we can create a separate redis cache for users with an above certain follower count and in our server check that cache if we get a cache miss on our regular redis server, before we attempt to check the sql database.
We can have a service worker periodically check our urls to see which ones have expired so we can add them back into our url pile.
Use multiple load load balancers, multiple servers, and backup our database periodically as well using service workers