Requirements

Functional Requirements:

• Create a short URL for a given long URL.
• Return the long URL associated with a given short URL
• No different long URLs should map to the same short URL and vice versa
• I assume the URLs can't be more than 2000 characters
• The resulting URL is not saved in our DB

Non-Functional Requirements:

• It should be able to scale
• Low latency

API Design

The API should have two endpoints:

1. One endpoint converts a short URL to a long and we can call it shortToLong
2. The other endpoint converts a long URL to a short and we can call it longToShort

Both of them accept a string of length

High-Level Design

We need to run our algorithm on a server. We can scale up our server vertically, but this has a ceiling and also introduces a single point of failure. Assuming the API is popular, we might run into a DDoS attack, or our server might fail. Horizontal scaling is more resilient. Assuming there are not many repeated URLs, using a cache may not be appropriate. We can add a DB to store the long and short URLs, using a simple Cache strategy such as write-back, where we write directly to the DB and update the cache later. For the DB we can shard on a combination of top level domain and first character range of the domain. To make the configuration easier we can use a load balancer to balance the load between these DBs. Since DBs failing is not causing any issues to the end customers we prefer Availability over consistency. Probably replication strategy is an overkill in this case

Detailed Component Design

Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.