Requirements

Functional Requirements:

• Create a short URL for a given long URL.
• Return the long URL associated with a given short URL.

Non-Functional Requirements:

• Should support tens of millions of users
• Should have low latency (30-40 ms)
• Should have high availability (Always available)
• Should be scalable (Support the addition of server instances to manage high traffic volume)

Capacity Estimations:

• Assume we will handle 1 million url shortenings per day
• Assume we need to support 10 million unique users
• Assume we need to support 100 million URL redirects per day
• Assume we need 8 bytes per short URL
• Assume we need 500 bytes for long URL

(1 million URLs/day * 30 days) = 30 million URLs a day * 8 bytes = 240 million bytes (or 0.24 gigabytes)

(100 million URL redirects/day * 30 days) = 3 billion redirects a day * 500 bytes = 1 trillion bytes (or 1000 gigabytes)

API Design

• shortenURL(): This API should take a url and replace it with a smaller version and stores both into the database.
  • Request: { longUrl: string }
  • Response: { shortUrl: string }
• getLongURL(): This API should fetch the long URL from the database and redirect the user to that long URL
  • Request: { shortUrl: string }
  • Response: { longUrl: string }

High-Level Design

The client will first hit a load balancer which will direct the request to the proper server.

Depending on the type of request, the server will call the URL shortening service or the URL redirection service.

The URL shortening service will store the long URL and create a short URL to store into the database.

The URL redirection service will first check the cache to see if we can find the long URL there. If it's not in there, we will check the database. The cache will handle the high volume of read requests to reduce the load on the database.

Detailed Component Design

URL Shortening Service

• Functionality
  • Accepts a long URL
  • Generates a shortened URL by using a hashing algorithm to generate a short unique ID that consists of [a-z][A-Z][0-9]. We can ensure it's unique by first checking if the short URL already exists in the database. We can also hash the user's username along with the URL to ensure uniqueness and prevent collisions.
  • Stores the mapping into our database
• Tech Choice
  • DynamoDB

URL Redirection Service

• Functionality
  • Takes short URL from incoming request
  • Retrieves the long URL from cache. If cache miss, we will retrieve the long URL from the database.
  • Redirects the user to long URL
• Tech Choice
  • DynamoDB
  • Redis

Trade Offs/Tech Choices

• A NoSQL database is used because they're designed to be better at horizontal scaling, if the number of short URL generation and redirects are increased, we can add more servers to handle the load.
• NoSQL is optimized for high volumes of write operations which we need since we will be generating millions of short URLs a day and storing that along with long URLs into our database.