System requirements

URL shortening is used to create shorter aliases for long URLs. We call these shortened aliases “short links.” Users are redirected to the original URL when they hit these short links. Short links save a lot of space when displayed, printed, messaged, or tweeted. Additionally, users are less likely to mistype shorter URLs.

For example, if we shorten the following URL through TinyURL:

We would get:

The shortened URL is nearly one-third the size of the actual URL.

URL shortening is used to optimize links across devices, track individual links to analyze audience, measure ad campaigns' performance, or hide affiliated original URLs. The system should be able to handle millions of URLs, allowing users to create, store, and retrieve shortened URLs efficiently. Each shortened URL needs to be unique and persistent. Additionally, the service should be able to handle high traffic, with shortened URLs redirecting to the original links in near real-time. In some cases, the service may include analytics to track link usage, such as click counts and user locations.

Functional:

1. Create Short URLs: Given a long URL, the service generates a unique, shortened alias that redirects to the original long URL. The shortened URL should use a compact format with English letters and digits to save space and ensure uniqueness.
2. Redirect to Long URLs: When a user accesses the short URL, the service should redirect them to the corresponding long URL with minimal delay.
3. Expiration of Short URLs: Some services offer the option to set an expiration time for the short URL, after which it becomes inactive.
4. Link Analytics: The system should be able to track the number of times each shortened URL is accessed to provide insights into link usage.
5. Custom Link. Users should optionally be able to pick a custom short link for their URL.

Scale Requirements:

1. 500 million new URL shortenings per month
2. Read:write ratio = 100: 1
3. Data retention for 5 years

Non-Functional:

1. High Availability: The service should ensure that all URLs are accessible 24/7, with minimal downtime, so users can reliably reach their destinations. If our service is down, all the URL redirections will start failing.
2. Low Latency: URL redirections should occur almost instantly, ideally in under a few milliseconds, to provide a seamless experience for users.
3. High Durability: Shortened URLs should be stored reliably so they persist over time, even across server failures, ensuring long-term accessibility.
4. Security: The service must prevent malicious links from being created and protect user data, implementing safeguards against spam, abuse, and unauthorized access to sensitive information.
5. Shortened links should not be guessable (not predictable).

Capacity estimation

Traffic estimates: Assuming, we will have 500 million new URL shortenings per month, then 100 * 500M = 50B redirections/month

QPS(Write): 500M / (30 days*24hours* 3600seconds) =~200 URL/s

QPS(Read/Redirection): 200URL/s * 100 = 20000 redirection/s

Storage estimates: 500M * 12months*5years = 30B URLS

If we assume one link size 500bytes

30B* 500bytes = 15TB

Bandwith (write): 200 URL/s * 500B = 100 Kb/s

Bandwith (read): 100 Kb/s * 100 = 10Mb/s

Memory estimates (cache):

20K * 3600 seconds * 24 hours = ~1.7 billion

To cache 20% of these requests, we will need 170GB of memory.

0.2 * 1.7 billion * 500 bytes = ~170GB

API design

• Create Short URL API. POST /shorten.

Parameters:

1. 1. original_url (string, required): The original long URL that needs to be shortened.
   2. custom_alias (string, optional): A custom alias for the shortened URL if the user wants to specify one.
   3. expiration_date (timestamp, optional): The date and time when the shortened URL should expire.
   4. user_id (string, optional): The ID of the user creating the shortened URL, if user accounts are supported.

Response:

1. 1. shortened_url (string): The shortened URL generated by the service.
   2. creation_date (timestamp): The date and time when the URL was shortened.
   3. expiration_date (timestamp, if provided): The expiration date of the shortened URL.

• Redirect API. Endpoint: GET /{shortened_url}.

Parameters:

1. 1. shortened_url (string, required): The shortened URL that needs to be resolved to the original URL.

Response:

1. 1. original_url (string) with status code 301

• Analytics API. GET /analytics/{shortened_url}. Parameters:
  1. shortened_url (string, required): The shortened URL for which analytics data is requested.
  2. start_date (timestamp, optional): The start date for filtering analytics data.
  3. end_date (timestamp, optional): The end date for filtering analytics data.

Response:

1. 1. click_count (integer): The total number of times the shortened URL has been clicked
   2. unique_clicks (integer): The number of unique users who clicked the shortened URL.
   3. referring_sites (list): The sites that referred traffic to the shortened URL.
   4. location_data (map): Geographic distribution of users who clicked the URL.
   5. device_data (map): Breakdown of devices (mobile, desktop, etc.) used to click the URL.

