System requirements

Functional:

1. url shortening : The system should generate a short URL when provided with a long URL.
2. url redirection : The system should redirect users from the short URL to corresponding long URL.
3. url expiration management: The service should allow users to specify expiration dates for short URLS after which short URLS should no longer redirect to the longs URLS.
4. user management: users should be able to create an account to manage their short URLS, view analytics, delete URLS if needed.
5. custom short links: user should have option to create custom short URLs instead of automatically generate ones.

Non-Functional:

1. Scalability: The system should be able to handle increasing volumes of requests, including both URL shortening and redirection, without significant performance degradation. for example it should accommodate growth from a few hundred requests per second to thougsands over time.
2. Availability: The service needs to be highly available with minimal downtime. ideally, the system should target an uptime of 99.9% or higher to ensure users can access the URLs at any time.
3. Performance: The response time for redirecting from a short URL to a long URL should be very low, typically under 10 milliseconds. The URL shortening process may take longer ideally under 10 seconds.
4. Security: The service should protect against malicious use, such as phishing attacks or spreading malware. This may involve implementing URL validation, monitoring and rate limiting to prevent abuse.
5. Data Privacy: The system should comply with data protection regulations( e.g. GDPR) and ensure that user data is handled securely.
6. Usability: The service should have a user friendly interface, making it easy for users to create and manage their short links.
7. Maintainability: The architecture of the system should allow or easy updates and maintenance. it should be modular, enables developers quickly identify and fixes issues.

Capacity estimation

1. Traffic Estimates:
   • for functionality (1) - creating short URLs: Assume an estimate of around 200 requests per second(RPS) for creating short links
   • for functionality (2) - Redirecting short URLs to Long URLs: A much higher estimate can be around 20,000 RPS for redirection due to high voloume of users accessing URLs.
2. Data Size Estimates:
   1. Assume that the average long URL is about 100 characters.
   2. the short url is typically about 8 characters
   3. Each URL entry may include:
      1. Long URL (100 bytes)
      2. short URL (8 bytes)
      3. Created Time ( 8 bytes)
      4. Created by User ID (20 bytes)
      5. Expiration Time ( 8 bytes)
   4. Thus, each entry could be approximately 144 bytes. for similicity's sake, we can round to 256 bytes total.
3. Daily Data Generation:
   1. Calculate how much data is generate daily:
      1. for short URLs : (200 RPS * 86400 seconds) * 256 bytes
      2. for url redirection , while this dats isn't stored, it is important to know that it can heavily influence load, as these would be the traffic metrics
4. Long term data storage:
   1. assuming the service runs continuously for 5 years
      1. 4.4 (GB/day) * 365 * 5 = 8 TB of data
      2. adding some buffer for growth, let's estimate about 15TB over 5 years

API design

1. shortenURL
   • Method : POST
   • Endpoint: /shorten
   • Description: accepts a long URL and returns a short URL.
   • Request Body:

{

"long_url": "http://example.com/some/long/url",

"user_id": "user123",

"expiration_time": "2024-12-31T23:59:59Z" // optional

}

• • Response:

{

"short_url": "http://short.url/abc123",

"created_at": "2024-01-01T12:00:00Z",

"expiration_time": "2024-12-31T23:59:59Z" // optional

}

1. redirectURL
   1. Method: GET
   2. Endpoint /r/{short_code}
   3. Description: accepts a short code and redirects to corresponding long URL.
   4. response: this is a redirect response with http status 302 to long URL.
2. getOriginalURL
   1. method : get
   2. endpoint: /original/{short_code}
   3. description: returns the original long url associate with short code
3. deleteURL
   1. method: delete
   2. endpoint: /delete/{short_code}
   3. delete a short url mapping
4. getUserURLs
   1. method: get
   2. endpoint /user/{user_id}/urls
   3. description: list all short urls created by the user

Database design

1. Data Model

A key-value store is highly effective for this use case, providing quick access to the mappings between short URLs and long URLs. Here’s how we can break down the schema:

Entities and Attributes

Short URL Mapping

• Short URL (Primary Key): Unique identifier for the shortened URL (e.g., abc123).
• Long URL: The original lengthy URL that the short URL will redirect to.
• Created Time: Timestamp indicating when the short URL was created.
• User ID (Foreign Key): The identifier of the user who created the short URL (if user management is implemented).
• Expiration Time: Time until which the short URL is valid.

ER Diagram

1. a single user can create multiple urls

High-level design

High-Level Architecture Overview

