System requirements

Functional:

1. URL Shortening:
   1. The system should provide a mechanism to shorten long URLs.
   2. Shortened URLs should be unique and not collide with existing ones.
2. Redirection:
   1. When users access a shortened URL, they should be redirected to the original long URL.
   2. The redirection process should be fast and seamless.
3. Custom Alias:
   1. Users should have the option to customize their short URLs with a chosen alias (if available).
   2. Alias should be unique across the system.
4. 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.
5. API:
   1. Offer a RESTful API to allow integration with other services and applications.
   2. API should support URL shortening, retrieval, and analytics retrieval.

Non-Functional:

1. Scalability:
   1. The system should handle a large number of URL shortening requests and clicks.
   2. Scalability should be achieved through horizontal scaling.
2. Performance:
   1. The redirection process should be fast, with minimal latency.
   2. Ensure that the system can handle concurrent access without performance degradation.
3. Reliability:
   1. The service should be highly available and have minimal downtime.
   2. Implement mechanisms for fault tolerance and disaster recovery.
4. Storage:
   1. Efficiently store and retrieve a large number of short URLs and their associated data.
   2. Use reliable and scalable storage solutions.
5. Backup and Recovery:
   1. Regularly backup data to prevent data loss.
   2. Implement a recovery process to restore data in case of failures.
6. Security:
   1. Implement security measures to prevent misuse and unauthorized access to short URLs.
   2. Support HTTPS for secure data transmission.

Capacity estimation

Let us assume our service will have the following usage patterns:

• 1 million new URL shortenings per day. which means an average 30 million shortenings per month.
• 10 million unique users.
• 100 million URL redirections per day.

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.

Storage Estimation for 5 years:

• • Short URLs: 1.8 Billion * 8 bytes = 14.4 GB
  • Long URLs: 1.8 Billion * 500 bytes = 900 GB
  • Other metadata: 1.8 Billion * 100 bytes = 180 GB

Total: ~1TB for 5 years (per database)

Every replication will need to be 1TB or more

API design

1. Create Short URL:

2. Retrieve Original URL:

3. Get URL Analytics:

Filters: date range, geography

GET /api/analytics/:shortUrl Response: { "clicks": 1023, "geography": { "US": 600, "IN": 200, "Other": 223 } }

Database design

• Table 1: ShortURLs
  • id (Primary Key)
  • alias
  • original_url
  • created_at
  • expiration_date

• Table 2: User
  • user_id (Primary Key)
  • name
  • email
  • password
  • Created_at

High-level design

1. API Gateway:
   1. Handles incoming HTTP requests.
   2. Validates and routes requests to the appropriate service.
   3. RateLimits and identify malicious inputs
2. URL Shortening Service:
   1. Generates short URLs and stores them in the database.
   2. Manages alias availability and expiration.
   3. Horizontally scalable
3. Redirection Service:
   1. Handles redirection based on the alias.
   2. Logs analytics data.
   3. Horizontally scalable
4. Cleanup Service:
   1. This service helps in cleaning the old data from the databases which includes expired links and inactive users.
   2. We can have a batch job that can run frequently to clean up expired records.
5. Load Balancers: To handle a large number of requests, we can use a load balancer to distribute incoming traffic across multiple instances of the services. We can add a Load balancing layer at three places in our service:
   1. Between Clients and services
   2. Between Services and database servers
   3. Between services and Cache servers
6. Caching:
   1. Since reading from the database can be slow and resource-intensive, we can add a caching layer to speed up read operations. We can use in-memory caches like Redis or Memcached to store the most frequently accessed URLs.

Request flows

Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...

Detailed component design

1. URL Shortening Service:

• Functionality:
  • Accepts a long URL.
  • Generates a unique alias or uses a custom one if available.
  • Stores the mapping in the ShortURLs table.
• Tech Choices:
  • Language: Python/Node.js
  • Storage: MongoDB/Redis



2. Redirection Service:

• Functionality:
  • Takes a short URL alias from the incoming request.
  • Retrieves the original URL from the database.
  • Redirects the user to the original URL.
• Tech Choices:
  • Language: Node.js
  • Caching: Redis for frequently accessed URLs.

3. Implement rate limiting on the shortening endpoint to avoid abuse of the service. For example, a limit of 100 requests per minute per user can be established to ensure fair usage.

Trade offs/Tech choices

Database choice:

Using a NoSQL database for a URL shortening service has several advantages, making it a good choice for certain aspects of the system. Here are some reasons why a NoSQL database may be suitable for this scenario:

1. Schema Flexibility:
   1. NoSQL databases, such as MongoDB or Redis, provide schema flexibility, allowing you to store data in a flexible, JSON-like format. This is beneficial for a URL-shortening service where the structure of data (e.g., short URLs, custom aliases, analytics) may evolve.
2. Scalability:
   1. NoSQL databases are generally designed to scale horizontally, making it easier to handle the growing volume of data and increasing traffic associated with a URL-shortening service. As the number of short URLs and analytics data increases, you can add more nodes to distribute the load.
3. High Write Throughput:
   1. URL shortening services involve a high volume of write operations, especially when generating and storing new short URLs. NoSQL databases are often optimized for high write throughput, making them suitable for scenarios where new data is frequently added.
4. Document-Oriented Storage:
   1. Many NoSQL databases are document-oriented, allowing you to store data in a JSON-like format. This is advantageous for storing complex data structures associated with short URLs, such as metadata, analytics, and custom alias information.

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

