System requirements

Functional:

• User can enter a url on the client side
• User gets back a shorter version of their url
• When anyone visits the shorter version of the url then they are redirected to the original version of the url
• URLs have a user-set expiry time with a max value

Non-Functional:

• Sub 400ms response time for new URLs
• Sub 400ms redirect time for visited URLs
• Safeguard against hash collisions so that once the user has a URL they can rely on it to only redirect to their URL
• Clean up expired data
• Scalable to tens of thousands of requests a second
• Rate limit requests to prevent abuse

Capacity estimation

The system is going to be relatively small with a few scalable parts

API design

There should be an API endpoint to convert a URL.

This is a PUT request where the request body contains the original URL and the expiry time.

It returns the new URL and the expiry time.

There should also be an API endpoint that will preform the URL redirects.

It would handle all requests to some path like https://myservice/url/* where the path after /url/ is the id of the short url

Database design

One database will have one table for URLs

Due to the simple nature of the data we'll use DynamoDB, but something like MySQL can work just as well. NoSQL databases wouldn't work as well if, later, we wanted to add features to e.g., show all URLs created by a specific user.

This table will have columns for id, original_url, new_url and ttl.

The primary key will be the new_url.

The ttl value will be used as the time to live.

We'll have another table in our database (this could also be a secondary DB like Redis or DynamoDB) to handle requests. Every time the user makes a request we'll store their ip and the request time.

This table will have columns for ip and ttl.

The primary key will be the ip.

The ttl value will be used as the time to live.

High-level design

At a high level we want to implement:

• a client with basic client side validation. Interactivity is pretty low on our page so we could use something like React, but we don't need it and normal html/css would work fine
• two lambdas, one for each API. These can be scaled separately
• a DynamoDB instance with a table for requests and a table for urls

Request flows

To get a short URL

• user lands on web page
• user enters an original url
• client side validation flags invalid characters (e.g., html tags) as an error
• user submits original url
• API Gateway receives request
• API Gateway proxies request to Lambda
• Lambda checks if user has made X requests in Y minutes and possibly rejects the request as rate limited
• Lambda sanitizes the URL
• Lambda hashes the URL with a random int and checks the DB for existing entries. The random int prevents hash collisions on two unique urls that resolve to the same hash. The check for existing entries prevents overwriting already distributed urls.
• Lambda continues to generate URLs until it finds a valid one
• Lambda returns the new URL
• Client gets the new URL
• User copies the short URL

Detailed component design

URL redirect lambda

• When hit, this lambda looks up the url entry in the DB
• If not found, it redirects to a not found page
• If found, it redirects to the original url by responding with a 302
• This lambda can be scaled independently of the url generating lambda depending on usage. AWS will automatically create more instances of this lambda. However, we have to be mindful of this because an extremely popular URL could increase our infrastructure bills so we might put a limit on our horizontal scaling to keep this in check.

Trade offs/Tech choices

I chose DynamoDB because it has easy access to the concept of ephemeral entries and because it's very fast. Our data is simple in nature with few relationships. This allows us to easily write and forget without managing foreign keys or transactions or scheduling cleanup jobs.

I chose Lambdas because they, like other serverless function technologies, can be easily scaled independently. The usage of the URL generation API will be much less used than the redirect API, therefore it has different scaling requirements. A long-running server may be more cost-effective for our service after we reach a certain level of popularity, but the difference in costs should be relatively small. We would need to do some napkin math to determine if the cost difference is significant for our business.

I chose a vanilla html/css app as our client due to the simplicity and relatively little interactivity we require. This will help us deliver a high quality and simple experience very fast with incredibly little maintenence, but it may not scale well in the long term if we want to continue to build more and more complex features into the platform. This is an acceptable tradeoff for a starting business with a single good feature.

Failure scenarios/bottlenecks

Our service can fail in the following ways:

• AWS outage results in no redirects / new generations
• DDB write/read capacity limitations may force us to consider sharding
• Invalid user input
• Running out of possible url hashes would force us to increase the length of our generated urls
• Global traffic from areas outside of our hosted infrastructure may be slow

Future improvements

We can build fault tolerance into the system by having multiple stand-by lambdas and DDB read replicas ready to handle extra requests. These lambdas and read replicas may exist in different regions to mitigate regional instability.

We can also deploy our infrastructure into different regions and have the client choose the closest API for better speeds.

We can also store the current url length in our database and run a scheduled job to update the length. When we start detecting too few urls availble (repeated failure to generate a new url) then we can update the minimum value and temporarily increase our URL size until the older URLs expire.