System requirements

Functional:

List functional requirements for the system (Ask the chat bot for hints if stuck.)...

1. Given a long URL, create a shortened one.
2. The shortened URL redirects to the long one.
3. The shortened URL does not expire.
4. Users cannot create accounts.
5. The same long URL always returns the same short URL.
6. Custom short url
7. Analytics
8. Batch shortening
9. Url validation

Non-Functional:

List non-functional requirements for the system...

Scalability: The service should be able to handle a potentially large number of users requesting URLs simultaneously and scale up as needed.

Availability: The service should be up as much as possible, ensuring high uptime for users.

Performance: The system should respond to URL shortening and redirection requests with low latency.

Consistency: The system should consistently return the same short URL for a given long URL, ensuring a reliable mapping for users.

Capacity estimation

Estimate the scale of the system you are going to design...

1. Data Size Per URL

Based on your breakdown, the storage requirements for each URL entry are:

• id: 4 bytes
• long URL: 100 bytes (max 100 characters)
• shortened URL: 20 bytes (max 20 characters)
• created_at: 4 bytes

Total size per URL:

[ \text{Total size per URL} = 4 + 100 + 20 + 4 = 128 \text{ bytes} ]

Given your assessment of 130 bytes per URL (which includes potential rounding or overhead), we can proceed with your calculation.

2. Daily URL Creation Storage

If you are creating 50,000 URLs each day, your daily storage requirement is:

[ \text{Daily Storage} = 50,000 \times 130 = 6,500,000 \text{ bytes} \quad $\text{or } 6.5 \text{ MB}$ ]

3. Yearly Storage Calculation

Over a year:

[ \text{Yearly Storage} = 6.5 \text{ MB/day} \times 365 \text{ days} \approx 2,372.5 \text{ MB} ]

Adding the 1,500,000 bytes (or 1.5 MB) as you suggested to account for additional data, you would have:

[ 2,372.5 \text{ MB} + 1.5 \text{ MB} \approx 2,374 \text{ MB} \quad \text{or } \approx 2.37 \text{ GB} ]

4. Total for 5 Years

To estimate the total storage for 5 years:

[ \text{Total for 5 Years} = 2,374 \text{ MB} \times 5 \approx 11,870 \text{ MB} \quad \text{or } \approx 11.87 \text{ GB} ]

So the total estimate is closer to about 11.87 GB over the span of 5 years, rather than 12.5 GB.

You can project anywhere from 250,000 to several million reads per day based on various scenarios

• Writes: ~30 writes/min
• Reads: ~175 reads/min

API design

Define what APIs are expected from the system...

1. POST /url
   • Description: Creates a shortened URL.
   • Request Body: { "long_url": "string" }
   • Response: Returns the generated short URL.
2. POST /custom_url
   • Description: Creates a custom shortened URL.
   • Request Body: { "long_url": "string", "custom_url": "string" }
   • Response: Returns the custom short URL if successfully created or an error if the custom URL is already in use.
3. GET /url
   • Description: Retrieves the long version of the shortened URL.
   • Request URL: /url/{short_url}
   • Response: Redirects to the long URL or an error if the short URL does not exist.
4. POST /batch/url
   • Description: Creates a batch of shortened URLs.
   • Request Body: { "urls": ["long_url_1", "long_url_2", ...] }
   • Response: Returns a mapping of short URLs to long URLs.
5. GET /analytics/{short_url}
   • Description: Gets analytics data about the shortened URL.
   • Response: Returns statistics such as click count, referrer, and timestamps of clicks.

Database design

Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...

Database Design Overview

1. Reason for SQL:
   • The data is well-structured (URLs and their associated analytics), making SQL a suitable choice.
   • Your projected storage needs (around 20 GB every 5 years) are manageable and well within typical SQL database limits.
   • SQL databases provide strong consistency, which is vital for maintaining the mapping of long URLs to short URLs.
2. Vertical Scaling:
   • As you mentioned, you can scale vertically by upgrading your existing database server with more CPU, memory, and storage, which is suitable given your growth forecast.
3. Indexes:
   • Creating indexes on the short_url column will significantly enhance performance in terms of retrieval speed, making queries for the redirection of short URLs efficient.

