System requirements

Functional:

Functions requirements for URL service

1. Given a long url , provide a shortened version of that URL
2. URL redirection (when user inputs shortened url in browser redirect to original url
3. Shortened url should be unique in the sense there should be one-to-one mapping between a long URL and shortened URL

Non-Functional:

List non-functional requirements for the system...

1. Service should be highly available.
2. Scalable , service should scale as the traffic grows
3. Fault tolerant , Service should be able to handle all levels of failure like DB level (Database down) , Application Level (Server crash)

Capacity estimation

Assuming 100 Million urls are generated in a day

1. Storage reqs

-> Write operation on the database = 100M/24/3600 = 1160

Now the nature of service is such that , reads will be more than write , let us assume that ratio is 10:1 for one write there will be 10 read operations

-> Read operation = 11600

Avg Len of URL = 100 Chars

1 URL needs = 100Bytes

one day storage requirement = 100 * 100M = 10GB

API design

There are two major APIs to support

1. POST - api/v1/data/shorten (This api takes in the input in Json format as a post request and returns the shortened URL

Input => Long URL

Output => Shortened URL

2 . GET - api/v1/shortUrl (This API is the redirection service that maps the shortened URL generated by POST request to long original url and redirects the user to the web page

Input => Shortened URL

Output => Long URL

Database design

As a starting nature of the data points to using a simple hashtable , but that is not practical for real time scnarios. We will use RDMS to store the Mappings , we will only focus on the data model of the core URL shortening service as of now. Lets name the table that we use to store the data as urls

Data Model -

shortened_url PK(primary key) - varchar

long_url - varchar

created_at - timestamp

expires_at - timestamp

user_id - varchar (optional if we track users to generate analytical services on top of URL shortener service)

shortened_url PK(primary key) - varchar this is chosen as primary key because access pattern is read by shortened url the get api which is read api as mentioned in Capacity estimation that reads to writes are 10:1 , get api needs shortened_url as the primary key.

High-level design

We will start with a basic design and then deep - dive into the components critical to the system

Basic flow of the system is as follows

Let us assume the short URL looks like this: www.tinyurl.com/{hashValue}. To support the URL shortening use case, we must find a hash function fx that maps a long URL to the *hashValue*.

The hash function must satisfy the following requirements:

• Each longURL must be hashed to one hashValue.
• Each hashValue can be mapped back to the longURL.

Hash function

Hash function is used to hash a long URL to a short URL, also known as hashValue.

Hash value length

The hashValue consists of characters from [0-9, a-z, A-Z], containing 10 + 26 + 26 = 62 possible characters. To figure out the length of hashValue, find the smallest n such that 62^n ≥ 365 billion. The system must support up to 365 billion URLs based on the back of the envelope estimation. Table 1 shows the length of hashValue and the corresponding maximal number of URLs it can support.

To shorten a long URL, we should implement a hash function that hashes a long URL to a 7-character string. A straightforward solution is to use well-known hash functions like CRC32, MD5, or SHA-1. The following table compares the hash results after applying different hash functions on this URL:

Base 62 conversion

Base conversion is another approach commonly used for URL shorteners. Base conversion helps to convert the same number between its different number representation systems. Base 62 conversion is used as there are 62 possible characters for hashValue. Let us use an example to explain how the conversion works: convert 11157₁₀ to base 62 representation (11157₁₀ represents 11157 in a base 10 system).

• From its name, base 62 is a way of using 62 characters for encoding. The mappings are: 0-0, ..., 9-9, 10-a, 11-b, ..., 35-z, 36-A, ..., 61-Z, where ‘a’ stands for 10, ‘Z’ stands for 61, etc.
• 11157₁₀ = 2 x 62² + 55 x 62¹ + 59 x 62⁰ = [2, 55, 59] -> [2, T, X] in base 62 representation. Figure 6 shows the conversation process.

1. longURL is the input.

2. The system checks if the longURL is in the database.

3. If it is, it means the longURL was converted to shortURL before. In this case, fetch the shortURL from the database and return it to the client.

4. If not, the longURL is new. A new unique ID (primary key) Is generated by the unique ID generator.

5. Convert the ID to shortURL with base 62 conversion.

6. Create a new database row with the ID, shortURL, and longURL.

To make the flow easier to understand, let us look at a concrete example.

• Assuming the input longURL is: https://en.wikipedia.org/wiki/Systems_design
• Unique ID generator returns ID: 2009215674938.
• Convert the ID to shortURL using the base 62 conversion. ID (2009215674938) is converted to “zn9edcu”.
• Save ID, shortURL, and longURL to the database 

The distributed unique ID generator is worth mentioning. Its primary function is to generate globally unique IDs, which are used for creating shortURLs. In a highly distributed environment, implementing a unique ID generator is challenging

Detailed component design

The flow of URL redirecting is summarized as follows:

1. A user clicks a short URL link: https://tinyurl.com/zn9edcu

2. The load balancer forwards the request to web servers.

3. If a shortURL is already in the cache, return the longURL directly.

4. If a shortURL is not in the cache, fetch the longURL from the database. If it is not in the database, it is likely a user entered an invalid shortURL.

5. The longURL is returned to the user.

• Rate limiter: A potential security problem we could face is that malicious users send an overwhelmingly large number of URL shortening requests. Rate limiter helps to filter out requests based on IP address or other filtering rules. If you want to refresh your memory about rate limiting, refer to the “Design a rate limiter” chapter.
• Web server scaling: Since the web tier is stateless, it is easy to scale the web tier by adding or removing web servers.

Trade offs/Tech choices

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

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?