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

Component 1: URL Storage & ID Generation (Database)

We use a relational database such as MySQL as the source of truth, storing:

• short_url_id (primary key)
• long_url
• creation timestamp
• optional user metadata

ID Generation

Instead of hashing with linear probing, we use a globally unique ID generator:

• Auto-increment ID or Snowflake-style IDs
• Encode the numeric ID into Base62 ([a-zA-Z0-9]) to form the short URL

Why this works

• Guarantees uniqueness without collision handling
• O(1) write performance
• No cross-node coordination for collision resolution

Indexing & Data Structures

• Primary key and secondary indexes use B-trees, providing O(log n) reads
• Optimized for read-heavy workloads

Scaling & Partitioning

• Database is sharded by ID range or hash
• Each shard can scale independently
• Read replicas handle GET traffic

Tradeoffs

• Strong consistency for writes
• Slightly higher write latency than NoSQL
• Operational complexity for sharding

Component 2: Tiered Caching System

We implement a multi-tier cache (e.g., Redis/Memcached) in front of the database.

How it Works

• L1 cache: most frequently accessed URLs
• Lower tiers: progressively less popular URLs
• LRU eviction policy used at each tier

Write Strategy

• Write-back cache
• Writes go to cache first
• Marked as dirty and flushed asynchronously to DB

Read Path

1. Check L1 cache
2. Fall through tiers
3. On miss, read from DB and promote entry upward

Scaling

• Cache nodes scale horizontally
• Hot keys naturally bubble to higher tiers

Tradeoffs

• Faster reads (critical for redirects)
• Eventual consistency risk
• Requires background flush workers and failure handling

Component 3: Application Servers & Load Balancer

Application Servers

• Stateless REST APIs
• Horizontally scalable
• Handle:
  • input validation
  • rate limiting
  • ID generation
  • cache + DB coordination

Load Balancer

• Reverse proxy (e.g., NGINX / ELB)
• Round-robin or least-connections routing
• Health checks to remove unhealthy nodes

Fault Tolerance

• Servers deployed across multiple AZs / regions
• Cache and DB replication for high availability

Tradeoffs

• Prioritizes availability and performance
• Eventual consistency accepted for cache

The ID generation service is replicated across multiple nodes using a Snowflake-style algorithm where each node has a unique worker ID. If a generator instance fails, traffic is routed to healthy instances. To prevent split-brain, worker IDs are statically assigned or coordinated via a consensus system like ZooKeeper or etcd.

In the event of a cache purge or restart, the system falls back to the database as the source of truth. Popular URLs are gradually repopulated into higher cache tiers based on access frequency, accepting temporarily higher latency during cache warm-up.

To handle traffic bursts (e.g., viral links), the system enforces rate limiting at the API gateway and uses request queues or token buckets for write requests. Excess requests receive HTTP 429 responses with retry-after headers to prevent cascading failures.