Table Structure

Here’s a structured outline of the two tables you defined:

1. Table: urls

CREATE TABLE urls ( id SERIAL PRIMARY KEY, long_url VARCHAR(255) NOT NULL, short_url VARCHAR(20) UNIQUE NOT NULL, created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP);

• id: A primary key to uniquely identify each row.
• long_url: The original long URL.
• short_url: A unique shortened URL representation.
• created_at: Timestamp for when the entry was created.

2. Table: analytics

CREATE TABLE analytics ( id SERIAL PRIMARY KEY, url_id INT REFERENCES urls(id) ON DELETE CASCADE, referrer VARCHAR(255), click_count INT DEFAULT 0, created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP);

• url_id: A foreign key referencing the urls table, linking analytics data back to the corresponding URL.
• referrer: Captures the source from which the user arrived (optional).
• click_count: A counter for the number of times the corresponding short URL has been accessed.
• created_at: Timestamp for when the record was created.

Transactions for Consistency

Using transactions for creating URLs and their associated analytics is crucial for maintaining data integrity:

• When you create a new short URL, you'd want to ensure that both the URL creation and the recording of its analytics happen together.
• If either operation fails, the entire transaction would be rolled back, guaranteeing that no partial records are created.

Sample Transaction

Here’s a high-level example of how a transaction might look when creating a new URL:

BEGIN; INSERT INTO urls(long_url, short_url) VALUES ('https://example.com/some-long-url', 'shortUrl1234')RETURNING id INTO new_url_id; INSERT INTO analytics(url_id, referrer) VALUES (new_url_id, 'https://referrer.com');

High-level design

You should identify enough components that are needed to solve the actual problem from end to end. Also remember to draw a block diagram using the diagramming tool to augment your design. If you are unfamiliar with the tool, you can simply describe your design to the chat bot and ask it to generate a starter diagram for you to modify...

High-Level Design Overview

1. User Request: The user sends a request to shorten a URL or access a short URL.
2. Load Balancer: Acts as a traffic manager to distribute incoming requests to available app servers, ensuring no single server is overwhelmed.
3. App Servers:
   • For a shorten URL request:
     • Check the database to see if the long URL already exists.
     • If it exists, return the corresponding short URL.
     • If it does not exist, store the new mapping of the long URL to a short URL and respond with the new short URL.
     • Store analytical data related to the URL creation.
   • For a redirect request:
     • Fetch the long URL corresponding to the short URL from the database.
     • Redirect the user to the long URL and log analytics data for that URL visit.

Request flows

Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...

• user requests to create a url, it checks if it exists, if not, it's created and returned, if it does, then we return it right away
• user requests to read url, it fetches the long url and redirects user. If it doesn't exist then a 404 is returned.
• user requests analytics, we fetch is based on the shortened or long url and return the data.

Detailed component design

Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...

1. Caching Popular URLs

Using a caching mechanism (like Redis or Memcached) to store the most frequently accessed short URLs will indeed allow for expedited retrieval, especially for high-traffic URLs.

2. Identifying Popular URLs

To determine which URLs are popular, using click counts is the most straightforward approach. Here are a few ways to implement this:

• Separate Table for Popular URLs:
  • You can create a dedicated table that keeps track of URLs based on their click counts. This table could be regularly updated to reflect the most frequently accessed URLs.
  • For example, a table structure could look like this:

CREATE TABLE popular_urls ( id SERIAL PRIMARY KEY, url_id INT REFERENCES urls(id) ON DELETE CASCADE, click_count INT DEFAULT 0);

• Using Existing Analytics Data:
  • You can utilize the existing analytics table to derive the most popular URLs by querying based on the click_count. This way, you dynamically determine popularity without needing additional storage.

SELECT url_id, SUM(click_count) as total_clicks FROM analytics GROUP BY url_id ORDER BY total_clicks DESCLIMIT N; -- Where N is the number of top URLs you wish to fetch

3. Caching Logic

• Initial Load: Upon starting your application or at specific intervals (e.g., daily), you can query your database to fetch the most popular URLs as determined by the above methods and populate your cache.
• Cache Updates:
  • Whenever a URL is accessed, increment its click count in the analytics table.
  • Periodically (e.g., every few minutes or once an hour), you should check click counts and update the popular URLs table or cache to reflect changes in popularity.
