System requirements

Functional:

1. Our system should be able to retrieve a long URL from a short URL
2. Users should also be able to customize their own URL

Non-Functional:

1. Availability over consistency -> We want the service to be available over consistent
2. Low latency. We want our system. to provide as minimal overhead as possible. Let's say <20ms per call
3. Available in multiple regions in the world

Capacity estimation

1. Assuming we are going to get 100 reads per second and 1 write per second.
2. Assuming 1 write per second, to encode the URL we would need 8 bytes of data. Assuming 10 ^ 5 seconds in a day, that gives us 8 * 10 ^ 5 Bytes of data a day, which is about about 800KB of data a day. Every year we will need 800KB * ~400Days = 320,000 = 320MB worth of storage needed per year
3. We will need multiple servers to handle 100 requests per second

API design

We would want to have 2 types of APIs - one API would serve to get the request and the URL.

The API would redirect the sender to the actual resource and on success return 302 (redirected) or fail on something like 404

The other API would let the user encode their URL in the UI portal. We should allow them to specify the URL themselves which can be hashed easily to locate where the URL is stored

Database design

The ideal database for this system would be key-value value based. Because each URL will have a unique hash we can use that as our key. A NoSQL database like DynamoDB would work perfectly for this design since it is a key-value based database with scalability built in.

High-level design

1. The clients will hit our load balancers where it will redirect the request to one of our application servers
2. Our application servers will then check our in-memory cache (Redis) to see if the hashed key exists. The cache server is LRU
   1. For scalability we can have multiple cache servers. For the application server to know which cache server the request belongs to we will have a cache client daemon running in each applications server, which uses consistent hashing to determine which cache server to check.
3. If we get a hit from our cache server, we will return the result. If we do not, then we will check the database. NoSQL database would be able to route the request tot eh correct partition and return the request. If not present, we return 404

Overall, I am okay with after the resource is added, that it takes some time for it to fully propogate to all DB replicas because eventual consistency is OK. However, we want to keep durability (write requests) and latency (making redirect as quickly as possible)

Request flows

For our caching strategy I will use a write-through caching strategy. This means during our write requests we will confirm the data is saved in both the cache and database before returning the response to the client.

• The trade-off with write-through caching is during write requests there will be higher latency since we'll be saving in both the cache and database. However, our read requests will be much faster since the data will already be in the cache.

Detailed component design

• I'd like the database to be replicated synchronously within the datacenter + async outside the datacenter
• My only concern is how we will generate the unique IDs. For this we can use base64 encode our URLs to shoten them. This will be our shortened URL that we same back to the client. An Example of this is https://tinyurl.co/{base64encoded}
• Although it is unlikely, we want to validate the generated hash is not a duplicate in our database. In this case we will check if the hash is already present in the database.

Trade offs/Tech choices

Trade-offs I am opting to use a write-through cache strategy that prioritizes reads over writes. I think this is a fair trade-off given our read-to-write ratio

Another trade-off we are making is around consistency for latency. Since we have chosen db replication to be asynchronous it is possible not all information datapoints will be immediately available to all replicas. However, I think this is a fair trade-off since users may not share or use the link instantly.

Failure scenarios/bottlenecks

Some failure scenarios

1. During writes there can be cache misses which will cause the write request to fail. We can implement a retry strategy for the API to be more resilient
2. We can run into duplicate hashes.

Bottlenecks

1. Our system can go down if someone very famous posts a URL that generates a lot of traffic

Future improvements

Instead of using a write-through caching strategy, I can opt in for a write-back strategy where we write to the cache immediately and asynchronously write to the DB. This will vastly improve our write latency, but will introduce complexity in adding an asynchronous process. If the asynchronous process fails, then we will have inconsistent data in both

Additionally, since our system is only eventually consistent, there is a few scenarios where this may not be acceptable. Let's say there is a very famous person who posts a link and within seconds we get 100s of thousands of requests. There are 2 problems here now:

the shortened url hasn't been replicated to all db nodes (especially the ones across the world);

we are getting a thundering herd problem - all of these requests are going to cache miss and all go to the disk which is slow and can cause additional problems/cost in our DB usage.

We can solve this problem by using a "push" based approach in cache for famous/reserve users - we first write in cache and then we write (and replicate) on disk. That would solve the replication/and thundering herd problem, but only if the cache daemon on the application server can have the ability to precisely determine the node id where the cache node with the resource is located.