System requirements

Functional:

1. duplicate url handling
2. readability of the alias
3. user can provide custom url (ask for handling this case optional based on time)
4. redirecting url
5. url expiry
6. tiny url delete
7. 2 users can share the same generated tiny url?

Non-Functional:

1. Highly available
2. Scalable
3. Performant
4. Eventual consistency

Capacity estimation

1. Assuming 10000 unique users per day and each user doing atleast 3 unique shortening requests - 30,000 urls per day.
2. If each url is ~ 5kb - then we need 150,000kb/day or 4500,000kb/month ~ 5GB or 60GB per year.
3. Considering 3 replicas- 200GB of storage for urls

API design

1. PUT /users/user/tinyUrls (string longURI, expireUrlAfterInDays)
   1. Returns 200 and shorturl on success
   2. returns 500 on server error
2. Delete /users/user/tinyUrls/shortUrl
3. RedirectToOriginal(string tinyURI)
   1. redirects to the longurl on success
   2. returns 404 if the alias is not found in the DB

Database design

1. Each user can generate and store multiple short urls
2. Each url will have metadata about its create date, expiry date.
3. We can use a NoSQL database because there is no set schema and no relations between tables.

URIMetadata table

• longuri (index)
• createdate
• expiry_date

URIMapping table

• longuri (index)
• tinyuri (index)
• expiry_date

URLActivity table

• longurl
• frequency
• numredirects
• numshorturls

We can index the longuri and short uri in the mapping table so look up on either will be fast.

High-level design

The system will contain a

1. load balanced set of web servers hosting 2 micro-service for generating and redirecting,
2. an API gateway to route the requests and help with rate limiting,
3. a caching layer that will store the frequently accessed mappings
4. a NoSQL database to store user details, their short urls and the mappings

It is a read-heavy Vs write-heavy system so we will have one leader and multiple replicas. The replicas will serve read requests while write will be done to the leader.

This will promise eventual consistency but higher availability and performance. Caching, load balanced micro-services and leader-follower database models will provide for eventual consistency, higher performance, scalability and higher availability.

Caching layer can use a simple memcache as the data structure is not complicated and its a simple key-value pair.

Monitoring and observability can be enhanced based on the urlactivity table

Request flows

GenerateURL API flow

1. User calls PUT REST API and passes in a http url, when it expires
2. API will validate the url, check in DB if a mapping exists, if not generate a new unique tiny url
3. Store new url and mapping in DB (leader) update cache and return

Redirect URL

1. User calls redirecturl API with the short url
2. Check in Cache if a mapping exists, if not check in DB
3. Redirects user to that url

Detailed component design

GenerateURL service will

1. verify if the long url is valid, returning the respective error codes if the url is invalid or cannot be reached, user already generated a shortUrl for this longurl etc.
2. To generate the short url we can hash the longurl and perform a Base64 encoding upto 6 characters to get an alphanumeric alias.
   1. Hashing will cause 2 users with same long url to get the same short url.
   2. To avoid sharing short urls, we can leverage a unique id generator, encode it with Base64.
3. Stores in the database the url metadata and mapping.
4. Returns the short url

RedirectURL Service will check if mapping exists and redirects user to the long url.

Because we are generating alphanumeric based aliases, we can distribute the data in the database using on consistent hashing of these aliases - range based distribution.

Trade offs/Tech choices

Caching layer can be REDIS but might be an overkill given we know the data structure ahead of time and its simple.

Database can be MongoDB as it is known to provide better concurrency via more effective locking methods and a leader-follower algorithm built-in.

We will be trading immediate for eventual consistency, so we can have high availability and performance.

Using hashing to generate short url can still be done by adding userid to the hash or to the url to maintain unique short urls for same long url for different users.

Failure scenarios/bottlenecks

Future improvements

1. For long urls that are for YouTube, redirect to them as they have a service to generate the short url - that will lessen load quite a bit because youtube is a big portion of urls that are shared.
2. If we chose unique id, we can generate them ahead of time and maintain a DB of used and unused ids, so we save time generating them.