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
3. Expiration:
   1. Provide an option for users to set an expiration date for their short URLs.
   2. The link will by default expire after a certain period if no expiration date is set.

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

Below are the number of url that we will have to store in our database for a 5 year period: 30 million * 5 years * 12 months = 1.8 Billion

Let’s consider we are using 8 characters to generate a short URL. These characters are a combination of 62 characters [A-Z, a-z, 0-9, _ ], something like http://ad.com/abXdef21. This will give us a total of 3.2 Trillion unique combinations.

Let's try to understand how much storage we will need to store the data for 5 years.

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

We may also want to ensure that the links ecnoded aren't malicious or point to dark web/denied reosuces. If a user tries to encode something like that, we may deny the request on create API flow.

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

• 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

Detailed component design

1. I'd like the database to be replicated synchronously within the datacenter + async outside the datacenter
2. Because we are randomly generating a link using 8 characters of [a-z, A-Z, 0-9], there will like not be any collisions within 5 years. To prevent collisions, we can check if the randomly generated 8 characters are in our DB before we save.
3. 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.

1. We are not keeping track of used hashes effectively,
2. We are making a lot of DB calls on create, lowering write latency
3. The hashes ran out so we shorter urls aren't short anymore.
4. System can go down if someone very famous posts a URL that generates a lot of traffic
5. We have a few components that introduce SPOF

CAP Theorem Implications for URL Shortening Service:

• AP (Availability and Partition Tolerance):
  • In a URL-shortening service, high availability is often more critical than strict consistency. Users expect quick access to short URLs, and downtime or delays in availability are less acceptable. Therefore, prioritizing availability and partition tolerance is a common choice.
• Consistency Trade-offs:
  • Achieving strong consistency across all nodes in a distributed system can introduce delays, especially during periods of network partition or high traffic. The system might choose eventual consistency, where all nodes will eventually converge to the same state, but immediate consistency might not be guaranteed.
• Eventual Consistency:
  • Since URL shortening services often involve distributed data across multiple nodes or data centers, eventual consistency might be a pragmatic approach. Users might experience temporary inconsistencies between nodes, but the system would work towards converging to a consistent state over time.
• Caching and Redirection:
  • Caching is often employed to improve performance and availability. If a node has cached data, it can still provide a redirect even if it temporarily loses contact with the main database. This approach enhances availability and partition tolerance.

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.