System requirements

Functional:

List functional requirements for the system (Ask the chat bot for hints if stuck.)...

• A user should be a able to input a URL and receive a shorted URL.
• Generated URLs should be permanent, and always continue to work
  • URL mappings should be relatively small data, so an ever increasing DB should be manageable. However, if our service were to expand in users to the point where this was infeasible, we could consider some TTL expiring system for our URLs. But for ease, we will assume they are permanent.
  • Generated URLs should be the same for the same input URL.
• Users should be able to go to our website at the shortened URL, and be redirected to the long URL.
• There is no user system necessary for our initial application.

Non-Functional:

List non-functional requirements for the system...

• We need to be highly available - we want low downtime for our service.
• We can be eventually consistent - if it takes some time for a URL to be available at the returned link, it is okay.
• Links should be redirected very quickly to the longer URL. We don't want users to be waiting at our service for a long time.

Capacity estimation

Estimate the scale of the system you are going to design...

Let's assume we have 100k users daily, and each user creates 1 unique URL per day.

Each URL will store its generated link (say a max of 32 bytes), and the given URL (an average of 100 bytes).

That is an approximate of like 32 * 100 * 100k = 320,000,000 bytes => 320 MB per day.

API design

Define what APIs are expected from the system...

There will be two main APIs in our system:

• CreateShortened(url) => shortened url ID
• GetUrlFromShortenedId(shortenedId) => URL

Our CreateShortened method should return the same value for the same URL.

Database design

Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...

Our database can use a pretty standard NoSQL DB to start. We will just use the generated ID as the key, and the value will be the long URL.

We don't need the full capabilities of a relational DB for our service, since it is basically a simple mapping of ID -> URL. Even if we want to add some metadata in the future, it should fit nicely into the NoSQL pattern, as it will be easily to add parameters to the unstructured data of the key.

The schema should be pretty simple:

UrlMapping

• id (this is the shortened URL's ID): string
• url: string

The ID here should be some simple random alpha numeric key, that is generated from the hash of the URL.

We will need to make sure we account for collisions in our hashing.

High-level design

You should identify enough components that are needed to solve the actual problem from end to end. Also remember to draw a block diagram using the diagramming tool to augment your design. If you are unfamiliar with the tool, you can simply describe your design to the chat bot and ask it to generate a starter diagram for you to modify...

Here we will have a URL generation service, that will do two things:

1. Take the given URL, hash it, resolve conflicts, and return the shortened URL
2. Take a given shortened ID and fetch the full URL.
3. Our client application will take the full URL and redirect the user to it.

Request flows

Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...

1. A user can request a shorted URL from our system, inputting a longer URL.
2. A user can visit a link at the shorted URL, and we will fetch the longer URL, and redirect the user.

Detailed component design

Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...

The URL service will hash the given URL so we can ensure that the same URL will return the same shortened ID, saving us some DB space.

If the hash hits a conflict we can easily resolve this by appending an increasing number to the end. It should be very unlikely multiple links will have so many collisions, so this should be okay.

The Database can be eventually consistent as well if we create replicas in different regions. If it takes a few seconds (even a minute) for a URL to become available in all regions, it should be fine, since people requesting shortened URLs generally want to share it on another service/website, which won't get published immediately.

Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...

A tradeoff with a NoSQL DB is that analytics might be difficult to query. If for example, we wanted to store the number of clicks a particular link got, we would not be able to do that easily without copying the data over to a more relational DB.

We also don't have any way to "remove" old URLs from the DB. Again, this choice was made assuming that links are permanent and that storing these links forever would be very minimal on DB costs.

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

In theory we might have a race condition where two people request differing URLs that hash to the same value, and only one of them wins the write. But this scenario should be relatively small, and perhaps one way to offset this is to return to the user what URL we saved to the DB by fetching it on the success page of our application.

Another failure case is the URL does not exist in the DB (in the case of a typo). In this case, we will just return a 404.

We can also add some IP address rate limited to avoid spamming from bots or malicious users.

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?

One improvement could be a caching layer + service for very commonly accessed links. If for example, a popular influencer creates a shortened link to an affiliate website, and that link gets thousands or millions of clicks, we can detect that this link is being fetched very often, and cache it for faster access.

This layer would be put in front of the url service.

Another improvement could be creating a user service/system for users to manage their created links. But in this case we would likely want to hash not only the given URL, but use the user's ID to create the shortened URL's ID to ensure a unique URL per user.