System requirements

Functional:

1. The system should provide a short URL for a long URL
2. The system should handle the expiration of old links either by deleting or archiving
3. The system should redirect users to the long URL

Non-Functional:

1. The system should have minimal latency
2. the system should scale with increased users
3. The system should be highly available

Capacity estimation

40,000 user per month (upper limit in growth phase)* 100bytes per row= 4mb per month

4mb * 12 = 48 mb per year for user table

2000 writes per month (upper limit in growth phase)*450 bytes per row= 900kb

1mb (upper limit) *12 =12 mb for a year

API design

The API's will be called after the client has reached the load balancer and the rate limiter. The implementation of load balancer and rate limiter will be discussed in the overall design part.

1. POST: create_short(long_ul,user_id) : returns 200 if we have successfully updated our db with the short URL,returns the response and the short URL. will return error if URL is invalid or user_id does not exist. If there are duplicate long_urls, we will return 200 and let the user know this already exist avoiding duplicates into our db.We will use a hash based algorithm to create the shorts. Sha 256 can be a good option here. if there are duplicate elements with the same hash but different long URLs we can append user_id or time stamps to the long URL to minimize this. (time can be better since we can keep adding time stamps if it happens a second time. In case there is an error with the write we will inform the client with an error message.
2. GET : validate_long_url(long_url) : returns 200 if URL is valid, we will use a 3rd party API to scan the URL for any malicious content, this will be called inside get_short. Will throw an error if long_url is malicious. This may be a potential bottleneck given our reliance on external apis. If the content is malicious we can block the user in our db and invalidate their previous urls.
3. GET: get_long(short_url): redirects the client to the long URL, first seeing if the URL is in the cache and if its a miss looking at our read only data base. will throw error if the URL is non-exsisitent. We should also be mindful of expired links, we can expire links after a given time frame using a job and after that time frame delete the rows by a job.will only. return if its active based on db
4. POST : create_user(user_id): creates the user with a user id. We can utilize several authentication mechanisms such as google auth

Database design

URL_TABLE:

1. primary_id ->UUID
2. user_id-> foreign key to the user (index to query based on user, for analytics, banning,and fast querying based on user)
3. short-> will have the shorter URL
4. long-> will have long URL
5. created_at -> date, add will index to help with expiring and analytics
6. is_active-> boolean to let us know if it's active, will index to help query and possibly delete after a certain time
7. access_count-> integer, updated every time we read, to help with analytics, will index to help with analytics such as where access_count> x

USER_TABLE:

1. primary_id ->UUID
2. user_id-> foreign key to the user (index to query based on user, for analytics, banning,and fast querying based on user)
3. created_count-> will increment every time user creates a short,will help identify top creators and maybe charge them after x number of creation
4. is_active-> will let us know if the user is banned
5. created_at-> help with identifying dates where their account was created
6. is_authenticated-> Help us with authentication

We will follow a single-leader replication as this design is a heavy-read design. The replication will help with redundancy.Since this is a heavy read application it makes sense to shard the database using consistent hashing based on the long url.

We will use a write-around cache to help with our reads. The write-around is because we assume many of the writes will not be popular, and writing through the cache will probably be wasted. The cache size can be 20% of our capacity to start; based on the access patterns, we may need to increase or decrease the size. We will use the LRU cache to evict since we don't need the least recently used data. For increasing or decreasing the size of our cache we can look at the top items in our cache (most accessed ) vs bottom items. If the size is similar we can increase the cache, but if there is a huge gap in access we can decrease the cache.

High-level design

Although our design uses a single leader replication we are deploying this across the globe in multiple regions. This will help improve redundancy and improve latency.We will use multi region data replication to improve consistency. Each region will have its own leader and followers and changes would replicate async to other regions. Since it is likely that each region will favor different links we will have region specific cache.

We will use a global load balancer followed by a regional and rate limiter as a point of entry. The rate limiter will help prevent denial of service and ensure the system is available. The load balancers first job is to route based on the nearest server, this ensures faster writes and reads.The load balancer then can either run and allocate resources based on the load on each server or use a consistent hashing protocol.We can implement the rate limiter based on IP address .If the user exceeds the limit we can display a message letting them know. In case of a failure in one region we can have the load balancer direct the traffic to another region.

Writes:

Assuming the client is authenticated, we will write to the leader and update the follower nodes for write requests. To minimize the risk of writing to the leader and not updating followers, we can only return the response when we can read from the followers. To mitigate this issue, we can implement a quorum strategy.So when majority of follower nodes have been updated we will let the client know the write was successful. In the case of a delay or time out we would first use a retry mechanism but if it persists it makes sense to inform the leader about the write not going through and ask them to repeat the process and abort the writes.

Above was assuming that the links are safe to write to our database. As stated we will use third party API's to sanitize the links and make sure they don't have any malicious content. Our reliance on third party apis introduce a single point of failure. To minimize this we can have 5 apis to utilize for our safety checks. This could potentially lead to inconsistent writes because one API could flag a link as malicious but another one could think its ok. In order to mitigate this we can have an odd number of API'S and create a voting mechanism

Reads:

Reads would follow the same protocol regarding load balancing and rate limiting as writes. We should increase rate limits for reads however because this is a heavy read system.The read requests would first have to go to the cache, if its a hit we can return the response and if its a miss we can go to our follower nodes and see if it exists if not return a message that the link does not exists and if it does we update our db and increment the value associated with reads per url.

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

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? Also you could draw a diagram using the diagramming tool to enhance your design...

Trade offs/Tech choices

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

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?