Requirements

Functional Requirements:

List the key functional requirements for the system (Ask the AI for hints if stuck)...

• System returns a short URL for every long URL
• System keeps a map of short url to long url in the database 5 years TTL
• System generates unique short URL even for duplicate entries of long url
• System redirects to long URL for short urls

Non-Functional Requirements:

List the key non-functional requirements (performance, scalability, reliability, etc.)...

• System must remain available at all times
• System must be able to retain 5 year of data (assumed)
• System must be able to scale for peak load
• System should have low latency

Capacity Estimation

Estimate the scale of the system. Consider daily active users, read/write ratio, storage requirements, bandwidth, and any relevant QPS calculations...

Lets assume we have upto 8 character short url

Number of possible urls 26^8 = ~ 32^8 = 2^(5*8) = 2^40 = ~10^(3*4) = ~10^12 URLs # Quite a lot

Assuming 10 million users per day, each making 6 requests per day = 60 mil requests

With, 1:99 write to read ratio, it becomes 500,000 writes and 50 million read per day

Average write per sec = 500,000/100,000 = 5 QPS

Average read per sec = 50 M/ 100,000 = 500 QPS

Peak Read QPS = ~1500 QPS

Peak write QPS = ~15 QPS

Each short URL is 8 bit long = ~ 1 byte

DB requirements = Size of long URL + Size of short url + timestamp = 500 B + 1 B + 500 B = 1 KB

500,000 URLs per day = 5*10^5 * 1 KB = 500 MB

Yearly DB size = 365*500 MB = ~150 GB

Assuming this grows by 10% every year = ~2 TB for 5 Years

Daily Cache size = Unique URL hits per day * (Size of short url + size of long url) = ~500 B * 10% of reads per day (due to hot keys) = ~ 500 B * 5 Mil = 2.5 Mil * 1 KB = ~2.5 GB = ~2.5 GB * 1.2 (Safety margin) = ~3 GB

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

# Creating short url

Request: POST /api/v1/shortened

Body: {"long_url": "..."}

Response: {status_code: 201, "message": "Created", "url": "bit.ly/2MBRJ23B"}

# Getting long URL

Request: GET /api/v1/{short_url}

Response: {status_code: 302, "message": "Found", "Location": "https://www.mylongurl.com"}

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.

# POST REQUEST

Client will send long url to the API Gateway

The API Gateway will redirect the service to shortner service which will return a unique short url

The Shortner will make an entry in the db and populate the read cache with the new shortened url

The API Gateway will return the shortened url to the client

# GET Request

The client will make a get request to API Gateway with shortened url

The API Gateway will forward this request to redirect server

The redirect server will check if the cache has a corresponding long url

If found in cache, the long url is returned

If cache miss, the db is scanner for short url

If found, the short url is added to cache and returned with response code 302

If not found, 404 response is returned to the client

# On API Gateway

The TLS termination will happen at API Gateway

The rate limiting can be handled at API Gateway

# Shortner Service

The shortner service will compute the short url from the long url (probably using some hashing algorithm with long_url+timestamp+userIP as key)

Database Design

Define the data model. Identify the main entities, their attributes, and relationships. Consider the choice of database type (SQL vs NoSQL) and justify your decision based on access patterns...

There would be a url_mapping table with shortened_url code as the primary key and long_url, created_at, expiry, created_by

There can be another table with url_code as primary key and click_count as another column

The database would preferably be a NoSQL DB like mongodb

Since this can be a 2 TB database in 5 years, it is important that we shard the data between nodes using something like consistent hashing with short_code as partition key. This will also help us avoid the hotspot problem as some URLs will be hit more than others.

The write operations needs to be consistent. We'll allow duplications of long urls and will create unique short code for duplicate writes. This will prevent the need to scan entire tables to lookup if short url exists for existing long url

The reads can be eventually consistent. In the worst case scenario, this will only return 404 temporarily.

Further, indexes can be created on short_code to improve lookup time

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.

# Shortner Service

The shortner services will create a 8 character long base62 hash_code against long_url+timestamp+IP. This will minimize the collision chances and will yield a unique short_code. We can also add server side salt to prevent guessing of the short codes

This will also saves us time from making db lookups to validated if the code is unique.

We can eliminate the need of cache for write operations.

In case of expiry of URLs, the service should also send delete and purge request for the expired code to cache and CDN

The shortner service can be a simple FASTAPI based stateless application.

In case of service disruptions and failure to generate code, the shortner service can return appropriate response like 429 too many request.

This will help load balancer service to temporarily pause sending request to this replica of the service.

Another way can be to use the response code to throttle the API Gateway and retry after some time.

When the traffic is increased, the shortner service can be horizontally scaled based on usage metrics

# API Gateway

Besides routing and acting as reverse proxy, the API gateway can implement rate limiting for unauthenticated users