Design a URL Shortener System

Have you ever wondered what goes on behind the scenes of all those systems that shorten a URL?

In this post, we will examine the architecture of such systems. This is a very common question in system design interviews, and this particular one could be classified as easy level.

1 - Requirements of a URL Shortener System

The first thing we need to consider is the requirements we need to have a complete application or system.

This type of application has one main functionality:

When you click on a short URL, it redirects you to a completely different one.

Along with this main functionality, come two key features:

- The URL must be short, as that’s the premise of our application.

- The application must always be available (99.9999% uptime) and fast (<200 ms).

These are the main requirements, but others exist that are not so obvious at first glance. In an interview, it’s always beneficial to mention these points, even though in most cases you won’t need to go further:

• No two URLs can be duplicated.
• Detect malicious URLs.
• Custom aliases: instead of generating an automatic short URL, the user can specify an alias, even if it’s longer.

2 - API Design

Once we have the requirements, we move on to the creation of the API itself. Here, you'll need to mention/define or draw (depending on the interview) all the key endpoints of the API. In this case, we have four, so let's define them all.

• POST /urls: Create a new resource (in this case, a URL)
• GET /{short-url}: Reads a resource and redirects to the original URL
• PUT /urls: Modifies a resource
• DELETE /{short-url}: Deletes a resource

Things to keep in mind about this design.

For PUT /urls, you could debate what type of modification you want: should it be possible to modify the short URL with a new alias, or should that action just create a new URL? Or should it be immutable after creation? You can discuss these possibilities in an interview.

Remember, there is never just one correct or incorrect solution. What’s really important is your ability to discuss the different options.

2.1 - HTTP Status Codes for Redirection

Within our GET method, we are going to redirect to another URL. Therefore, we must specify the correct HTTP status code in our application’s response. We have two options:

1. Status code 301 for a permanent redirect. In our case, as long as the URL exists in the system, we will redirect, meaning we return a 301 code.
2. Status code 302 for a temporary redirect. In other systems, we might need a temporary redirect. In our system, we could add an expiration date (DateTime field) for the redirect, in which case we would use 302. This is an important point to mention in an interview.

Note that with a 301, browsers cache the redirect. This means that even if a user clicks the link, the request may never reach our system again, which might not be ideal for production since these links are often tied to analytics, statistics, region, etc.

Mentioning this approach, if you like this format, you may also be interested in my book Building Distributed Systems, where we explore many of the topics covered in this post in depth.

3 - Architecture Design of a URL Shortener

When creating designs, it is best to start with the most basic use case and then evolve the solution. That way, especially in an interview scenario, you have time to think and communicate with your interviewer.

For our initial requirements, we need a user to be able to create links and, of course, to be able to read, update, and delete them. So let's create a simple solution.

In this solution, we have the following entities:

• Clients: either the UI or an external client calling our API.
• A single code instance that handles all operations.
• The database.

Additionally, even though it is not shown, we also have user management for creating/updating links.

The process is straightforward: a user makes a call to the API, which creates a record in the database and returns it to the user.

If a user provided an alias, or we have implemented an expiration field, we must also consider those when creating the record.

For reading, it’s similar: the user makes a GET with the short URL and it reads from the database and returns the real URL with status code 301 (Permanent Redirect) or 302 (Found).

This simple architecture might be a good fit as a simple solution or MVP, but obviously, we cannot stop here as there are more requirements.

3.1 - Which Characters Do We Use for Short URLs and How Many?

A common solution here is to use base62. Why? Just as base 10 includes digits 0-9, base 62 includes 0-9 plus the uppercase and lowercase letters A-Z, a-z. This massively reduces the number of characters needed if you convert a base 10 number to base62.

For example, the base 10 number 123456789 converts to 8M0kX in base62.

Now that the range [0-9][A-Z][a-z] is clear, we need to determine the URL length needed. All you have to do is raise 62 to the number of target characters to see how many possible combinations there are:

62^1 = 6262^2 = 3,844..62^6 = 56 billion URLs62^7 = 3.5 trillion URLs62^8 = 218.3 trillion URLs

