System requirements

Functional:

1. Given a URL, return a shorter URL which points to our service and redirects to the original URL.
2. Be able to service around 200 short URLs being created every second.
3. Be able to service around 2000 short URLs being clicked every second.
4. The short URLs may be edited to point to new URLs
5. The short URLs may be invalidated

Non-Functional:

1. Gather analytics such as click rates for the short URLs, along with referer and client device information for individual click events.

Capacity estimation

There are two categories of data we need to store

1. The short URL data:
   1. Each record consists of a long URL (150 bytes), a short URL (8 bytes), a user id (20 bytes), a status (1 byte), a creation time stamp (8 bytes), an expiration time (8 bytes), which adds up to 145 bytes
   2. 200 records per second are created, which gives us a little over 800 gigabytes per year. Rounding it up to 1 TB/year, we can estimate we would need 20TB of storage after 20 years. If we also factor in around 10% growth, then at the end of 20 years we would need 57.27 TB. This is relatively manageable.
2. Analytics data: We don't need to keep analytics data forever, but it promises to be quite voluminous as it is linked to _clicks_ rather than URL creations, and also because we may collect several data points for each click. That being said, this is going to be a write heavy workload with an infrequent read. I propose we use a database designed specifically for analytics loads such as BigQuery, Redshift, or Snowflake. We can adjust our collection and retention strategies in the future to manage storage costs for this kind of data.

API design

We will ignore analytics collection for now, and focus on the functional requirements, which are creation, editing, and reading of short URLs. As such we would need the following API routes

GET /api/:short_url

Purpose: Meant to get the target URL associated with a short URL. Expects short_url as path argument, and returns a HTTP Temporary Redirect.

Response: 302 target_url

PUT /api/:short_url

Purpose: Meant to update the short URL

Request body args:

• new_url: optional string, if the URL needs to be updated
• invalidated: optional boolean, if the URL needs to be invalidated or revived

Response: 200

PUT /api/shorten

Purpose: Meant to create a short URL

Request body args:

• target_url: required string

Response: 200, along with short_url

Database design

Each record will contain the following

1. user_Id: string
2. target_url: string
3. short_url: string
4. status: boolean
5. creation_time: string
6. expiration_time

We don't need to aggregate, or model complex relationships in this data, so we can use a read optimized no-sql database such as DynamoDB.

High-level design

Our system consists of

1. A load balancer. The client contacts the load balancer.
2. Multiple frontend servers depending on the traffic. This is where we serve our web frontend from.
3. Multiple application servers depending on the traffic. This is where we provide our REST API. Our frontend access the API through our load-balancer.
4. A Write through in-memory key-value cache. This is used to speed up lookups of frequently visited short URLs.
5. Short URL database. This is where short URL data lives. We would want to emphasize availability and partition tolerance by accepting eventual consistency, thus employing some sort of consensus algorithm. However most database systems now come with such features built-in and let you tune the level of consistency and availability as per your needs.
6. Analytics service. This service is responsible for writing analytics data to our analytics database. Depending on our needs, we may write our in-house analytics service, or utilize a COTS solution such as Segment or Amplitude. Both our frontend and application servers communicate with the analytics service.
7. Analytics database. This is where our frequently written, infrequently read, voluminous analytics data lives. I recommend an analytics focused database such as Redshift, BigQuery, or Snowflake for this piece.

Request flows

Creating a short_url

Visiting a short_url

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...

Trade offs/Tech choices

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

Failure scenarios/bottlenecks

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

Future improvements

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