Loading...
Estimate the scale of the system. Consider daily active users, read/write ratio, storage requirements, bandwidth, and any relevant QPS calculations...
Maximum # of URLs needs to considered.
When considering read to write ratio, there should be more reads than writes. More users will use the shortened URL to visit the actual site than to actual create new shortened URLs. Let's assume a ratio of 9:1 for reads to writes.
If we assume a million daily active users, then that would be 900,000 readers and 100,000 writers/new urls per day. Assuming that each URL is around 100 characters, then we'll need 100 bytes. If we have 100,000 new writes per day, then we'd need 10,000,000 bytes or 10 MB per day. For a year, we'd require around 30,000MB which would be 30GB per year. If we need to retain data for up to 5 years, then that would be 150GB for every year.
In general, we'd require 2 APIs.
One to create the shortened URL when passing in a 'long' url. This would be a POST request.
POST api/v1/shorten
The parameter would be the actual long URL
The other would be to return a redirect (either 301 or 302) with a location header pointing to the long url
GET api/v1/shortURL
The parameter would be the short URL passed in the URL.
At a high level, there are a few main components. The first is the main "shortener" which actually takes the original URL and creates a hash of it to append to our "https://tinyurl.com/{hash_value}. To properly handle requests and ensure availability, we'd have multiple instances of the actual shortener. We'd then have a load balancer to route requests from the client and as a reverse proxy from the client such that requests are routed to healthy instances. Once the long url has been hashed, the server will send a POST request to the database to create the mapping between the hash value and the long url. The server would then send "tinyurl.com/{hash_value} back to the client. That would be the initial 'shortening' phase of things.
But on the other hand, we also need to consider what happens when the user enters/visits the shortened URL. This would be the "get" request. We should be able to have the same server handle the read requests as well. Instead, the server will make a request to the database to find the relevant mapping between the hash value/shortened URL and the original URL. For now, let's assume that we want to lighten the load on the server and don't want all read requests to be sent to the server. In this case, we'd return a 301 redirect with the response of the 'long url'. Now the client's browser will automatically visit the long url whenever the shortened url is input as the address without visiting the url shortener service. This is because a 301 represents a permanent move and the browser will remember that. Any requests from the same client would automatically be directed to the long url without hitting our server.
The database is relatively straightforward.
Here, I'll choose to make use of a hashtable. The key will be the hash value and the value will be the actual 'long url'.
When creating a new record, we'll want to assign the hash value to as the key and then the long url as the actual value.
Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.
The main component of interest is the hash service as well as how to associate a hash value with an actual URL.
One thing we'll want to consider is how to associate a hash value with an actual 'url'. Assuming the url portion is made up of only alphanumeric characters in the range of A-Z, a-z and 0-9, then in total we have 26 + 26 + 10 characters, leading to 62 possible characters. The easiest way to convert from a hash value (an integer) value into characters is to do so in base 62. For example, let's assign A-Z as the values 0-25, a-z as the values 26-51, and 0-9 as 52-61. If we have a value like 63, then we'd have AB I believe. This would allow us to actually get the URL. In the database, we'd store the value of '63' as the key and the long url as the value.
One thing that we'll need to handle is collisions in terms of IDs. When multiple servers are generating hash values, there may be a chance of conflicts if there are multiple instances of the hash service. If there is only one, there is no conflict, but it becomes a bottleneck and Single point of failure. If we do have multiple instances of the hash service, we can make use of the Snowflake style ID generator. We allocate 64 bits for each hash value. Here we can allocate 41 bits for the time stamp, 10 bits for the hash server instance, and 12 bits for the actual sequence number. 12 bits allows for 2^11 different combinations per second, which should be sufficient for our use case.
The next challenge is security. Because the snowflake approach is monotonically increasing, any malicious actor can find out how we 'hash' our values and reverse engineer it. To prevent that, we may may also want to use a crypotgraphic hash to encode the generated hash value. This way, only the server knows the secret and has the key.
The other thing that's worth considering is whether or not we actually need to query the database every time. In most cases, there may be 'hotspot' shortened URLs and repeated queries to the database may overload the database. To lessen the load, we could introduce a cache in between the server and the database. Thus anytime we query the database, we'd query the cache to see if that key value pair is stored there. If yes, then we retrieve it from the cache. If not, then we retrieve from the database, and write through the cache as well. Of course, we want to ensure that the cache has a TTL for each entry to prevent stale entries.
For further caching, we can also store the redirect codes associated with a short code at the CDN level, preventing later requests from hammering our servers.
So for database partitioning, we could separate the database into different shards. The most straightforward is to assign a key via its hash value (consistent hashing). The node following the key in the hash ring will be the one assigned to 'store it'. If nodes are added and removed, then we can easily adjust a small subset of keys that will be assigned to a new node (if added) or reassigned to an existing node if removed.
For replication/availability, we can also assign read replicas for each of the nodes. In the case that the master fails, we can use a consensus algorithm to vote in a new leader and have it stand in.