System requirements

Functional:

1. It should take input from the user a valid URL.
2. It should produce an alias of the input URL as a shorter version of the URL.
3. For example, after using more than 5 URLs user have to login and purchase a plan.
4. Upon signup, login, purchase user should get notification email.
5. User should see a dashboard to view all source URLs and its shortened versions.
6. User should be able to create multiple short URLs for duplicate source URLs.

Non-Functional:

1. A shortened URL should handle multiple concurrent redirects.
2. Each short URL should have a unique guid.
3. User cannot delete an URL after generating it.
4. There should be two microservices one for generating short URLs known as Service1, another for serving the short URLs known as Service2.
5. Service1 and Service2 can scale independently though they are using same DB with read isolation and short URL guid cannot be deleted/edited.
6. Newly created URLs can be activated after 5mins for syncing backend data.
7. The short urn identifier will be response cached via Redis for 15 mins.
8. Service2 will have load balancer based on weighted average.
9. Service1 will have load balancer if required.
10. Once Service2 has redirected to the source URL it will not wait for actual source URL to load.

Capacity estimation

1. A Service2 should handle 10,000 concurrent redirect at max without facing latency of greater than 1 second.
2. Service1 can handle 1000 user sessions to generate URLs.
3. The Service2 can scale out 5x during peak time and scale down during low traffic.

API design

1. Serivce1 user login: POST /users/login
2. Serivce1 user session: GET /users/{id} using JWT
3. Serivce1 create URL: POST /createurl in the post body the source URL will be passed
4. Serivce1 get short URL used internally: GET /shorturl/{guid}
5. Serivce2 get short URL: GET /redirect/{guid} returns the source URL of the website. load balanced

Database design

1. There is a single relational DB for both services.
2. There should be a table 'Table0' that will store details of source URLs with columns 'source_url', and 'source_url_id' as primary key. 'source_url_id' is a large integer generated through a hash function.
3. There should be a table 'Table1' to map the details with columns - 'source_url_id' as foreign key of 'Table0', and 'url_id' as primary index.
4. There should be another table 'Table2' to store shortened URL details with columns - 'user_id', 'shortened_url_guid' as clustered index and 'url_id' as foreign key of 'Table1'.

High-level design

1. Login module.
2. URL source identifier module for Service1.
3. URL shortener module for Service1.
4. URL provider module for Service2.
5. URL redirector module for Service2.
6. Fault tolerance / load balancer for Service2.
7. Response Caching module for Service2.

Request flows

1. User session is activated via Serivce1.
2. In Service1, when creating a short URL, the hash function will be used to identify the source URL to check whether the same source URL is already present in the 'Table0'. If false, the hash value will be stored in 'source_url_id' with the 'source_url'. An event will be raised to carry further operation on 'Table1'. When this event is finished another event will be raised to call short URL generator asynchronously. If true, the same hash value will be reused to make a new entry in 'Table1'.
3. When providing the short URL for the first time by the URL generating service, the short URL guid will be generated, stored in 'shortened_url_guid' of 'Table2' and the same 'url_id' from Table1.
4. The generated guid is then appended with the base address of the URL shortener service and returned to the user.
5. When a short URL is visited via Service2, the 'shortened_url_guid' will retrieve the 'url_id' from Table2 and query the 'source_url' from Table0 with help of table joining.
6. Before returning the 'source_url' via Service2 there will be an event driven counter that will count number of times a short URL is visited, and it will cache the 'url_id' in Redis.

Detailed component design

1. For Service1 we are reutilizing the source URL because the source URL can be very large sometimes and as we are not limiting the number of short url for same source it can be challenging to index the large url string. That is the reason a linear hash function will be used that will identify the Source URL in the system.
2. We are using event driven architecture to make every internal call async and independent to each other.

Trade offs/Tech choices

1. A column DB can also be used here but we are trying to leverage FK query in relation DB based on identifiers.
2. We are storing GUID of short URL as clustered index. This can be challenging and cause slow DB reads but if we generated the GUID properly it should not create much slowness.
3. We are using one DB instead of tradition multiple DB in microservices because we want quick and simple solution for our reads and write with response caching to avoid eventual consistency.

Failure scenarios/bottlenecks

1. redirected URL is invalid.
2. Multiple different short URL which has same Source URL are requesting from different location and we have to cache all 'url_id' per design which is waste of memory.
3. Indexing GUIDs can lead to huge DB paging size may require sharding.
4. Event driven call can fail, and, in that case, user will have no short URL as requested.

Future improvements

split the single DB design into multiple small DB services with more complex algorithm.

Introduce retry logic for event safe calls.