Name: 設計短網址服務（TinyURL System Design | URL Shortner System Design Interview Question | Bitly System Design）
Uploaded: 2023-10-17T18:23:51.000Z
Duration: 24 min 36 s
Description: 設計短網址服務

未來簡單式

Hello everyone! Welcome to codeKarle. In this video we'll be talking about

形容詞最高級

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

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?

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

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

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.

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).

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,

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.

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