System requirements

Functional:

1.Input: given long URL : return a much shorter URL

2.URL re-direct: input: shorten URL, re-direct it to the original URL

Non-Functional:

1. High availability.
2. high Fault tolerance

Capacity estimation

Estimate the scale of the system you are going to design...

API design

Define what APIs are expected from the system...

1. POST: /{longURL} => return short URL
2. GET:/ shortULR => return long URL

Database design

1. URL : id {shortULR, longURL }

High-level design

Generate shorten URL

Hash the longULR (hashKey) to shortURL (hashValue)

Re-direct:

Once service received a tinyurl request, it will map back to the original longULR key with 301 re-direct

Request flows

1. Shortening flow: Create hashFunction hashF: each longURL key will be mapped to a hashValue as shortURL. Meanwhile push the shortURL to longURL as the reverse key value into another hashTable for later re-direct flow.
2. Re-direct flow:

URL mapping DB check shortURL -> longURL hash Map

Get longURL: hashTable.get(shortURL)

Perform the redirect based on the longURL

Detailed component design

We could consider base 62 hash algorithm or hash collision resolution

Hash collision: MD 5 , CDC 32 which uses first 7 character

Trade offs/Tech choices

Approach 1 [chosen]Base 62: Support 62 character.

Pros:

No need to concern collision

URL length is not fixed, it goes up with ID

Cons: Require unique ID generator

Approach 2: Hash collision:

Pros:Fixed short ULR length

No need unique ID generator

Cons: expensive to query the DB and build mitigate for resolving collision (recursive to append pre-defined string)

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

Future improvements

1. Redis cache for accessing re-direct ULR mapping instead of access URL server every single time
2. Rate limit: Control large number of URL shortening request.
3. Scaling: multiple web server to scale for stateless architecture
4. DB scaling with partition