System requirements

Functional:

Shortening a Long URL:

Input: The service accepts a long URL.

Output: The service generates and returns a short URL (8 characters) linked to the provided long URL.

Redirecting from a Short URL:

Input: The service accepts a short URL.

Output: If the short URL is found, it redirects the user to the corresponding long URL. If the short URL does not exist, it returns a 404 Not Found error.

Handling URL Expiration:

The service should allow setting an expiration time for the short URL upon creation, after which the short URL will no longer be valid and will auto-expire.

Collision Handling:

During the creation of a short URL, if a collision occurs (i.e., a generated short URL already exists), the service must generate a new short URL until a unique one is obtained.

Non-Functional:

Performance:

Response Time: The service should respond to short URL creation requests in under 10 seconds and redirect requests in less than 10 milliseconds.

Throughput: The service should handle 200 requests per second for short URL generation and 20,000 requests per second for redirecting.

Scalability:

The system should be designed to scale horizontally to accommodate increasing loads without degradation in performance.

Availability:

The system should ensure high availability, minimizing downtime and providing consistent redirection even during peak load periods.

Durability:

Implement RDB snapshotting to persist data, ensuring URL mappings are recoverable after server restarts or crashes.

Simplicity:

The API should be simple and user-friendly, facilitating easy integration and usage by developers or end-users.

Security:

Ensure basic security measures are in place to prevent unauthorized access, such as rate limiting and protection against abuse (e.g., spam linking).

Capacity estimation

Request Types:

Creating Short URLs (shortenURL): Approximately 200 requests per second.

Redirecting URLs (redirectURL): Approximately 20,000 requests per second.

Data Storage:

For each URL mapping, let's estimate the storage requirements. Each mapping will include:

Long URL: 100 bytes (average length)

Short URL: 8 bytes

Expiration (if used, can be handled in TTL): you may not store it explicitly in Redis, but for consistency, we'll consider it.

Total size per entry can be approximated as follows:

Total size per entry = Long URL + Short URL

Total size = 100 + 8 = 108 bytes

For simplicity and to cover some overhead, we can round this up to approximately 256 bytes.

Daily Data Generation:

For short URL creation (assuming they persist):

Number of short URLs created per day: [ 200 \text{ requests/second} \times 60 \text{ seconds/minute} \times 60 \text{ minutes/hour} \times 24 \text{ hours/day} ] [ = 17,280,000 \text{ short URLs/day} ]

Daily data size for storage for short URLs (using 256 bytes): [ 17,280,000 \text{ entries/day} \times 256 \text{ bytes/entry} \approx 4.4 GB \text{ per day} ]

Long-Term Data Generation:

Assuming continuous operation for 5 years at the rate computed:

Total data size generated in 5 years: [ 4.4 \text{ GB/day} \times 365 \text{ days/year} \times 5 \text{ years} \approx 8 \text{ TB} ]

Adding some buffer for growth:

Estimated total size would be approximately 15 TB over 5 years, accounting for any additional mapping growth.

Read Load Consideration:

For redirect requests:

On average, as the redirect load is around 20,000 requests per second, the system should maintain high read throughput.

If Redis is properly utilized with TTL, the cached records will allow handling of a significant percentage of requests without hitting the disk.

Summary of Capacity Estimation

Short URL Creation:

Approximately 200 requests/second, leading to about 4.4 GB of data per day.

Estimated total over 5 years: about 15 TB.

Redirects:

Approximately 20,000 requests/second, heavily leveraging caching to maintain performance under loads.

Key Considerations

Redis Scaling: As traffic increases, ensure Redis can handle the data growth, potentially utilizing sharding and clustering for scalability.

Backup Strategy: Ensure appropriate data backup strategies are in place to handle potential data loss scenarios, given Redis's in-memory nature.

API design

1. Shortening a Long URL

• Endpoint: POST /shorten
• Description: This endpoint accepts a long URL as input and returns a short URL.
• Request Body:
• { "long_url": "http://example.com/some/very/long/url" // Optional: "expiration_time": "YYYY-MM-DDTHH:MM:SSZ" (for setting expiration if needed)}
• Response:
  • Success (HTTP Status 201 Created):
  • { "short_url": "http://short.url/abc12345"}
  • Error (HTTP Status 400 Bad Request):
  • { "error": "Invalid URL format"}

2. Redirecting from a Short URL

• Endpoint: GET /{short_url}
• Description: This endpoint redirects users from the short URL to the corresponding long URL.
• URL Parameters:
  • short_url: The abbreviated URL part to look up.
• Response:
  • Success (HTTP Status 301 Moved Permanently):
    • Redirects automatically to the long URL.
  • Error (HTTP Status 404 Not Found):
  • { "error": "Short URL not found"}

Example Workflow

1. Shorten URL:
   • Client sends a POST request to /shorten with a long URL.
   • The service generates a short URL, stores it in Redis, and returns the short URL.
2. Redirect URL:
   • A client accesses the URL GET /abc12345.
   • The service checks Redis for the mapping of the short URL.
   • If found, it performs a 301 redirect to the long URL. If not found, it returns a 404 error.

Additional Considerations

• Input Validation: Ensure that long URLs are properly validated to prevent invalid inputs.
• Rate Limiting: Implement rate limiting on the API endpoints to prevent abuse by limiting the number of requests allowed per user in a given timeframe.
• Error Handling: Consistent error messages and HTTP status codes should be maintained throughout the API for better client handling.

Summary

With this API design, you've created a streamlined process for shortening and redirecting URLs, prioritizing simplicity and user experience.

Database design

We don't use any DB as we are storing only with Redis with proper persistance

High-level design

Long URL -> Generate Short URL with non-colliding Hash and of course with validating URL. Once generated save the long URL and Hash in Redis(Key-value).

Short URL received. Find the hash from the short URL and for the hash get the long URL and send with the proper status, if not found return with Corresponding HTTP code.

Request flows

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...

Trade offs/Tech choices

I took the trade off between Redis and DB. I felt since its the key value pair getting stored, it may be suffice to use the Redis rather than a DB

Failure scenarios/bottlenecks

Bottlenecks will be if redis goes for a toss. However for the frst cut of the product this would be fine I believe

Future improvements

Based on scalability we will try bringing in a NoSQL DB like Dynamo, CouchDB etc