System requirements

Functional:

Develop endpoints for below requirements:

1. URL shortening: Take long URL as input and send short URL as response.
2. URL redirection: Redirect the short URL to original corresponding long URL.
3. Validation and error handling: Incorporate validations for input URL and show meaningful error messages for scenarios like malformed URL, expired links.
4. Links will expire after a configured time(like 5/10/20 years).

Non-Functional:

1. Availability - System should be available all the time. to ensure this we can have multiple instances running on a cloud platform for the application. A load balancer can be added to distribute requests across multiple instances.
2. Scalability - system should be scalable depending upon the load. Deploying the application on cloud platforms like Openshift, Kubernetes, PCF would allow auto scaling.
3. Performance - System should be able to take the load during peak hours too. SLA for this is defined under capacity estimation section.
4. Logging and monitoring - System should be able to monitor time taken for servicing the requests and identify areas which are taking more time. This can be done by using external logging tools like Grafana, Dynatrace, etc.
5. Shortened links should not be predictable.
6. REST APIs exposed should be able to integrate with third party services or UI interfaces.

Capacity estimation

Traffic

Assuming 20:1 read/write ratio

Number of unique shortened links generated per month = 10 million

Number of unique shortened links generated per seconds = 10 million /(30 days * 24 hours * 3600 seconds ) ~ 4 URLs/second

With 20:1 read/write ratio, number of redirections = 4 URLs/s * 20 = 80 URLs/s

Storage

Assuming lifetime of service to be 10 years and with 10 million shortened links creation per month, total number of data points/objects in system will be = 10 million/month * 10 (years) * 12 (months) = 1.2 billion

Assuming size of each data object (Short url, long url, created date etc.) to be 500 bytes long, then total require storage = 1.2 billion * 500 bytes = 0.6 TB

API design

1. POST: /shorten/{url}
2. GET: /redirect/{url}

Build Utilities

1. Validate URL for e.g.: malformed, valid or expired
2. Algorithm to generate random string for shortened url

Clean-up Service/Batch Design

Clean up service (daily batch) would pick up the urls which are present in the system for longer time(configurable) like 5/10/20 years and put effective end date as current date.

Database design

As the system needs high availability and needs to handle high volume of data, NoSQL DB like MongoDb, Cassandra, Redis would be better choice.

URL Mapping Table/Collection: Each document should have longUrl, shortUrl, effectiveStartDate, effectiveEndDate, createdby, updatedBy, createdDate, updatedDate

Spring Batch Tables: In-built tables provided by spring batch to capture batch context, params and other details. this would be needed for clean up service.

High-level design

There will be 2 microservices -

1. URL shortening/redirection service
2. Clean up service

Request flows

Detailed component design

Shorten URL Design:

1. Validates the provided URL using the URLValidator and also check if it is not malformed.
2. If the URL is valid from above step, it pings the URL to check its availability.
3. Fetches existing URL details from the database.
4. Depending on the action mode (NO_ACTION_MODE, SAVE_MODE, UPDATE_MODE), it:
   1. Returns the existing short URL(when URL exists within current date time range - NO_ACTION_MODE).
   2. Generates a new short URL, checks for its existence in the database, and persists it. (when URL doesn't exist in DB - SAVE_MODE)
   3. Updates the existing short URL record with dates in the database(when URL exists, but not in current time range - UPDATE_MODE)
5. If the URL is invalid, it throws an InvalidURLException.
6. Duplicate URL handling scenarios -
   1. Duplicate Long URL Scenario 1- if the same long URL exists in system and it is effective within current date, then respective short url(already stored in DB) will be returned.
   2. Duplicate Long URL Scenario 2 - if the same long URL exists in system and it is effective within current date, then effective end date will be updated as high date in DB for the existing record.
   3. Duplicate Short URL - After shortening a long URL, there will be an additional check(recursive function) to check if the short URL already exists in DB.

This component will also have Redis Cache integration to avoid hitting DB for records which are already in cache, hence improving performance of the system.

Shortened URL Generator Utility

Step 1: Generate an MD5 hash of the long URL

Step 2: Get First 6 bytes of the hash

Step 3: Convert these bytes to decimal:

Step 4: Encode the result into a Base62 encoded string

Clean up Service:

This is a Spring batch service which would be configured to run once a day. It will put effective end date as current date + 1 for the URLs which have start date greater than configurable time (5/10/15 years)

Trade offs/Tech choices

1. Hashing Algorithm: Chances of collision could be higher with MD5 algorithm used for shortening the URL. However, with this solution outlined here, there are additional steps post applying MD5 algorithm which make the collision rate really low.
2. System Availability: To make the system highly available, there is a possibility of having data inconsistency across different instances or if spread across different networks.

Failure scenarios/bottlenecks

If the clean up service puts effective end date for a URL, then the redis cache server for shorten URL service should be evicted. Else, it would still refer to older set of valid records.

Future improvements

1. User Experience: Allow user to enter their own custom short url
2. Analytics : Track number of times a shortened URL is redirected.
3. Security: User session can be introduced, the users can login and see the URLs shortened by them. If multiple users are trying to shorten the same long link, they still have the same short url.
4. Clean up service: Post user session is implemented, if any link created by a particular user is expired then a mail notification can be sent to them.