System requirements

Functional:

1. Given URLs, generate alias and make sure each alias is unique
2. Given alias, redirect the user to the corresponding orignal URL

Non-Functional:

1. Service is reliable and consistent
2. Service can handle multiple concurrent read requests

Capacity estimation

Reads:

If we are building a service similar to TinyURL, imagine we have 10M users that use it on average 5 times per day.

5 * 10M = 50M requests / day

50M / 24 / 60 / 60 = 580 QPS

Writes:

We expect this service to have a lot fewer requests made per second, let's say it's ten times fewer, 58 writes / second, 5M requests per day

Also, assume the system has 1B URLs stored, which is a fair assumption if 5M writes are made per day for 200 days.

API design

set_alias(url: string, alias: string) -> error: set the alias of the url, return error if the operation cannot be done

go_url(alias: string) -> string: return the URL given the alias

Database design

We could use SQL database to store the URL data, as it is using B+ tree under-the-hood that optimizes for reads, which are satisfying our requirements.

In the flowchart I put Shard1 and Shard2, but it actually could scale horizontally based on the URLs added to the service. These shards could be placed at corresponding regions and AZs to improve the availability of the service and satisfy potentially country-based legislation requirements.

We also put LRU before our databse shard as there could be common hotspots when using the service. For instance go -> www.google.com could be a hotspot when using the service but a random document that shared between a private group might not be.

We want an alias to map to a unique URL, so alias is unique.

High-level design

High level design of the system is shown in the flow chart. With load balancer doing the routing and authentication, and hashing service to generate the uid, handling collisions, and making sure the alias satisys the size requirement. Since we allowed user to set alias themsevles in our API design, this service doesn't need to generate a random unique string as alias but we can provide this as an option.

Request flows

1. Client makes the request
2. Requests passes through load balancer and being directed to hashing service
3. Hashing service checks the request type

• set_alias: check if both alias and request are well-formed, then write to DB
• go_url: check if alias exists in DB, if fetch the URL from DB, else return an empty string

Detailed component design

Database/Shards: Scale horizontally by adding more shards, scale vertically by adding more machines in each shard

LRU: LRU by its name is a least recently used cache. It's good for our use case to store some commonly used URLs to speed up query time

Hashing Service: It could be a single server as ~600 QPS is not a big load

Trade offs/Tech choices

1. Scaling horizontally vs vertically: though scaling horizontally makes sense if we are running a global service or has a lot of database entries, modern database could handle 1B entries by scaling vertically as well. Sharding would slow down writes as we need to check the uniqueness of the alias among different shards.

Failure scenarios/bottlenecks

1. Shard down: If one of the shards are down and there is no replication/backup, data might be permanently lost. So, when we are adding shards, we should pair it with multiple replicas. But synchornization for replicas are needed for this case so we could use Write-Ahead-Log (WAL) to make sure these replicas are eventually consistent.
2. Concurrent writes with the same alias. It is possible that hashing service received two requests with the same alias which attempts to set to different URLs. So it is important to consider the timestamps of the request and reject the request which is considered later. We could use a global lock built in the service instead of the lock from the user to make sure the timestamp is consistently compared.

Future improvements

1. Hashing service could be scaled to provide other functions. e.g. seeing the analytics of the alias and URLs. Having a homepage for commonly used aliases etc.