System requirements

Functional:

1) The system should output a short URL that takes us to the long URL

2) Links will expire after a year, pointing to a response that says they are expired and will get deleted after another year

3) The system should scan for malicious content

Non-Functional:

1. The system should be scalable and handle well under heavy load
2. The system should be available
3. The system should be seamless and minimize the time between write and read

Capacity estimation

10kb per row for url table * 50,000 writes=500 MB  per day

500MB * 365= 182.5 GB  per year for URL table

10kb per row for user table * 1000 *365= 3.65 GB for user table

API design

1. get_short(short_url)-> returns long url,return empty string if it doesn't exsist,throws error if invalid
2. create_short(user_id,long_url)-> returns short, writes to leader db and increments counter for user,will return error if user id is invalid or block user if content is inappropriate
3. delete_short(user_idmshort_url)-> allows users to optionally delete their short
4. create_account(email,auth_token)->allows user creation

Database design

URL Table:

1. Primary ID
2. User ID (Foreign key to users table)
3. long URL (Index)
4. short URL
5. created_at (Index)
6. is_active (Index)
7. how_many_times_clicked (index)

User Table:

1. Primary ID
2. email_Address (index)
3. created_at (index)
4. number_of_shorts_created (index)
5. is_active (index)

High-level design

Write Operations:

1. The user interacts with the Load Balancer.
2. Load Balancer distributes load based on server load.
3. We will use sha-256 to hash the URL and take the first 8 chars as short URL
4. if there is a collision and the hash already exists we check if the long is same,if it is we return the long and write to user table so more than 1 person has the short and long associated with them, if the collision is because of different long URLs we will append user id to the long and hash that
5. Web Servers write data to the Leader Database.
6. Leader Database updates Follower Databases for replication.

Read Operations:

1. User accesses Load Balancer for reads.
2. Since this is a heavy-read operation we will allocate 20% of DB size to caching
3. A write-Through Cache is utilized.
4. If there's a cache hit:
5. Return data directly from the cache.
6. If it's a cache miss:
7. Read data from the Follower Databases for retrieval.
8. We will use LRU for cache eviction
9. If link is expired we will let the user know

Scalability:

1. Will use sharding based on consistent hashing, the hash would be of the long URL
2. Will run a job every day to mark expired links based on created at index
3. If the link is created more than a year ago it will be marked expired
4. If the link is created more than two years ago we will delete it

Request flows

Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...

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?