Loading...
There will be broadly 2 APIs. We will use them as REST APIs, so that it will be easy to integrate with third parties too.
1) Create URL - createURL(longURL, apiKey, userId) This can be a POST Request
2) Get the created Short URL - This can be a Get Request. Get https://shortUrl This will return a response code of 302 instead of 301. 302 means redirect temporarily, so all redirection requests will hit the backend , and we can keep track of the most popular urls for analytics.
The argument is always whether to choose a RDBMS database or a NoSQL database. In this case, we care more about the volume of data, since we need to be able to store about 60 TB of data throughout the lifetime of the service.
The schemas that we will need to store
We can choose a NoSQL database like Cassandra or MongoDB for the database design.
At a high level,
1) Get URL Request - the client makes the API requests to a webserver to get a long Url for the short URL. The webserver checks if the tinyUrl exists in the database, if so , it returns the longUrl for that. If not, it sends a URL not found error.
2) Create the TinyURL request - The client sends a longURL to be shortened. The Webserver application shortens it and stores it in the Database.
At a high level, the above would work. But there are many Single point of failures. For example, the Webserver, the Database are all Single point of failures. There is also no cache. So we can add some loadbalancers and also add a cache.
The modified design would look like in the diagram.
Request flow for creating a tinyUrl
Request Flow for getting a longUrl for a requested shortUrl.
The TinyUrl Shortening Algorithm and Subsequent Scaling. There are number of ways to generate the unique tinyURL to store in the database.
Scaling depends on the kind of database we choose. If we use MongoDB for example for storing the tinyURLs, we can use the generated tinyURLs as the shard keys and use them to distribute the data across the various shards.MongoDB supports distributing data acorss multiple machines using shards.
If we choose a RDBMS database, sharding can be used as a scale out approach too where the database tables will be partitioned and each partition will be on a separate RDBMS server.
There will be many database instances, we could select a very large counter like 100000000 and divide them in ranges like 100000000+1 to 100000000+10M , 100000000+10M - 100000000+20M and so on. This will also ensure that there are minimal collisions and also generate unique URL encodings from the range of the counter assigned.
Zookeeper can be used to maintain the co-ordination and synchronisation between the database servers.
For caching, we can use Memcache. Caching can be implemented based on the 80-20 rule. We can start with caching 20% of the traffic and scale the cache servers based on the usage and requirements.
The trade off would lie between choosing a NoSQL database and SQL database. With a NoSQL database, we achieve eventual consistency, whereas with the SQL database we achieve consistency because of the ACID properties.
Again, the replication and sharding is easier in NoSQL databases than SQL databases.
It really depends on the kind of algorithm we choose to generate the URLs and also the amount of data that needs to be stored.
Storing the unique tinyURls in advance.
A key generation service , which can generate as many 7-character strings in advance and store it in a database. This will ensure, we don't need to encode anything on the fly for the request and just assign the unique url key for the longUrl.
In this process, we will also need to keep track of the used keys. Probably segregate them out into two separate Databases.
Analytics
When the URLs hit our backend server for redirection, we can keep track of the most requested tinyURLs and subsequently put that data in a Kafka queue for further processing and analytics.