As you can see, each additional character increases the possibilities exponentially, and the right length is likely between 6 and 8; six seems a bit too short, and for slightly more, you can simply use 7 characters, as 8 is likely excessive.

It's very unlikely that your service will ever need a URL that long.

Additional note: in C#, with unsigned int the maximum number is 4,294,967,295—four billion, which fits in 6 characters. But you always have the option to use unsigned long, where the max value is 18,446,744,073,709,551,615 (18 quintillion), and in base62 this is 11 characters (LygHa16AHYF).

Let's assume that 7 characters are enough. The reason is simple: 3.5 trillion is 3,500,000,000,000, and in one year there are 31.5 million seconds (31,536,000), which means you would need almost 110 years at 1000 creations per second to exhaust the namespace, so it will never happen.

3.2 - Keeping Count of URLs

Previously, we discussed which and how many characters to use; now comes the moment to generate those values.

One solution might be to generate a random number, hash it, and trim to 7 characters. That value would then be saved to the database.

But that solution is likely to produce collisions at some point—not perhaps during the lifetime of your system, but technically possible.

The best solution here is to use a service coordinator. Some common options are Redis—why? Redis is a distributed, single-threaded cache, which means it performs one action at a time, so you’ll never get a collision.

But an even better solution is to use a dedicated service like Zookeeper, which autonomously handles value assignment safely and correctly.

The main reason is that scaling can get complicated, especially if you need to scale Redis. It would require heavy configuration to avoid ID collisions between instances.

That’s why we use a pattern called counter-batching, where when an instance starts, it connects to the service-coordinator and gets a range of IDs to operate with.

For example, instance 1 gets the range 1 to 1,000,000. That way, it keeps the range in memory without needing to query the coordinator every time. When instance 2 connects, Redis gives it 1,000,001 to 2,000,000, and so on. Once an instance exhausts its range, it asks Redis both to mark the range as complete and to get a new range.

Of course, the coordinator—Redis, Zookeeper, or your choice—would deliver the range in base 10, and conversion to base62 happens inside each instance.

3.3 - Scaling a URL Shortener Application

Scaling is very important today in cloud services because it allows you to keep the cost of running infrastructure at a minimum. To do this, you must be able to automatically detect when to scale your applications, either vertically or horizontally. In our case, horizontal scaling—adding instances—is most common.

But for our particular use case, it doesn’t stop there. Due to the nature of the application, our read volume will be much higher than our write volume.

For example, take Twitter—it no longer shortens URLs directly, but it used to—and let's look at a tweet by Betis:

This tweet was written once: a POST call is made with the link, and a short link is returned.

At the time the screenshot was taken, 9,400 people had seen that tweet. Assuming just 0.1% click through, that's already 9 people who have visited the link. Therefore, we can safely assume read usage is 10 times greater than write usage.

This suggests it may be worthwhile to split the API in two: one for reads and one for writes.

Additionally, when reading, we will also write URL redirection data to a distributed Redis cache. That way, subsequent calls are served from Redis, which is much faster and requires fewer resources than hitting the database every time.

The final process would be something like this:

To create new resources, the process is as follows:

1 - The client makes a call to the API Gateway.

2 - Since it’s a POST method, we use the write API’s load balancer to assign an instance.

3 - We obtain the range from the coordinator, or if we already have it, we calculate the next value.

4 - Save the record in the database and return the short URL.

4.1 - Optionally, we could also save the new URL in the distributed Redis cache that stores URL data.

Once created, let's discuss accessing the URL.

5 - The user clicks the link, and it goes to the API Gateway.

6 - As it’s a GET method, it goes to the read API’s load balancer.

7 - We check if the record is in Redis.

8 - If it’s not, we read it from the database.

9 - Add the record to Redis and return the long URL, using status code 301 or 302 to redirect the user.

Finally, when saving to the cache, we do so with a specific TTL so that the cache is not a 1:1 copy of the database, but rather keeps the most needed values.

For example, specify a TTL of two days: as in the Twitter example, most clicks will happen in the first two days, and after a week or two, clicks will dwindle to none.

With this, we have the complete architecture for a URL shortening system.