Loading...
Design a shortener service that will receive a long URL and output a short ULR of 8-10 characters maximum. The service will redirect the user from a short URL to the original URL upon access.
Scalability: the system need tot handle 200 short URL generation requests per second, and 20 000 redirects per second.
Latency: Upon the access of the short URL the system should respond within 10 ms, while generation can take up to seconds.
Availability: The system should be highly available ensuring the users can always access the redirection functionality
Consistency: The system should generate for each use the mapping from the short URL to the original URL, possibly adding some expiration policies.
Reliability: The system should always respond back with the original URL
Security: The users or clients that stored the short URL should be able to retrieve the original URL.
Long URL is about 100 bytes, short URL is about 8 bytes, create by User Id 20 bytes, expiration time 8 bytes, created time 8 bytes in sum of 144 bytes ~= 2.6 GB of new data each day
the storage for 5 years needed of 2.6 GB * 365 * 5 ~= 5 TB of data
- generateShorlURL(longUrl) -> will return the 8bytes short URL, and will store the resulting mapping between short URL and long URL into the database
- redirect(shortUrl) based on the mapping retrieved from the database the user will be redirected to the original URL
User table
SHORT URL table
For the above capacity planning and the nature of the queries: not many relations between entities a MongoDB can be used. Mongo will offer a very good read performance and also very good Write(insert) performance for what we need for this system
The generation of the URL to be unique and to be short and main the randomness effect can use a technique of prepopulating URLs into database generation by combining letters and digits.
When a request to generate a short URL is received the system will choose which pre-generated short URL Id to assign.
shortenUrl(longUrl) will be receive by the APIGatteway, the Api Gateway will route the request towards ShortenService. This service will use a prepopulated short URL and save it in the datase.
redirectUrl(shortUrl) request will be received by the Api Gateway. ApiGateway will check if the request is in the cache, at cache miss the request is routed to the MappingService which will query the database.
Cache will help reducing response times for redirects requests and also will offload the database. The cache will be interrogated first when the redirect
API Gateway added to the system to help routing the requests to the correct service that will handle it. The API gateway can also help managing rate limits for some of the clients or preventing attacks.
ShortenService will be used to generate unique short URL for the combination of long URL and user ID using an hash technique to determine if the URL was already shorten by this user or simply rejecting the new generation of the new URL.
I choose MongoDB database in favor of a relational database. MongoDB is a document database storing the elements in documents being a perfect fit for our mappings between short URL and long URL. What was traded off is the strong consistency model offered by the relational databases, now the developers having to carefully maintain the strong consistency.
Cache was used to offload the database and speed the response times but a sharding technique based on the short URL should be employed to make the whole system scalable. Also a CDN can be employed to save frequently accessed URLs on the edges near to user geo location improving latency.
One possible failure: The pre-population of the short URL is not unique multiple shards of the database, generating collisions. An scheduled task can be employed to check the uniqueness of prepopulated data.
The prepopulated data in one shard is not enough till the next population, this can be addressed using some buffers of generated data.
Cache stampede: Multiple items in the cache expire in a aproximately the same time and multiple requests come for the exactly the same data resulting in multiple requests hitting the database for exactly the same data. This can be overcome using a jitter, subsequent requests for the same data can retry later at random time interval. Another solution will be to prepopulate the cache asynchronously in the background making sure the expiration date is spread. Also another technique using locks can be used to limit to 1 the requests which load the data from the database, any subsequent requests will wait.
Circuit breaker will be used between API Gateway and Mapping service allowing the mapping service to restart in case of failures and helping in case of a network partition
Strategies to populate the cache asynchronously in the background
Sharding techniques with write and read replica which and a replication factor that will improve database availability in case of a problem