System requirements

Functional:

1. Generate short URL for a long URL
2. Get Long URL against a short URL
3. Limit the rate at which the short URLs are accessed per second

Non-Functional:

1. Performance
2. Scalability
3. Reliability
4. Security
5. Monitoring

Capacity estimation

Traffic Estimation

1. Monthly Active Users: 10 Mn
2. Every user makes roughly 10 requests per day. Hence, 3 Bn Requests per month; 100 Mn Requests per day
3. Read to write ratio: 9:1 so 90 Mn reads and 10 Mn writes per day

Data Estimation

1. Since it's just mapping of the URL to a hashed string. We will calculate the length of the hash string to be generated uniquely to serve the requests for 5 years. To calculate total hashes to serve 10 Mn writes per day for 5 years without any collision or scanning heavily the DB, we'll do the math. In 5 years, total hashes = 10000000 * 365 * 5 = 18250000000 = 18.25Bn unique hashes in 5 years.
2. We'll use Base62 hashing to generate the hash. So, the calculate the length, we'll take 62^L >= 18.25Bn. Taking the log on both the side we figure out that the length of hash should be 6 to fit for 18.25Bn unique hashes.
3. In DB, we'll have a hash 6 bytes, long URL 255 bytes, active-status 1 byte, created_at 5 bytes and expiry 5 bytes. Total 272 bytes per record so 2.72GB writes per day resulting to roughly 5TB writes in 5 years.
4. Since we'll use hash string as a primary key and long url as index. The total storage that the indexing will use will be roughly 5 TB in 5 years.
5. We're logging the request also but we'll not focus on that for this design.

API design

1) API to generate the short URL

Request

POST /v1/url

{

url: "some_long_url"

}

Response

{url: "some_short_url"}

2) API to get the long URL

Request

GET /v1/url/{hash}

Response

{url: "some_long_url"}

Database design

We will use MySQL db to store the records having schema

hash - varchar(5) - primary key

long_url - varchar(255) - unique key

is_active - tinyint

created_at - datetime

expiry - datetime

High-level design

```

flowchart TD

Client["Client"];

APIServer1["API Server 1"];

APIServer2["API Server 2"];

APIServer3["API Server 3"];

APIGateway["API Gateway"];

LB["Load Balancer"];

DB[("DB")];

ES[("ES")];

Analytics["Analytics"];

Client --> | Send URL | APIGateway;

APIGateway --> | Rate Limited Req | LB

LB --> APIServer1

LB --> APIServer2

LB --> APIServer3

APIServer1 --> | Logs | ES;

APIServer2 --> | Logs | ES;

APIServer3 --> | Logs | ES;

DB --> APIServer1;

DB --> APIServer2;

DB --> APIServer3;

APIServer1 --> DB;

APIServer2 --> DB;

APIServer3 --> DB;

APIGateway --> | Response | Client;

ES --> Analytics;

```

Request flows

1. A client sends a URL to be shortened
2. It reached to API Gateway to sanitise the request and to check for rate limiting.
3. It reaches to load balancer that decides which server among the autoscaling group servers to send the request to.
4. The server processes the URL and saves the hash in the DB. At the same time, it also sends a log to Elastic Search. After processing, it returns the shortened URL to the LB that in turn returns to APIGateway followed by Client.
5. The Analytics server fetches the logs and does the analytics on it.

Detailed component design

Let's talk about the hash generating mechanism.

String md5Str = md5(long_url);

String base62Str = Base62(md5Str);

String hash = base62Str[:6];

Trade offs/Tech choices

MySQL vs NoSQL, we used MySQL as opposed to NoSQL that may look very prominent candidate here. But the fact the use case is just limited to fetching based on the primary key and URL, and that it takes less memory in MySQL as compared to NoSQL, I chose MySQL.

Scaling up MySQL can be a bit challenging as we may need to use replication using active-passive to start with and then it may need a combination of active-active and active-passive because of huge read requests.

I choose servers in the autoscaling group at AWS so that whenever the spikes of requests happen, the system will be able to handle it based on the load by increasing or decreasing the number of servers.

Failure scenarios/bottlenecks

The failure scenario could be that there's a sudden spike in the request flow and the AWS autoscaling group does not get a chance to boot up new servers fast resulting to throttled requests for some users.

Since we're using a single LB and API Gateway, they pose a single point of failures and may need to be scaled up just like the others.

Future improvements

The Application Server can be enhanced to check for quota for a short URL based on the number of clicks in a day or overall. This data can be store through Analytics in some database so that API Servers can request to it.