System requirements

Functional:

• Given a long URL, the system should return a short URL
• Given a short URL, the system should redirect to the long URL

Non-Functional:

• The system should be highly available
• The system should have low latency

Capacity estimation

• Let's assume we'll store each shortened URL for 10 years.
• Let's assume we'll create 1000 short URLs per second.
• That's 1000 * 60 * 60 * 24 * 365 * 10 = 315360000000 = 315 billion URLs in 10 years
• We'll use the A-Z,a-z,0-9 character set. Therefore we have 62 characters at our disposal.
• 62 ^ 1 = 62 unique URLs if we use 1-character URLs (< 315 billion)
• 62 ^ 6 = 56800235584 (56 billion) unique URLs if we use 6-character URLs (< 315 billion)
• 62 ^ 7 = 3,521,614,606,208 = 3.5 trillion unique URLs if we use 7-character URLs

We need to use at least 7 characters in our URLs.

Each short URL is approximately 7 bytes

Let's assume each long URL will be a maximum of 100 characters in length, therefore it's 100 bytes of storage

The user metadata and URL clicks info is about 500 bytes in size

Therefore, we have a ceiling of 1000 bytes to store for each URL (long, short, and user and URL clicks metadata)

For 315,360,000,000 URLs * 1000 bytes = 315,360,000,000,000 bytes = 315 Terabytes

API design

Define what APIs are expected from the system...

• POST /api/urls
  • input: JSON payload with long URL

• • output:
    • 201 created. JSON response with shortened URL

• • • 400 Bad Request
    • 409 Conflict
• GET /api/urls/{urlID}
  • input: URL ID as path parameter
  • output:
    • 404 Not Found
    • 410 Gone
    • 301 Redirect
      • We can also return a 302 to cache the result

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

Given that we estimate that 1000 URLs will be created per second, we can expect to have 1000 DB writes per second. Therefore we can estimate to have between 10000 to 100000 reads per second.

We can use a NoSQL database for this solution since we are not really looking for ACID compliance. Apache Cassandra, MongoDB, etc would be good

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

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

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

We can use the URL Shortener Service to generate all possible short URL keys (3.5 trillion URL keys) and store then in a SQL database (the keys DB) and we can mark each key as either used or not used. We need to use an ACID-compliant DB in the event that a key is assigned to two separate users.

We can have a background job service that runs once a day and purges URLs that have maxed their TTL.

We'll introduce a caching layer to cache popular URLs. We can choose either an LRU cache or a TTL cache to implement a cache eviction policy.

For our database. We can use a key-based sharding system to distribute URLs across the shards. We can also implement master-slave replicas for each shard. We can use the master for read-and-write operations and the slaves for read-only operations.

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?

• We can implement input validation to ensure we do not store malicious URLs
• We can implement rate limiting to prevent DDoS attacks and limit requests from a single source
• We can implement logging and monitoring by using tools like Elastic Search, Kibana, Logstash, etc, to ensure we can troubleshoot our system when something goes wrong