System requirements

Functional:

1. User can register with username and password
2. User can create an short url mapped to another url with specified deactivation ddl.
3. User can deactivate an url mapping.

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. 10M DAU.
2. 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.
3. 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.
4. 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_user(username: string, password: string) -> userid: string

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

redirect(short_url: string) -> long_url: string

deactivate(uid: string, short_url: string) -> success: bool

Database design

Schema:

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

{uid: string, username: string, salt: string, salted_password: string}

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. Account registration:

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

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.

Future improvements

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