System requirements

Functional:

1. URL Shortening:
   1. 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. Expriation:
   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 the system can handle concurrent access without performance degr
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

Assume following:

• 1 million new URL shortening per day = 30 million/month
• 10 million unique users
• 100 million URL redirections per day

Number of URLS for 5 year period = 30 million * 5 * 12 = 1.8 billion.

Assume 8 characters/URL. Combination of 62 characters [A-Z, a-z, 0-9]. Gives a total of 3.2 trillion unique URLs

Storage:

• Short URLs: 1.8 billion * 8 bytes = 14.4GB
• 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 1TB

API design

1. POST /api/v1/urls/shorten: This is the endpoint that accepts original URL, generates a hash and appends the hash to the URL and the shortened URL will be returned
2. GET /api/v1/urls/<alias>: endpoint that will accept the short URL and redirect to the original URL

Database design

Table 1: Short URLs

• 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. Web Server:
   1. Handles incoming HTTP requests
   2. Validates and routes requests to the appropriate service
2. Url Shorteninzg Service:
   1. Generates short URLs and stores them in the database
   2. Manages alias availability and expiration
3. Redirection Service:
   1. Handles redirection based on the alias
   2. Logs analytics data
4. Cleanup Service:
   1. This service helps in cleaning the old data from the databases which includes expired links and inactive users
5. Load Balancers: Add at locations:
   1. Between clients and application servers
   2. Between application servers and database servers
   3. Between application servers and cache servers
6. Caching:
   1. Since reading from db can be slow and resource expensive, 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

Detailed component design

1. URL Shortening Service:
   1. Functionality:
      1. Accepts a Long URL
      2. Generates a unique alias or uses a custom one if available
      3. Stores the mapping the ShortURLs table
   2. Tech Choices:
      1. Language: Python/Node.js
      2. Storage: MongoDB/Redis
2. Redirection Service:
   1. Functionality:
      1. Take a short URL alias from the incoming request
      2. Retrieves the original URL from the database
      3. Redirects the user to the original URL
   2. Tech Choices:
      1. Language: Node.js
      2. Caching: Redis for frequently accessed URLs

Trade offs/Tech choices

Database Choice:

Using a NoSQL is good in this scenario because:

1. Schema Flexibility
   1. NoSQL databases provide schema flexibility, allowing you store data in a flexible JSON-like foramt. This is beneficial for URL shortening service where the structure of data may evolve
2. Scalability:
   1. 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 node to distribute the load.
3. High Write Throughput:
   1. Sevice involves 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. Allows you to store data in JSON-like format. 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):
  • High availability is more critical than consistency in this scenario. Users expect quick access to short URLs and downtime or delays in availability are less acceptable
• 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 is not 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 incosistencies 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 mechanism 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 CDN for caching and distributing load through load balancers

Future improvements

1. Real-time analytics
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