System requirements

Functional Requirements:

1. Create Short URL: When given a long URL, the system should generate and return a corresponding short URL.
2. Redirect: When a short URL is accessed, the system should retrieve and redirect the user to the original long URL.
3. Custom Short URL: Optionally, allow users to create custom short URLs.
4. Track Clicks: Provide functionality to track the number of clicks or accesses on a short URL.
5. Manage Expiration: Allow users to set an expiration time for the short URL.
6. User Authentication: Have an authentication mechanism for users to keep track of their created short URLs.

Non-Functional Requirements:

1. Scalability: The system should be able to handle increasing loads (more users and URLs) without significant performance degradation.
2. Availability: The service should be highly available, with minimal downtime. Consider an availability target like 99.99%.
3. Performance: The response time for redirecting to long URLs should be low, ideally under 10 milliseconds.
4. Data Integrity: Ensure that URL mappings between short and long URLs are consistent and accurate.
5. Security: Implement measures to protect against malicious links (e.g., phishing) and DDoS attacks.
6. Usability: The system should provide an intuitive user interface for both URL creation and management.

Estimation Assumptions

1. Usage Patterns:
   • Creating Short URLs: Let's estimate around 200 requests per second. This is the rate at which users will generate short URLs.
   • Redirecting to Long URLs: This can be much higher, typically around 20,000 requests per second, especially if the service gains popularity and receives high traffic on shared links.
2. Data Sizes:
   • Assume that an average long URL is approximately 100 characters (about 100 bytes).
   • The short URL will be approximately 8 characters (about 8 bytes).
   • Additional metadata for each short URL may include:
     • Created time: 8 bytes
     • Created by user ID: 20 bytes
     • Expiration time (if applicable): 8 bytes
3. Total Data Size per Entry:
   • Long URL: 100 bytes
   • Short URL: 8 bytes
   • Created time: 8 bytes
   • User ID: 20 bytes
   • Expiration time: 8 bytes
   • Total: 144 bytes (round up to about 256 bytes for overhead)

Daily Estimates

• For Creating Short URLs:
  • 200 requests/second * 60 seconds/minute * 60 minutes/hour * 24 hours/day = 17,280,000 short URLs per day.
  • Daily data generated: 17,280,000 * 256 bytes = approximately 4.4 GB per day.
• For Redirecting Long URLs:
  • 20,000 requests/second * 60 seconds/minute * 60 minutes/hour * 24 hours/day = 1,728,000,000 redirects per day.

Long-term Storage Needs

• Over 5 years:
  • Short URL Data: Assuming constant growth; 4.4 GB/day * 365 days/year * 5 years = approximately 8 TB of data.
  • Adding some buffer for growth, we estimate around 15 TB as a conservative figure.

API design

API Endpoints

