Requirements

Functional Requirements:

• Create a short URL for a given long URL.
• Return the long URL associated with a given short URL.
• An efficient algorithm to create a short url

Non-Functional Requirements:

• High Availability: System must be up 99.999%
• High Scalability: Needs to be accessible globally
• Eventual Consistency: Should not choke the system if a write is not complete, and nodes are slightly out of sync
• High Scalability: With an increase in traffic, the system should have an automatic horizontal scalability setup. Since it is stateless, it makes it easier to do so

API Design

• POST: /tinyurl/{long_url}
  • Returns 201 Created
  • Must also return shortened link
• GET: /tinyurl/{short_url}
  • Returns 302 Redirect
    • Must hit the server before redirecting to save analytics data for later

High-Level Design

• Load Balancer
  • Redirects to the node cluster based on location so the server does not get overwhelmed
• API Layer
  • Components: Main API Server, Rate Limiter, any additional security checks
    • Main API Server
      • Handles both GET and POST requests
      • Saves metadata for shortened url
    • Rate Limiter
      • Can use a bucket strategy based on ip address to protect from malicious attacks on the server.
    • Other security checks
      • Using JWT tokens to only allow a specific limit to users to create urls
• Cache Layer
  • API Layers checks cache if there's a hit on long_url, if not check DB then saved into cache
  • TTL for items should be 10 minutes since we don't expect changes to urls but we do want to help reduce load on db and lower latency
• DB Layer
  • Main storage for long_url to short_url
  • Schema
    • PK: id
    • long_url: string
    • short_url: string
    • other fields

Detailed Component Design

• URL Shortening algorithm
  • Create as short as possible
  • 62 = len([a-z][A-Z][0-9])
  • 62^7 number of possible short urls
  • Based62 approach or Traditional encryption CRC32
  • CRC32 Approach
    • Uses CRC32 to encrypt long_url to create a short
    • Must handle collisions
    • If there are collisions, add a fix suffix to make it unique
  • Based62
    • Each number is associated with a character
      • 0-25: a-z
      • 26-51: A-Z
      • 52-62: 0-9
    • Based62 current id until 0
    • String will always be unique
    • Con predictable to find the next iterate
  • We can select CRC32 approach this can introduce a little more security
• Caching Strategy
  • Uses a cache-aside strategy if there's a miss in the cache
  • TTL Policy: ejects after 1-minute reduce cache bloat
  • Cache Bloat: Cache needs to flush items ever minute
  • Georeplicated so when changes happen in one node it should ripple to other nodes to stay in sync
  • During updates of urls this should also be updated to indicate that the cache is not hosting stale data

How do you handle failure modes?

If there's a network outage, what path should we use to resolve it?

Should the load balancer immediately recognize the issue and redirect to clean path?

That also means the database needs to be georeplicated, especially if an entire area example WEST 2 is not accessible.

• The design should include a more detailed strategy for handling network outages and system failures, including failover mechanisms and data backup strategies.

• Consider adding more detail on how the system will achieve high availability and scalability. This could include details on database sharding, data replication strategies, and the use of cloud-based services for scalability.

• Address potential issues with data consistency in a distributed system. This could include strategies for ensuring eventual consistency, such as the use of vector clocks or conflict-free replicated data types (CRDTs).

Failover Mechanisms

• Redundancy:
  • Running multiple clusters globally to create redundancy
• Health Checks:
  • Run automated health checks to detech failures and trigger failover processes. Can check if each path clears successfully
• Load Balancing
  • Helps distribute traffic across multiple servers
• Data Replication
  • Databases both sql storage and cache have async replication
  • If API Layer cannot reach DB it should have automatic system to point to a replica