# Requirements of TinyURL's Design

### Requirements for URL Shortening Design <a href="#requirements-for-url-shortening-design-0" id="requirements-for-url-shortening-design-0"></a>

Let’s look at the functional and non-functional requirements for the service we’ll be designing:

#### Functional requirements <a href="#functional-requirements-1" id="functional-requirements-1"></a>

* **Short URL generation**: Our service should be able to generate a unique shorter alias of the given URL.
* **Redirection**: Given a short link, our system should be able to redirect the user to the original URL.
* **Custom short links:** Users should be able to generate custom short links for their URLs using our system.
* **Deletion**: Users should be able to delete a short link generated by our system, given the rights.
* **Update**: Users should be able to update the long URL associated with the short link, given the proper rights.
* **Expiry time**: There must be a default expiration time for the short links, but users should be able to set the expiration time based on their requirements.

**Question**

As a design choice, we don’t reuse the expired short URLs. Since we don’t reuse them, why do we need to delete them from our system?

So far, we’ve kept the default expiration time to five years. If we relax that limitation and start saving the records forever, our datastore’s search index will grow without bound, and querying time from it can add noticeable latency.

\----------------

#### Non-functional requirements <a href="#non-functional-requirements-0" id="non-functional-requirements-0"></a>

* **Availability**: Our system should be highly available, because even a fraction of the second downtime would result in URL redirection failures. Since our system’s domain is in URLs, we don’t have the leverage of downtime, and our design must have fault-tolerance conditions instilled in it.
* **Scalability**: Our system should be horizontally scalable with increasing demand.
* **Readability**: The short links generated by our system should be easily readable, distinguishable, and typeable.
* **Latency**: The system should perform at low latency to provide the user with a smooth experience.
* **Unpredictability**: From a security standpoint, the short links generated by our system should be highly unpredictable. This ensures that the next-in-line short URL is not serially produced, eliminating the possibility of someone guessing all the short URLs that our system has ever produced or will produce.

**Question**

Why is producing unpredictable short URLs mandatory for our system?

The following two problems highlight the necessity of producing non-serial, unpredictable short URLs:

1. Attackers can have access to the system-level information of the short URLs’ total count, giving them a defined range to plan out their attacks. This type of internal information shouldn’t be available outside the system.
2. Our users might have used our service for generating short URLs for secret URLs. With the information above, the attackers can try to list all the short URLs, access them and gain insights about the associated long URLs, risking the secrecy of the private URLs. It will compromise the privacy of a user’s data, making our system less secure.

Hence, randomly assigning unique IDs deprives the attackers of such system insights, which are needed for enumerating and compromising the user’s private data.

\----------------

<figure><img src="https://1055613405-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MlQzjDKRh_AaQvZflWz%2Fuploads%2FTscg0O6C5xaGLHymePAJ%2FScreenshot%202023-09-06%20at%2012.52.44%20AM.png?alt=media&#x26;token=78ec8d3f-dd51-4802-92cc-6d349fa73eaa" alt=""><figcaption></figcaption></figure>

### Resource estimation <a href="#resource-estimation-0" id="resource-estimation-0"></a>

It’s better to have realistic estimations at the start. For instance, we might need to change them in the future based on the design modifications. Let’s make some assumptions to complete our estimation.

**Assumptions**

* We assume that the shortening:redirection request ratio is 1:1001:100.
* There are 200 million new URL shortening requests per month.
* A URL shortening entry requires 500 Bytes of database storage.
* Each entry will have a maximum of five years of expiry time, unless explicitly deleted.
* There are 100 million Daily Active Users (DAU).

#### Storage estimation <a href="#storage-estimation-1" id="storage-estimation-1"></a>

Since entries are saved for a time period of 5 years and there are a total of 200 million entries per month, the total entries will be approximately 12 billion.

<figure><img src="https://1055613405-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MlQzjDKRh_AaQvZflWz%2Fuploads%2F3IQ3h4VFWmuqqqbrffmO%2FScreenshot%202023-09-06%20at%2012.53.17%20AM.png?alt=media&#x26;token=417250b2-e982-4473-b4af-8cb6e35cc3cc" alt=""><figcaption></figcaption></figure>

**URL Shortening Service Storage Estimation Calculator**

| URL shortening per month | 200 | Million |
| ------------------------ | --- | ------- |
| Expiration time          | 5   | Years   |
| URL object size          | 500 | Bytes   |
| Total number of requests | f12 | Billion |
| Total storage            | f6  | TB      |

<figure><img src="https://1055613405-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MlQzjDKRh_AaQvZflWz%2Fuploads%2FHX1CNnyT8oIubd2dg6tK%2FScreenshot%202023-09-06%20at%2012.53.35%20AM.png?alt=media&#x26;token=f7258fc0-d123-425e-a3a3-e0ef71ef510e" alt=""><figcaption></figcaption></figure>

#### Query rate estimation <a href="#query-rate-estimation-0" id="query-rate-estimation-0"></a>

Based on the estimations above, we can expect 20 billion redirection requests per month.

