System requirements

Functional:

• request a shortened URL
• redirect a user to an original URL by a shortened version

Non-Functional:

• shortened URLs lifetime
• cache for redirection
• hashing and collisions

Capacity estimation

• 16B per shortened URL
• 256B per original URL
• 2B per timestamp

API design

• POST body=<normalized-original-url>
• GET query=<shortened-url>

Database design

• NoSql persistent DB for redirect cache, like Redis
• shortened URL for key
• original URL for value
• MongoDB for shortened URLs storage
• key - shortened URL
• timestamp - date of the creation
• original URL

Shortened URL storage will also include an index on original URLs, so that the service can check efficiently if there's already a shortened URL present.

High-level design

We have a pretty simple design:

• a load balance
• shortener service, which handles URL shortening requests
• redirection service, which handler user redirection requests
• cache for shortened URL keys
• cache for

Request flows

We have two main flows to cover:

• a request for shortening an URL
• a request for redirection with a shortened URL

For the first one a request first goes to a load balancer and is dispatched to a proper instance (taking current load into consideration) of a shortener service, which generates a new one, puts it in the DB. Then it returns the result to the user.

For the second case a request also starts from going to the load balancer, but then it gets routed to a redirection service. It first checks its own cache and if the record for the shortened url cannot be found goes to the DB and then either returns an error to the user or puts the original URL to cache and redirects the user.

Detailed component design

Redirection service will use a MD5 hashing algorithm for shortening URLs. It will only take first 7-8 characters from a hash to use as a key. If we have a collision here, we that rehash current full MD5 hash again, until we get rid of collisions. And only then we add a new record to the DB.

Trade offs/Tech choices

Shortener service will not add records to the cache since we would expect less shortening requests and more redirection ones.

Failure scenarios/bottlenecks

• if a user tries to request a redirect to an expired on non-existent shortened URL, we will just return 404
• we can occasionally miss the cache for a record that was added recently and go directly to the DB, which doesn't break consistency, but can be a performance hit

Future improvements

• we can later add a possibility of requesting custom shortened URLs
• we will need to cover APIs and services with different metrics for analytics, performance monitoring, etc.