Requirements

Functional Requirements:

• Create a short URL for a given long URL.
• Return the long URL associated with a given short URL.

Non-Functional Requirements:

• System should be scalable using horizontal scalability
• System should handle durable
• System should be able to handle heavy traffic (high throughput, low latency)
• system should be highly available.

Capacity Estimation

• considering their are 100 new long url registered daily. So, to keep it simple if the long url takes 10 bytes of space and short url takes 5 bytes of space then in order to store 1 record in db it will take 15 bytes. As we are considering daily 100 new urls registered the space required to store 100 urls daily would be 100 * 15 = 1500 bytes minimum. If we consider a time period of lets say 5 years then it would be 1500 * 5 * 365 = 27, 37, 500 bytes. So, 28, 37, 500 bytes of memory we need to provision in order to store 5 years of data.

API Design

The API service following REST architecture performs 2 operations (endpoints):

1. POST a long url and get the short url by passing it to hash functions in order to reduce the size of it and store the mapping of long url to short url in db.
2. Make a GET call in order to get long url on the basis of short url for redirection

High-Level Design

1. When the request goes from the client the request first goes to DNS server for ip resolution (which is the public ip of load balancer).
2. When the request reaches load balancer they get distributes across instances.
3. The request reaches the server running our application.
4. If it is a post request it goes to the master DB. The entry gets created to DB and the cache gets updated in case entry did not exist earlier.
5. All the reads happens through the replica db in case of case miss.
6. The caching layer provides short url in case of cache hit.
7. We have multiple DB replicas in case master goes down slave will be promoted.

Database Design

1. We will use a SQL database like PostgreSql or any other sql DBs
2. Will use a cache layer (write though strategy) with a TTL for duration based on user subscription (if a user has a subscription of tiny url service for 1 year the long url will be returned for the short url for 2 years only).

Detailed Component Design

1. clients could be of 2 types one who posts the long url in order to get the short url (POST call to Tiny Url Server). Before we generate a short url we would if the long url that has come for it any short url exists. Since it is a one to one mapping we can create index on long url column. And to quickly check if an entry exist we can use bloom filter if it return negative result. Then we will create a short url and store an entry of it in the database.
2. clients who hit the short url in order to get the long url (GET call to Tiny Url Server)
3. tiny url service creates a mapping (entry) in the db for long and short url mapping. And algorithm (hash function) which runs in order to generate short url from long url. Tiny url service also gets the long url based on short url.
4. Cache / Redis - all the request goes to cache first if its a hit that means key exists in cache and the data is fetch from cache and returned to client. In case of cache miss if its the very first hit it calls goes to the db creates and entry in cache and response is returned to the client. If the client subscription ended we will end 3XX status code (301 resource move permanently). In case of cache hit will serve the traffic with sub milliseconds latency since it is key value store.
5. Database - SQL database to store the records (create and delete based on subscription) will store short url, long url, and timestamp
6. For Scalability -> we have multiple instance of tiny url running on different server (horizontal scaling based on CPU utilisation we will add/remove an instance) in order to increase the throughput.
7. Load Balancer -> to distribute the load across the instances. It can be used to direct the traffic to a healthy instance if the instance is down/crashed. Ensures healthy instances are always running.
8. Database replication -> we have one master database for write and one database for read. To make the data consistent we can CDC (tool like Debezium) which will use log file to replicate data in slave database (WAL). In case write DB is down we can promote slave db.