1. Create Short URL
   • Endpoint: POST /shorten
   • Request Body:
   • { "long_url": "string", // The original long URL to be shortened "user_id": "string", // (Optional) ID of the user creating the short URL "expiration_time": "datetime" // (Optional) When the short URL should expire}
   • Response:
   • { "short_url": "string", // The generated short URL "created_time": "datetime" // Timestamp of creation}
2. Redirect URL
   • Endpoint: GET /{short_url}
   • Path Parameter:
     • short_url: The short URL identifier.
   • Response: (Redirects to the long URL, typically handled by the server redirect)
     • HTTP 302 Found: Points to the long URL.
3. Get Long URL Details
   • Endpoint: GET /details/{short_url}
   • Path Parameter:
     • short_url: The short URL identifier.
   • Response:
   • { "long_url": "string", // The original long URL "click_count": "int", // The number of times this URL has been accessed "created_time": "datetime", // Timestamp of creation "expiration_time": "datetime" // When this short URL will expire}
4. List User URLs
   • Endpoint: GET /user/{user_id}/urls
   • Path Parameter:
     • user_id: Unique identifier of the user.
   • Response:
   • { "urls": [ { "short_url": "string", "long_url": "string", "created_time": "datetime", "expiration_time": "datetime" } ]}
5. Delete Short URL
   • Endpoint: DELETE /{short_url}
   • Path Parameter:
     • short_url: The short URL identifier.
   • Response:
     • HTTP 204 No Content: Indicates successful deletion of the resource.

Database design

Data Model

Based on the requirements, we'll have a single primary entity to represent the mapping of short URLs to long URLs. Here's what our database structure might look like:

1. ShortURL
   • short_url: string (Primary Key) – Unique identifier for the short URL
   • long_url: string – The original long URL
   • created_time: datetime – Time when the short URL was created
   • user_id: string (Optional) – ID of the user who created the short URL
   • expiration_time: datetime (Optional) – Time when the short URL will expire
   • click_count: int – Number of times the short URL has been accessed

ER Diagram

Here's an ER diagram representation of the ShortURL entity. This will help visualize the relationships and attributes involved.

SHORT_URLstringshort_urlPrimary Keystringlong_urldatetimecreated_timestringuser_idForeign Key referencing USERdatetimeexpiration_timeintclick_countUSERstringidPrimary Keystringnamestringemailcreates

Key Considerations:

• Database Type: A NoSQL database (like DynamoDB) could work well for fast access and scalability, while a relational database (like PostgreSQL) can be used for stricter consistency and complex queries.
• Indexes: You might want to create secondary indexes on user_id and expiration_time to enhance lookup performance and manage the deletion of expired URLs.
• Data Retention: Consider how long you'll retain data for the short URLs. If there's an expiration mechanism, this can help you manage storage effectively

High-level design

Key Components

1. API Gateway: Manages traffic, provides security features like rate limiting and authentication, and forwards requests to relevant microservices.
2. Shortening Service: Responsible for creating short URLs and storing the mappings in the database. This service interacts with the database to save the newly created short URLs.
3. Mapping Service: Handles requests to redirect from short URLs back to long URLs. It looks up the short URL in the database and retrieves the corresponding long URL.
4. Database: Stores the URL mappings and associated metadata (like created time, user ID, expiration time, and click count).
5. Cache: A caching layer (e.g., Redis) sits between the API Gateway and the Database to speed up access to frequently requested short URL mappings.
6. CDN (Content Delivery Network): Optionally, a CDN can be used to cache long URL mappings for high-frequency accesses, allowing faster redirection and reducing load on the backend.

Request flows

Request Flow for Creating a Short URL

1. Client: The user sends a POST request to the API Gateway with the long URL they wish to shorten.
2. API Gateway: Forwards the request to the Shortening Service.
3. Shortening Service:
   • Generates a short URL.
   • Saves the mapping of the short URL to the long URL in the Database.
   • Optionally, stores the mapping in the Cache for quicker future access.
4. Response: The API Gateway sends the generated short URL back to the client.

Request Flow for Redirecting to a Long URL

1. Client: The user sends a GET request to the API Gateway with the requested short URL.
2. API Gateway: Forwards the request to the Mapping Service.
3. Mapping Service:
   • First checks the Cache to see if the long URL for the short URL is available.
   • If it's a cache hit, the long URL is retrieved and the request is redirected to the long URL.
   • If it’s a cache miss, it queries the Database for the long URL.
4. Database: Returns the long URL to the Mapping Service.
5. Mapping Service: Sends the long URL to the API Gateway, which performs the redirect to the client.

sequenceDiagram participant Client participant API_Gateway participant Shortening_Service participant Database participant Cache participant Mapping_Service Client->>API_Gateway: POST /shorten (long URL) API_Gateway->>Shortening_Service: Request to create short URL Shortening_Service->>Database: Save mapping (short URL, long URL) Shortening_Service->>Cache: Store mapping (short URL, long URL) Database-->>Shortening_Service: Confirmation Shortening_Service-->>API_Gateway: Return short URL API_Gateway-->>Client: Response with short URL Client->>API_Gateway: GET /{short_url} API_Gateway->>Mapping_Service: Request to retrieve long URL Mapping_Service->>Cache: Check for long URL alt Cache Hit Cache-->>Mapping_Service: Return long URL Mapping_Service-->>API_Gateway: Forward long URL API_Gateway-->>Client: Redirect to long URL else Cache Miss Mapping_Service->>Database: Query for long URL Database-->>Mapping_Service: Return long URL Mapping_Service-->>API_Gateway: Forward long URL API_Gateway-->>Client: Redirect to long URL end

Detailed component design

1. Shortening Service

Functionality

• The Shortening Service is responsible for generating a unique short URL when a user submits a long URL.
• It saves the mapping of the short URL to the long URL in the database and caches it for later use.

Scalability

• The service can scale horizontally by deploying multiple instances behind a load balancer, allowing it to handle increased traffic.
• As the number of short URLs increases, it's important for this service to efficiently manage collision avoidance (two identical short URLs).

Data Structures and Algorithms

• Hash Set for Collision Checking: Use a hash set to keep track of existing short URLs. Before finalizing a new short URL, check if it exists in the set.
• Random Generation Algorithm: Generate an 8-character short URL using a combination of uppercase, lowercase letters, and digits. This can be done using a random number generator to pick characters.

Diagram for Shortening Service

flowchart TD A[Client] -->|POST /shorten| B[Shortening Service] B -->|Generate short URL| C[Hash Set] C -->|Check for collisions| D{Collision Found?} D -->>|No| E[Database] E -->|Save mapping| F[Cache]

There was an issue generating the diagram for the code above.

2. Mapping Service

Functionality

• The Mapping Service handles requests to redirect users from short URLs to their corresponding long URLs.
• It retrieves the long URL from either the cache or the database.

Scalability

• This service can also scale horizontally, allowing for multiple instances to handle high read traffic, especially during peak times.
• Using a caching strategy greatly reduces the load on the database, improving scalability.

Data Structures and Algorithms

• Redis or In-memory Database: A key-value store like Redis is ideal for storing short URL mappings in memory for rapid access.
• LRU Cache: Implement a Least Recently Used (LRU) cache mechanism to evict the least accessed short URLs from memory, ensuring more frequently accessed URLs remain cached.

Diagram for Mapping Service

flowchart TD A[Client] -->|GET /{short_url}| B[Mapping Service] B -->|Check Cache| C[Cache] C -->|Retrieve long URL| D{Cache Hit?} D -->>|Yes| E[Return Long URL] D -->>|No| F[Database] F -->|Return Long URL| E

There was an issue generating the diagram for the code above.

3. Cache

Functionality

• The cache serves as an intermediary storage that holds frequently accessed short URL mappings, speeding up redirection requests.

Scalability

• The cache can be horizontally scaled by adding more nodes. Caching layers can be deployed in clusters to improve performance and redundancy.
• Auto-scaling based on cache hits and misses can help maintain performance during traffic spikes.

Data Structures and Algorithms

• Hash Map: A hash map is used to store key-value pairs (short URL to long URL) for O(1) average time complexity on lookups.
• Eviction Policies: Use policies like LRU or LFU (Least Frequently Used) for cache eviction strategies to manage the size of the cache effectively.

Diagram for Cache Component

flowchart TD A[Mapping Service] -->|Cache Miss| B[Cache] B -->|Store Mapping| C[Hash Map] C -->|Eviction Policy| D{Cache Full?} D -->>|Yes| E[Evict Old Entry] D -->>|No| F[Store in Cache]

There was an issue generating the diagram for the code above.

Conclusion

These three components work together to ensure the URL shortening service operates efficiently, handles high loads and maintains quick response times for users. By utilizing appropriate data structures and algorithms, each component can efficiently manage resources and user requests while ensuring scalability.

If you have any further questions or would like to deepen your exploration into other components, just let me know!

Trade offs/Tech choices

1. Database Choice: SQL vs. NoSQL

Trade-off: Choosing between a traditional SQL database (like PostgreSQL) and a NoSQL database (like DynamoDB or MongoDB).

• SQL Advantages:
  • Strong consistency, which is important for ensuring that the relationship between short URLs and long URLs remains accurate.
  • Built-in support for complex queries and relationships.
• NoSQL Advantages:
  • Higher scalability due to horizontal scaling capabilities.
  • Better performance in terms of read/write speeds for large volumes of requests.
  • More flexible schema allowing for easy updates as features evolve.

Choice: A NoSQL database like DynamoDB was chosen for its scalability and performance under high load, especially for read-heavy workloads where quick lookups are critical.

2. Caching Strategy: In-Memory Cache vs. Persistent Cache

Trade-off: Deciding whether to use an in-memory caching solution (like Redis) or rely on database queries for every request.

• In-Memory Cache Advantages:
  • Significantly faster access times for frequent queries, reducing load on the database.
  • Ability to scale the cache independently of the database.
• Persistent Cache Advantages:
  • Cached data is retained even during restarts or failures, adding resilience.

Choice: An in-memory cache (Redis) was selected because the service will benefit from the speed of cache accesses, especially for redirect operations that are read-heavy. Using a caching strategy helps reduce latency and load on the database.

3. URL Shortening Algorithm: Hashing vs. Random Generation

Trade-off: Choosing between hashing the long URL to create a short URL or randomly generating short URLs.

• Hashing Advantages:
  • Deterministic: The same long URL always produces the same short URL.
  • Less chance of collision, provided good hash functions are used.
• Random Generation Advantages:
  • Less likely to hit existing mappings, given a large enough key space.
  • Avoids complexities associated with managing the unique mapping of hashes to URLs.

Choice: Random generation was chosen for simplicity. The likelihood of collisions can be managed with a collision-checking mechanism using a hash set before finalizing a new short URL.

4. API Gateway vs. Microservices

Trade-off: Implementing an API Gateway versus a monolithic architecture.

• Monolithic Advantages:
  • Simplicity in deployment and development.
  • Easier to manage in smaller-scale applications.
• Microservices Advantages:
  • Scalability: Individual services can be scaled independently based on load.
  • Better fault isolation; issues in one service won't bring down the entire system.

Choice: An API Gateway was implemented to handle microservices architecture. This choice facilitates scalability and allows for separate scaling of each service, crucial for handling varying loads between URL creation and redirection services.

5. Expiration and Data Retention

Trade-off: How to handle expired URLs and what data retention strategy to use.

• Retain Expired URLs Advantages:
  • Can provide insights into usage trends and analytics.
• Delete Expired URLs Advantages:
  • Reduces the storage burden and keeps the database clean.

Choice: It was decided to implement a system to automatically delete expired URLs after some time while logging required analytics data. This balances data retention for analytics while maintaining efficient use of storage.

Conclusion

Overall, the trade-offs made in the design of the URL shortening service focus on achieving a balance between efficiency, scalability, ease of maintenance, and user experience. Each technology choice was driven by the anticipated load and usage patterns, as well as a clear understanding of the service's functional and non-functional requirements.

1. Database Failures

Scenario: The database becomes unavailable due to network issues, crashes, or high latency.

• Impact: Users will be unable to create new short URLs or retrieve existing ones, leading to a poor user experience.
• Mitigation:
  • Implement read replicas to offload read requests and improve availability.
  • Use database sharding to distribute the load across multiple servers, enhancing performance.
  • Set up timeout and retry mechanisms in the application to handle temporary failures gracefully.

2. Cache Misses

Scenario: The cache is unable to return the long URL for a given short URL (cache miss).

• Impact: This leads to additional load on the database for read requests, which can degrade performance.
• Mitigation:
  • Implement an LRU (Least Recently Used) eviction strategy to ensure that popular mappings remain cached.
  • Consider pre-caching commonly accessed short URLs based on trending data to reduce cache misses.

3. High Traffic Surge

Scenario: A sudden spike in traffic (e.g., due to a viral post linking a short URL).

• Impact: This could overwhelm API requests, leading to longer response times or crashes.
• Mitigation:
  • Utilize load balancers to distribute traffic evenly across service instances.
  • Implement auto-scaling of application instances based on traffic load to dynamically allocate resources.
  • Introduce rate limiting on the API to prevent abuse and manage user load.

4. Collision Handling

Scenario: Randomly generated short URLs may collide (i.e., produce the same short URL for different long URLs).

• Impact: Users will receive incorrect links or fail to create new links.
• Mitigation:
  • Before finalizing the short URL, check for existing mappings in a temporary structure (like a hash set).
  • If a collision is detected, generate a new random short URL and retry until a unique short URL is found.

5. Expired URLs and Data Deletion

Scenario: Managing expired short URLs and cleaning up the database.

• Impact: If expired URLs are not deleted, they can clutter the database, leading to reduced performance and increased storage costs.
• Mitigation:
  • Implement a background job to periodically remove expired URLs from the database.
  • Track expiration in the database, using a time-to-live (TTL) mechanism where URLs auto-expire.

6. Network Latency and Timeouts

Scenario: Increased network latency when calling external services (like a third-party API or database).

• Impact: Slower response times for users, leading to frustration and potential abandonment of the service.
• Mitigation:
  • Use asynchronous calls for non-blocking operations to improve response times.
  • Configure sensible timeout settings to prevent long waits on service calls.

7. Data Loss

Scenario: Potential data loss due to various reasons (e.g., server crashes, poor error handling).

• Impact: Mapped URLs may become permanently lost, leading to a disrupted user experience.
• Mitigation:
  • Ensure data is written atomically with confirmation before processing any further steps.
  • Implement backups of the database at regular intervals to prevent data loss.

8. DDoS Attacks

Scenario: Malicious actors overwhelming the service with requests.

• Impact: Legitimate users may be unable to access the service, leading to increased operational costs.
• Mitigation:
  • Implement a Web Application Firewall (WAF) to filter out malicious traffic.
  • Use CDNs to absorb high amounts of requests and mitigate direct attacks on the origin server.

Conclusion

Identifying these failure scenarios and bottlenecks allows proactive design and build strategies into the system to enhance resilience and performance. It’s essential to continuously monitor and test the service to ensure that it can effectively handle unexpected events while maintaining a good user experience.

Future improvements

1. Custom Short URLs:
   • Improvement: Allow users to create their own short URLs instead of random generation, providing more branding and personalization options.
   • Mitigation: Implement validation checks to prevent duplication and ensure that user-defined short URLs meet specific criteria (e.g., character limits, banned terms).
2. Analytics Dashboard:
   • Improvement: Provide users with analytics on their generated short URLs, such as click-through rates, geographic distribution of clicks, and referral sources.
   • Mitigation: Ensure that analytics data is collected efficiently and in a manner that does not impact the performance of the primary services (e.g., using separate analytics databases or services).
3. User Accounts and Authentication:
   • Improvement: Implement user accounts so users can track their created short URLs, access analytics, and manage expirations easily.
   • Mitigation: Use token-based authentication (like JWT) to ensure secure access while mitigating risks of unauthorized access.
4. Rate Limiting:
   • Improvement: Introduce rate limiting to manage the number of requests per user in terms of creating and redirecting URLs.
   • Mitigation: Use tools or libraries to implement rate limiting, helping prevent abuse and ensuring fair usage among clients.
5. Geographic URL Redirection:
   • Improvement: Offer smart redirection based on the geographic location of the user, sending them to regional content or specific landing pages.
   • Mitigation: Use geolocation APIs to determine user location efficiently while considering privacy and data protection regulations.
6. Expiring Links:
   • Improvement: Allow users to set expiration times for their short URLs, providing a mechanism to manage link lifecycles effectively.
   • Mitigation: Automate background processes to clean expired URLs from the database to prevent clutter and maintain performance.

Mitigation Strategies for Failure Scenarios

1. Database Failures:
   • Implement multi-region database setups to ensure data availability and resilience against regional outages.
   • Use automatic failover mechanisms to switch to backup databases seamlessly when the primary database fails.
2. Cache Misses:
   • Implement a cache warming strategy where frequently accessed URLs are proactively loaded into the cache based on historical access patterns.
3. High Traffic Surge:
   • Use a content delivery network (CDN) to cache static content and absorb traffic spikes, reducing the load on the application servers and databases.
4. Collision Handling:
   • Enhance the random generation algorithm to use more characters or base-58 encoding to significantly reduce the probability of collisions, even with high volumes of URLs.
5. Expired URLs and Data Deletion:
   • Develop an automated scheduled task for cleaning up expired URLs, while also archiving data for analytics purposes.
6. Network Latency and Timeouts:
   • Introduce circuit breaker patterns to prevent hitting services that are under duress, allowing the system to remain responsive even during high-latency scenarios.
7. Data Loss:
   • Ensure that data is replicated in real-time to a backup system and implement regular backup routines to prevent data loss.
8. DDoS Attacks:
   • Set up automated traffic analysis to detect unusual patterns indicating DDoS attacks and apply blacklisting and rate limiting measures dynamically to safeguard the application.

Conclusion

Implementing these future improvements and mitigation strategies will enhance the functionality, performance, and robustness of the URL shortening service. Regular monitoring, testing, and user feedback will be crucial for refining and evolving the system to meet changing demands and technological advancements.