Asked in: Google, Facebook, Amazon, Adobe
Design a URL Shortening service like Tiny URL. The goal is to design a highly scalable service that could allow users to create shorter URLs, given long URLs, and have read and write functionality.
Tiny-URL is a URL-shortening web service that creates shorter aliases for long URLs. Whenever the user visits the short URL, he/she will be redirected to the original URL.
Before jumping to the solution, as an interviewee, we should always discuss with the interviewer what he/she wants. This brings us to a discussion around the requirements and features of the system.
The URL shortening service like Tiny-URL should have the following features:
This section will look at the estimate of the number of monthly requests, storage, etc. The most important thing to keep in mind here is that our system will be read-heavy, i.e., the number of reading requests per second can be up to 1000 times more than the writing request. Here, we will assume that our read/write = 100 : 1
Following will be the key components in the URL shortening application:
Traffic Estimation: We can assume that we will have 500 million new URL shortening requests per month; with a 100:1 read/write ratio, we can expect 50 billion redirections during the same period (100 * 500 million= 50 billion).
Storage Estimation: Let us assume that we are willing to store our data (short URL + long URL) for ten years then, the number of URLs we will be storing would be = 500 million * 10 * 12 = 60 billion URLs
Now, we assume the URL's length to be 120 characters (120 bytes) on average and then add 80 more bytes to store the information about the URL. Total storage requirement = 60 billion * 200 bytes = 12TB
What is the minimum length of the shortened URL to represent 60Billion URLs? We will use (a-z, A-Z, 0–9) to encode our URLs which leads us to use base62 encoding. Now, the questions arise, what should be the length of the short URL generated to cater to 60 billion requests. Let us find out.
The longer our key, the more URLs we have, and the less we have to worry about our system ever running out. However, the point of this system is to keep our URL as short as possible. Let’s stick with 7 because even if we consumed 1000 keys a second, it would take 111 years to run out.
To generate a unique short URL, we can compute it using the Unique Hash(MD5, SHA256, etc.) of the original URL and then encode using base62. If we use the MD5 algorithm as our hash function, it’ll produce a 128-bit hash value. After base62 encoding, we’ll get a string having more than seven characters. We can take the first 7 characters for the key.
MD5(Long URL) -> base62encode(128-bit hash value) -> FE66AB71IT…
There is a problem with this approach. This could (however unlikely) result in duplication or collisions in the Database. One of the solutions to this problem is to use a counter, which keeps track of a count (0–3.5 Trillion) so that in each case if we encode the counter value, there is a guarantee of no duplicates/collisions. Let’s see how we will use the counter - we will use a single server that will be responsible for maintaining a counter. Whenever the application servers receive a request, they will talk to the counter, which returns a unique number and increments the counter.
In this case, we will use a distributed systems manager, such as Zookeeper.
Let us see how a distributed systems manager like Zookeeper solves our problem:
We can use REST APIs to expose the functionality of our service. Below is an example of the definitions of the APIs for creating and deleting URLs without service:
api_dev_key(string): The API developer key of a registered account. This will be used to throttle users based on their allocated quota.
original_url(string): Original URL to be shortened.
custom_alias(string): Optional custom key for the URL.
user_name(string): Optional username to be used in the encoding.
expire_date(string): Optional expiration date for the shortened URL.
Returns (string): A successful insertion returns the shortened URL. Otherwise, it returns an error code.
url_key is a string that delineates the shortened URL that needs to be deleted. A successful deletion will return.
While designing systems, we have two types of databases (of course, we don’t want to back to the old days where file systems were used): Relational Databases or NoSQL. For our system, relational queries will not be a large part of it/occur rarely. So, here we will go with NoSQL. A NoSQL choice would be easier to scale.
Database schema: We will need two main tables: 1 to store user information and 1 to store URL information.
We know that our database is going to be read heavily. We have found a way to speed up the writing process, but the reads are still slow. So we have to find some way to speed up the reading process. Let’s see.
We can speed up our database reads by putting as much data in memory as possible, AKA a cache. This becomes important if we get massive load requests to a single link. If we have the redirect URL in memory, we can process those requests quickly. Our cache could store, let’s say, 20% of the most used URLs. When the cache is full, we would want to replace a URL with a more popular one.
A Least Recently Used (LRU) cache eviction system would be a good choice.
We can shard the cache too. This will help us store more data in memory because of the more machines. Deciding which thing goes to which shard can be done using “Hashing” or “Consistent Hashing.”
With multiple access systems like this one, a web server may not handle it yet. To solve this problem, I will use many web servers. Each web server will take a partial request from the user.
Since we have a large-scale system with multiple access happening simultaneously, a server may not handle the requests. To solve this problem, we can use multiple servers with a load balancer between “the client and the server” and “the server and the database” and avoid a single point of failure, and we will use multiple load balancers.
Initially, we can use a simple Round Robin approach that distributes incoming requests equally among backend servers. This would be the easiest to implement. A Round Robin LB does not consider server load, so our LB may still forward requests to an overloaded or slow server.
To distribute the load among servers, we will use the Least Connection Method. When a server is configured to use the least connection load balancing algorithm (or method), it selects the service with the fewest active connections.
Hence in this way, we could design a highly scalable Tiny-URL service.
Thanks to Chiranjeev and Navtosh for his contribution in creating the first version of this content. If you have any queries/doubts/feedback, please write us at firstname.lastname@example.org. Enjoy learning, Enjoy system design, Enjoy algorithms!
Subscribe to get well designed content on data structure and algorithms, machine learning, system design, object orientd programming and math.