• Cache Lifetime: Set an expiration or a TTL (time-to-live) for cache entries to ensure that it doesn't hold outdated data indefinitely.

Cache Retrieval Flow

Here’s how the flow would look when a user requests a short URL:

1. User Requests Short URL: The request hits the load balancer and is directed to an app server.
2. Check Cache: The app server first checks the cache for the requested short URL.
   • If Found in Cache: Return the long URL quickly.
   • If Not Found in Cache:
     • Query the database to fetch the long URL.
     • After retrieving, store this URL in the cache for future requests.
3. Increment Click Count: Update the analytics table to increment the click count for that URL.

Implementing a message queue for handling analytics reporting is a smart approach, especially for high-traffic URLs that experience a significant number of read requests. This strategy allows your system to offload immediate write operations away from the main application flow, improving overall responsiveness and scalability. Let’s break down how this can work effectively:

1. Using a Message Queue

A message queue (such as RabbitMQ, Kafka, or AWS SQS) can facilitate asynchronous processing of analytics data. Here's how it would fit into your architecture:

Flow for URL Read Requests and Analytics

1. User Requests Short URL: A user clicks on a short URL.
2. Load Balancer & App Server: The request gets routed through the load balancer to an app server, which fetches the corresponding long URL.
3. Increment Click Count:
   • Instead of directly updating the analytics table right away (which could create a bottleneck),
   • Publish to Message Queue: The app server sends a message to the queue with relevant analytics data (like the short URL identifier and optional referrer).
4. Analytics Processor: A separate consumer service that listens to the message queue processes incoming analytics messages.
   • It dequeues messages and updates the analytics database in a more controlled and efficient manner, batching updates where possible.
5. Redirect User: The app server redirects the user to the long URL.

2. Benefits of This Approach

• Decoupling: By decoupling the analytics processing from the main user request cycle, your application can respond faster to users.
• Scalability: The analytics processing service can scale independently based on the volume of messages in the queue, allowing for handling bursts of traffic more effectively.
• Batch Processing: The analytics processor can accumulate counts and perform batch writes to the database, reducing the overhead associated with frequent single-row writes.

3. Potential Considerations

• Message Retention: Decide how long the message queue should retain messages in case the analytics processor is down or needs to be scaled.
• Error Handling: Implement mechanisms to handle failures in processing messages, such as retries or dead-letter queues for messages that can’t be processed successfully.
• Eventual Consistency: Understand that there will be some delay between the clicks being recorded in the analytics table and the actual user redirection, but this delay is typically acceptable in analytics use cases.

1. Batching Click Events

By batching click events, you can aggregate several actions into a single message that represents a total count. This reduces the number of messages sent to the analytics processor.

How It Works:

• Aggregation Logic: Maintain an in-memory structure (e.g., a dictionary or hash map) in your app server to accumulate click counts based on the referrer and the URL.
• Time Window: Set a time window (e.g., 10 seconds) during which click events are aggregated. If the same short URL is clicked multiple times from the same referrer within that window, increment the count in memory rather than sending multiple messages.
• Message Generation:
  • After the period or when a threshold (e.g., 5 clicks) is reached, send a single message to the analytics queue that contains the total count for that referrer.
  • This message might look something like:
  • { "short_url": "shortUrl1234", "referrer": "https://referrer.com", "click_count": 10, "timestamp": "2023-10-01T12:00:00Z"}

2. Benefits of Batching

• Reduced Latency: Fewer messages means less time spent sending and processing each message.
• Lower Database Load: By sending aggregated counts rather than individual click events, you decrease the number of write operations to the analytics table.
• Improved Throughput: The analytics processor can process larger batches of data at once, making it more efficient.

Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...

• Used sql instead of nosql because my data is structured and can scale vertically, plus I need consistency. But it's tougher to scale horizontally or if my data becomes more unstructured like for analytics.

Failure scenarios/bottlenecks

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

• Too many write requests to the analytics service.
• Database failure.

Future improvements

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

• we'll use a leader follower pattern with our db to handle it going down and retain our data.