Requirements

Functional Requirements:

1. Shorten Url, given a long url, the short_url must be compact and unqiue.
2. For a given short_url, it should redirect to a long_url (original url). The latency should be as los as possible.
3. Link expiration based on TTL, so links auto expire after a duration.

Non-Functional Requirements:

• Low latency: P95 should be below 10 secs. Redirects must be below 10ms, since any delay in latency is perceived as a broken or suspicious link. URL Creation can take some time. (50ms).
• High Availability: The system should be highly available: 5 9's = 99.999% available. The redirect path should be highly available. URL Creation can sustain brief outages, but redirects cannot have.
• High Scalability: the system should be able to store billions of stored urls, with thousands of redirects per second.
• Durability: Once the mapping is created in DB, it should not be lost. These short urls are embedded in to docs, so any mapping lost leads to errors without recovery.
• Trade Off between consistency and availability: (CAP Theorem): Availability over Consistency.

COST ESTIMATION:

Assume: 200 WPS => 200 * 86400 / day

read : write = 100:1

therefore number of redirects : 20000/sec

Storage:

short_code : 7chars => 7bytes

long_url: about 100bytes

user_id: 20bytes

created timestamp: 8bytes

estimated timestamp: 8bytes

total 1 record = 7 + 100 + 20 + 8 + 8.= 143 bytes

== 256 bytes (when metadata, indexes are involved)

therefore daily storage => 256 * 200 * 86400/day = approx 4.4 GB/day

Bandwidth:

Write : 50KB/sec => negligible

Read (Redirect) 5MB/s (due to large payload of long_url)

Caching:

Storing last 30 days of fetched mappings => 80 to 90% cache hits

API Design

1. POST /api/v1/url

req payload:

long_url: string

expires_at: timestamp

auth : Api key in header

Response: 201 Created

short_code: string,

long_url string (for validation)

createdAt: timestamp

expiresAt: timestamp

authentication: using API key in sent in headers

rate limit: 100 req/s per user for free tier, piad subscriptions can have higher.

return 429 with a Retry-after header if too many requests.

Validation: The server should validate that the long_url is a well formed url with a supported scheme (HTTPS, HTTP) reject javascript:. ftp: data: to prevent abuse.

Check if url is reachable using the HEAD request, although this will increase latency for create, but is bearable.

2.GET /api/v1/url

params: short_url = short_url

success response: 302 Found

response header: Location: long_url

auto redirection without authenticaton

If the short_url has been expired or doesnot exist, return 404.

For expired link, send a message field with response stating that the link has expired.

Other headers to be included: Cache-Control and X-Robots-Tag to tell search engines whether to cache the short_url or original url.

301: Moved Permanentely, Browser stores the mapping in cache. There for high reads, bit no analytics or stale date validation for this matter

High-Level Design

1. The User (web/app) will send a post request to generate a short url for the given long url, this will be sent as payload.
2. The request will pass through an api gateway and based on the route, it will go to the load balancer.
3. The load balancer with round-robin configured ( static load balancer) will route the specific request to the Shortening microservice.
4. The shortening microservice will create a short url using hash based methods and store the value in the DB (key -value store).
5. There will be worker (bull worker if using nodejs) in shortening service that polls for jobs in the redis queue and updated the redis for caching the data with a specific TTL. (This helps in reducing read req to DB)

Detailed Component Design

1. Load Balancer : A Static Load balancer with round-robin algorithm will be good fit as it will ensure equal distribution of traffic between different instances. This works in Layer 4 hence can consume more traffic, and also handle SSL/TLS encryption and termination.
2. API Gateway: Works in Layer 7, forwards requests based on the route. Handles Rate limiting using token bucket algorithm for protection against DDOS. Handles Authentication and Authorization of USERs using RBAC. Responses can also be cached for lower latency.
3. Shortening Service: Generates a short_id based on the hash of first 6-8 characters of the long_url. This is used as a unique key to be stored for mapping the original url in the KV DB. For ensuring uniqueness, we can create hash functions on the first 7 bytes of the long_url along with calculate the next index where the DB will filled. We can also prefix the short_id generated using a namespace such as name of the org, which can be sent with request payload.
4. Mapping Service: This Checks against the DB whether a mapping between the short_id and the long_url exists. If it doesnot, then it will return 404. Also, if the current timestamp is greater than the expiry timestamp, then it will return 404 , with error message of "Link Expired" In order to deal with stale links.
5. Database Design: A Key value based NO-SQL DB isused such as Dynamo DB. It is reliable and highlly available due to the replicas create across 3 AZs.
6. Cache: LRU Eviction policy is used in order to remove keys. The mappings used in the past 30 days will be cached so that 80% to 90% request will be a cache hit.
7. CDN: Content Delivery Network will be used to cache the the most frequently used mappings of short and long urls, thereby not taking the request to the backend to fetch the most popular link.

Schema

short_url: string

long_ur: string

userId: uuid

created_at: timestamp

expires_at: timestamp