System requirements

Functional:

1. user input a url and get a short url
2. user can login/logout
3. user can manager their existing url including add/remove/edit
4. browser request short url, system can search and redirect browser to real url

Non-Functional:

1. system can store 1 billion url
2. no retention period
3. CPS = 10

Capacity estimation

1. each url size 1024 byte
2. 1 billion url = about 1 tera byte storage
3. 10 CPS, 1 web server is enough, need at least 2 web server for HA
4. condisderd we only use character/number in short url, we need at lease 6 characters to cover 1 billion urls.

API design

/api/v1/login

/api/v1/logout

/api/v1/#userid/list

/api/v1/#userid/add

/api/v1/#userid/remove

/api/v1/#userid/edit

Database design

Table: UserInfo

user id:integer (pkey)

user account:string (build index)

password:string

user name:string

Table: URLs

url id:integer (pkey)

user id:integer (indexing)

url:string

tinyurl:string (build index for quick query)

timestamp:time

High-level design

You should identify enough components that are needed to solve the actual problem from end to end. Also remember to draw a block diagram using the diagramming tool to augment your design. If you are unfamiliar with the tool, you can simply describe your design to the chat bot and ask it to generate a starter diagram for you to modify...

Request flows

Browser->Redirect Service->URL query service->DB catch-> DB -> real URL (send http redirect response with real URL)

User Browser->Manage Service->DB (sign in user, add/remove/edit url mapping)

Detailed component design

1. redirect service is state-less, multiple instances running on multiple machines to avoid single point issue.
2. url query service recive request from redirect service, searching DB for match url
3. catching system can use radis, and sperate shards by url hash
4. algorithm to gerenate short URL: use SHA256 to calcuate hash of input URL, xor with random generate 256 bit number, convert the result to string by base64, use the last 6 characters as short url.
5. we can use 2 characters hash from user+time stamp in the head of short url to avoid collision.
6. redirect service has a rate limiter to check frequnce request, include incoming IPs, requested URLs.
7. There is firewall before loadbalancer to protect network attack like ddos attach
8. user can use name/password login, or sign in with Oauth, which supprot 3rd part IAM like google/microsoft/facebook

1. updated url will take some time to uploaded in catch, depends on how we expire the data in catch.
2. this is a tradeoff consistency to make sure high available and partion fail tolanrence, this is a "AP" system.

1. nodes in catch system failed will cause catch missing and rebuild catch, which will deplay response temporarly.

build memory db to speed up search response time.