Requirements

Functional Requirements:

• Create a short URL for a given long URL.
• Return the long URL associated with a given short URL.
• Data must be save for a default time of 5 years but it is customizable by user
• Get APIs must redirect automatically the user to the returned api

Non-Functional Requirements:

• 99.99 up time
• 100 ms p99 response for Get APIs
• Should scale automatically horizontally
• Dashboard with metrics must be created to allow observability
• Automatic ticketing should be created based on metrics & defined threashold

Capacity Estimation

The biggest bottle neck would be the distributed database and the biggest issue for distributed databases is hot partitions.

Assuming a limit per partition of 3000 read hits per partition where the short URL is the partition key, my system can handle that 3000 per second per one single short url to resolve.

I think we can estimate a max number partition keys equal to the possible number of permutation using letters and number so using english alphabet that would be 26 letter + 10 number is 36 with a max length of short url of 8 char (otherwise it is too long) we have a max storage capacity of 36^8 but if I am case sensitive it i 62^8 which is a really big number and we should be able to generate a lot of keys.

Considering for the first year a traffic of 1000 tps with 20 percent write, 8 char partition key and average 100 char long key, then we can assume for the first year to have around 6 Billion entries on the first year. At an approximate sixe of 150 bytes per entry we are going to have a databse of 3 Billion X 150 bytes = 450 GB roughly which is acceptable

if we assume that the request are distributed evenly in the request, then we can have a max of 3000 read (hot partition) per second per key.

I expect to have a lot more read that write and the hot partition issue should not be an issue with traffic under 3K TPS.

Considering the high read to write ration I will put a cache in front of the DB and one in CloudFront to reduce the read load on my system.

For the table size I will have a primary key that it is the short url (8 char), then the column to store the long url (5000 char max), then the ttl to delete the data.

if we start with a traffic of 1000 TPS total I expect 80 percent to be read and 20 percent to be write. This means that if the traffic increases to 3000 tps in the new two years, the read are going to increase to 2666 tps and 333 tos of writes

API Design

we are going to have read apis, create apis, update apis and delete apis.

• CreateShortLink: this is a POST method that will contain the long link and an optional parameter that it is the custom name for the short link (if available, we can use a bloom filter in the client to quickly check if a short url is available). This will return the 2XX response with the short url if it succeded or an error message. The error will always be 4XX to avoid exposing interanal vulnerabilities and one common error to thow will be "ShortURLAlreadyInUse" if the customer give us a short link request.

This API will also take a deafult timeToLive parameter to decide how long to persist this shorten URL. Default is 5 years.

• UpdateShortLink: this patch method take as a parameter a shortURL and then new long url to make it and the optional TTL. It returns the short url if the operation succedd or a "ShortUrlNotFound" if the short url was not found
• GetLongLink: this is a get method and it will get as parameter only a short URL; It return a 3XX response if the operation succeed and it will redirect to the long url link. If the short url is not found it returns ShortUrlNotFound.
• DeleteShortURL: this is a delete method and it will take as parameter only the shortURL. It return a 204 response if suceeds or a ShortUrlNotFound if the URL was not found.

Note: CreateShortLink, UpdateShortLink and DeleteShortURL require authentication but GetLongLink does not

High-Level Design

(AWS cloud design)

I will have my service running in in ECS tasks. This will provide me low latency responses and the ability to scale up and down just starting new tasks (or pods) as traffic mandates.

the request will first go trough the load balancer that it will have a target groupt of ecs tasks to ditribute the traffic. the ECS task will read and write to dynamoDB but in between dyanamoDB and the ECS tasks I will have a DAX (DynamoDBAccelerator cache) to get faster response and reduce the use of the database). I will also use cloudFront (a CDN serice) to store common used short URL in CDN and reduce the traffic to my server.

For monitoring and alarming I will use cloudwatch and cloudwatch actions and for authentications and permission I will use amazon cognito.

To create the Key in the Database I would use an algorithm like sha-1 with collision resolution but instead of reading in the Database of the key already exists, I will use a bloom filter and then read in the DB only if needed. this will generate unique Primary keys at a low cost.

Finally, I need a rate limiter that can be implemented in API gateway using usage plans.

Database Design

Define the data model. Identify the main entities, their attributes, and relationships. Consider the choice of database type (SQL vs NoSQL) and justify your decision based on access patterns...

Detailed Component Design

the database scaling could be an issue with a lot of reads to the same Key (if a short url becomes really popular). To fix this we implemented cache in DNS and cache in DAX but the tradeoff is that we may serve outdated data to the customers.

Also, the API is returning 301 for redirecting instead of 302 which means that the web browser is going to store the redirect URL but this is also another trade off we are okay with so we can support really high traffic