System requirements

Functional:

1. User sends a long url, service return a short url.
2. User can access the original long url given a short url.
3. No duplicate short url generated for different long urls.
4. The long url and short url should be persistent in the system

Non-Functional:

1. User is not able to customize the short url

Capacity estimation

Assume we host the service for 10 years, each long/short urls take 100 bytes.

The storage is: 10000000 * 365 * 100 bytes * 10 = 3.65 TB

The avg QPS is 10000000 / 24/3600 = 115

Peak QPS is 115 * 2 = 230

API design

• GenerateShortUrl API
• request: longUrl
• response: shortUrl
• FetchLongUrl API
• request: shortUrl
• response: longUrl

Database design

Url Table

• PK: id
• longUrl: string
• shortUrl: string

High-level design

• API Gateway server, used for accepting API requests and routes the requests for different service.
• ShortUrlGeneratorService: A microservice to generate unique value give the input long url
• UrlDBAccessService, used for querying the longUrl/Short URL mapping in database.

Request flows

GenerateShortUrl flow:

• Client sends a request to API Gateway server
• API Gateway sever call UrlDBAccessService to check whether there is already an existing short url for the request, if yes, return directly. If not, send the request to ShortUrlGeneratorService.
• ShortUrlGeneratorService generates a hash value and converts to a 7 digit value.
• ShortUrlGeneratorService call UrlDBAccessService to store the mapping.
• UrlDBAccessService checks whether the short url exists. If yes, it throws an error to ShortUrlGenratorService to create a new one. If not, store the mapping in DB.
• ShortUrlGeneatorService returns the short url to API service and then return to client.

FetchLongUrl flow:

• Client sends a request to API Gateway server
• API gateway srver call UrlDBAccessService to fetch the short url.

Detailed component design

In ShortUrlGeneratorService, we could use MDB, SHA-1 algorithm to generate a has value and use Base64 conversion to shorten the url.

For hot urls, we could add a cache in UrlDBAccessService. Then it doesn't have to query the db everytime when there is a new request.

Trade offs/Tech choices

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

Failure scenarios/bottlenecks

When the API server, services or database are down, it caused a single point failure issue.

For server, we could start multiple distributed servers to handle the request.

For database, we could use replication to backup the data.

Future improvements

If the request spikes or abuse behavior, we could add a rate limiter to filter out request based on IP address or other filter rules.