1. Client: The end-user applications (web or mobile) that interact with the shortening service.
2. API Gateway: The entry point for all client requests. It manages incoming traffic, routes requests to appropriate microservices, handles authentication, and implements rate limiting.
3. Shortening Service: The core service responsible for accepting long URLs and generating short URLs. It also manages the mappings between them and communicates with the database and caching layers.
4. Cache Layer (e.g., Redis): Used to cache mappings of short URLs to long URLs for quick access. This reduces database load and improves response times for redirection requests.
5. Database: A persistent storage system (like DynamoDB, MongoDB, or MySQL) that stores long URL mappings, user metadata, and expiration details.
6. Monitoring/Logging: This component tracks performance metrics, logs events for debugging, and sends alerts for anomalies or issues.

Request flows

Request Flow for shortenURL

Here’s a breakdown of the flow for creating a short URL:

1. Client Request: The user sends a request to create a short URL with the long URL, user ID, and optional expiration time.
2. API Gateway: The request first hits the API Gateway, which routes it to the Shortening Service.
3. Shortening Service:
   • The service generates a short code for the long URL.
   • It stores the mapping (short URL, long URL, user ID, expiration time) in the database.
   • Optionally, it updates a cache entry (if a caching layer is used) for quick access later.
4. Response: The service sends a response back to the client that includes the short URL that was created.

Request Flow for redirectURL

1. Client Request: The user accesses a short URL.
2. API Gateway: The request is routed via the API Gateway.
3. Cache Check: The system first checks the cache to see if the short URL is registered.
4. Redirect Logic:
   • Cache Hit: If found, it retrieves the long URL and responds with a redirect to the client.
   • Cache Miss: If not found, it queries the database for the corresponding long URL.
   • After fetching the long URL from the database, it updates the cache for future requests.
5. Response: Finally, the user is redirected to the long URL.

Detailed component design

Let’s delve deeper into three critical components of the URL shortening service: the Shortening Service, the Cache Layer, and the Database. We’ll look at their scaling capabilities, underlying algorithms, data structures, and how they interact with each other.

1. Shortening Service

Functionality:

• Responsible for receiving long URLs and generating short URLs.
• Maps short URLs to long URLs, manages user associations, and handles expiration.

Algorithms and Data Structures:

• Random String Generation: To create short URLs, a random string generator can be used to ensure uniqueness. For example, a simple algorithm can generate an 8-character alphanumeric string.
• Collision Handling: If a generated short URL already exists, a check can be implemented to re-generate a new string until a unique one is found.
• Hashing (optional): Alternatively, you might use a hash function (like SHA-256) on the long URL to create a short URL, followed by a truncation step, with collision handling for any duplicates.

Scaling:

• The Shortening Service can scale horizontally by creating multiple instances behind a load balancer. This allows it to handle a higher number of requests simultaneously.
• As load increases, you can also optimize the service with increased caching or by using background processing (e.g., using a job queue).

2. Cache Layer (e.g., Redis)

Functionality:

• A high-speed in-memory caching layer that stores frequently accessed mappings between short URLs and long URLs.
• Caches result sets for redirects to minimize database lookups.

Algorithms and Data Structures:

• Key-Value Store: Redis operates as an in-memory key-value database, which is ideal for caching short URL mappings.
• Least Recently Used (LRU): Implement an LRU eviction policy to remove the least accessed entries when the cache limit is reached. Redis provides built-in support for LRU eviction.

Scaling:

• Redis can scale horizontally by adding more nodes and partitioning the dataset among them (Redis Cluster).
• It can handle thousands of simultaneous connections, making it suitable for high-volume read operations.

3. Database (e.g., DynamoDB)

Functionality:

• Stores the mappings of short URLs to long URLs permanently, including user metadata and expiration.

Algorithms and Data Structures:

• Key-Value Access: Utilize primary keys for fast lookups of short URLs. Each item can be stored as a document (in a NoSQL context) or a row in a relational database.
• Secondary Indexes: In NoSQL databases, you can create secondary indexes on user IDs or expiration times to swiftly query and manage user-specific data.

Scaling:

• DynamoDB is designed to scale automatically based on demand, providing consistent performance as the number of requests grows.
• It offers provisioned and on-demand capacity modes, allowing you to adjust capacity settings dynamically.

Trade offs/Tech choices

When designing a URL shortening service, several trade-offs and technology choices must be made to balance between performance, scalability, maintainability, and complexity. Here’s an overview of important trade-offs and the reasoning behind chosen technologies.

1. Database Type: SQL vs. NoSQL

• Trade-Off: Choosing between a relational database (like MySQL) versus a NoSQL database (like DynamoDB or MongoDB).
  • Reason for NoSQL: Given that a URL shortening service expects high read/write traffic, a NoSQL database was chosen due to its ability to scale horizontally and provide high throughput. The flexibility in data schema is also beneficial for accommodating changes in user metadata or mappings.
  • Downside: NoSQL databases typically don’t enforce strict ACID properties, which could lead to eventual consistency issues in certain scenarios. However, the need for rapid access to short URL mappings outweighed this concern.

