System requirements

Functional:

• User requests alias URL for their long URL
• User receives an alias URL.
• Unique Mapping - the same long URL, e.g www.google.com should return same URL alias.
• Once a URL Alias is created, it cannot be deleted/updated - it is immutable.

Q:

What if the system already has a short URL for that long URL. E.G User 1 adds Google.com to tinyURL and user2 does the same. I take it only 1 tiny URL should be made?

A:

Unique Mapping: When a user requests to shorten a long URL, the system should first check if that particular long URL already exists in the database. If it does, the service can return the existing short URL instead of creating a new one.

Non-Functional:

Scalability:

The system should handle growing numbers of URL creation and redirection requests without performance drops. Horizontal scaling (adding more servers) is key.

Security:

The service must protect against abuse, such as malicious URLs, spamming, and ensure that short URLs do not expose sensitive data.

Performance:

Lookups and redirects must be fast. Using caching (like Redis) and efficient database indexing ensures minimal latency.

Availability:

• The service should be highly available, meaning users can always create and access short URLs even during failures. Load balancing, replication, and failover strategies are essential.

Daily Active Users (DAU)

For a URL shortening service, you might expect a varying number of users. For our estimate:

1. DAU Estimation: Let's assume you expect around 1 million users daily interacting with the service.

Activity Levels

• Each user on average generates about 2 short URL requests per day.
• Each user will likely redirect through their short URLs approximately 10 times a day.

Requests Estimation

Based on the above assumptions:

• Total Short URL Creation Requests per Day:
  • $1,000,000 \text{ users} \times 2 \text{ requests/user} = 2,000,000 \text{ requests/day}$
• Total Redirect Requests per Day:
  • $1,000,000 \text{ users} \times 10 \text{ redirects/user} = 10,000,000 \text{ redirects/day}$

Data Storage Estimation

Data Model

Let's assume each entry for a shortened URL includes:

• Short URL (8 characters)
• Long URL (average of 100 characters)
• Created time (timestamp)
• User ID (for tracking, average of 20 characters)
• Expiration time (optional, average of 8 bytes)

The total size for one mapping might look something like this:

• Short URL: 8 bytes
• Long URL: 100 bytes
• Created Time: 8 bytes
• User ID: 20 bytes
• Expiration Time: 8 bytes
• Total Size per Entry:
  • Approximately 144 bytes (rounding up for simplicity, let’s say around 256 bytes for overhead, indexing, etc.)

Total Storage Requirement

• Short URL Storage Needs:
  • Daily: $2,000,000 \text{ entries} \times 256 \text{ bytes} = 512 \text{ MB}$
  • Assuming continuous growth, in a year:
    • $512 \text{ MB/day} \times 365 \text{ days} = 186,880 \text{ MB} \approx 182 \text{ GB}$
• Redirect Storage Needs:
  • Each redirect won’t require new storage but will reference existing records. For high throughput, we would want to account for rapid access through caching and databases.

Now, rounding up for growth and redundancy, you might plan for about 200 GB to 500 GB of data storage in the first year, depending on how aggressively you believe users will use the service.

Summary

You might design your application under the assumption that:

• Daily Active Users: ~1 million.
• New Short URLs per Day: ~2 million.
• Storage: ~200 GB to 500 GB including growth.

API design

As our URL Alias System only requires CREATE, RETRIEVE we can use a simple RESTful API approach.

POST /api/v1/shorten

Request:

• longUrl: string (required)

Response:

• shortUrl: string

Behaviour:

• Checks if longUrl already exists.
• If yes, return existing shortUrl.
• If no, create a new alias and return it.
• Once created, the mapping is immutable.

GET /api/v1/{shortUrl}

Request:

• shortUrl: path parameter

Response:

• HTTP 301/302 Redirect to longUrl

Behaviour:

• Look up shortUrl.
• Redirect to the associated longUrl.

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

MongoDB Collections:

1. User

• userId (primary key)
• emailAddress
• createdAt

2. UserSession

• sessionId (primary key)
• userId (foreign key)
• jwtToken
• createdAt
• expiresAt

3. URLAlias

• shortUrl (primary key)
• longUrl (indexed)
• userId (foreign key, optional if anonymous usage is allowed)
• createdAt

Use a Master/Slave DB Replica approach to split WRITE/READ operations to minimise DB Load.

