System requirements

Functional:

• system will receive request with long URL and must return short URL
• system will receive request with short URL and must return original long URL

Non-Functional:

• Prioritizing availability over consistency
• Low latency
• Available in in multiple regions in the world

Capacity estimation

Estimate the scale of the system you are going to design...

1. We can see that we are going to get about 100 reads per second and maybe as much as 1 write per second
2. If we have 1 read per second, to encode a URL we would probably need 8 bytes of data, assuming there is about 10 * 10 ^5 seconds in a day, we get about 8 * 10 ^ 5 Bytes of data a day which is 800 MB of data every day.
3. With 100 reads per second, we can't get away with having everything one host, I think we would need to scale beyond that

API design

1. Endpoint that receives POST request to shorten URL
   1. Request includes:
      1. URL to be shortened
      2. Any kind of association with enterprise/user?
   2. Response includes:
      1. Shortened URL
      2. Error message if we can't generate a URL
      3. code 200
2. Endpoint that receives GET request with shortened URL
   1. Request includes:
      1. Shortened URL
      2. Any kind of required enterprise/user info
   2. Response includes:
      1. Original URL
      2. Error message if we can't retrieve URL
      3. Code 302

Assumption: front end will handle actual redirection using the original URL

Database design

Because we are only concerned with two values (the original URL and the short URL), we can use a key-value store, where key is short URL and value is original URL. NoSQL works well for this and is easy to scale.

High-level design

You should identify enough components that are needed to solve the actual problem from end to end.

1. API Gateway
2. Cache
3. URL Service
4. Database

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

• Request is first received by API Gateway which will do the following
  • If POST request: will pass request along to URL Service
  • If GET request: will check the cache and if there's no hit then will send request to URL Service. Will update cache if cache miss
• URL Service will do the following
  • If POST request: will validate the inputted URL and generate a shortened URL and create new record in the DB with this URL and the original
  • If GET request: retrieve original URL from DB using request params
  • Return error if DB operations fail or if an invalid/malicious URL is submitted as part of the request

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?

1. API Gateway
   1. The gateway will handle load balancing and rate limiting
   2. It needs to be able to handle high read traffic and should not act as a single point of failure, thus we'd want some kind of redundancy at this layer
2. URL Service
   1. We want to use some kind of hashing strategy to generate short URLs
   2. Make sure we are only generating unique short URLs, they shouldn't already exist in the DB
   3. The service should validate the URL before creating a record in the DB. Is the submitted URL real and is it a safe site to visit?
3. Cache:
   1. Employing a cache-aside strategy, this could cause some latency in reads, but for now seems acceptable
   2. We'll use a LRU invalidation strategy as it seems likely some URLs will simply be more popular/visited than others in general
4. Database:
   1. For this system I am choosing to optimize for reading rather than writing, thus I'm choosing to have one primary DB that handles writes and multiple secondary DB that can serve read requests
   2. This also serves the requirement of prioritizing availability over consistency

Trade offs/Tech choices

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

1. Optimize system for reads over writes
   1. We know that we are likely to receive more read operations than write operations in the normal course of usage. So we made certain decisions to reflect that (database replication strategy)
2. Optimizing availability over consistency: database replication strategy

Failure scenarios/bottlenecks

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

1. Writing many URLs at once can cause latency
2. System needs to be able to handle a lot of read traffic
3. Ensure we are keeping close track of our url generation
   1. Is it functioning properly?
   2. Do we have duplicates?
   3. Have we run out of short URLs?

Future improvements

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

1. Could add more primary database instances that can accept writes --> consistency problems
2. Change our cache strategy based on how we see users using the system