possibly one of the most common system design interview question.

So let's see how do we design a URL shortening service, something very similar to tinyurl.com.

Let's start with the functional (FRs) and non functional requirements (NFRs).

This is a fairly straightforward problem. You have these two functional requirements -

given a long URL, you get a short URL. So, when somebody wants to shorten the URL,

they'll give you a long URL and you need to return a shorter URL for that.

On the other side, when somebody hits a short URL then you basically redirect the

person to the longer URL, which is the second point.

On the non-functional side, this service needs to be highly available and it should work at a very

low latency. Because, let's just say, we were building it for a Facebook or a Twitter kind of a scenario,

it would just be a bad experience if it just takes a lot of time to respond.

And this being a very platform kind of a component,

it needs to be always available and respond back in a very short time.

The very first thing to answer is - What should be the length of our short URL?

That depends upon the scale that we need to build this system for.

If we're just told a couple of hundreds of URLs, maybe 2-3 characters are more than enough.

But if you are building it at a Google scale or a Facebook scale,

then we need to think over what should be the length of our short URL.

Because we should not run out of the short URLs.

Another option is - we build a system agnostic of the length and we start from somewhere

and it keeps on incrementing.

But let's start with a fixed length to start.

The very first question you need to ask your interviewer is - What is the traffic you are looking at?

How many unique URLs will come to you for shortening?

Probably every day, every month, something of some number.

Until what duration you need to support that?

Let's just assume that -

Once a URL is converted into a shorter URL, you need to save it for at least next ten years.

Sounds a bit too much, but let's just take it as a number, okay.

With that in mind, let's look at how can we come up with the potential length.

So, let's just say that your interviewer tells you that there are 'X'

number of requests that come to you every second.

So, (X * 60) is the number of requests. These are basically the number of short

URLs that you have to generate.

So, these are the number of requests that come to you in a minute.

These are the number of requests that come to you in an hour.

Multiplying by 24 gives you the number of requests in a day.

Multiplying by 365 gives you the number of requests in a year. Multiplying by 10 years.

Whatever this number would be, you should be able to build a system which can handle

these number of unique requests.

Let's just say this number is 'Y'. Now, the next question to ask is -

What all characters can you include in the short URL? Should it be just numbers? Could it be alphabets?

Could it be capital alphabets and small case alphabets? What all is allowed?

Generally, people take [A to Z], [a to z] and numbers.

So maybe we can stick to that but you could ask your interviewer and then you could come up with

a set of, basically a character set that is allowed for short URLs.

For now, let us assume that we'll take [a to z], [A to Z] and numbers [0 to 9].

These are 62 characters which you can use in the short URL.

Now, you need to have some length, you need to come up with a length which can handle

these number of URLs, these number of unique combinations of these 62 characters.

Let's just say if the length was 1, then you can support 62 URLs.

Because there is one possibility each.

If the length of the short URL is 2, then you can support (62 ^ 2), which is some number let's say.

Basically, you need to come up with a number where (62 ^ n) is greater than this number Y.

You solve this equation and you get the answer to n. n would be log62(Y).

The feeling of it.

Let's say, if this number comes down to be 4.5, then you take n = 5 so you will create short URLs of length 5.

As a general number, (62 ^ 6) is somewhere around 58 billion if I am not wrong

and (62 ^ 7) is somewhere around 3.5 trillion. Both of these are very massive numbers.

Depending upon what is your use case, you can come up with some length.

Let's just say, for our use case, we will stick to 7 characters.

Generally, I have seen it's a standard that these short URLs generally use 7 characters, may be more at times.

But we will stick to 7 characters and we will be able to support 3.5 trillion unique URLs.

That I am assuming is more than this number (Y).

If it so happens that this Y is even more, then you can probably take 8 characters,

9 characters or whatever.

Now, let's look at one of the potential architectures that can solve this problem.

This is not a final version. We will iterate over it.

So, let's just say, there is this UI, which takes the long URL as input and gives back the short URL.

So, it will call the Short URL Service. There'll be multiple instances of this service, which somehow

generates a short URL and stores it in the database and returns the short URL to the customer.

On the other side, this could also be used when somebody hits a short URL wherein the Short URL Service

would fetch the long URLs from the database and then redirect the user to the longer URL.

This looks nice.

But then we have not covered one important point that how does this service really generate a short URL.

Even though we had those 62 characters, for all the communication further we'll just assume,

we'll just use numbers so that it's easy to calculate and think over it.

Let's just say, there are multiple instances of this service and all of them are getting some requests.

This service could also generate a number 111, this service could also generate a number 111

and then we will end up with a collision.

If two services generate a same short URL for two requests then we have a problem.

In technical terms it's called a collision but for us it's a problem

because we cannot have one short URL pointing to two long URLs.

You can say that the possible solution could be that we first check in the database and then you know

kind of retry. That would be fine but then the problem is that's not really efficient.

What we need is a predictable way to generate a short URL knowing that there would be no collisions at all.

One very simple way to do that is using one of the features of Redis.

So let's just say, we use a Redis cluster and all of these services request a number from Redis.

Redis makes sure that it will always return a unique number. So basically what it will do is -

it will start the counting from 1 all the way up to billions, trillions, whatever.

