System requirements

Functional:

1. Ability to take a URL and return a shorter form of the same URL
2. The shorter URL could be provided by the user or generated by our service.
3. The user can tell our service if they want the short URL to expire after some time.

Non-Functional:

1. Availability over consistency - We want our service to be available at all times instead of being consistent
2. Low Latency - Results to queries must be fetched in a short amount of time
3. Our service should be available in multiple regions of the world

Capacity estimation

Estimate the scale of the system you are going to design...

1. We are going to assume that we have to 100 reads per second and 10 write per second, a ratio of 10:1.
2. For every URL, we assume we need 100 bytes of data, there are roughly 10^6 seconds in a day, thus, we need 100 * 10^6 bytes of data in a day, which comes out to be 100 GB data per day
3. We assume that our URLs can be stored for 10 years, meaning we need 365 * 10 * 100 GB = 365000 GB or 365 TB of storage.
4. With 100 reads needed every second, we would need multiple servers to handle our requests, a single server would not do. Hence, our servers would need to be horizontally scaled.

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 301 status code in case the longer URL will permanently be redirected to the shorter URL. In this case, the shorter URL is cached in the browser and in case of future requests to the long URL, the browser does not contact the URL shortening service and redirects to the shorter URL based on the cached URL value. This can help reduce server load.
   3. We can return the 302 status code in case the longer URL has been temporarily redirected to a shorter URL. The URL may change in the future and as a result, future GET requests will be sent to our server
   4. We return 404 in case a shorter URL corresponding to the longURL is not found
2. POST /v1/shorten/:longURL/:customURL/:redirectionTime
   1. Creates a short URL for the sent long URL, return status code 200 is returned in case of success
   2. The shortURL is stored in our database along with the time up until that redirection is valid, which is specified by the value of redirectionTime. In case a value for redirectionTime is not given, we assume permanent redirection. In case a value is not present for customURL, we generate our own short URL.

Database design

Since we are more concerned with reads here and less about writes, we can utilize a database that employs a single leader replication technique. In a single leader replication scheme, the leader would be responsible for the writes and all of the followers would be replicas of the leader that would handle all of the read requests.

Single leader replication is utilized by relational databases like MySQL and PostgreSQL. Among those two, MySQL utilizes row locking to deal with competing processes, while PostgreSQL uses Serializable Snapshot Isolation, which is a form of optimistic concurrency control. PostgreSQL is utilized when we know that we are not going to be running into competing processes, hence, we utilize PostgreSQL as our database.

Inside our database, we can create a hash of the long URL which would be the short URL, add an index to shortURL so all the records in our database would be sorted based on the shortURL. All searches for the corresponding longURL would take O(log(n)) time, where n is the total number of records in our table.

classDiagram

class shortURL {

+int id (auto increment) PK

+String longURL

+String shortURL

}

High-level design

1. We employ a simple design where the request a client makes is first forwarded to a Load Balancer, the load balancer balances load using the Round Robin scheme to find the best server for handling the request. The request then reaches the appropriate application server.
2. The application server then checks a URL cache to see if the result is present in the cache, returns the response if it is, otherwise, we check the database. Since we are going to be doing more reads than writes here, we use Redis, which is an in-memory non relational database that utilizes a single leader replication scheme to serve fast reads. As our caching policy, we use Least Recently Used.
3. The write flow would be pretty similar to this

flowchart TD

B["Client"];

C{"Load Balancer"};

D["Application Server"];

E["Redis Cache"];

F["PostgreSQL Database"];

B --> C;

C --> D;

D --> E;

D --> F;

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. In the database, synchronization would be handled by PostgreSQL itself within a data-center. Among different data centers, data could be synced asynchronously since we have established that we are prioritizing availability over consistency.
2. To generate a shortURL for a longURL string, we can use the Base 62 hashing algorithm, which will make sure that the hash values that are generated are all unique and fit within a 64 bit integer.

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.

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

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.