System requirements

Functional:

• Given a long URL, the system should generate a short and unique alias that represents the original URL.

Non-Functional:

1. Availability: The service should be highly availablem, ready to make request any time
2. Low latency: Service should return data at low time respone
3. Consistency : Service need to guarantee when user access short URL are always redirected to the correct long URL

Capacity estimation

1. Request Volume

• • Assume you handle 200 requests per second for creating short URLs.
  • Assume 20,000 requests per second for redirecting using the short URL.

• For each URL mapping entry, consider including the following fields:
  • Long URL (~100 bytes on average).
  • Short URL (~8 bytes).
  • Created time (8 bytes).
  • User ID (20 bytes).
  • Expiration time (8 bytes).
• Calculate the entry size and total storage per day and year:
  • Estimate each entry approximately at 256 bytes.
  • Daily data generated: 200×60×60×24×256 bytes = 4.4 GB/day
  • Annually: 4.4 GB/day × 365 days = ~1.6 TB/year

API design

POST : /api/v1/url->  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/v1/url/{shortUrl} -> To get short URL and respone to original URL

Database design

Database Choice:

• Consider using a key-value database like DynamoDB for the ShortURLs table. This aligns with the requirement for a simple and scalable mapping from short URLs to long URLs, as it can handle high read and write throughput, can be configured for strong consistency, and provides automatic partitioning and replication features.

• Table 1: ShortURLs
  • id (Primary Key)
  • alias
  • original_url
  • created_at
  • expiration_date

• Table 2: User
  • user_id (Primary Key)
  • Created_at

High-level design

1. Client: Request to get long URl from short and to send long URL to store
2. API Gateway: Security and Authentication, Rate Limiting and Throttling:
3. Load Balancers : Distribute incoming HTTP requests (both reads and writes) across multiple backend servers. Prevent overload on any single server. Enable horizontal scaling and high availability.
4. URL Shortening Service:
   1. Generates short URLs and stores them in the database.
   2. Manages alias availability and expiration.
5. Redirection Service:
   1. Handles redirection based on the alias.
   2. Logs analytics data.
6. Cache : Store frequently accessed URL mappings to reduce database loading
7. Database: Store a map between short and long url, store user id

flowchart TD

A["Client"]

D["API Gateway"]

B["Load Balancers"]

E["URL Shortening Service"]

F["Redirection Service"]

C["Database"]

H["Cache"]

I["Authentication Service"]

A --> |HTTP Request| D

D --> |Authorized Requests| I

I --> |User Authenticated| B

B --> |Distribute Load| E

E --> |Create/Lookup URL| C

E --> |Cache Short URL| H

F --> |Short URL Request| H

H --> |Cache Hit| A

H --> |Cache Miss| F

F --> |Redirect to Long URL| C

F --> |Return Long URL| A

Request flows

sequenceDiagram

  Client ->> API Gateway: POST /api/v1/url

  API Gateway ->> Shortening Service: Forward request

  Shortening Service ->> Database: Store short URL mapping

  Database -->> Shortening Service: Acknowledge

  Shortening Service -->> API Gateway: Return short URL

  API Gateway -->> Client: Return short URL

  Client ->> API Gateway: GET /api/v1/url/{shortURL}

  API Gateway ->> Mapping Service: Forward request

  Mapping Service ->> Cache: Check for short URL

  alt Cache Hit

    Cache -->> Mapping Service: Return long URL

  else Cache Miss

    Mapping Service ->> Database: Query long URL

    Database -->> Mapping Service: Return long URL

    Mapping Service ->> Cache: Update cache

  end

  Mapping Service -->> API Gateway: Send long URL

  API Gateway -->> Client: Redirect to long URL

Detailed component design

1. Caching

Caching Layers:

• CDN (Content Delivery Network): Ideal for caching frequently accessed mappings at the network edges, reducing latency for commonly requested URLs.
• In-Memory Cache (e.g., Redis): Positioned within the data center to cache frequently accessed data closer to the application logic, offering fast access and reducing database load.

Eviction Policy:

• Use a least recently use(LRU) to remove Short URl has been not use for long time while New data needs to be stored.

Cache update strategy:

• Write-through: Every data write to database, update to the cache, maintain consistency
• Lazy Loading means the cache is populated only when there's a cache miss. If the data is not in the cache, it's fetched from the database, and then stored in the cache for future requests.

2. Get Shorl Url:

• ShortUrl : to create unique shortURl we store short as a hash of long URL.
• For expamle: /Facebook/com/post-id/1231 and return aH102
• Check Hash value if it already in db to prevent duplicate data.

erDiagram

USER ||--o{ URL: "creates"

URL {

string id "Primary Key"

string shortUrl "Shortened URL"

string longUrl "Original Long URL"

date createdAt "Creation Date"

date expirationDate "Expiration Date"

string userID "Foreign Key referencing USER"

}

USER {

string id "Primary Key"

string name "User's Name"

string email "User's Email"

}

CACHE {

string shortUrl "Primary Key"

string longUrl "Cached Long URL"

}

URL ||--o{ CACHE: "stored in"

3. Database:

Database Partitioning:

1. Sharding: Use like scailing process, Scale out storage and write capacity. Avoid bottlenecks of a single large database.
2. For a URL shortener, the best shard key is usually ShortURl:
   1. Random or uniformly distributed (Base62, hashid, etc.)
   2. Used in almost every read/write operation
   3. Small and immutable

Trade offs/Tech choices

CAP Theorem 

Prioritize Availability + Partition Tolerance (AP):

• It’s better to serve stale or cached redirects than to fail.
• E.g., if a user requests sho.rt/abc123, and the DB is partitioned, return from cache or replica.
• Database choice : Couchbase, Cassandra, DynamoDB
• Trace off: Always available but may return stale (eventually consistent) data

Failure scenarios/bottlenecks

Load balancer failure:

Scenario:

• High volumn request could make load balancer overload

Mitigations:

✅ Use multiple LBs (HAProxy, AWS ELB, etc.).

✅ Enable health checks and auto-recovery.

Database Bottleneck or Outage

Scenario:

• Database is overloaded or goes down.
• Writes (creating new short URLs) or reads (redirects) fail.

Mitigations:

• ✅ Use read replicas for scalability.
• ✅ Add caching layer (Redis) to absorb read load.
• ✅ Implement sharding to horizontally scale.
• ✅ Use failover or multi-region databases.

Future improvements