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

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

API that takes in a long url writes it to DB and returns a short url

• this API implements write-back DB style writing to the cache first and flushing asynchronously later
• The API writes the long url, short url, date and time, and user and creates a hash ensuring security
• When writing we partition the DB by alphabetical order breaking htem up into sections to speed up writes and reads
• When actually writing hashes, we can implement linear probing to ensure there are no hash collisions
• When ensuring no URLs are already taken, we can conduct a binary search on the partitioned part of the DB
• When writing, we have a prepopulated DB to mitigate race conditions when 2 different users are attempting to write to the same URL short or long. We institue predicate locks for this

We have another API that takes in a short URL and returns a long URL

• It reads from the cache, and if it misses we add it to the cache implementing Least Recently Used principal

We can aslo implemnt URLs to ensure security and validation

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.

• We would have a backend relational DB like MySQL that has tables detailing the Long URLs, Short URLs, their audit information, and relationship mapping
• We can implement a tiered cache before writing to DB implementing a write-back style
• Next we before that we have a set of servers that can be horizontally scaled
• After that is a reverse proxy that acts as a load balancer directing traffic
• then there is the client that connects to the proxy over HTTPs

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.

• We would have a backend relational DB like MySQL that has tables detailing the Long URLs, Short URLs, their audit information, and relationship mapping
• We can implement a tiered cache before writing to DB implementing a write-back style using Least Recently Used style of cache eviction
• To increase performance, the higher tiered caches are URLs that are clicked or used more frequently
• Next we before that we have a set of servers that can be horizontally scaled
  • If there is an increased amount of traffic, we can add more servers to account for it
• After that is a reverse proxy that acts as a load balancer directing traffic
  • Therefore, if any server goes down, we can allocate traffic accordingly using a round-robin algorithm
  • The load balancer also maintains that no server becomes overwhelmed or is underutilized
• then there is the client that connects to the proxy over HTTPs
• Our client will have input validation to defend against SQL injections and Cross site scripting when dealing with inputs for URLs
• Implements write-back DB style writing to the cache first and flushing asynchronously later
• Within the DB we can implement a B-Tree data structure for quicker read times enhancing our get apis
• The API writes the long url, short url, date and time, and user and creates a hash ensuring security
• When writing we partition the DB by alphabetical order breaking them up into sections to speed up writes and reads
• When actually writing hashes, we can implement linear probing to ensure there are no hash collisions
• To ensure no URLs are already taken, we can conduct a binary search on the partitioned part of the DB which runs in nlogn time rather than linear
• When writing, we have a prepopulated DB to mitigate race conditions when 2 different users are attempting to write to the same URL short or long. We institute predicate locks for this
• The server reads from the cache, and if it misses, we read to the DB and we then add it to the cache implementing Least Recently Used principal
• To mitigate collisions, we auto increment in the DB
• Across these horizontally scaled servers, we can implement data replication ensuring absolute consistency, redundancy, and availability
• These servers will be housed across different regions mitigating risk to regional disasters such as outages, natural disasters, or other risks

nt sends a request to create a short URL

(e.g., POST /shorten)

Load balancer routes the request to an application server

Application server validates input

• checks URL format
• optional auth / rate limiting

Short URL ID is generated

• via hash / ID generator
• collision checked (retry if needed)

Write to cache (L1 or write buffer)

• entry stored immediately for fast subsequent reads
• marked as “dirty” if using write-back

Asynchronous write to database

• DB is the source of truth
• background worker flushes dirty cache entries
• retries on failure

Cache propagation

• popular URLs promoted to higher cache tiers
• less frequent URLs age out naturally via LRU

Response returned to client

• short URL sent back once cache + DB write is acknowledged (or cache-only if eventual consistency is acceptable)