Requirements

Functional Requirements:

• Create a short URL for a given long URL.
• Return the long URL associated with a given short URL.

Non-Functional Requirements:

• The system should ensure the uniqueness of the shortened URL
• The redirection to the long URL should happen in less than 100 milliseconds
• The system should be reliable and available 99.99% of the time (availability > consistency)
• The system should scale to support 1B shortened URLs and 100M

Capacity Estimation

Estimate the scale of the system. Consider daily active users, read/write ratio, storage requirements, bandwidth, and any relevant QPS calculations...

API Design

1. POST: /urls

1. GET: /url/:short-code
2. PATCH: /urls/short-code

1. DELETE: /urls/short-code.

High-Level Design

Describe the overall system architecture. Identify the main components needed to solve the problem end-to-end. Use the diagramming tool to create a block diagram.

1. Client: This is the component that will request to create the short URL and get the long URLs
2. Load balance: Distribute the traffic among the horizontally aligned servers
3. API Gateway: This will be used to route the request and rate-limit the number of requests coming to the server.
4. Write Service: This service will recieve the POST requests from the client to encode the long URLs and return the short URL in response.
5. ID generation: This is a dedicated service for ID generation used by the write service. The sole purpose of this component is to implement the logic of encoding based on the configured algorithm and return the encoded URL to the write service.
6. Queue: I have implemented this queue here in case we get a high number of write requests; then this queue can be used to insert the encoded URL into the database in an asynchronous way. This way, we can retry the events where the database insertion failed on the first attempt.
7. Database: This is a key-value-based NoSQL database where the mapping of short URLs and long URLs will be stored along with their expiration time details and other details.
8. Read Service: The API gateway will route all the GET requests to this service, which will be responsible for retrieving the original long URL for the provided short URL.
9. Cache Layer: Cache is implemented to store the most frequently retrieved URLs so that we don't have to query the database every time.

Database Design

Define the data model. Identify the main entities, their attributes, and relationships. Consider the choice of database type (SQL vs NoSQL) and justify your decision based on access patterns...

The core entities of this system are:

• Long URL
• Short URL
• User

For this system, we will use a NoSQL database because it is read-heavy. The ratio of read to write will be approximately 100:1. Considering this, a NoSQL database like dynamoDB should be an optimal choice for this. All redirect GETs use DynamoDB's strongly consistent reads to prevent 'not found' errors immediately after creation. We will have two data models, one for storing the URL mappings and another that we can keep for user information.

1. url_mapping
   1. short_code (partition key)
   2. long URL
   3. expiration_time (TTL-based expiration time)
   4. created_at
   5. created_by
2. users_table
   1. username
   2. email
   3. full_name
   4. phone
   5. created_at

Detailed Component Design

Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.

The Unique ID Generation service:

This will work based on a unique global-level counter value. To implement this in a distributed system, we can use Redis, which runs on a single thread and operates atomically. The INCR function of Redis will always increase the counter value by 1. Every time a URL shortening request is received, the write service will take the counter value and encode it with base62 encoding. This counter logic will introduce a security issue as any one predict the encoded URLs in the system. To tackle this, we can use a random string to create an XOR with the counter value. We could have also used the encoding after taking a hash of the long URL, but that would create the chance of duplicates in a large amount of data, and we would have to retry multiple times with another hash. On a large scale, this could be non-negotiable.

Now, if the load is increased and we need to horizontally scale the write service, then, in this case also, maintaining Redis as a global counter, there will be no chance of duplication. There could be a question of introducing the network call in each write operation, but that network call will be very fast. If we want to avoid this many network calls, then we can ask for a batch counter from Redis. For example, an instance can ask for counter values from 1 to 10000 in a single network call, and if another instance is calling Redis, then that instance will receive the counter values from 10000 to 20000. Once the counter is exhausted in Redis, the instances can request another batch. This way, instances can keep the counter in memory and perform writes faster.

The Cache Layer Designs:

1. CDN: CDN will be there at the edge locations to serve all the hot tier requests. Although it is more costly and adds a layer of complexity to the system, it is worth implementing for a scale of 20000 reads per second. CDN will directly redirect the short URL to the designated long URL because it caches the redirect response received from the primary server. This way, the request will never reach the backend server, reducing the load significantly.
2. Redis Cache: Redis will be implemented at the server level to serve all the warm-tier requests. The cache miss from the CDN cache layer will reach the server and look into the Redis cache. If there is a cache hit, then redirection will be processed in 5-10ms, which is pretty fast compared to a database query.
3. If a URL is getting updated, then the backend server needs to update the cached data at the CDN layer and in Redis also.
4. For ultra-hot keys, CDN and Redis absorb the load before it hits DynamoDB. And DynamoDB's built-in replication naturally distributes read load for hot partitions

Handle Failure Scenarios:

In case there is a cache miss at the CDN layer, then the request will reach the backend server, and there it will look for the entry in the Redis cache. If there is a cache hit at the Redis level, then it will immediately respond; otherwise, in case of a cache miss, it will fall back to a DB lookup. Data will be fetched from the DB, written back to the Redis cache and returned to the client.

To handle the cases of the database being down, we can have database replicas, which are provided by dynamoDB. We just have to make sure that our primary server should be able to call the replica copy of our DB without any problem in case the DB is down.

Partitioning:

We will be using the short_code as the partition key, as it is generated from a large space to make sure it is always unique. This uniqueness and partition key will make sure each redirect hits exactly one shard in case of a cache hit via Redis, and in case of a cache miss via dynamoDB