2. Use of Caching Layer

• Trade-Off: Introducing a caching mechanism (e.g., Redis).
  • Reason: By adding a caching layer, the service can significantly reduce the number of database reads for frequently accessed short URL mappings, thus improving response times for users. This is essential for handling high loads without degrading performance.
  • Downside: The added complexity of maintaining cache coherence and ensuring cache expiry policies can lead to stale data if not managed correctly. A strategic approach, such as utilizing TTL (time-to-live) for cache entries, was adopted to minimize these risks.

3. Request Handling: Synchronous vs. Asynchronous

• Trade-Off: Synchronous processing for API responses versus asynchronous handling for URL shortening.
  • Reason for Synchronous: For user-facing requests like shortenURL, synchronous processing is preferred to provide immediate feedback to users. However, if the service expands to heavy URL analytics, some operations can transition to an asynchronous model to prevent blocking and allow for higher scalability.
  • Downside: Synchronous requests might lead to bottlenecks during peak loads, but immediate user feedback remains critical for a smooth user experience in this context.

4. Microservices vs. Monolith

• Trade-Off: Opting for a microservices architecture versus a monolithic architecture.
  • Reason for Microservices: This design choice enables independent deployment and scaling of different components, such as the shortening service, caching layer, and user management. It allows teams to develop and deploy services independently, leading to increased agility.
  • Downside: Microservices introduce complexity in inter-service communication and require robust orchestration and monitoring. However, the benefits in terms of decoupled scaling and development outweigh the initial overheads.

5. Database Consistency vs. Availability

• Trade-Off: Choosing consistency models in connection to high availability.
  • Reason: Prioritizing availability for the redirect functionality was paramount, allowing users to access URLs even with potential stale data from the cache. This aligns with typical use cases where users prioritize fast responses.
  • Downside: This choice may result in users occasionally being redirected to outdated long URLs if a mapping hasn’t propagated through the caching layer, but the service accepts this in favor of responsiveness.

6. Security Measures

• Trade-Off: Implementing authentication for user management versus allowing public access to URL shortening.
  • Reason for Selective Authentication: While the API has endpoints for shortening URLs that can be accessed without authentication, user-specific operations (like listing or deleting URLs) are protected. This balances ease of access for general usage and security for user-sensitive data.
  • Downside: Making parts of the service public may lead to misuse or abuse (e.g., spam links). Implementing rate limiting and monitoring access logs helps mitigate these risks.

Summary

Overall, the tech choices made were informed by the specific needs of the URL shortening service, emphasizing scalability, performance, and user experience. Each trade-off was carefully considered, taking into account the potential impacts on system reliability, maintainability, and security.

Failure scenarios/bottlenecks

1. Database Failure

• Scenario: The database goes down due to hardware failure, software bugs, or other issues.
• Impact: If the database is unavailable, the service will fail to store new URL mappings and may not be able to retrieve existing mappings needed for redirection.
• Mitigation:
  • Implement database replicas to provide failover capability.
  • Use a managed database solution that offers automatic backups and failover mechanisms.
  • Consider a caching layer (like Redis) to serve requests while the database is down, minimizing downtime.

2. Cache Misses

• Scenario: A large amount of traffic results in frequent cache misses if the cache is not sized appropriately.
• Impact: Cache misses lead to increased load on the database, which can slow down response times for redirect operations and lead to potential bottlenecks.
• Mitigation:
  • Use an LRU eviction strategy to ensure popular entries remain in cache.
  • Implement a cache preloading mechanism by populating the cache with frequently accessed URLs based on historical data.

3. High Load on Redirect Service

• Scenario: High volume of simultaneous redirect requests due to a viral link or marketing campaigns.
• Impact: The service may experience slow response times or become unresponsive if it cannot handle the traffic.
• Mitigation:
  • Use load balancing to distribute requests evenly across multiple instances of the redirector service.
  • Scale out instances of the redirector service dynamically based on traffic load.
  • Utilize CDNs (Content Delivery Networks) to cache common short URLs geographically closer to users.

4. Rate Limiting and Abuse

• Scenario: Malicious users may attempt to overload the system by rapidly creating numerous short URLs or overusing the redirect functionality.
• Impact: This could lead to performance degradation, denial of service, or resource exhaustion.
• Mitigation:
  • Implement rate limiting on API endpoints to restrict the number of requests from a single user within a specified time frame.
  • Monitor usage patterns and apply IP blocking for abusive behavior.
  • Use CAPTCHA for user registration or URL creation to mitigate spam.

Future improvements

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