System requirements

Functional:

1. Shortening URLs: Users can input a long URL and receive a short alias in return.
2. Redirection: When a user clicks on the shortened URL, they should be seamlessly redirected to the original URL.
3. Analytics Tracking: The service should track the number of clicks on each shortened URL, unique visitors, and other metrics.
4. Custom Short Links: Users may have the option to create custom short links rather than a randomly generated string.
5. Expiration Dates: Optionally, the short links can have expiration dates after which they no longer redirect to the original URL.
6. User Accounts: Allow users to create accounts to manage their links and track analytics over time.
7. API Access: Provide an API for developers to programmatically create short links and retrieve statistics.

Non-Functional:

1. Performance:
   • Low latency: The service should redirect users to the original URL within a few hundred milliseconds.
   • High availability: The service should be operational and reachable 99.9% of the time.
2. Scalability:
   • The system should handle significant traffic, especially if it's popular. For example, it should support thousands to millions of URL shortening requests per day.
3. Security:
   • Implement measures to prevent malicious use, such as spam URLs or phishing links.
   • Use HTTPS for secure transmission of data.
4. Data Persistence:
   • Ensure data is reliably stored and can handle failures (e.g., by using a robust database storage solution).
5. Usability:
   • Keep the user interface simple and intuitive for both individuals and developers.
6. Analytics Reporting:
   • The analytics system should be able to provide reports quickly, even under high traffic.

Capacity estimation

Assuming there are 100,000 URLs shortened per day and 1,000,000 clicks per day on those shortened links.

In terms of storage size, we have 100,000 * 200 bytes = 20,000,000 bytes = ~20 MB per day to save in database. It's 7.3 GB per year.

Write capacity: 100000 / 86400s = 1.15w/s peak times 3. 3w/s

Read capacity: 1000000 / 86400s = 11.5r/s Peak times 3. 33r/s

API design

All the api below can only be accessed by authenticated users.

POST /shorten: accept original url as input and return a shorten url as response.

GET /shorturl: Redirects the user to the original long URL based on the short URL.

GET /analytics/:shortUrl: Get analytical data for the short url passed in.

POST /shorten/custome: accept original url and custom alias as input and return a shorten url as response.

Database design

URL table:

Create index for shortUrl

• id (primary key)
• shortUrl
• OriginalUrl
• userId
• createdOn
• expiredOn

Analytical table:

• id (foreign key)
• shortUrl
• numberOfClicks
• userId
• uniqueVisitors

High-level design

flowchart TD

 B["client"];

 C{"Shorten service"};

 D["NoSQL Database"];

 E{"Analytic service"};

 F{"Retrieval service"};

 G{"API Gateway"}

 H{"Redis cache"}

 B --> G;

 G --> C;

 E --> D;

 C --> D;

 F --> H;

 G --> E;

 G --> F;

 H --> D;

Request flows

sequenceDiagram

  Client->>Shorten Service: Shorten the url

  Shorten Service->>Data Base: Save shorten url to db

  Shorten Service->>Client: Here is the shorten url

  Client->>Retrieval Service: Go to this short url

  Retrieval Service->>+Cache: do you have the resource available?

  Cache-->>Data Base: No, fetch it from DB

  DataBase-->>Cache: Here is the data

  Cache->>-Retrieval Service: Yes. Here you go

  Retrieval Service->>Client: 302 Redirect

Detailed component design

For the shorten url service, i would like to use an algorithm to calculate the shorten url efficiently, may be use its database self-increment id as a seed, so that database can help us to do the deduplicate.

For the url retrieval service, we can use Redis served as cache so that it can return result for most recent queries. We can also set expiration for the cache data as the same as the expiration date for the url itself.

To achieve high availability, we can have api gateway to route user's request to healthy service node and spin up more service resources to serve peak time.

For Data Persistence, we can create db replica so that we can fail over to backup database in case main db is down. We can do eventual consistency here since the data for this case is not necessarily in sync in real time. And assuming occasional data loss is acceptable.

Trade offs/Tech choices

We are using cache to improve read performance, so it is adding complexity to the system since we need to make sure cache data is deleted once the url is expired.

The algorithm we are using to generate short url is relying on database self-increment id, it will be challenging if there are multiple database servers. Since their id generation is independent

And we are using eventual consistency for data sync here, so it may cause the issue that data may be lost and user may not be able to get the data they want if the data is still waiting for sync.

Failure scenarios/bottlenecks

The initial design didn't use cluster for some of the services, so it may have single point of failure issue in case the service is down.

No cache for analytic data, there will be lots of reads to database if many users are querying for the same url.

If the cache is expired, and lot of requests come in, all of them will hit the database.

If the shorten url is posted by a famous person, there will be lots of queries come at the same time, since the url is not in the cache yet, all the requests will hit database.

Future improvements

Use clusters for all services so that we always have back up for services.

Need to create a filter service to filter phishing urls.

Create cache for analytic data.

If the url is expired, set the cache to return an empty result for query.

For the famous urls issue, there needs to be a lock on the searched key so that other threads need to wait when some thread is trying to search the key and update the cache. After the cache is updated and lock is released, other threads will be able to read the newly cached data. Or we can proactively push the url to cache if the url belongs to a power user