System requirements

Functional:

URL SHORTENER

• URL Encoding Engine for transformations.
• Checking for Hashing Collisions

REDIRECT

• User's must have the ability to redirect to the appropriate to proper URL
• Redirection should be with minimal latency

TOKEN EXPIRATION

• Enable user's to set expiration to their key:value pair entry

API

• Supporting Req/Responses
• RESTFul Architecture

Non-Functional:

Scalability

• Available through Horizontal Scaling

Reliability

• Must be 99.999% available throughout the year
• Implement fault-tolerance

Performance

• Optimized read heavy architecture
• User's should be able to be redirected to the appropriate web page

Storage

• Efficient way to retrieve key:value pair

Security

• Support HTTPS for data transmission
• Backup and Recovery

Capacity estimation

Application should be able to handle 20,000 read requests per seconds while managing 200 write requests per second

Amount of Read request per Day:

20000 * 86400(amount of seconds in the day) = 1,728,000,000 Read requests

Amount of Read request per Month would be around 51 Billions Read request

Amount of Write request per Day:

200 * 86400(amount of seconds in the day) = 17,280,000 Write requests

Amount of Request per Month would be around 510 Millions Read requests

API design

POST /api/shorten : This is the API that accepts the original URL, service will generate a hash, this hash will be appended to the URL and the shortened URL will be returned.

GET /api/redirect/(short_url) : This is the API that will accept the short URL and redirect to the original URL

Database design

Since this data store has the core functionality of storing key value pairs with long URL associated with short URL for redirection. Since how read/write request ratio is 100:1 its better to focus on optimizing the read request. Hence this architecture doesn't require relational modal so we'll opt for a Nosql Solution implemented using DynamoDB or MongoDB

High-level design

Request flows

Client Request Initiation

• The client sends a request to the API Gateway, which serves as the entry point for all incoming requests.

API Gateway Processing

• The API Gateway validates, authenticates, and routes the request to the Load Balancer to distribute the workload efficiently.

Load Balancer Routing

• The Load Balancer forwards the request to one of the available Servers for processing.

Server Processing

• The server processes the request and forwards it to the API , which acts as the intermediary for backend services.

Data Handling & Processing

• The API interacts with various backend components:
  • Queries the Database (n2) for retrieving or storing information.
  • Checks the Cache (n4) for quick access to frequently requested data.
  • Routes requests to the Redirection Service if necessary.

Database Replication

• The Database updates or fetches data and synchronizes with Database Replicas for redundancy and performance optimization.

Redirection & Logging

• If applicable, the Redirection Service processes the request and logs relevant actions in the Logs Service for monitoring and debugging.

Response Handling

• Once the required operations are completed, the response follows the reverse path:
  • Data retrieved from the database/cache/redirection service is returned via the API.
  • The API forwards the response to the server.
  • The server sends the response back through the Load Balancer.
  • The Load Balancer routes the response to the API Gateway.
  • Finally, the API Gateway returns the processed response to the client.

Detailed component design

A load balancer distributes client requests across multiple backend servers to prevent a single server from becoming overloaded. It operates at different layers:

• Layer 4 (Transport Layer): Uses TCP/UDP to distribute traffic (e.g., AWS NLB, HAProxy).
• Layer 7 (Application Layer): Routes requests based on URLs, cookies, or headers (e.g., Nginx, AWS ALB).

Horizontal Scaling (Adding More Servers) – As traffic increases, more servers are added behind the load balancer.

Auto-Scaling with Cloud Services – Services like AWS ELB integrate with Auto Scaling Groups (ASGs) to spin up/down instances dynamically.

A cache stores frequently accessed data in-memory to reduce database queries and improve response time. Your system likely uses Redis or Memcached for this purpose.

Horizontal Scaling – Distributed caching via Redis Cluster or Memcached shards.

Algorithm Used: Least Recently Used (LRU) Eviction Policy

Why LRU?

• Ensures that stale data is removed from the cache efficiently.
• Keeps frequently accessed data in memory.

How LRU Works:

1. Every time a key is accessed, it moves to the front of the LRU queue.
2. When the cache reaches capacity, the least recently used item (at the back) is evicted.
3. Implemented using a Doubly Linked List + Hash Map for O(1) operations.

Trade offs/Tech choices

