System requirements

Functional:

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

1. URL shortening : given a long URL -> returns shortened URL
2. URL redirecting: given a short URL -> redirects to original url

Non-Functional:

List non-functional requirements for the system...

High Availability

Scalability

Fault Tolerance

Capacity estimation

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

1. Write operation: 100 M URLs are generated per day
2. Write operation per second: 100M/24*3600 = 1160 seconds
3. Assume read ratio = 10:1
4. Read operation per second = 1160*10 = 11600
5. Assume URL shortener service will run for 10 years = 100M*365*10 = 365 billion records
6. Assume average original URL length = 100
7. Storage requirements for 10 years = 365B*100*bytes = 3.65TB

API design

Define what APIs are expected from the system...

URL shortening:

POST: api/v1/data/shorten

request param: {longUrl: longURLstring}

return shortUrl

URL redirecting:

GET: api/v1/shortUrl -> return long url

Database design

Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...

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...

URL redirecting- client sends short URL and tinyUrl sends status code : 301 and location:longUrl and visit long URL by sending to amazon server, where it gets cached.

URL shortening - it passes through hash function and return hash value

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...

URL shortening flow -

1. client sends long url and check if ling url exist in db.
2. If yes, then return short url
3. If no, then it generates unique Id and convert ID to short URL using base 62 conversion. Then it saves ID, long URL and short URL in DB.

URL Redirecting flow -

1. Client clicks short URL link
2. Load balancer forwards the request to web servers
3. if short URL is already in cache, it returns long url
4. if short Url not in cache, hit db call
5. if not in db, then invalid short URL
6. otherwise return long URL

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...

Deep Dive:

Url shortening - there are hash functions - MD5, CRC32 which can generate hash code. The hash length can be not more than 7 as there are total 62 possible characters in shorten url and 62^7 ~3.5 billion which is within our storage capacity. But this hash function can cause collision and we can take 7 characters from hash code and append predefined length +hash code(7 characters) in case of collision. It is expensive to query database if url exist, so to improve performance we can use bloom filters, which is space efficient probabilistic technique to test if an element is member of set.

Another approach - base 62 conversion which is 0-0,1-1...11-a...35-z, 36-A,61-Z since there are 62 characters we use base 62 conversion to generate hash value.

URL Redirecting Service:

As there are more read than write, mapping is stored in cache to improve performance

Trade offs/Tech choices

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

1. Shorter URL value can lead to collision if we used CRC32, MD5 hash methods but we used base 62 conversion on unique ID to avoid collision.
2. To improve performance and faster lookups, we used cache (redis) as consistency issues can occur in case of NoSQL where there is eventual consistency.
3. Centralized system can cause single point of failure, so we used distributed system that scale well but introduce replication delay

Failure scenarios/bottlenecks

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

1. Too many request for short URL can occur. So need to add Rate Limiter.
2. In case of unique ID generator for base 62 conversion, as it is easy to figure our next available id increments by 1 and can cause security issues.
3. In case of invalid short URL request, it hits DB call which is expensive.

Future improvements

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

Database scaling

Web server scaling

Analytics to track clicks for URL shortening