System requirements

Functional:

1. What will be the max and min length for long and short url?
2. What is daily request?

Non-Functional:

1. Scalable.
2. Uniqueness --> each short url must be unique
3. Low latency.
4. Secure.
5. Reliable.

Capacity estimation

Let's assume daily user is :

100Million

Short url length is 7 char

and long URL is 128 chars

Total record for 10 years

100M*365*10 --> 365000M--> 365Billion

Lets assume average size of each row is 100Bytes

Than --> 365B*100 --> 36500GB --> 35.5TB

Lets say we have 3 replicas

3*35.6TB --> ~100TB

Transaction per second

100M/86400 --> 1100 TPS

Lets say 10:1 is read and write ration

so Overall TPS will be 1100*10 --> 11000TPS

We are using base 62 to convert short url

Total unique possibilities is. 62^7 --> 3.5Trillion

API design

Api to generate short URL

Method : POST

API : /v1/generateUrl

Request --> { url : "input url"}

Response --> shortUrl

API to get long url -->

Method : GET

API : v1/getUrl/{shortURL}

Response : long url

Header will redirect status code i.e : 301

Database design

Table urls{

string : shortUrl --> Primary Key /partition Key

string : url --> unique key

date : createdAt

}

High-level design

Generate short URL :

Generate short url flow :

1.Client call to back-end service.

1. After dns resolve request land to API gateway.
2. API gateway will route request to one of the machine.
3. Machine will ask next integer from zookeeper.
4. Convert number to base 62.
5. Save it in DB and put in cache.

Get long URL :

1.Client call to back-end service.

1. After dns resolve request land to API gateway.
2. API gateway will route request to one of the machine.
3. Machine will check url in cache.
   1. If found in cache return long url
4. Else lookup in DB, if no record found return 404 status code
5. Return long url.

Request flows

Client --> API Gateway

API to URLGeneratorService and vice versa.

URLGeneratorService to Zookeper --> to get next number.

URLGeneratorService to cache --> to lookup shortURL

URLGeneratorService to Db --> To read and write data

Detailed component design

Client --> Who is requesting for data.

API Gateway -->

1. Authenticate user.
2. Rate limiter.
3. Load balancer--> route request to URLGeneratorService in round robin fashion.
4. front facing of external.

URLGeneratorService -->

1. Validate the request.
   1. If already exist return the existing short url
2. Generate new number from zookeeper.
3. Convert this number short URL using base 62.
4. Save short and long URL in DB.
5. Provide long url for short url request.

Database

1. Maintain long and short url mapping in DB.

Cache :

1. Store shortUrl : key and long url value.

Zookeeper :

1. Responsible to generate next number

Trade offs/Tech choices

Data base: As we don't need ACID property also required a scalability is priority, so NOSQL Db will be better choice. We can use Cassandra (If we have internal expertise and have strong management team), or DyanomoDB (If cost not matter)

Also DynamoDb will be help for CDN setup(If we have CDN also in AWS).

Cache : As we required 11K TPS read and write we can user Redis as distributed cache.

Put TTL least use key.

Failure scenarios/bottlenecks

1. Zookeeper will be a bottlenecks as all machine is continuously asking to generate next number. That will be bottleneck in scaling.
2. When new URL is coming for short URL, in current design it has to scan all database to check if short URL exist against this or not. That will degrade the performance.

Future improvements

1. Zookeeper -->
   1. We can bucketization the whole ranges into subranges [start,end) Ex : Let say we split each range into 1Million --> So total range will be 3.5trillion/1M --> 1Million bucket. Now we can assign each random bucket to individual machine. When we scaleUp then discovery service will take care that unused bucket only assigned to new machine. Now all read and write against this machine will be done on this range only.
2. Optimize search for new request --> Bloom filter is a good choice to identify if this URL is present or not, there is partially fault seach i.e acceptable for this usecase.