System requirements

Functional:

• The user should be able to provide a long URL and get a shorter version of it that is unique
• The user should be able to see all the URLs they have shortened.
• The user should be able to create custom shorter URLs

Non-Functional:

• The system must redirect with minimal latency
• The system must have high availability as the long URLs will not be accessible through the short link if the system is down.

Capacity estimation

We estimate that this service will have 1 million active users and that these users create about 5 URLs per week.

Users: 1 million

Weekly Shortening requests: 5 million

Daily Shortening requests: 700k

Redirect requests: 10 x day x URL = 7 million redirects per day

Traffic Totals:

700K shortening requests per day

7 million redirects per day

~8k TPS Redirects

Storage Totals:

• a URL can have up to 2k characters. average is 100 characters which is roughly 100 bytes
• a short url has a max of 10 chars which is roughly 10 bytes

To store 700k URLs per day we will need: 70MB

To store 700k shortUrls per day we will need: 7 MB

in a span of 10 years we will need: ~280GB

for a total of 2.5 billion URLs shortened

API design

signup(email, password, full name) -> User

shortenUrl(userId, fullUrl, alias (optional)) -> ShortenedUrl

redirectUrl(urlAlias)

getShortUrls(userId)

Database design

Users

userId -> UUID (PK)

email -> varchar

password -> varchar(40) | binary()

name - >varchar

ShortUrls

urlAlias (PK) -> varchar

ownerId (FK Users) -> UUID

redirectionUrl -> varchar

created_at -> timestamp

High-level design

For the high level design we should have the following components

• An API Gateway that routes the request from the client to the servers
• The API gateway also serves as a Load Balancer and keeps state of the healthy servers
• The Control Plane service that is in charge of processing the creating requests
• a Data plane service that serves the redirection requests.

Considering that the number of URLs creates is tenfold the number of redirects on average, this design allows for a separation of concerns and independent scalability of the redirection use case. it also allows us to increase the fault tolerance of our service as issues in the control plane where URL redirects are created do not affect existing records.

Request flows

Shorten URL flow:

1. The client submits a shortenUrl request to our metadata service
2. Metadata services creates the unique id and saves the ShortUrl object in the cache using a write through cache
3. The Metadata service returns the shortened URL to the client
4. The Cache eventually writes the request to the DB

Redirect flow:

1. The client visits the short URL which calls the redirectUrl API
2. The redirection service gets the original URL from the cache and returns the response to the client with a redirect header to the original URL

Detailed component design

URL Redirection service

The URL redirection service is a simple service behind the API Gateway that checks a cache with the short URL provided and returns a special header and http code with the response telling the browser to redirect using the location header and a 301 redirect status code.

There are two types of redirects commonly used in the HTTP 301 Permanently moved and 302 Temporarily moved.

301 code tells the browser that the URL has moved permanently, therefore, the browser can cache the destination URL so subsequent requests do not need to reach to the redirection service.

302 code tells the browser that the URL has temporarily moved. therefore, each subsequent request must hit the redirection service to know the actual permanent location.

In this case, it makes sense to use 301 "Permanently Moved" because we have stablished that URLs cannot be updated so they are not expected to change. Also, it reduces the load on our service when using the URL from the same browser multiple times.

URL Metadata Service:

This Service is in charge of handling shortenUrl requests and it serves two functions:

• Shorten URLs and store the values in the database
• Provide a list of shortened URLs to the owners

To shorten a URL we have stablished that the URL must have the following characteristics:

• Be unique
• Map to a long URL based on a unique string
• Be alphanumeric

Top build the URL and determine how many characters we can have, we can do the following calculation:

We can use:

Numbers from 0-9: 10 chars

Lowercase characters: 26

uppercase chars: 26

we have 62 possible characters to mix. to figure out how long the hash value can be for our estimations, we can find the number such as 62 to the power of n, is greater than 2.5 billion URLs

62^6 = ~56 billion URLs, so our shortened version, will have a max of 6 characters plus the domain.

To accomplish this we could take two approaches:

One using a hash function - a hash function that hashes the full URL into a close to unique string. Ideally we should use a well studied and stablished hash function, like MD5, SHA that have proven statistical distribution. however, these functions produce longer hashes. For example, SHA256 produces 64 character hash. We could use only the first 6 characters of it, however, this will eventually lead to collisions. To resolve collisions, we could append an arbitrary string and check the database to see if the unique hash exists, if not succeed, and if it does exist, keep trying with other random string until we succeed.

This is expensive.

Another option is to generate a UniqueId for each shortenUrl request and encode that in base 62 (because we have 62 possible characters) since the ID will be Unique, it is guaranteed that the encoded will also be unique.

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?