System requirements

Functional:

Given long url -> return shortened url

Given shortened url -> redirect to original long url

Non-Functional:

High availability: The url shortener service could run properly even some exception happens.

High scalability: The system should be highly scalable to be able to handle high volume of data

High performant: The system should perform high throughput and low latency

Capacity estimation

1. Traffic volume

1. 100 million request per day
2. Each shortened URL accessed 10 times

Total requests : 100 million * 10 = 1 billion requests per day

2. How long is the shortened url?

As short as possible

3. What characters are allowed in the shortened url?

A-Z a-z 0-9

4.Write operation per second: 1 billion / 24 /3600 =~ 11600

5. Read operation:

1. Assuming radio of read operation to write operation is 10 : 1, so the read operation per second is 116000
2. Assume average url lengh is 100 bytes
3. Assume url shortener service will run for 10 years, so 1 billion * 365 * 10 = 3.65 trillion

Total storage for 10 years is 100 bytes * 3.65 trillion is 365 PB

API design

1. Shorten long url

Post:

/api/v1/data/shorten

request payload:

{longUrl: long url string}

return: shorten url

1. Get shorten url

Get:

/api/v1/shortUrl

return: long url

Database design

Apprently, this is a read heavy system, so the relational database is the better option. However, due to this high volume of request per second, even we can scale the relational database horizentally we still may suffer from the distributed transactions, so I prefer the highly scalable and highly available non-relational database instead, for example, cassandra.

We also need Redis to be the cache center sit between database and applications to reduce the pressure for the database and speed up the processing time, the cache strategy we can use cache-aside for simplicity, and use LRU for the expiring strategy to evit the less frequently used data

Design:

Id: 123

shortUrl: tinyUrl

longUrl: xxxx/xxxx/xxxx

High-level design

Request flows

Short url generation flow:

1. The client would make the request of the short url generation and check the nearest CDN cache center whether it have the url, and return it directly if url present
2. If don't have it in CDN, the request will be sending to the load balancer and distributed to the one of the application server depends on the routing strategies.
3. Server will handle and process the request and check whether Redis (cache-aside) have the value, return it if url present
4. Otherwise the requests will be sending to the Database and check whether we can get the url from there, and return it if url present in the Database
5. If also absent in the database, the server will generate the shorten url and return to the client
6. Meanwhile an asynchronized thread will take the url and persist into the database, and also update the cache.

Short url redirect flow:

1. The client would make the request to the nearest CDN cache center and redirect to the long url if present
2. If not, request will be sending through load balancer to the corresponding application
3. Application will take and process the request and check whether the url present in Redis, and redirect to the long url if present
4. If not, make the request to the database and redirect to the long url if present
5. If also not in the database, return failed response

We can use bloom filter to check whether url is not exist in the database to further reduce the pressure of the database

Detailed component design

Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...

Service design:

1. How to make the shorten url unique?

Hash + collision resolution

Cache design:

1. How would you design the data structure to be stored in the cache?

we can use hash structure of Redis to store it, key is shorten url, value is long url

Trade offs/Tech choices

1. Make the short url unique: in approach of Hash and collision that we were selected to make the shorten url unique, we will send the long url + pre defined string request back to the application and repeat the whole process, it will leads to the high volume of request and may overwhelming our application if request traffic is very high. Other approachs dont have to repeat the whole process, but there are some other complexities also, so there are some trade offs and we should utilize them based on our needs.
2. Databases: There are always a battle between Relational database and non-relational databse, I'll use non-relational database in current design to handle such the high traffic as per our needs, we'll lose the transactions but we dont care it so much, but we can benifit from the advantage of utilizing non-relational database such as high-scalibility and high-availability, and also for read operations if the data in SSTables.
3. Scale-up the application server or scale-out? If the resources of one single server is sufficient, we can Scale-up more than one application in one single server. If all servers have same resources and dont have too much extral resources to be used, we can scale-out the application instance accross all servers.

Failure scenarios/bottlenecks

1. For server, If volume is very high, it might overwhelm our application. We can horizentally scale the application and mitigate the pressure of single application
2. For CDN, If volume is very high, we might need to buy more CDN instances to handle that
3. For Cache, if volume is very high, we can use Redis Cluster to make the whole Cache center highly available (three masters three slaves)
4. If everything we've tried still make the database not able to handle such the high volume, we can use leader-less replication to replicate the instance of database, and make the read process to be hitted to the master nodes and slave nodes as well, and write operation only go through the master node to avoid distributed transactions which is very expensive and would introduced much more complexities.

Future improvements

1. Build a monitor system to track the metrics of the whole distributed system;