Requirements

Functional Requirements:

1. create a short URL - given a long URL, returns a unique shortened alias
2. redirect - given a short url, return the original long url with 302 http code

Non-Functional Requirements:

1. high availability - the system should stay up even if servers fail (no single point of failure)
2. low latency - redirects must complete in under 100ms
3. horizontally scalable - should handle millions of URLs and billion of redirects by adding more servers

Capacity Estimation

trafic estimation

1. assume 500k new URL's per day
2. r/w ration 100:1
3. redirects per second: aprox 580 reads/sec

storage estimation

1. each url record ~ 500 bytes
2. urls per year - 500k x 365 = 180 millions
3. storage per year - 182m x 500bytes = 91gb

growth

1. 20% yearly

API Design

endpoints:

1. POST /api/urls

request:

{

"longUrl": "long url"

}

response http code 201:

{

"shortUrl": "serviceurl/reference"

"longUrl": "original long url"

"createdAt":"creationalTimeStamp"

}

2 GET /reference

response http code 302

Header Location: "original long url"

High-Level Design

Load balancer -> redirects any request to 1 of the servers available. on round robin base and provides analytics of traffic usage and with autoscaling group

server -> instances of the application that handles the requests, creates a short url based on base62 (?) encoding

cache -> handles hot cache for the quick access, works as a cold cache for repetitive request for a period of time,

configured in cluster on different nodes

Database -> holds of the data, has at least 1 replica, applying CQRS principle, reads and writes are separated between them, some nosql - casandra as en example as it uses hash for data lookup replica factor 3(?)

scenarios:

create-> user posts a request -> load balancer sends it to one of the services available -> service creates a short link using selected method -> posts it to the cache and DB, service returns the response with required fields

get-> user accesses the link -> load balancer sends the request to one of the services -> service looks for the value in the cache -> 1) value found in cache -> response created and send to the user; 2) value not found in cache -> service makes a lookup to the DB; 1) value found -> response is composed and returned to the client and cache updated; 2) value not found -> bad response composed and send to the client

Database Design

1 table in total with the schema:

```

CREATE TABLE url_mappings ( short_key text PRIMARY KEY, long_url text, created_at timestamp);

```

selects only by short key

no updates for the records

if the record is found in at least 1 db -> provide the result

writes -> successful to any db instance

reads -> successful with the first record found

replicas-> up to number of services

Detailed Component Design

URL generation service

service that generates the value to be stored in the DB

on generate requests based on char base62 random string with fixed size

on insert it validates that the key is available to insert (select for the key) and either inserts or regenerates the key (the longes the key, the the minimal collision chance)

after the key insertion into the db the response is formed and is send to the client

after that step the cache service receives the record for primary lookup with relatively small TTL

for the original URL extraction:

the user requests the original record with the shortened URL

the service validates the cache for the reference, if the value is found - returns it and composes the 302 response for the client

if the value wasn't found in the cache, service performs DB lookup with the key

then it forms the response and inserts the value into the cache

the generator service is handled by monitoring tool that assures that at least 1 service is available and scaleup and scaledown the instance number