Loading...
Short URL generation: Our service should be able to generate a unique shorter alias of the given URL
Redirection: Given a short link, our system should be able to redirect the user to the original URL
Custome short links: Users should be able to generatge custom short links for their URLs using our system.
Deletion: Users should be able to delete a short link generated by our system, given the rights.
Update: Users shold be able to update the long URL associated with the short link, given the proper rights.
Expiry TIme: there must be a default expiration time for the short links, but users should be able to set the expiration time based on their requirements.
Availability: Our system should be highly available, because even a fraction of the second downtime would result in URL redirection failures. Since our system's domain is in URLs, we don't have the leverage of downtime and our design must have fault-tolerance conditions instilled in it.
Scalability: Our system should be horizontally scalable with increasing demand.
Readability: The short links generated by our system should be easily readable, distinguishable and type-able
Latency: The system perform at low latency to provide the user with a smooth experience.
Unpredictability: From a security standpoint, the short links generated by our system should be highly unpredictable. This ensures that the next-in-line short URL is not serially produced, eliminating the possibility of someone guessing all the short URLs that our system has ever produced or will produce.
To expose the functionality of our service, we can use REST APIs for the following features:
Shortening a URL
We can create new short URLs with the following definition:
shortURL(api_dev_key, original_url, custom_alias=none, expiry_date=none)
A successful insertion returns the user shortened URL. Otherwise, the system returns an appropriate error code to the user.
Redirecting a short URL
To redirect a short URL, the REST API's definition will be:
redirectURL(api_dev_key, url_key)
A successful redirection lands the user to the original URL associated with the url_key.
Deleting a short URL
similarly, to delete a short URL, the REST API's definition will be:
deleteURL(api_dev_key, url_key)
A successful deletion returns a system message, URL Removed, conveying the successful URL removal from the system.
Short URL generator:
Our short URL generator will comprise a building block and and an additional component:
We build a sequencer in our building blocks section to generate 64-bit unique numeric IDs. However, our proposed design require 64-bit alphanumeric short URLs in base-58. To convert the numeric (base-10) IDs to alphanumeric (base-58), we'll need a base-10 for the base-58 encoder.
Load Balancing: We can employ Global Server Load Balancing (GSLB) apart from local load balancing to improve availability. Since we have plenty of time between a short URL being generated and subsequently accessed, we can safely assume that out DB is geographically consistent and that distributing requests globally won't cause any issues.
Cache: For our specific read-intensive design problem, memcached is the best choice for a cache solution. We require a simple, horizontally scalable cache system with minimal data structure requirements. Moreover, we'll have a data-center-specific caching layer to handle native requests. Having a global caching layer will result in higher latency.
Rate Limiter: Limiting each user's quota is preferable for adding a security layer to our system. We can achieve this by uniquely identifying users through their unique api_dev_key and applying one of the rate-limiting algorithms.
Encoder for TinyURL
Our sequencer generates a 64-bit ID in base-10, which can be converted to a base-64 short URL. Base-64 is he most common encoding for alphanumeric string generation. However, there are some inherent issues with sticking to the base-64 for this design problem: the generated short URL might have readability issues because of look-alike characters. Characters like 0 and O, I and l can be confused while characters like + and / should be avoided because of other system-dependent encodings.
Converting base-10 to base-58
We keep dividing the base-10 number by 58, making note of the remainder at each step we stop where there is no remainder left. Then we assign the character indexes to the remainders, starting from assigning the recent most remainder to the left-most place and the oldest remainder to the right-most place.
Example: Let's assume that the selected unique ID is 2468135791013.
Base-10 = 2468135791013
Base-58 = [1][6][48][20][41][4][6][17]
Base-58 =27qMi57J
Converting base-58 to base-10
The process of converting a base-58 number into a base-10 number is also straightforward. We just need to multiply each character index by the number of 58s that position holds, and add all the individual multiplication results.
Example:
Base-58 =27qMi57J
Base-10 = 17+348+13456+7999592+226329920+31505124864+228412155264+2207984137552
Base-10 = 2468135791013
For services like URL shortening, there isn't a lot of data to store. However, the storage has to be horizontally scalable. The type of data we need to store includes:
User details
Mappings of the URLs, that is, the long URLs that are mapped onto short URLs.
NoSQL is a suitable choice for storing data. In particular, MongoDB is a good choice for the following reasons: