Requirements

Functional Requirements:

• Create a short URL for a given long URL.
• Return the long URL associated with a given short URL.

Non-Functional Requirements:

• List the key non-functional requirements (eg low latency, scalability, reliability, etc.)...
• Redirection request should be low latency < 100 ms
• this is read heavy system with 100:1 read write ratio and we should be able to handle scale of 100M read request daily
• System should be highly available it would be bad for other business if user is not able to access their website
• Short Url should not be predictable otherwise compititior can crawl

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

CREATE FLOW:

POST /create

Request:

url : longUrl

user: user details

Response:

shortUrl : 200 Ok

Read FLOW:

GET /{shortUrl}

Response: 302 Redirect to long 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.

Database Entity

URL MAPPING

ShortURL

LongUrl

Gateway:

1. Request Routing: It directs incoming requests to the appropriate service, whether it's for creating a short URL or retrieving the original URL.
2. Rate Limiting: To ensure fair usage and protect against abuse, the entry layer can implement rate limiting, controlling how many requests a user can make in a given timeframe.
3. Load Balancing: It can distribute incoming traffic across multiple instances of backend services to enhance performance and availability.
4. Authentication and Authorization: If your service requires user accounts or custom URLs, the entry layer can manage user authentication and enforce access controls.
5. Response Formatting: It formats the responses from backend services before sending them back to the client, ensuring consistency in the API's output.

READ FLOW:

API server will check in cache if short url exists it will redirect otherwise it will read from db and update the cache and then redirect

if not found we will send 404 error

Cache will use LRU strategy and we will use 80-20% we will be storing 20% of the db size in redis and this will updated every time we miss a url and hit the db entry will be made in redis before returning to user

CREATE FLOW:

user sends a request to API server api server will generate a random unique id and will encode it and then save this entry in our db and will return this encoded unique id to customer

Unique Id Genration Process:

Every time a API server will start it will ask for a range from redis sever redis server will increase the current range by 1000 and then return the number say x

our api server then will use ids from x+1 till x+1000 if the range exhausted then it will again ask for next range

if range start to exhaust very frequently we can allocate bigger blocks but if a server dies then we will loose those many ids which is okay i think as we are enough keys to trillions of record if use base64 encoding with just 7-8

letters

Since out API Server now stateless we can horizontally scale on db side single server is sufficient to store as i am expecting at most 1B url and each entry is 100Kb in TB size so we can shard with shortUrlId if we arise need to scale the db layer

We can use a simple Key Value Storage like Dynamo DB for our purpose and in case we server dies we can loose those range of keys which is fine in our case

Storage Layer(Dynamo DB ):

1. Supports Quick Lookup for key
2. Allow Horizontal Scalability out of the box
3. Highly Avalible

and we will be using REST service for our enrty point

if we need analytics we can drop a message in kafka queue every time we read a url that we will be then consumed by analytics service but for this i am keeping it out of scope

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.