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 201 code and a failed one 400, in the event that the url is not a valid url.
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 scale horizontally using sharding.
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.
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. So we are trading consistency for latency.
Another tradeoff we are making is around how we read/write from cache since we are writing to our cache only on post requests, we are sacrificing latency on a write for better latency on a read.
Try to discuss as many failure scenarios/bottlenecks as possible.
1) Problems with eventual consistency
2) A lot of SPOF in our system.
1) Additionally, since our system is only eventually consistent, there is a few scenarios where this may not be acceptable. Let's say there is a very famous person who posts a link and within seconds we get 100s of thousands of requests. There are 2 problems here now:
the shortened url hasn't been replicated to all db nodes (especially the ones across the world);
we are getting a thundering herd problem - all of these requests are going to cache miss and all go to the disk which is slow and can cause additional problems/cost in our DB usage.
We can solve this problem by using a "push" based approach in cache for famous/reserve users - we first write in cache and then we write (and replicate) on disk. That would solve the replication/and thundering herd problem, but only if the cache daemon on the application server can have the ability to precisely determine the node id where the cache node with the resource is located.
2) Well, we do have a few things which are SPOF - we can deploy many load balancers, servers, databases nodes, and cache nodes, but we need to be very careful with the algorithm that is generating hashes for the shorter URLs. there is many things that can go wrong: