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. The frontend servers serve up the Web application providing the user interface for our URL shortening service.
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. Auth Service: this service provides the authentication and authorization service.
5. Auth database: this is the database containing user details such as name, user id, account status etc.
6. A Write through in-memory key-value cache. This is used to speed up lookups of frequently visited short URLs.
7. 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.
8. 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.
9. 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

Frontend server

This provide the user interface for our visitors (people who visit a short url) and users (people who create and manage short urls). the frontend servers utilize the auth server for user authentication, and the application server for creating, editing, and reading short urls. It is essentially a CRUD interface.

Application server

The application server provides the REST API for creating, editing, invalidating, and reading short URLs. When creating a short URL, the application server checks the user details to ensure the user can create a short URL. Then it generates a short URL as discussed later, writes it to both the cache as well as the database, and finally returns a suitable response to the frontend server.

When editing a short URL (changing the target URL or invalidating it), the application server again checks user details to make sure the user is authorized to make these changes, and updates the database and cache with the new details.

When resolving a short URL, the application server first checks the cache. If the target URL is found, then it is returned to the frontend, otherwise the application server checks the database, updates the cache with the value that has been found, and returns it as part of the API response. In case a target is not found, then the server returns a 404 response.

URL Shortening

We want to come up with a hashing function that when given a URL string, returns a hashed value. We know that 200/seconds over 20 years translates to more than 57 billion URLs that must be shortened. That means our hashed value (consisting of 9 digits, 26 lower case, and 26 upper case letters) needs to be up to 8 digits long (62^8).

A straightforward way to generate a hash is to use a common hash function like MD5, CRC32 etc. However, all of these provide strings longer than 8 letters, which means we end up with wasted space. We can try to minimize this by utilizing only a part of the output hash, but than can lead to hash collisions, which can be resolved by repeatedly checking for collisions and updating our hash. That's slightly inefficient but we can use techniques like bloom filters to speed that up.

Another approach might be to generate unique ids (I suggest emulating Twitter's Snowflake id generation approach) and encode the id using base 62 encoding. with a structured id generation like snowflake along with a random component (), we can virtually eliminate the security concern of being able to guess the next id, or of having hash id collisions.

Load balancer

The load balancer helps spread our traffic across multiple frontend server instances (and the API calls over multiple application server instances). This is also where we implement things like rate limiters to protect our system from abuse such as DDOS attacks.

Trade offs/Tech choices

For URL shortening, I have suggested Base 62 encoding a unique id, instead of a more straightforward approach such as CRC32 or MD5. I have done this to avoid repeated hash collisions which would cause repeated rehashing.

I have also suggested using COTS solutions for analytics instead of building in-house systems, as that is a non-functional requirement and there are mature, well established solutions available in the market.

Failure scenarios/bottlenecks

The database layer can often be a source of failures, especially if only one instance is used. I propose using a distributed database system layout along with a suitable consensus approach such as PAXOS in order to promote availability and partition tolerance. With our requirements, we can tolerate eventual consistency, so this is a perfect scenario for such a set-up.

Future improvements

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