System requirements

Functional:

• Input a url, return a shortened url
• Redirect a shortened url to the original long url
• analytics on shortened url link clicks i.e. number of times it was clicked
• permanent storage and ability to use shortened urls indefinitely
• Handle duplicates gracefully (either opt in to using previously generated shortened url, or just create a new shortened url)
• Ability to delete links
• In the case of a bad long url, the system should handle it gracefully.

Non-Functional:

• Redirects to original long url should have low latency
• durability on shortened url
• eventual consistency

Capacity estimation

10M links shortened per day -> 100 TPS

100:1 read:write ratio

1B redirects per day -> 10K TPS

100 bytes size of average long url

8 chars for each shortened url hash -> 26^8 possibilities is more than enough. 8 chars is 8 bytes.

To be safe let's assume each row in the db (which will include the long url, the hash, created_at, id) is 200 bytes.

10M links shortened per day * 200 bytes = 2B bytes = 2 GB per day

API design

POST /shortenUrl

request: {longUrl: "https://wikipedia.com/computer_science}

response: {shortenUrlHash: "defabcab"

GET /tinyurl.com/hash

response redirect to long url

So two endpoints - one to shorten a url and one to get a shortened url (and be redirected to its long url)

Database design

one table called shortenedUrls

key-value or document based approach can work

schema:

_id: string (will be used as the hash)

long_url: string

created_at: date

expiry_date: date

clicks: int

High-level design

Cache will be a TTL (time to live).

2 GB per day of writes = 14GB per week = 56 GB per month

so cache ttl can be 1 month easily.

for a write:

1. user makes a POST request with a long url to be shortened
2. request is sent to a link shortening service
3. unique hash is created
4. then data along with hash is sent to kafka
5. kafka message is sent to an available task runner
6. data is first sent to nosql data store
7. Only after data is successfully added to data store is it then added to the cache

For a read:

1. user makes a get request (navigates to shorten url)
2. the request is sent to a redirect service
3. redirect service first goes to the cache
4. On a cache hit:
   1. user is redirected to long url with a 301 response
5. On a cache miss
   1. the value is accessed from the data store
      1. if value is not found, user gets a 404 response
      2. if value is found, the value is first added to the cache and user is then redirected to the long url
6. If the retrieved long url is invalid then response is intercepted and a 404 page is displayed.

Request flows

Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...

Detailed component design

Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...

Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...

Failure scenarios/bottlenecks

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

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?