1. API Gateway (D)

• Tech Choices:
  • AWS API Gateway, Kong, Nginx, Traefik, Apigee
• Trade-offs:
  • 🟢 Pros:
    • Centralized authentication, request validation, rate limiting, and security.
    • Load balancing and service discovery.
  • 🔴 Cons:
    • Introduces latency due to additional processing.
    • Becomes a single point of failure if not properly managed.

2. Load Balancer (A)

• Tech Choices:
  • Nginx, HAProxy, AWS Elastic Load Balancer (ELB), Traefik
• Trade-offs:
  • 🟢 Pros:
    • Distributes traffic efficiently to prevent overload on any single server.
    • Can improve availability and redundancy.
  • 🔴 Cons:
    • Requires additional configuration and monitoring.
    • Can introduce a bottleneck if not horizontally scalable.

3. Server (C)

• Tech Choices:
  • Node.js, Django, Flask, FastAPI, Express.js, Spring Boot, .NET Core
• Trade-offs:
  • 🟢 Pros:
    • Handles business logic and routes requests effectively.
    • Provides flexibility in processing requests before forwarding them to the backend services.
  • 🔴 Cons:
    • Scalability depends on proper deployment strategies (containerization, Kubernetes, etc.).
    • Requires efficient logging and monitoring to detect failures.

4. API Layer (n1)

• Tech Choices:
  • GraphQL, REST (Flask/FastAPI/Express), gRPC, OpenAPI
• Trade-offs:
  • 🟢 Pros:
    • Acts as a central point for backend logic and microservices orchestration.
    • Can optimize requests by reducing redundant queries (GraphQL, gRPC).
  • 🔴 Cons:
    • REST APIs may result in over-fetching/under-fetching of data.
    • GraphQL introduces complexity in caching and rate limiting.

5. Database (n2) & Replicas (n6, n7)

• Tech Choices:
  • PostgreSQL, MySQL, MongoDB, DynamoDB, Redis
• Trade-offs:
  • 🟢 Pros:
    • Replication improves read performance and fault tolerance.
    • SQL databases offer ACID compliance, while NoSQL provides flexibility.
  • 🔴 Cons:
    • Replication increases operational complexity.
    • NoSQL sacrifices strong consistency for scalability.

6. Cache (n4)

• Tech Choices:
  • Redis, Memcached, AWS ElastiCache
• Trade-offs:
  • 🟢 Pros:
    • Reduces database load by serving frequently accessed data.
    • Improves application response time.
  • 🔴 Cons:
    • Requires cache invalidation strategies to maintain consistency.
    • Memory overhead may increase costs for large datasets.

7. Redirection Service (n3)

• Tech Choices:
  • Nginx Reverse Proxy, AWS Lambda, Cloudflare Workers
• Trade-offs:
  • 🟢 Pros:
    • Improves routing and redirection efficiency.
    • Can be used for A/B testing or feature flagging.
  • 🔴 Cons:
    • Additional network hops increase latency.
    • Misconfigurations can cause security vulnerabilities.

8. Logging Service (n8)

• Tech Choices:
  • ELK Stack (Elasticsearch, Logstash, Kibana), Grafana Loki, AWS CloudWatch
• Trade-offs:
  • 🟢 Pros:
    • Helps monitor system health and debugging.
    • Allows proactive issue resolution.
  • 🔴 Cons:
    • Large log volumes can lead to storage and performance concerns.
    • Requires structured logging formats for meaningful insights.

Failure scenarios/bottlenecks

Single Point of Failure at the API ENDPOINT ,we should decentralize operation at this level, allowing API to be more scalable and be fault tolerant by using Horizontal scaling

Load Balancer – If it fails, all requests are blocked.

API Gateway – A failure here prevents requests from reaching backend services.

Database – A failure can cause system-wide data unavailability.

Future improvements

Implement Load Balancer Redundancy to avoid failure at the entry point.

Optimize API Gateway Performance using rate limiting & autoscaling.

Ensure Database Scaling with replication, sharding, and connection pooling.

Use Distributed Caching to reduce direct DB queries.

Optimize WebSocket Connections with message brokers.

Implement Asynchronous Logging to avoid slowing down requests.

Deploy Redundant Redirection Services to ensure high availability.