System requirements

Functional:

• Shorten URL
• Redirect URL
• URL Expiration
• Analytics

Non-Functional:

• Availability
• Response Time --> low response time (esp. redirect functionality, preferably < 10ms)
• Scalability
• Durability

Capacity estimation

We're going to do back-of-the-envelop estimation here :

• Assuming there are atleast 1 Million of Daily Active Users
• Assuming on average users generate 2 shortUrls per day, and the maximum of shortUrls that a user can generate is 10.
• QPS = 2 * 1.000.000 / 24 / 3600 = 11.57 = ~24
• Peak QPS = 5 * 24 = ~120
• 10 years of storage for URLs = 10 * 2 * 1.000.000 * 365 = ~7.300.000.000 records.

API design

There are gonna be 2 main API for the system, that are :

• POST /api/v1/shorten-url with body payload of the longUrl as a string, with response code 201
• GET /api/v1/get-long-url/{shortenUrl}, shortenUrl here is a string, this will return a response code 302 redirect (no browser caching) because we're going to implement analytics such as click rate, etc.

Database design

So we're going to use SQL database because our data will be in a fixed schema, that mainly will be containing shortUrl (string) and longUrl (string) as the columns. In order to, reduce latency, we also going to implement in-memory data store a.k.a caching (with key-value pair of shortUrl and longUrl respectively), especially for frequently accessed data (our caching mechanism will be LFU).

High-level design

Already created in the high level diagram.

Request flows

1. User will first access the domain in the browser, and the DNS will return the public IP Address of the load balancer.
2. The load balancer then distributes the requests evenly across the web servers.
3. The web server then will check if the shortUrl available in the cache or no, if no fetch the data in the database, if still not available, then the shortUrl is invalid.
4. Return the longUrl back to the client with redirection (302 redirect status code).

Detailed component design

Continuing from the current high level diagram, in-depth, :

• There will be a hashing process in order to transform the long url into the short url (hashed). After the hashing process is done, we need to check if the hashed url is already available in the database or no, if no then store it, if yes then re-hash it again. There are a lot of hashing technique that we can use, and the most suitable technique for this scenario is base 62 conversion. The hashValue will contains characters of [a-z = 26; A-Z = 26, 0-9 = 10] so there are gonna be 26 + 26 + 10 = 62 of possible characters. Next, we need to find the length of the hashValue that can support 7.3 billions of records (10 years storage). Find n which 62^n is the closest but more than or equals to 7.3 billions. We found n is 6. So the hashValue length is going to be 6 characters.
• We implemented auto-scaling in the web servers, so it can horizontally scale the web servers automatically when there are a lot of requests or least of requests.
• In each web server, we implement Authentication to make sure only the authenticated and appropriate client can access the API, and we also implement Rate Limiter to limit user requests and also to prevent DDoS attacks. It also can be an efficient mechanism if there is gonna be a peak burst of requests at a certain time.
• We implemented cache here to make querying more fast and efficient because it stores data in-memory not in disk, especially frequently fetched data.
• We also make sure that our Cache and DB is scalable because we do horizontal scaling in our DB, especially using sharding technique to make sure the data is distributed evenly inside each shard and can make querying more efficient. Celebrities data (data that are popular to be accessed) are also handled perfectly here.

Trade offs/Tech choices

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

Failure scenarios/bottlenecks

• Bottleneck can occur on the load balancer when there are a lot of users accessing the same load balancer.
• There is no SPF, because we horizontally scaled all of our components/servers, so if one is down, there are still the others.

Future improvements

• To solve the bottleneck on the load balancer, we can horizontally scale the load balancer into consisting of more than one load balancer. For instance, we can horizontally scale the load balancer based on its region, e.g. Load Balancer (for North America), Load Balancer (for South America), and so on.