• URL Management API. GET /user/urls

Parameters:

1. 1. user_id (string, required): The ID of the user whose URLs are being requested.
   2. page (integer, optional): The page number for paginated results.
   3. page_size (integer, optional): The number of results per page.

Response:

1. 1. urls (list): A list of URLs shortened by the user, including metadata like creation date and expiration date.

• Delete Short URL API. Endpoint: DELETE /{shortened_url}.

Parameters:

1. 1. shortened_url (string, required): The shortened URL that needs to be deleted.
   2. user_id (string, required): The ID of the user requesting the deletion.

Response:

1. 1. status (string): Confirmation of deletion or error message if the operation fails.

How do we detect and prevent abuse? A malicious user can put our service out of business by consuming all URL keys in the current design. To prevent abuse, we can limit users to a certain number of URL creations and redirections per some time period (which may be set to a different duration for different user types).

Database design

A few observations about the nature of the data we will store:

1. We need to store billions of records.
2. Each object we store is small (less than 1K).
3. There are no relationships between records—other than storing which user created a URL.
4. Our service is read-heavy.

A highly available NoSQL database (e.g., DynamoDB or Cassandra) is used to persist mappings between long URLs and short aliases. NoSQL is preferred for its high write throughput, horizontal scalability, which aligns well with the structure of URL mappings.

Alternatively we can also use RDBS (for example MySQL) with single leader replication strategy because URL shortening service is a read-heavy application.

High-level design

URL Shortening

Users should be able to input a long URL and receive a unique, shortened alias. The shortened URL should use a compact format with English letters and digits to save space and ensure uniqueness.

The design for URL shortening follows a basic two-tier architecture that processes requests quickly and scales to handle high volumes:

1. Client: The frontend application sends HTTP POST requests containing long URLs to the URL Shortening service.

2. URL Shortening Service: The backend receives requests and is responsible for creating and returning shortened URLs. It performs these key functions:

• Generates a unique, short alias by encoding the URL or using hashing techniques to ensure uniqueness.
• Stores the mapping of long URLs to short aliases in the database.
• Manages errors and ensures each short URL is unique across all users.

3. Database: A highly available NoSQL database (e.g., DynamoDB or Cassandra) is used to persist mappings between long URLs and short aliases. NoSQL is preferred for its high write throughput, horizontal scalability, and key-value storage model, which aligns well with the structure of URL mappings.

URL Redirection

When users access a shortened URL, the service should redirect them seamlessly to the original URL with minimal delay.

The URL redirection service ensures that users accessing a shortened URL are quickly redirected to the original URL with minimal delay. This design focuses on high read throughput and low latency, as the read traffic will be significantly higher than URL creation.

1. API Gateway: As we now have two request types, we need an API Gateway. This acts as the entry point for all incoming requests, routing POST requests to the URL Shortening Service and GET requests to the URL Redirection Handler.

2. URL Redirection Request Handler: Accepts GET requests with the shortened URL, retrieves the original URL from the cache or database, and responds with a 302 Found status and the original URL in the Location header to facilitate seamless redirection.

3. Caching Layer: To reduce latency and offload read requests from the database, we implement a caching layer (e.g., Redis) that stores frequently accessed URL mappings in memory, making retrieval almost instantaneous.

4. Database: In cases where a URL is not found in the cache, the system retrieves it from the NoSQL database (previously implemented for URL Shortening) and updates the cache to optimize future requests.

3. Link Analytics

The system should be able to track the number of times each shortened URL is accessed to provide insights into link usage.

To track the number of accesses for each shortened URL, we introduce an Analytics Service that counts and stores access events in real time. This setup provides useful insights into link usage patterns and is designed to scale for high traffic.

1. API Gateway: Routes GET requests to both the URL Redirection Handler (for redirection) and the Analytics Service (for tracking access).

2. Analytics Service: Tracks each URL access by incrementing a counter associated with the short URL. This service logs access events and can be optimized by using a lightweight in-memory counter before periodically updating the database.

3. In-Memory Database: For high-speed access counting, we use an in-memory data store like Redis to cache the counters for each short URL. This enables real-time tracking and reduces the load on the main database.

4. Database: Periodically, the Analytics Service flushes the in-memory counters to the main NoSQL database to ensure persistent storage of access counts.

Request flows

Detailed component design

Generating Unique Hash

After generating a unique integer ID for each URL, we need to encode it into a shorter, readable string to create a user-friendly shortened URL. The encoding method must balance shortness with usability, avoiding special characters that might be confusing or hard to type.

