System requirements

Functional:

• System should take a long URL, ands return to the user a shortened version of this URL
• When the shortened URL is accessed, it should re-direct to the original URL.
• Each shortened URL should be unique while active.

Non-Functional:

• System should be able to handle a high number of redirections

Capacity estimation

I estimate about 200 URL creations per second and about 20,000 URL accesses per second.

API design

• shortenUrl - this API takes in a long URL and returns back the shortened version. It is a POST
• redirectUrl - this API takes in a shortened URL and returns back the long URL. It is a GET
• Both API's are restful

Database design

Since read capacity is quite high, we're going to want to go with a NoSQL database, something like DynamoDB or MongoDB. The key-value pair model will work well for our data since the key would be the shortened URL and the value would be the long form URL that we are redirecting to.

We will also want to store the creation time and last access time. This is so that we can expire dormant URLs and keep table cost lower.

High-level design

• First a user calls the shortenUrl API (POST) and passes in the long formed URL that they wish to shorten. The API Gateway will route to a Lambda Function that creates a UUID that will represent the long formed URL
• Once the Lambda Function creates the UUID, it will store the UUID (partition key) into DynamoDB with the long formed URL as the value.
• The user then receives back the shortened URL/UUID.
• When the user accesses the shortened URL, the redirectUrl (GET) API is called.
• The API gateway invokes a Lambda Function that queries the DynamoDB by the UUID (partitionKey) and gets back the long form URL. The API then returns this long form URL to redirect to.
• There should also be a caching layer to lessen the load on the database.
• We will also need a sweeper to expire and invalidate URL's that have not been accessed in over 1 year.

flowchart TD

B["User"];

C{"API Gateway"};

E["DynamoDB"];

n0["Shortening Service"];

n1["Redirecting Service"];

B --> C;

C --> B;

C --> n0;

C --> n1;

n0 --> E;

E --> n1;

n1 --> C;

n0 --> C;

Detailed component design

• Component: Shortening Service
  • This service needs to generate a UUID for an input long form URL. In the unlikely event where there is UUID collision, a new UUID can be regenerated. This can be checked with a read against DynamoDB with the generated UUID. If no collision it is safe to write.
• Component: Redirecting Service
  • This service needs to take in a UUID and fetch the long form URL and return it back. It will first check a Redis cache to determine if the long form URL is cached or not. If it is, it will fetch the URL from the cache and return it. Otherwise, it will fetch the URL from DynamoDB and cache the result into Redis with a 20 minute TTL. This keeps things inexpensive for high frequented URL's as they'd only need to be fetched from DynamoDB once every 20 minutes (or longer). For less frequent URL's the cache might be overkill. It's possible that a particular UUID results in a cache miss and is also not present in the database. In these cases, a 403 Resource Not Found will be thrown.
• Component: Sweeping service
  • We can't let all of the URL's dangle in DynamoDB if we don't want to be paying millions of dollars for unnecessary storage. This is why we store the creation time + last access time in DynamoDB. We will have a sweeper service that runs every day that queries the database for all entries that were created over 1 year ago and not accessed in the past 3 months. This is so that dormant URLs are cleared from our system to save on disk space. This also prevents collision if URLs are generated with the same UUID in the future.

Trade offs/Tech choices

• The cache can be expensive for URLs that are not accessed frequently. Luckily they are cleared from the cache within 20 minutes thanks to the TTL.

Failure scenarios/bottlenecks

• During high traffic times, we could reach DynamoDB's write limit and have requests throttled.
• We can breach lambda's provisioned concurrency and force auto scaling. This can cause potentially long cold starts leading to dropped requests.

Future improvements

• Create an SQS queue to patch up dropped requests. For example, if we exceed DynamoDB's write capacity during a high traffic period or spike, we can return the shortened UUID URL to the user, and put a message in the queue. The message can wait for 10 seconds, and then re-invoke the lambda to retry the DynamoDB write.