<figure><img src="https://1055613405-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MlQzjDKRh_AaQvZflWz%2Fuploads%2FaevFYIRy13jBqneAQ91n%2FScreenshot%202023-09-06%20at%2012.54.02%20AM.png?alt=media&#x26;token=d03b9994-e5c5-44db-b100-064c7b2d2c93" alt=""><figcaption></figcaption></figure>

#### Bandwidth estimation <a href="#bandwidth-estimation-1" id="bandwidth-estimation-1"></a>

<figure><img src="https://1055613405-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MlQzjDKRh_AaQvZflWz%2Fuploads%2FAYIxnkKPIhptV6qiIwNN%2FScreenshot%202023-09-06%20at%2012.54.29%20AM.png?alt=media&#x26;token=eb1d64cf-d0ed-4a12-999d-437cac02c7c4" alt=""><figcaption></figcaption></figure>

#### Memory estimation <a href="#memory-estimation-0" id="memory-estimation-0"></a>

We need memory estimates in case we want to cache some of the frequently accessed URL redirection requests. Let’s assume a split of 80-20 in the incoming requests. 20 percent of redirection requests generate 80 percent of the traffic.

<figure><img src="https://1055613405-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MlQzjDKRh_AaQvZflWz%2Fuploads%2F2XQAOtpLu5wYWFIiA4wc%2FScreenshot%202023-09-06%20at%2012.54.52%20AM.png?alt=media&#x26;token=062d6dfd-0791-4211-9da4-a42a8d61d0d6" alt=""><figcaption></figcaption></figure>

**URL Shortening Service Estimates Calculator**

| URL shortening per month       | 200   | Million  |
| ------------------------------ | ----- | -------- |
| URL redirection per month      | f20   | Billion  |
| Query rate for URL shortening  | f76   | URLs / s |
| Query rate for URL redirection | f7600 | URLs / s |
| Single entry storage size      | 500   | Bytes    |
| Incoming data                  | f304  | Kbps     |
| Outgoing data                  | f30.4 | Mbps     |
| Cache memory                   | f66   | GB       |

#### Number of servers estimation <a href="#number-of-servers-estimation-0" id="number-of-servers-estimation-0"></a>

We adopt the same approximation discussed in the [back-of-the-envelope calculations](https://ylbbak99.gitbook.io/grokking-modern-system-design-interview/back-of-the-envelope-calculations/put-back-of-the-envelope-numbers-in-perspective) to calculate the number of servers needed: the number of daily active users and the daily user handling limit of a server are the two main factors in depicting the total number of servers required. According to the approximation, we need to divide the Daily Active Users (DAU) by 8000 to calculate the approximated number of servers.

<figure><img src="https://1055613405-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MlQzjDKRh_AaQvZflWz%2Fuploads%2FKdeN3GZOkiZBxDHMtzR3%2FScreenshot%202023-09-06%20at%2012.55.21%20AM.png?alt=media&#x26;token=d38eb9fb-eee5-4d08-930f-93268749efe2" alt=""><figcaption></figcaption></figure>

#### Summarizing estimation <a href="#summarizing-estimation-0" id="summarizing-estimation-0"></a>

Based on the assumption above, the following table summarizes our estimations:

| Type of operation   | Time estimates |
| ------------------- | -------------- |
| New URLs            | 76/s           |
| URL redirections    | 7.6 K/s        |
| Incoming data       | 304 Kbps       |
| Outgoing data       | 30.4 Mbps      |
| Storage for 5 years | 6 TB           |
| Memory for cache    | 66 GB          |
| Servers             | 12500          |

### Building blocks we will use <a href="#building-blocks-we-will-use-0" id="building-blocks-we-will-use-0"></a>

With the estimations done, we can identify the key building blocks in our design. Such a list is given below:

<figure><img src="https://1055613405-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MlQzjDKRh_AaQvZflWz%2Fuploads%2Flf69CuYJSg9EFokYLUN0%2FScreenshot%202023-09-06%20at%2012.55.45%20AM.png?alt=media&#x26;token=f0a9bed3-dc65-4987-9813-5ed6a3ae9707" alt=""><figcaption></figcaption></figure>

* [**Database(s)**](https://ylbbak99.gitbook.io/grokking-modern-system-design-interview/databases/introduction-to-databases) will be needed to store the mapping of long URLs and the corresponding short URLs.
* [**Sequencer**](https://ylbbak99.gitbook.io/grokking-modern-system-design-interview/sequencer/system-design-sequencer) will provide unique IDs that will serve as a starting point for each short URL generation.
* [**Load balancers**](https://ylbbak99.gitbook.io/grokking-modern-system-design-interview/load-balancers/introduction-to-load-balancers) at various layers will ensure smooth requests distribution among available servers.
* [**Caches**](https://ylbbak99.gitbook.io/grokking-modern-system-design-interview/distributed-cache/system-design-the-distributed-cache) will be utilized to store the most frequent short URLs related requests.
* [**Rate limiters**](https://ylbbak99.gitbook.io/grokking-modern-system-design-interview/rate-limiter/system-design-the-rate-limiter) will be used to avoid system exploitation.

Besides these building blocks, we'll also need the following additional components to achieve the desired service:

* **Servers** to handle and navigate the service requests along with running the application logic.
* A **Base-58 encoder** to transform the sequencer’s numeric output to a more readable and usable alphanumeric form.
