Loading...
Given the expected capacities above, we can estimate how much storage we would need for saving the necessary information for each URL. This necessary information would include 1) the long URL, 2) the shortened URL, 3) the user id of the user who created the URL, 4) a created at timestamp, and 5) an expiration timestamp. Let's assume that each of the timestamps are 4 bytes (so 8 bytes for timestamps) and that the user_id is a 4 byte int, which would allow us to support billions of users, more than enough. That brings us to 12 bytes, but we will need more for the URL strings.
For a standard shortened URL, let's aim to support a maximum length of 8 characters. That should balance the desire to have URLs short enough to fit on social platforms and SMS, with the desire to have the URL be long enough to reduce collision rates when it comes time to developing our hashing that will convert long URLs to short URLs. We may want to support URLs longer than 8 characters if the user wants a custom alias, but for this capacity estimation we will naively assume most URLs are the shorter 8 character ones. If we assume our short URLs are 8 characters long and the average long URL is 100 characters long, then we will need at least 108 bytes to store those. That takes our total average storage per URL to at least 120 bytes.
If we are creating 200 new short URLs per second, that is 12,000 URLs per minute, 720,000 URLs per hour, and which would be more than 15 million shortened URLs per day. Multiplying that by 120 bytes per URL, we would need to store more than 1.5 billion bytes, which would be more than 1.5 GB per day.
More storage will be needed to support things like analytics, but let's ignore that for now so we can focus on the design of some other parts of the system.
We need to support a POST route where a user can create a new shortened URL. In the request, the user will need to provide the long URL to be shortened, the expiration timestamp (if any), and the custom alias (if any).
Our API also needs to support GET requests to shortened URLs, which will result in redirects to the appropriate long URL.
We will need separate queries for things like user login and analytics, but for now I want to focus on the core functionality.
The key table in our database will be a table of URLs. In that table, we will need to store all the fields discussed in capacity estimation above, specifically 1) a primary key, 2) a long URL as a string, 3) a short URL as a string (which could be a custom alias), 4) a created_at timestamp, and a 5) expires_at timestamp.
At a high level, our system will have 1) a load balancer accepting requests from the client, 2) a UrlCreationService, 3) a main database containing the URL mappings and related data used for writes, 4) a replica database used for reads, 5) a cache, and 6) instances of a UrlRetrievalService.
To avoid collisions in our short URLs, ideally we would have a single UrlCreationervice which hashes long URLs into short URLs. While having a single UrlCreationService could become a bottleneck, at 200 requests per second, we should be able to provide the service with sufficient resources to handle such a load. If we need to horizontally scale the UrlCreationService, we'll need to make sure we properly handle not creating duplicate short URLs.
The UrlCreationService and UrlRetrievalService can be scaled up as needed based on traffic. Depending on the exact caching strategy, we may want to support multiple caches either with replicas of the same caches data or we might shard the URLs across multiple cache instances.
There are two key request flows we need to focus on in the core service: 1) the POST request to create a new short URL and 2) the GET request to be taken to the appropriate long URL.
Let's focus on the creation of the new short URL first. The request should first hit the load balancer, which can then pass the request on to an instance of the UrlCreationService. Within the UrlCreationService, the long URL will need to be hashed and stored in the database. To get a short URL (assuming no custom alias was specified), the UrlCreationService will make a call to the UrlHashingService. When the UrlCreationService has received the short URL, the service will need to persist the full mapping of data for the URLs into the database. Assuming a successful write to the database service, the UrlCreationService/load balancer can return a success response to the client with the shortUrl contained in the response. If the write to the database fails, such as for instance a custom alias already being in use, the UrlCreationService/load balancer should return a failure to the client indicating the reason for the failure such as the custom URL already being in use.
For the GET request to be taken to the appropriate long URL, the client's request will first hit the load balancer. The load balancer will first check the cache for the long URL. If the long URL exists in the cache and has not expired, the load balancer can simply return the long URL. If there is a cache miss, the load balancer will request the long URL from an instance of the UrlRetrievalService. The UrlRetrievalService will look up the long URL from the read replica of the database and return the long URL to the client/load balancer.
Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...
Let's focus first on the UrlCreationService. To process URL creation quickly, we need to constantly have unique short URLs available for use that have not previously been stored in the database. Within the UrlCreationService, we could have some service responsible for returning tokens that will be our short URLs. That service should at all times have at least several thousand unique short URLs available to hand to the UrlCreationService to be assigned to new long URLs.We can imagine each short URL as a token and we need a bucket with thousands of such tokens ready to be used that have already been produced and checked for uniqueness. Some long running process within the UrlCreationService could be responsible for making sure the bucket is constantly refilled as tokens are used up so that we can create new short URLs quickly as requests come in. If this is too much to handle within the UrlCreationService, we could have a separate service responsible for keeping the tokens ready that the UrlCreationService would call.
We should also talk about the cache. To be able to process redirects quickly, we need to be able to retrieve URLs as fast as possible. We can likely expect that some URLs will be much more frequently accessed than others, and these should be cached to reduce the load on the read replica of the database. To make reads from the cache fast, we could use a key/value store like Redis with quick in memory storage. In this case, the key would be the short URL and the value would be the long URL. This may be simplest and fastest, but we would be missing the expiration time from the key/value pair in the cache. If we used this strategy, we would want some other process which is aware of expiration times to be constantly evicting pairs from the cache which have expired. This would only be acceptable if we are fine with occasionally returning a redirect for an expired URL that has expired but not yet been evicted from the cache. This may be a worthwhile performance tradeoff so long as we do not leave expired key/value pairs in the cache on average for very long. If we do not want to pursue this path, we could either store the expiration time in the cache as part of the key/value pair or specify an expiration time at the time a key/value pair is originally placed in the cache.
Given the large number of URLs we will be storing, a single cache may not be sufficient to meet our latency requirements. In this case, our key/value pairs will need to be partitioned across multiple cache instances. To do this, we will need to use a hashing algorithm based on the short URL which would enable the UrlRetrievalService to know which instance of the cache to call to find the relevant long URL.
Within the read replica of the database, we will need to make sure we have sufficient indexes on the short URLS, long URLs and expiration times so that read queries are fast.
Explain any trade offs you have made and why you made certain tech choices...
This is a relatively straightforward system, but complexity will rise as more instances of services are added and as the data size grows and more shards are necessary to support fast querying.
Try to discuss as many failure scenarios/bottlenecks as possible.
As outlined, we have several points of failure. Each of the UrlCreationService and UrlRetrievalService would need multiple instances to be running to ensure availability even if a specific node were to go down or become unreachable.
While the design provides for a read replica of the database, we would need to be prepared to promote the read replica in the event the main database were to go down or stop accepting writes. In such a case, a new read replica would also need to be provisioned to ensure we maintain the speed of writes and reads our service requires. Similarly, we would need to be prepared to handle a cache going down with the ability to spin up new instances of the cache and have the cache be properly filled with frequently accessed URLs.
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?
To handle multiple instances of our services, we could use Kubernetes to handle automatically spinning up services either when some go down or to spin some new instances as demand rises.
For the cache and databases, we would need our infrastructure to be able to respond to issues where those services need to be failed over or restored.