System requirements

Functional:

• Create short URL from an arbitrary URL
• Given a short URL, redirect the user to the original URL

Non-Functional:

• Scalability - the amount of required resources should increase at a manageable rate
• Abuse prevention - the system should be protected from misuse such as distributed denial-of-service (DDOS) attacks and fake traffic
  • Could use something like CloudFlair to detect DDOS and bot traffic

Capacity estimation

• Daily storage = (10^2 bytes / URL) * (5*10^6 URLs) = (5*10^8B) * (1MB / 10^6B) = 5*10^2MB = 500MB
• Yearly storage = (500 MB / day) * (365 days / year) = 182,500MB / year = 182GB / year
• QPS (reads) = (5 * 10^7 queries / day) * (1day / 10^5s) = 5*10^2 queries / second = 500 queries / second
• QPS (writes) = QPS (reads) / 10 = (500 queries / second) / 10 = 50 queries / second

Notes

• 100 characters per URL
  • 1 character = 1 byte (ASCII)
  • 100 bytes / URL
• Base62 encoding
  • 6 characters can encode ~60 billion values
  • 1 character = 1 byte (ASCII)
  • 6 bytes per URL
• 1 million users
• 5 million URLs generated per day
  • ~2 billion URLs generated per year
• 50 million URL reads / redirects per day

API design

For simplicity, we'll focus on just creation of a short URL and retrieval of the original URL.

Create Short URL:

Endpoint: POST /short_url

Request structure:

```json

{

"url": "string"

}

```

Response structure:

```json

{

"shortUrl": "string

}

```

Get URL:

Endpoint: GET /url?short_url_id={string}

Response structure

```json

{

"url": "string"

}

```

This endpoint will return a 404 if the provided short URL doesn't exist.

Database design

Given the traffic estimates of 50 writes per second and 500 reads per second, it doesn't matter much what time of database is used for this system. However, I'm more familiar with relational databases, so I would use something like PostgreSQL or MySQL.

The database schema just requires a column for the short URL key (AKA ID) and another column for the original URL.

High-level design

In this design, the client first hits an API gateway that will route the request to the appropriate service. The API gateway can have functionality such as rate limiting, DDOS protection, and authentication / authorization to protect the system from undesired traffic and to enforce restrictions as needed. For simplicity, I won't delve into the configuration of the API gateway.

Request flows

Once the request passes the checks of the API gateway, it is forwarded to a service instance.

For requests to create a URL, the service will generate a hash of the original URL and use it as the key / ID of the short URL and then persist the entry (shortURL and original URL) in the database.

For read requests, the service will first check the cache for the given short URL. If the URL is in the cache, then it'll be returned. Otherwise, the service will fetch it from the database.

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

• The database requires a cluster with leader-follower replication. It's not necessary to handle the expected traffic since a single instance would be sufficient. However, it is necessary to add resilience to the system in case an instance were to fail
• The services are stateless and use the cache and database for any shared state
• The API gateway and cache also have multiple instances for resilience
• Also, all components can be horizontally scaled based on traffic

Trade offs/Tech choices

• The short URL ID is generated by taking the hash of the original URL, which is not the most optimal approach since it doesn't guarantee there will be duplicate hashes
• The infrastructure is hosted in a single data center for simplicity

Failure scenarios/bottlenecks

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

• Network partitions aren't explicitly designed for in the current design. For instance, if the network connectivity between the services and the database and cache are disrupted, then the system should have a defined behavior

Future improvements

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

1. The infrastructure in the design lies in a single data center. To minimize latency for users located far from the data center, the system should be distributed across multiple data centers. However, introducing multiple data centers will add complexity to the system. For instance, it would have to deal with data synchronization
2. The hash generation logic should be moved to a dedicated component like a sequencer to ensure that all generated IDs are unique
3. The database might need to be horizontally sharded as it grows