Several encoding options were considered:

Option 1: Hexadecimal (Base16)

Characters: Uses digits 0-9 and letters a-f, making 16 possible characters.

Example: The integer 123456 is encoded as 1e240 in hex.

Pros: Widely recognized and straightforward to implement.

Cons: Not compact enough for URL shortening; a 64-bit integer in hex would result in a 16-character string, which is too long for our needs.

Option 2: Base64

Characters: Uses A-Z, a-z, 0-9, +, /, and =, making 64 possible characters.

Example: The integer 123456 is encoded as MTIzNDU2 in Base64.

Pros: More compact than hex, resulting in shorter strings.

Cons: Uses special characters (+, /, =), which can cause issues in URLs and make typing more difficult.

Option 3: Base62 (Chosen Solution)

Characters: Uses A-Z, a-z, and 0-9, totaling 62 characters.

Example: The integer 123456 would be encoded as W7E in Base62.

Pros: Shorter strings without special characters, making it ideal for URLs. A Base62 encoding of 6 characters can represent over 56 billion unique IDs, which meets our system's requirements.

Cons: Slightly more complex encoding/decoding process since 62 is not a power of 2, but manageable.

Expiration of Short URLs

Should entries stick around forever, or should they be purged? If a user-specified expiration time is reached, what should happen to the link?

If we chose to continuously search for expired links to remove them, it would put a lot of pressure on our database. Instead, we can slowly remove expired links and do a lazy cleanup. Our service will ensure that only expired links will be deleted, although some expired links can live longer but will never be returned to users.

Whenever a user tries to access an expired link, we can delete the link and return an error to the user.

A separate Cleanup service can run periodically to remove expired links from our storage and cache. This service should be very lightweight and scheduled to run only when the user traffic is expected to be low.

We can have a default expiration time for each link (e.g., two years).

After removing an expired link, we can put the key back in the key-DB to be reused.

Should we remove links that haven’t been visited in some length of time, say six months? This could be tricky. Since storage is getting cheap, we can decide to keep links forever.

URL redirecting

301 redirect vs 302 redirect.

301 redirect. A 301 redirect shows that the requested URL is “permanently” moved to the long URL. Since it is permanently redirected, the browser caches the response, and subsequent requests for the same URL will not be sent to the URL shortening service. Instead, requests are redirected to the long URL server directly.

302 redirect. A 302 redirect means that the URL is “temporarily” moved to the long URL, meaning that subsequent requests for the same URL will be sent to the URL shortening service first. Then, they are redirected to the long URL server.

Each redirection method has its pros and cons. If the priority is to reduce the server load, using 301 redirect makes sense as only the first request of the same URL is sent to URL shortening servers. However, if analytics is important, 302 redirect is a better choice as it can track click rate and source of the click more easily.

For our case we should choose 302 because we have analytic's requirements.

Trade offs/Tech choices

There are some trade-offs I am making when designing the read/write flows around the cache. Some choices are who is adding things to the cache and who is just reading from the cache. We are trading off write latency (which is OK to be slow) with read latency (which we care that is fast).

Another trade we are making is around consistency. We are again trading off consistency for latency, we want the request to be serving reads as fast as possible without fully waiting for all replications to complete. The reason is again we care about latency and most likely link doesn't need to be immediately available within seconds of creation. Since our users would probably not share a link instantly.

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

Future improvements

One potential issue with the current design of generating IDs on demand is that it could become a bottleneck under high load. we need to generate a unique ID for each new URL as requests come in and save it to the database. The high load could overwhelm the database.

This is where we want to consider pre-generating a batch of IDs periodically or when the system starts up, and then hand them out as needed.

The advantages are:

1. This has the advantage of being able to handle a sudden influx of requests.
2. We also have lower latency since we don't need to generate an ID from scratch when a request comes in (although this is a small overhead).

The downside is that:

We lose the timestamp property of the ID. Since in our current design, the timestamp is part of the ID, we lose the ability to track when the URL was created by looking at the ID. This may even be an advantage for security in the case of URL shorteners since we don't want to leak the creation time of the URL. In an application like Twitter, we want the opposite-we want the ID to encode the creation time of the URL.

It's also more complex to implement as we need to manage the batch of IDs and ensure that we don't run out and have to generate more IDs when the batch is exhausted. This is extra infrastructure to maintain.

We could end up generating more IDs than we need which could lead to inefficiencies and wasted resources.