System requirements

Functional:

1) Given a short URL, retrieve corresponding long URL

2) Give a long URL, generate a unique short URL.

3) The mapping between short URL and long URL should be unique.

Non-Functional:

1) Scalable: able to handle millions of users and request without performance degradation.

2) Availability: System should be highly available.

3) Performance: Redirect function should be super fast.

Capacity estimation

For functionality 1, 20000 request per second

For functionality 2, 200 request per second

including all alphabets (26) and integers (10)

8 characters ~ 36^8 ~ 2.8billion entries

assume long url is approx 100 characters

200*3600*24*365*20 ~ 0.12billion entries

Each long -> short URL conversion would include:

• Long URL (100B)
• Short URL (8B)
• Created time (8B)
• Created by user ID (20B)
• Expiration time (8B)

Each entry is 144 bytes. Round to 256 Bytes

Per day, the service would generate 200 * 3600 * 24 * 256 = 4.4GB of data.

API design

shortenURL(str long_url, user_ID, expiration_time=None): Takes a long URL and returns a short URL.

redirectURL(str short_url): Takes a short URL and returns the associated long URL.

Database design

DynamoDB : key value pair. horizontal scaling and performance driven. strongly consistent.

• Short URL (8B) - primary key
• Long URL (100B) - secondary index
• Created time (8B)
• Created by user ID (20B) - secondary index
• Expiration time (8B)

High-level design

At a higher level, we need to have two calls:

1. A shortened URL
2. A redirect URL

A shortened URL will basically allow a user to give a long URL, and the service will return a short URL.

A redirect URL service is basically a user will type in a short URL and the service will return the long URL.

Request flows

Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...

Detailed component design

Caching

Performance and scalability of redirect URLs are very important. We employ two levels of caching. Requests will naturally have locality of access, so caching will be effective. At the closest location from the clients we will have a CDN which will be storing short to long mappings for the most frequently requested URLs. For example, if a celebrity posts a short URL in their social network post this mapping should be there in the CDN and CDN can be hosted at internet exchange points. Making the response time from client quite short. It has limited storage space so it can store only a small set of frequently accessed mappings. High volume of requests are handled by CDN without even reaching the API gateway. It is quite beneficial from scalability and fault-tolerant perspectives.

At the data center, we will employ a caching node. For example, we can use Redis. We can install multiple Redis nodes, which can store a larger set of mappings. It is still faster than accessing the database. This would provide performance and scalability gains.

And both CDN and Redis cache can employ LRU (Least Recently Used) eviction algorithms to ensure that popular mappings stay in place.

Partitioning

the database and the cache should be partitioned for improved scalability so short url is a good choice for partitioning key because the services primarily look up cache and database by short url by having this as a partition key the service can find the right cache and database node to access quickly

it is randomly generated, so it would evenly be distributed across the nodes.

Trade offs/Tech choices

There are two ways to create a short URL:

1. By hashing SHA-256 or MD5 the long URL
2. To randomly generate it

There is a trade-off pro of the hash approach: you don't have to generate random numbers. Con is that the created hashes might collide, particularly since a random string of characters will be shorter than what the hash algorithms generate, increasing the risk of collision.

Pros of random generation:

1. Lower probability of collision
2. If a newly generated random string collides with an existing one, we can simply generate another random string.

Cons of random generation:

1. It would require computational power to generate random numbers.
2. However, since Linux and other OSes support fast random number generation, we assume the cost should be manageable.

We will pick random generations in this exercise.

Failure scenarios/bottlenecks

All the components (load balancer, web servers, cache, and database) should have multiple instances for improved availability. There should be a robust monitoring and alerting system on them. All nodes can fail, so let's look at some of the important failure cases.

failure in the mapping service.

If the mapping service fails due to hardware failure, crash, or software bug, it would directly impact the most time-sensitive operation of the system (redirect URL). To mitigate this, we should always run multiple mapping service nodes. It is a stateless service, so we can have multiple nodes of the same service. We can use a coordination service like ZooKeeper to track which nodes are alive. If one node sends a heartbeat to ZooKeeper, which indicates it's likely dead, then another node should take its place.

failure in cash

Losing cache would also impact the redirect URL functionality. For example, let's say the Redis cache that is holding 10 of the mappings between the short URL and long URLs goes down due to the faulty memory. So, mapping services will now have to access the database for each of these mappings, making requests much slower and increasing the load on the database. This may even have some kind of cascading impact - database gets slower and slower, mapping services retry making the database even busier. We can have multiple mitigations.

Let's say for one leader we put two read-only replicas. Rights are handled by the leader and propagated to the read replicas by transmitting a write log. Redis reads can be handled by all three. If the leader goes down for some reason, one of the read replicas can become the leader after the leader selection process and take over the responsibility as the leader. This would avoid the aforementioned scenario.

Mapping services could also have a mitigation strategy to avoid overloading the database, for example, exponential backoff before read drawing, rate limiting and circuit breaking.

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?