System requirements

Functional:

• given a long url, the system should be able to generate a short url and return this to the user.
• given a short url, the system should be able to redirect the request to the original url.
• the short url should have a TTL, which could optionally set by users. Default value could be 24 hours.

Non-Functional:

• fast: accessing the shortened url should be fast enough with a comparable latency as accessing original url.
• the system should be able to support a large number of users.
• the system should be available at a high rate.

Capacity estimation

Let's say the DAU is 100M users, each user would have 10 requests to shorten the urls, and 100 requests to access existing shortened urls.

• Storage: 100M * 10 * 100KB = 100M * 1MB = 100TB/day
• Write requests: 100M * 10 = 1000M requests, peak hours = 10K seconds, so requests per second = 1000M/10K = 100K per second.
• Read requests: 1M per second.

API design

Define what APIs are expected from the system...

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

data models:

• user: user_id, name, email
• shortened url: id, original_url, shortened_url, creation_time_stamp, redirect_count, expiration_time

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

This system should contain several components:

• client: which should send either a write request to shorten an URL, or read request to access a URL.
• the request will go through an API gateway and reach a certain server to process the request.
• for a write request, it goes to shorten service, which generates a unique, shortened URL for the given URL.
• the shorten results will be stored in a database which stores the original url, shortened url, and expire time.
• for a read request, it goes to redirect service, which lookup the original url from the shortened one, and redirect if valid. Otherwise return an HTTP error code.



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

flowchart TD

A[User Interface] -->|Sends URL to| B[URL Shortening Service]

B -->|Stores in| C[Database]

B -->|Forwards analytics to| D[Analytics Service]

B -->|Handles redirects via| E[Redirect Service]

E -->|Fetches original URL from| C[Database]

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

• url shortening service:

input: original url, output: shortened url.

algorithm: base62 encoding: (0-9a-zA-Z)

• pro: human readable.
• how long is the shortened url? 62^N (when N=6, it is 56.8 * 10^9 unique sequences). In our case, the total number of request are 100M * 10 = 10*9. So 6 characters should be enough to cover our use case.

• url redirect service

input: shortened url, output: redirect to original url.

flow: if the shortened url is valid: redirect with original url. If the shortened url expired or invalid, return an HTTP error code.

caching: since a shortened url would be accessed multiple times during its lifecycle, a caching service would be useful to improve the latency of this service.

Trade offs/Tech choices

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

SQL vs No-SQL for shortened url database.

• since the shortened url data is large and have no strong relational constraints, a nosql solution would be a good choice. For example we can use MongoDB to store the data.

Failure scenarios/bottlenecks

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

Future improvements

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

we can add analytics to the system.