And each time it gets a request, it increments the counter and responds back.

We will make sure that all of these guys are getting unique numbers and from

unique number at base 10, they can convert to base 62 and generate the short URL.

Now that would work fine but then we have a problem.

The problem is that first of all, everybody now is connecting to Redis.

So, we have Redis under a huge amount of load.

Second problem is - remember one of the important key things of any system design interview,

you should never create a single point of failure.

What is happening is - in all the requests that have to generate a short URL, this Redis becomes a single point of failure

and there is no backup to it. If this goes down then there is no way we can recover, which is a problem.

You can argue that we can have multiple Redis but that's also tricky.

Moreover, if the scale becomes beyond the capacity of one Redis machine, then we are in much bigger problem.

Why? Because, let's say, if one Redis is not able to scale to the latency requirements that we wanted to,

this will again start choking the whole system.

Another alternate is - that we keep multiple Redis that will give us high availability and it will give us

better performance because now there are multiple machines and some of these

machines will talk to this Redis and let's say this machine talks to this Redis.

This would work just fine till the time these Redis don't start generating duplicate numbers.

If both the Redis are starting from the same index, again they'll start generating duplicates.

What we need to do is - somehow make sure that both these Redis do not generate a same number.

One very simple way is - to give a series to this Redis, another series to this Redis to start with.

That would work fine. But, what if you have to add a third Redis.

Now it becomes complicated. Now you need somebody to manage what series are being given to whom.

Plus once you have that management piece, we might as well try to get away from Redis.

Let's try to look at a slightly more advanced system which can generate unique URLs without using a Redis,

without having a single point of failure.

Let's look at one of the possible solutions which can solve this problem.

Remember, what we need. Whenever we get a long URL and we need to convert it to a short URL,

we basically need to make sure that our service machine should be able to generate a unique number,

which will never ever get repeated even by any other instance of the service.

So, each of these two service instances should generate a number, which other ones will never ever generate.

Convert that number from base 10 to base 62 and return back. This is the flow that we need.

What we've done is - again going over the UI,

so this is the, green thing is basically the Long to Short UI,

from where somebody can give a long URL and expect to get a short URL as an output.

It talks to a load balancer and behind it are multiple instances of Short URL Service.

What I am trying to now do is - I have introduced a Token Service.

The idea is all of these guys need to have a number.

And making sure that none of them, none of the other machines generate the same number.

One of the simple ways to do that is -assign ranges to each of the machines.

I can say that - this Short URL Service will request a token range from Token Service.

Each time Token Service gets a request, it will run on a single threaded model

and it will give a range to any of the service instances.

Let's say, it says that, I am giving a range (1 - 1,000) to this machine.

Now, this machine on startup will also call Token Service.

So, all of these services call Token Service either when they start up

or when they are running out of the range.

Now, let's say, this service got a range from (1001 - 2000).

Similarly, other instances of the same service would also get some range.

This Token Service can be built on top of a MySQL, because it runs at a very low scale.

It will get a call once in a couple of hours and it will return like the ranges.

I have taken these numbers as (1 - 1,000). Realistically, it will be a bit larger number

so that at least it can run for an hour or so.

So, now Token Service has given numbers to each of these services.

Now, the flow is very simple.

Let's say, a request reaches this service. It takes the first number 1001, converts that into base 62 and

returns the output. Obviously after saving it.

The next request comes, it increments it. It takes 1002, saves it in Cassandra, returns back.

Next request comes in, it uses 1003.

Let's say, it somehow gets lots of requests, gets to 2000. At that point in time, maybe a bit before that also,

when we are closing the end of the range, it will query Token Service and get the next range.

Let's say, the next range that this service got is (5001 - 6000), let's say.

So, now it will continue processing this one.

Now, when (5001 - 6000) is assigned to this service, when this service will make a request,

it can possibly get (6001 - 7000), but it will never get this (5001 - 6000) range. Why?

Because that thing is maintained by Token Service and the way it would probably work is -

it will keep a range as a record and keep a flag, whether it is assigned or not.

In a simple MySQL, on transaction basis, you get a record. When you get a request, you take the

first unassigned token range and return that.

And because it will then sit on top of a MySQL database, it will make sure that it is always unique.

So, this becomes kind of our read flow.

Now, let's say, there is a massive amount of traffic.

All we need to do is - keep multiple instances of Token Service, at max.

Even though it might... so, there are multiple ways to scale it. First of all, we can increase the length of the range

so that it doesn't get bombarded too often. So, instead of thousands - thousands, we can allocate

millions of tokens at once so it doesn't get too many requests.

And anyway, this service will be distributed in multiple geographies at least and multiple data centers

so that this doesn't become a single point of failure.

There are some problems in this.

Possible problems are - What if this service got this (5001 - 6000) range, started working for a while,

used a couple of tokens and then it kind of got shut down and died?

Let's say, there was an Out Of Memory error and this process got killed. What happens to those tokens?

So, those tokens go away. Go away as in, there is no track record of how many tokens are being used.

All what is happening is - it is iterating over that list in-memory and assigning one token to each request.

If this service dies down, it will probably, on the same machine, it will get started up again

and the next time we will get another token range.

Let's say, third time, it gets a token range of (9001 - 10000).