Requirements

Functional Requirements:

List the key functional requirements for the system (Ask the AI for hints if stuck)...

• generate a smaller URL from a larger URL
• the same URL should not be used twice
• the small URL should redirect to the original URL

Non-Functional Requirements:

List the key non-functional requirements (performance, scalability, reliability, etc.)...

• the URL shortening service should have 5 nines availability
• your generated URL should redirect to the original URL for up to 1 year
• latency of the redirect should be below a 100ms

Capacity Estimation

Estimate the scale of the system. Consider daily active users, read/write ratio, storage requirements, bandwidth, and any relevant QPS calculations...

The system is more read than write heavy.

1M DAU who create one link a day. These links are visited at least 50 times a day.

write volume: 1,000,000 writes / day / 100,000 = 10 writes / second

read volume: 500 reads / second

API Design

Define the APIs expected from the system. This is your chance to analyze and define the read and write paths so that you can come up with the high-level design...

• createTinyURL(original URL)
• redirectURL(tiny URL)

High-Level Design

Describe the overall system architecture. Identify the main components needed to solve the problem end-to-end. Use the diagramming tool to create a block diagram.

This diagram shows the high-level architecture of a URL shortening service. A user sends a request through the API Gateway/Load Balancer to the URL Shorten Service, which generates a unique identifier and stores the mapping between the shortened URL and the original URL in a NoSQL database. For users visiting a shortened URL, the request goes through the API Gateway and CDN to the Redirection Service. The redirection service first checks the cache for the URL mapping and falls back to the database when needed, allowing frequently accessed URLs to be served quickly while reducing database load.

Database Design

Define the data model. Identify the main entities, their attributes, and relationships. Consider the choice of database type (SQL vs NoSQL) and justify your decision based on access patterns....

we are going to use a Key-Value store in the NoSQL database: I would opt to use a DynamoDB or Cassandra DB. While all of these come with built in sharding, but that's something we would add based on consistent hashing to make sure the keys are evenly distributed.

Detailed Component Design

Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.

NoSQL databases use B trees to make reads very fast.

• Key Value Stores

API Gateway:

• use it when you have multiple microservices in your system, so clients don't have to learn how to communicate with your various services independently.
• you can have client-to-gateway services (where you have a load balancer in front of your gateway, so you can add multiple clients for your gateway service) or gateway to client (where your api gateway does the load balancing in front of your services)
• Examples of LBs are NGINX and AWS ELB.
• API Gateways handle Authentication, rate-limiting, throttling, routing requests, and request validation.

Caching architectures:

• Cache-Aside checks the cache and falls back to the DB and writes to the cache then
• LRU - Least Recently Used
• LFU - Least Frequently Used makes more sense for our use case because it adapts to spikes in traffic well