System requirements

Functional:

1. User can create an short url mapped to another url with specified deactivation ddl.
2. short urls can redirect to long urls.

Non-Functional:

1. The system should be highly available.
2. The url should be immediately available after mapping is created.
3. The shortened url should be pretty small, for example, 8 characters after the website: tiny.url/aaaaaaaa.

Capacity estimation

1. Assume every user creates 1 mappings per day. 10M mapping created per day, which is 100 mapping generation per second. It is sufficient to handle in one machine.
2. Every mapping takes 1KB of space. Since mapping is deleted after deactivation, and assume 10 period for mapping, and every user creates 10 mapping per day, the storage requirement is 10M * 10 * 10 * 1KB = 1TB of storage. And there are 1B mapping stored.
3. Assume every url is used 1 times per day, 1B * 1 redirections per day, 1 10K redirections per second. At peak times, assume 100K redirections per second.

API design

create_mapping(long_url: string, end_time: Date) -> short_url: string

redirect(short_url: string) -> long_url: string

Database design

Schema:

{short_url: string, uid: string, long_url: string, end_date: Date}

High-level design

1. short url generation. short url generation takes 2 machines for availability. The short url is encoded as {base}/{encoding of generated number}. Generated number is date + per-node counter. For machine 0, per-node counter is 0, for machine 1, per-node counter is 1. In this case, there won't be the same short url for two different long url. It is sufficient to encode generated number into 8 characters.
2. Store short/long url mapping to storage. 100K redirections. Assume every machine handles 25K reads, we could have 4 replicas of the same data to serve reads. For write, writes to all 4 machines.

Request flows

1. Generate a new mapping: goes to API server. API server calls number generation service to get a unique short url, stores the short url and long url into 4 replicas. Once all successful, ack the user.
2. Redirection: goes to API server. API server calls any replica to retrieve the stored value. If found, provide the long url to the user.

Detailed component design

1. For the unique url generation service, altough 1 machine is sufficient, we provide 2 machines for availability concerns. urls generated by two machines are disjoint set, there is no further interaction required. If API server fails to get short url from one, try to retrieve from another one.
2. Every mapping has a end_time. When mapped to a long url that has already expired, does not redirect and delete the mapping immediatly.
3. To save more space, the backend could run a periodic service that deletes expired mapping per day or per week.

Trade offs/Tech choices

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



Failure scenarios/bottlenecks

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

1. API server talks to short url generator. The short url is generated, but not received by API server. In this case it is fine because no two generated url could be the same.
2. API server tries to store url mapping to all 4 replicas. If one replica dies, it is not processed. To solve this problem, we could make every replica group an availability group, thus making every replica with high availability.
3. The API gateway is now a single point of failure. To solve this, simply employ two identical API server, since there is no state stored in API gateways.

Future improvements

1. Rate limit mapping generation based on IP to prevent DDoS.
2. Provide user registration service to allow users to manage url mappings, and provide long-lived mapping feature for premium users.