System requirements

Functional:

List functional requirements for the system (Ask the chat bot for hints if stuck.)...

Non-Functional:

List non-functional requirements for the system...

Capacity estimation

We'll estimate that there will be 1 million URLs generated per day.

Writes: 1 million / day

Writes per second: 1 million / 24 / 3600 = 11.57

Reads: We'll make an assumption that this is a read heavy system of 10:1 so there will be 10 million reads per day with a read per second of 11.57 * 10 = 115.7

Number of records over 10 years: 1 million * 365 * 10 = 3.65 million records

Assume average URL length will be 100 characters

Storage requirements over 10 years is 3.65 million * 100 bytes = 365 million bytes

API design

POST api/v1/data/shorten

• request parameter: { originalUrl: string }
• return: shortUrl

GET api/v1/data/shortUrl

• return longUrl for HTTP redirection

Database design

See ER Diagram

High-level design

See HLD.

Request flows

See Sequence Diagram.

Detailed component design

Hashing the long url into a short url:

1. Hashing the url with a built in hashing function like md5 or sha-1 would be fine if the output wasn't so long. You could take the first n characters, but then you could have hash collisions. To solve for hash collisions you can repeatedly generate a new short url by appending a predefined string until you don't find the new string in the database. Downside is that this is expensive to continuously query the db.
2. Base 62 conversion approach: Since the number of possible characters in the shortened URL is [0-9] (10) [a-z](26) [A-Z](26) you have 62 as a base conversion number. We'll generate a unquie id and then convert it to base 62 to get the short url hash.

Trade offs/Tech choices

• We use a 301 redirect to show that the requested url is permanently moved to the long url so that the browser can cache appropriately. We could use a 302 redirect as well to show that the url is temporarily moved. The downside is that we would get more load on the server to resolve the short URL since we aren't caching it browser side, but it can help with analytics tracking if you wanted to see how many times a url was exactly visited.

Failure scenarios/bottlenecks

If we fail to retrieve the long URL during this process then we can't perform a 301 redirect. In this scenario, we would place the user on the tinyurl web page and notify them that the redirect did not work.

We need a distributed unique id generator to ensure the base 62 conversion operates on a globally unique ID.

Future improvements

Some areas of improvement are how to handle malicious requests to shorten a URL. We can use rate limiting to rate limit based on user IP address as one potential solution.

The database itself could be sharded or replicated since right now it acts as a single point of failure.