1. Database Outage:
   1. Bottleneck: Redirection and URL shortening services heavily depend on the database. A failure to reach the database or high latency to get the result might lead to a bad user experience.
   2. Mitigation: Implement caching mechanisms to retrieve URLs that are in high demand and load balancing to handle partial outages.
2. High Traffic Peaks:
   1. Bottleneck: Sudden spikes in traffic could overwhelm the system in case the URL is added as a backlink to a popular webpage.
   2. Mitigation: Use a content delivery network (CDN) for caching and distributing load through load balancers.

Future improvements

1. Real-time Analytics: analytics service to provide real-time data.
2. Link Customization Options: Expand customization options, such as allowing users to set vanity paths.
3. Integration with External Analytics Tools: Allow users to integrate their short URLs with external analytics tools like Google Analytics.
4. Smart Alias Generation: Implement smarter algorithms for alias generation to improve user experience.

Feedback:

High Level Design

Your high-level design for a URL shortening service captures essential components effectively, demonstrating an understanding of how a system of that nature would operate. However, there are areas for improvement, deeper exploration, and consideration of trade-offs that can help elevate your design to a more advanced level. Below is a detailed analysis along with suggestions for improvement.

Analysis of High-Level Design

1. API Gateway

• Strengths: Incorporating an API gateway is crucial for managing incoming requests, enforcing security measures like authentication and rate limiting, and serving as a single entry point.
• Improvements: Consider implementing a service mesh or API management platform (like Istio or Kong) to handle microservices communication, tracking, and logging more effectively. Include features such as global request tracing to understand user behavior better and find any bottlenecks in real-time.

2. URL Shortening Service

• Strengths: The design mentions alias generation and storage, which are crucial functionalities of a URL shortening service.
• Improvements:
  • Algorithm for Generating Short URLs: Consider using a base-conversion algorithm to generate short URLs by encoding numeric IDs in a shortened form. Using a combination of alphabets and numbers can boost the number of possible URL variants. For example, using Base62 (0-9, A-Z, a-z) can significantly expand your range.

Request for URL Shortening

Generate Unique ID

Encode Unique ID using Base62

Store Short URL Mapping

Return Short URL

• Database Selection: Use a NoSQL database (like MongoDB or DynamoDB) for quick lookup, storage, and retrieval of mappings. Ensure your data model allows for easy querying by the short URL.

3. Redirection Service

• Strengths: Having a dedicated service for redirection adds value through analytics and possible performance enhancements.
• Improvements:
  • Implement a caching layer (e.g. Redis) to store frequent URL mappings temporarily, significantly reducing lookup times.
  • Include monitoring tools to track the performance metrics related to the redirection service.

4. Cleanup Service

• Strengths: Addressing expired links is a vital part of maintaining a URL shortening service.
• Improvements: Instead of a batch job that may run occasionally, consider implementing a background job queue (like Celery) for cleaning up old records. This provides flexibility and responsiveness for handling notifications and cleaning tasks asynchronously.

5. Load Balancers

• Strengths: Deploying load balancers to distribute requests is essential for scaling.
• Improvements: Utilize a layered approach with multiple load balancers (Application Load Balancer + Network Load Balancer). Ensure that session affinity is considered if the service maintains session states.

6. Caching

• Strengths: Using caching is imperative to enhance performance.
• Improvements: Extend caching strategies by implementing cache expiry policies and employing cache invalidation mechanisms to enhance data consistency. For instance, utilize a “write-through cache” for real-time caches.

Proposed Technologies

Here are several technologies that could enhance your design:

• Redis or Memcached: For caching short URL mappings and improving read performance.
• RabbitMQ or Kafka: For asynchronous message processing, providing resilient and scalable cleanup services.
• MongoDB: A NoSQL database that can be easily scaled and supports flexible data structures, perfect for storing URL mappings and metadata.
• Grafana + Prometheus: For efficient monitoring and alerting to give insight into the system's health and performance.

Alternative Designs

Consider exploring alternative designs, such as:

• Microservices Architecture: Splitting the URL shortening service into more granular microservices, such as dedicated services for analytics, user management, and a separate URL shortening service. This approach increases resilience and scalability but requires more robust inter-service communication (possibly utilizing REST or gRPC).
• NoSQL vs. SQL Trade-offs: If your service needs complex queries on relationships (for example, user bases, active links), a relational database may be beneficial despite the additional complexity.

Algorithms and Data Structures

• Hashing: Consider using a hashing mechanism for the original URL to create a unique identifier. You can optimize collision management strategies by implementing double hashing or chaining.
• Bloom Filters: These can help in checking if a long URL has already been shortened, reducing redundancy. Bloom filters have a small memory footprint and are efficient for membership checks albeit with a possibility of false positives.

Exists

Not Exists

User Requests Short URL

Check Bloom Filter

Return Existing Short URL

Generate Short URL

Store in Database

Final Recommendations

1. Consider Security: Implement HTTPS, validation, and sanitization for URLs to prevent malicious inputs and ensure user safety.
2. Implement Real-Time Analytics: Utilizing tools such as Google Analytics or building a custom analytics service could provide user insights and usage metrics.
3. Documentation and Testing: Ensure you have adequate documentation (API specs, architectural diagrams) and automated tests covering unit, integration, and load scenarios to ensure system reliability and maintainability over time.

Conclusion

Your high-level design for a URL shortening service captures many essential components and principles. By incorporating the above improvements, technologies, and alternative considerations, you can evolve your design toward a more robust, scalable, and efficient solution, transitioning from a junior to a mid-level or even senior design thinking approach. Focus on exploring each component in depth and understanding the trade-offs involved in technological choices, which can significantly enhance your problem-solving capabilities in system design.