Use a REDIS cache (Redis can be horizontally scaled) to cache frequently used URLs. Cache Invalidation will be LRU (Least Frequently Used) and TTL

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

Components Overview

1. Client: This is where the user initiates the request to shorten a URL.
2. API Gateway: Acts as the single entry point that routes requests to the appropriate services. It can handle load balancing, SSL termination, and may implement security measures like authentication.
3. Load Balancer: Typically a Layer 7 (L7) load balancer is used to distribute incoming requests to multiple web servers for better performance and reliability.
4. Authentication: Validates the user's JWT token to ensure they are permitted to perform the requested operations.
5. Web Server: Hosts the API. It is responsible for handling incoming requests and coordinating with caches and the database.
6. Redis Cache: Used for caching recently accessed URL mappings to speed up response times for popular URLs. If a request for a short URL is found in the cache, it is immediately returned to the client.
7. MongoDB: This is where the URL mappings are stored. If the mapping is not found in the cache, the web server checks the MongoDB database.

Interaction Flow

Here's how the flow would typically work:

1. Client initiates a request to shorten a URL by sending a request to the API Gateway.
2. API Gateway acts as a reverse proxy, forwarding the request to the appropriate web server.
3. Load Balancer directs the request to one of the available web servers.
4. Authentication checks the JWT token to verify the user's identity.
5. Web Server checks Redis Cache for the short URL. If it exists, it responds back with the URL.
6. If the URL isn't found in Redis Cache, the web server checks MongoDB:
   • If the long URL mapping exists, it returns the existing short URL.
   • If it doesn’t exist, it creates a new short URL entry in MongoDB and returns it to the client through the API Gateway.

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

Here's how the flow would typically work:

1. Client initiates a request to shorten a URL by sending a request to the API Gateway.
2. API Gateway acts as a reverse proxy, forwarding the request to the appropriate web server.
3. Load Balancer directs the request to one of the available web servers.
4. Authentication checks the JWT token to verify the user's identity.
5. Web Server checks Redis Cache for the short URL. If it exists, it responds back with the URL.
6. If the URL isn't found in Redis Cache, the web server checks MongoDB:
   • If the long URL mapping exists, it returns the existing short URL.
   • If it doesn’t exist, it creates a new short URL entry in MongoDB and returns it to the client through the API Gateway.

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

1. API Gateway

The API Gateway is your first line of defense and smart routing.

• Responsibilities:
  • Routing (directs /shorten to web servers, /shortUrl to redirection handlers)
  • SSL Termination (offloads HTTPS work from backend servers)
  • Basic security enforcement (rate limiting, IP filtering, JWT validation pre-check)
• Scalability:
  • Horizontally scalable by deploying multiple instances behind a cloud load balancer.
  • Popular implementations: Kong, NGINX, AWS API Gateway.
• Special Consideration:
  • Use caching at the gateway if you want to handle frequent redirects even faster without hitting Redis.

2. Redis Cache

Redis dramatically reduces lookup latency for popular URLs.

• Responsibilities:
  • Store mapping {shortUrl: longUrl} temporarily in memory.
  • TTL (Time-To-Live) settings can be applied based on access frequency.
  • Acts as a first-level read cache before querying MongoDB.
• Algorithm / Data Structures:
  • Simple Key-Value store for mapping.
  • Optionally, Least Recently Used (LRU) cache eviction policy to keep hot data in memory.
• Scalability:
  • Redis itself can be scaled vertically (bigger instances) or horizontally (via clustering and partitioning).
  • Redis Cluster automatically partitions keys and balances across shards.
• Performance:
  • Redis operations are O(1) for both reads and writes.

3. MongoDB

MongoDB is your durable storage for mappings.

• Responsibilities:
  • Permanent storage of {shortUrl, longUrl, userId, createdAt}.
  • Index on both shortUrl (primary key) and longUrl (for uniqueness checking).
• Scalability:
  • Sharding based on shortUrl ensures even distribution.
  • Replica sets for high availability and read scaling (read replicas).
• Data Integrity:
  • Use unique indexes on shortUrl to guarantee no collisions.
  • During creation, query with a hashed or encoded long URL to prevent duplicates if needed.
• Special Optimization:
  • Background workers to clean expired links if you later add expiration.

Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...

1. NoSQL (MongoDB) vs SQL (Postgres/MySQL)

