Detailed Component Design

API Gateway

Description: Handles incoming requests, and retrieves data from caching service for popular queries, or routes to Service Layer
APIs
1. POST /api/v1/shorten
  1. Description: Create a short URL for a given long URL
  2. Request Body:

{
  "longUrl": "https://example.com/some/long/url"
}

1. GET /api/v1/redirect/{shortUrlId}
  1. Description: Redirect users to the long URL associated with the given short URL
  2. Response: 302 Redirect to the long URL

Caching Service

Description: Responsible for storing popular queries (retrieving longUrl redirects)
APIs
1. GET /{shortUrl}
  1. Output:

{
  "longUrl": "https://example.com/some/long/url"
}

1. 1. The underlying storing system should utilize Time-To-Live expiration strategy and cache purging to remove stale data
  2. Eviction policy: Can be Least Recently used or Least Frequently used

Load Balancer

Description: Route requests to different instances of Shortener Service based on different conditions like geographical nearest, numbers of instances spawned, etc.

Shortener Service

Description: Responsible for creating and retrieving short URLs
Responsibilities
1. Generate unique short URLs
2. Map short URLs to long URLs
APIs
1. POST /shorten
  1. Input:

{
  "longUrl": "https://example.com/some/long/url"
}

1. 1. Output:

{
  "shortUrl": "abc123"
}

1. 1. Design: It uses the aforementioned Identifier Generation Algorithm to generate shortUrl and store URL mappings to the Database.
2. GET /{shortUrl}
  1. Output:

{
  "longUrl": "https://example.com/some/long/url"
}

1. 1. Design: It retrieves the data entry from Database using shortUrl as index. Returns 404 for shortUrl not found.
Identifier Generation: We need to ensure the generated short URLs are unique and avoid collisions.
1. Sequential IDs: This approach generates identifiers in a linear fashion (e.g., 1, 2, 3, ...). While simple, it can lead to predictable URLs that are easy to guess, which is a security concern. Additionally, it may create bottlenecks in high-concurrency environments. This is not recommended.
2. Random Strings: Generating random alphanumeric strings (e.g., using UUIDs or a base-62 encoding) can help create unique identifiers that are hard to guess. This method reduces the likelihood of collisions but requires a mechanism to ensure uniqueness, which can add complexity.
3. Hashing: Hashing the long URL using algorithms like SHA-256 and then truncating the result can also create unique identifiers. However, this may lead to collisions, necessitating a check against existing identifiers.
4. Custom Patterns: If we want to allow users to specify custom URLs, it requires additional logic to validate and ensure uniqueness across the identifier space.
5. I recommend random strings here. In case a collision happens, we can keep generating random strings, until there is no collision. This ensures the uniqueness of the generated identifier and avoid security concern from sequential IDs.
Non-Functional Requirements
1. Scalability: Can scale horizontally by adding more instances, or vertically by upgrading existing instances
2. Performance: Response time should be under 100ms for URL shortening
3. Reliability: Redundant instances behind a load balancer
  1. Generator Outrages: In case the generator service is unavailable, we could implement a fallback mechanism like maintaining a local cache of recently generated IDs or use a secondary ID generation service.
  2. Split-Brain: This occurs when network partitions occur, causing instances to operate independently without knowledge of each other and generate colliding IDs. We could incorporate a shard-based approach where each node is responsible for a specific range of IDs, reducing the risk of collisions.
4. Consistency: Read operations are consistent. If there is a collision during write operation, where Data Layer returns a collision error, we implement retry mechanism to generate new identifier.

Database

Description: Stores URL mappings and analytics data
Data modeling:
1. URL mapping table
  1. Columns: id (primary key), short_url, long_url, created_at, updated_at
  2. Indexing: Create an index on short_url for fast lookups
2. Analytic data
  1. User metrics
    1. Popular shortUrl queries
    2. User actions (URL creation vs. URL retrieval)
    3. Geographic data
  2. Performance metrics
    1. Response time
    2. Error rates
  3. A/B testing data
Non-functional requirements
1. Scalability: Implement database sharding to distribute data across different instances
2. Performance: Recommend using non-relational database like NoSQL to store data, since queries are simple and require low latency and high scalability
3. Reliability: Database replicas can help recover when one instance is down
4. Consistency: Read operations can be concurrent. Write operations can be concurrent among different database shards.

Submissions

Displaying Solutions with Scores Ranging from 1 to 10

Submissions

Displaying Solutions with Scores Ranging from 1 to 10