System Requirements

Functional:

1. Ability to take in a URL and return a short form of the URL
2. The shorter URL could be provided by the user or generated by the service
3. The user can set an expiration time for a short URL that they generated

Non-Functional:

1. Availability over consistency - We want out service to be highly available, we are aiming for eventual consistency
2. Latency - Results to queries must be fetched in a short amount of time
3. Scalability - Our service should be easy to scale
4. Fault Tolerant - System must be partition tolerant

Capacity Estimation

1. We are going to assume that we do 100 reads per second and 10 writes per second
2. For every URL, we assume we need 100 bytes of data, there are roughly 10^5 seconds in a day, thus, we generate 10^6 URLs in a day, needing 10^8 bytes of data, which comes out to be 100 MB data per day
3. We assume URLs are stored for 10 years, meaning we need 365 * 10^8 * 10 bytes of data, which is 365 * 10^9 bytes of data, that is, 365 GB over 10 years
4. Factoring in replication, we would need at least 1000 GB or 1 TB data over 10 years

API Design

We would need two APIs, one of type GET and the other of type POST.

1. GET /v1/shorten/:shortURL
   1. Returns the long URL corresponding to the shortURL sent in the request
   2. We can return the status code 301 in case the longer URL is permanently moved to the shorter URL. In this case, the browser caches the response and uses it to fetch the long URL. Future requests for the long URL are not directed to the service. This can help us reduce server load
   3. We can use the status code 302 in case the longer URL is temporarily redirected to the shorter URL. The URL may change in the future and as a result, the request is always sent to the server
   4. We return 404 in case the shorter URL does not have a corresponding longer URL
2. POST /v1/shorted/:longURL/:customURL/:redirectionTime
   1. Creates and returns a short URL for the longer URL, returns 200 in case of success, status code of the form 4XX in case of failure
   2. The short URL is stored in the database along with the time up until which it is valid, which is specified by the value of redirectionTime. We also check if customURL is already present in our database, if it is, then we let the user know and generate a URL ourselves. If customURL and redirectionTime do not have a value, we assume that the user does not intend to provide an alias and the redirection does not have a time limit and the redirection is permanent

Database Design

1. We have already established that our system is more read heavy and less write heavy. We can utilize a database that employs single leader replication where the leader is responsible for writes and the replicas are responsible for reads. We can scale the replicas as the demand for reads grow
2. We are not going to be running into scenarios where need row level locking in our database, hence, we can go for a relational database that uses an optimistic form of concurrency control, since we never run into that scenario
3. We keep generating a unique ID which will serve as the base of our longURL and generate a hash of that and use the hash as the shorter URL
4. We cache all data in a in-memory data store like Redis

classDiagram

class url {

id int PK (auto increment)

longURL string Index

string shortURL Index

}

High-Level Design

1. We employ a simple design where the request a client makes is first forwarded to a load balancer
2. Load balancer forwards the request to an API Gateway, which sends the request to the appropriate service
3. All GET requests are forwarded to the fetch service and all the POST requests are forwarded to the URL shortening service

flowchart TD

client["Client"]

loadBalancer["Load Balancer"]

apiGateway["API Gateway"]

fetchService["Fetch Service"]

shorteningService["Shortening Service"]

database["Database"]

cache["Cache"]

client --> loadBalancer

loadBalancer --> apiGateway

apiGateway --> fetchService

apiGateway --> shorteningService

fetchService --> database

fetchService --> cache

shorteningService --> database

Request flows

sequenceDiagram Client->>+Server: Do you have the resource for me? Server->>+Cache: Do you have this resource for me? Cache->>-Server: Yes, here you goo. Server-->>-Client: 302 Redirect Server-->+Database: Do you have the request for me? Database-->>-Server: Yes, here you go Server-->>Client: 302 Redirect/404 Error

Detailed Component Design

1. As our load balancing algorithm, we use round robin since we there are no states here
2. API gateway handles rate limiting for us, gracefully rate limiting the user and letting them know that they are being rate limited
3. For our hashing algorithm, we utilize base 62 conversation
4. Our database generates a unique, we convert the number to base 62 and that string server as a shortened form of our URL
5. With base 62 conversion, we are sure that the generated URLs are unique and that they are increasing in nature
6. We utilize least recently used as our caching strategy, maximizing the number of cache hits

Trade Offs/Tech Choices

1. We are prioritizing our system for reads over writes, which is evident from the choice of our database which employs single leader replication. In case of heavy writes, our system will slow down
2. We are prioritizing availability over consistency which is again evident from the choice of our database, where we chose PostgreSQL over MySQL
3. For our cache, we use Redis

Failure Scenarios/Bottlenecks

1. Our application server upon getting a GET request, checks the cache first to see what the longer URL is for a given short URL. This can lead to cache misses that can be expensive
2. Since we are using Round Robin as our load balancing scheme, it is possible that the request could be directed to a server that is far away from the user, slowing down response times. To combat this, we can use index based load balancing using Layer 4

Future Improvements

1. We have not considered the thundering herd problem, wherein a short URL can see a sudden spike in the number of users wanting to access it. Such short URLs can be written to cache first and then the database, so that redirect requests can be served using the cache, leading to fast response times and reduced load on our database.
2. We have not considered the scenario where we would like to do analytics on the URLs and keep a count of the number of times a particular URL is accessed from our service