System requirements

Functional:

• Generate shortened URL
• Accessing shortened URL

Non-Functional:

• Scalability
• Availability
• Security
• Rate limiting
• Performance
• Monitoring

Capacity estimation

• 1 billion shortened URL's per day
• 365 billion shortened URL's per year
• Assuming we store url's for 5 years, a shortened url length of 7 (using lowercase, uppercase,and numbers in our url) would be sufficient
• 62^7 gives us around 3.5 trillion unique url's
• We would need ~24.5 TB to store the shortened urls and ~245 TB to store the redirect url giving us a total of 269.5 TB of data storage needs.
• 
  

API design

• PUT: createUrl(redirectUrl)
• redirectUrl: The URL the shortened URL will redirect to
• GET: /(shortenedUrl)
• shortenedUrl: The URL code to redirect to its un-shortened counter-part

Database design

We will be using a NoSQL key-value database to store our data. It is quick to access and write to since we don't have any relational entities.

Key / value

shortened_url(key): {

redirect_url: the redirect url

created_at: The timestamp at which the shortened_url was created

}

High-level design

Building blocks:

• NoSQL database (Redis/Memcached)
• Range handler (for serving ranges of shortened urls to different shards)
• LRU Cache (for serving popular shortened url's quick)
• Rate limiter (to prevent DoS/DoR attacks)
• Load balancer (L3)

Request flows

Generating shortened URL

1. Client can make a request to createUrl to create a shortened URL.
2. Application server will input the url submitted by the user to the database where the range handler will allow the database to assign the url to an empty shortened URL.
3. The database will return the shortened url to the application server where it will then forward it to the cache asynchronously as well as return it to the user

Accessing a shortened URL:

1. Client will make a put request using the shortened URL code.
2. The Application server will check if the code exists in the cache.
3. If it does it will return the code to the user
4. If not, it will request the sharded database for the code and input it into the database while also returning it to the user.

Detailed component design

The rate limitter will protect us from DoS attacks by mitigating quick bursts of traffic. It will also protect our limited short codes from getting depleted too quick by disallowing clients from making too many shortened urls too quickly

The L3 load balancer will sit at the network layer where it will efficiently route traffic with little overhead.

The Database will be a sharded redis database. Redis has built-in support for sharding as well as replication so that abstraction will result in less difficulties when integrating.

The range handler will allocated a range of shortened url codes to each sharded db instance. This is so we don't have any overlap or fighting for shortened url codes. There will also be a lower chance of conflicting codes.

Trade offs/Tech choices

I chose to use redis compared to memcached since redis has more built-in abstractions for sharding/replication.

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?