• Choice: MongoDB (NoSQL).
• Why: Easier horizontal scaling (sharding by short URL), flexible schema (can evolve data models if needed).
• Trade-off:
  • Pros: High availability, built-in replication, fast for simple lookups.
  • Cons: We lose strong ACID guarantees across multiple documents. Complex queries (joins) are harder.
  • Reasoning: URL mappings are simple Key-Value lookups — MongoDB’s strengths match this use case.

2. Redis Caching

• Choice: Redis for fast in-memory reads.
• Why: High throughput (~millisecond latency), perfect for caching hot short URL mappings.
• Trade-off:
  • Pros: Super fast read times, scalable with clustering.
  • Cons: Data is volatile (if Redis crashes and no persistence is configured, data could be lost).
  • Reasoning: Since Redis is only a cache (not source of truth), losing Redis means only slower performance, not data loss.

3. JWT Authentication

• Choice: Long-lived JWT tokens for user session validation. If we need to invoke user session we can use a mixture of Short-Lived JWT and Long-Lived JWT. The Short-Lived JWT can be use client-side, and the Long-Lived JWT can sit in our MongoDB User Session to re-validate a user's Short-Lived JWT.
• Why: Stateless, no server-side session storage needed, easy to validate via public key.
• Trade-off:
  • Pros: Scalable, easy for distributed systems.
  • Cons: Revoking a JWT is hard (you need a token blacklist or short TTLs).
  • Reasoning: For a lightweight service where login/logout isn’t frequent, JWTs offer good balance between scalability and security.

4. URL Shortening Approach

• Choice: Pre-check if long URL exists before generating a new short URL.
• Why: Ensures same long URL always maps to the same short URL (unique mapping).
• Trade-off:
  • Pros: Cleaner DB, no duplicates, easier tracking.
  • Cons: Small overhead during URL creation (requires checking DB first).
  • Reasoning: Saves long-term storage and keeps user experience consistent.

5. Single Region Deployment Initially

• Choice: Start with one region and later expand.
• Why: Keep architecture simple initially, save on multi-region complexity and cost.
• Trade-off:
  • Pros: Faster to launch, easier to debug.
  • Cons: Higher latency for international users, single point of failure risk.
  • Reasoning: Optimize for early adoption and scale globally once DAU demands it.

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

1. API Gateway Single Point of Failure

• Problem: If the gateway node crashes, no requests can be routed.
• Solution: Deploy redundant API Gateway nodes behind a DNS-level load balancer (like AWS Route53) for failover.

Load Balancer Failure

• Problem: Load balancer itself can fail under high load or misconfiguration.
• Solution: Use managed, highly-available load balancers (AWS ELB/ALB) and health checks to detect and shift traffic quickly.

3. Redis Cache Failure

• Problem: Cache failure could dramatically increase database load, causing slower redirects and potential DB overload.
• Solution:
  • Enable Redis persistence (AOF/RDB snapshotting).
  • Redis replication (primary-replica) and automatic failover via Redis Sentinel or cluster mode. Use a Mutex to lock operations until the cache is re-populated once the DB provides us a key/val.

4. MongoDB Bottlenecks

• Problem:
  • High write load (new URLs) could cause replication lag.
  • Indexes on large collections may become slow over time.
• Solution:
  • Shard the collection based on ShortURL or hash of LongURL.
  • Periodic index maintenance (compact, reindex).
  • Scale read replicas horizontally.

5. Hot URL Redirects (Cache Miss)

• Problem: Popular short URLs might cause MongoDB to get hammered if cache misses occur suddenly.
• Solution:
  • Cache expiration (TTL) tuning for popular URLs.
  • Pre-warm cache with top N URLs based on access logs.

6. Authentication Service Latency

• Problem: Verifying JWT (especially if using external public keys) can introduce slight latency.
• Solution: Cache public keys locally on servers with periodic refreshing.

7. Link Overload (DDoS attack on short URLs)

• Problem: Abusive scripts can massively hit one or more short links, overloading your system.
• Solution:
  • Apply rate limiting per IP at API Gateway.
  • Implement WAF (Web Application Firewall) rules.
  • Monitor and block abusive patterns.

9. URL Alias Collision

• Problem: If using random/hashed aliases, there's a chance two different long URLs collide.
• Solution:
  • Use sufficiently large ID space (base62 encoding).
  • Retry on collision detection automatically.

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?