System requirements

Functional:

1. URL Shortening: User should be able to submit a long URL and receive a unique short URL in response
2. URL Redirection: redirect users from short URL to original long URL when accessed
3. Error Handling: System should provide clear message for handling invalid URL, non-existent short URLs or any service failures
4. Analytics: Users should be able to view how many times a short URL has been accessed
5. API Access: Service should expose both shortening URLs and retrieving URL
6. Input Validation: Validate the format of the provided long URL before processing

Non-Functional:

1. Performance: System should handle specified number of request per seconds. 1000 TPS with an average of 200ms
2. Scalability: Service should be able to scale horizontally to handle increased loads without degradation of performance
3. Reliability: High Available, aiming for atlease 99.9% uptime
4. Security: Ensure abuse such as rate limiting & input sanitization to avoid injection attacks
5. Usability: The API should be well documented
6. DataRetention: how long URL statistics and mappings will be retained in the system

Capacity estimation

1 Million URL = 10^6

-- Each URL shortened to alpha numeric string (6 characters )

-- 62 possible character (A-Z, a-z, 0-9)

-- 62^6 = 56,800,235,584 potential unique URLs

API design

1. createShortenedAPI - to create a shortend URL
2. redirect - to handle redirect from short URL to original URL

Database design

ID (primary Key)

original_URL

shortened_URL

High-level design

1. Client/Application - UI for interacting the service
2. API Gateway - manages incoming api requests and forwards them to appropriate service
3. Shortening Service - handles the URL shortening logic
4. Database - Stores the mapping between original URL and shortening URL
5. Redirect Service - handles request to the shortened url and retrieves the original URL

Request flows

When a user accesses a shortened URL, the request flow would be:

1. User submit long url to be shortened, the API Gateway receives the forward request to shortening the URL
2. The shortening service checks for a unique string and interact with the database to ensure the uniqness
3. After storing the mapping of long URL to the short URL, a response is sent back to the user

When a user accesses a shortened URL, the request flow would be:

1. The user clicks on a short URL
2. API Gateway forwards the request to redirect service
3. the redirect service retrieves the original url from the db
4. user is then redirected to the original url

Detailed component design

1. API Gateway

• Responsibility: Acts as the entry point for all API requests. It handles routing, authentication, and rate limiting.
• Key Features:
• Forward requests to the appropriate backend services (Shortening Service or Redirect Service).
• Handle user authentication and authorization.
• Implement rate limiting to prevent abuse.

2. Shortening Service

• Responsibility: Handles the logic for creating short URLs and storing the mapping of long URLs to short URLs.
• Key Features:
• Generate a unique short URL (e.g., using base conversion or hash algorithms).
• Validate the input URLs and return error messages for invalid inputs.
• Interact with the Database to store and retrieve URL mappings.

3. Redirect Service

• Responsibility: Manages the logic for redirecting users from short URLs to their corresponding long URLs.
• Key Features:
• Retrieve the original URL from the Database based on the short URL provided.
• Perform HTTP redirection to the original URL.
• Handle cases where the short URL doesn't exist (404 error).

4. Database

• Responsibility: Stores the mapping between the long URLs and their corresponding short URLs.
• Key Features:
• A structured table that includes fields for the original URL, short URL, and additional metadata (e.g., creation date, usage count).
• Efficient indexing to allow fast lookups of short URLs.

5. Analytics Service (Optional)

• Responsibility: Tracks usage statistics for the shortened URLs.
• Key Features:
• Collect data on how often each short URL is accessed.
• Generate reports on URL usage trends and patterns.
• Provide an API to fetch analytics data when needed.

6. Caching Layer (Optional)

• Responsibility: Improves performance by caching frequently accessed short URLs.
• Key Features:
• Use in-memory storage systems (like Redis or Memcached) to reduce Database load.
• Cache original URLs for popular short URLs to speed up access.

Here’s how these components interact at a high level:

API Calls

Route to

Store/Retrieve

Route to

Lookup

Return Data

Redirect User

Track Requests

Cache Lookups

User

API Gateway

Shortening Service

Database

Redirect Service

Analytics Service

Caching Layer

In this diagram:

• Users interact with the API Gateway.
• The API Gateway routes requests to either the Shortening or Redirect Service.
• Both services interact with a shared Database.
• Optionally, an Analytics Service tracks URL usage, while a Caching Layer improves performance by caching frequent lookups.

Trade offs/Tech choices

1. Storage vs. Performance:

• Trade-off: Using more storage-efficient representations (like short URLs) may require additional computation to resolve to the original URL.
• Consideration: You might choose between a more complex algorithm to save database space or a simpler algorithm that may consume more space but has faster lookup times.

1. Consistency vs. Availability:

• Trade-off: A distributed system may favor availability over strong consistency, especially during network partitions.
• Consideration: You could decide to implement eventual consistency for URL redirection, allowing for a more resilient system where read replicas can return results even during failures.

1. Simplicity vs. Extensibility:

• Trade-off: A simple architecture may be easier to implement but may become more difficult to manage as requirements grow.
• Consideration: Opting for microservices might complicate the deployment but provides flexibility for future extension (like adding analytics without affecting the shortening service).

1. Mature Technologies vs. New Technologies:

• Trade-off: Utilizing well-established technology comes with community support but may not have the latest features or performance optimizations found in newer tools.
• Consideration: For example, you might choose between a traditional relational database (like PostgreSQL) and a NoSQL database (like MongoDB) based on the need for schema flexibility versus ACID compliance.

Technology Choices

1. Database:

• Relational: PostgreSQL or MySQL for structured data and transactions.
• NoSQL: MongoDB or DynamoDB for horizontal scalability and flexible schemas.

1. Caching Layer:

• Redis: For fast retrieval of frequently accessed short URLs, reducing database load and improving response times.
• Memcached: Another option for caching frequently accessed items, though with more limited data persistence features.

1. URL Generation:

• Hashing Algorithm: Using SHA-256 or MD5 could allow for unique shortened URLs, but with potential for collisions if not managed.
• Base Encoding: Using base62 encoding (A-Z, a-z, 0-9) to generate short URLs without collisions, while ensuring they remain concise.

1. Analytics:

• Elasticsearch: For real-time analytics and data visualization.
• Prometheus: For monitoring and alerting on system performance.

1. API Framework:

• Express.js: For building a REST API with Node.js, providing a quick setup for handling HTTP requests.
• Spring Boot: For Java-based services with robust support for REST APIs.

1. Deployment:

• Containerization: Using Docker to ease deployment and scaling of service components.
• Cloud Services: AWS, Google Cloud, or Azure for hosting, providing managed services like databases, load balancers, and more.

Failure scenarios/bottlenecks

Failure Scenarios

1. Database Failure:

• Scenario: The database becomes unavailable due to hardware failure or network issues.
• Mitigation: Implement database replication to maintain replicas, allowing for failover in case of primary database failure. Use connection pooling to manage database connections efficiently.

1. Service Downtime:

• Scenario: The Shortening Service or Redirect Service goes down, preventing users from shortening or accessing URLs.
• Mitigation: Utilize load balancers to distribute traffic across multiple instances of the service. Implement health checks and auto-scaling to maintain service availability.

1. High Traffic Load:

• Scenario: An unexpected surge in traffic could overwhelm the system, causing slow responses or service outages.
• Mitigation: Utilize a caching layer (like Redis) to reduce pressure on the database for frequently accessed URLs. Implement rate limiting to manage excessive requests from a single user.

1. Network Issues:

• Scenario: Network latency or outages could impact communication between services or between the client and the server.
• Mitigation: Utilize retries with exponential backoff for service calls and implement circuit breakers to prevent cascading failures.

1. Hash Collisions:

• Scenario: Two different long URLs generate the same short URL due to an error in the URL generation algorithm.
• Mitigation: Use a combination of a hashing algorithm with base encoding and a uniqueness check in the database. If a collision is detected, regenerate the short URL.

1. Data Loss:

• Scenario: Accidental deletion of URLs from the database.
• Mitigation: Implement soft deletes (marking records as deleted rather than physically removing them) and maintain regular backups of the database.

Bottlenecks

1. Database Bottleneck:

• The database can become a bottleneck, especially if all requests are routed through it.
• Mitigation: Implement read replicas to distribute read requests and consider partitioning or sharding the database for better scalability.

1. Service Bottleneck:

• If the Shortening Service processes requests sequentially without adequate resource allocation, it may become a bottleneck.
• Mitigation: Scale horizontally by deploying multiple instances of the service and utilize a message queue to handle requests asynchronously.

1. Network Latency:

• Increased latency in network calls between services may degrade user experience.
• Mitigation: Use local caching to store frequently requested short URL mappings, reducing the need for repeated database calls.

1. Cold Start Issues:

• Microservices may experience cold starts, leading to delays when they need to be instantiated.
• Mitigation: Keep a minimum number of service instances always running or employ a serverless architecture to handle variable loads efficiently.

Future improvements

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