System requirements

Functional:

1. short url generation
2. redirection
3. user can choose custom url
4. short url deletion
5. short url update - user can update the short url with a different long url
6. expiry time - every short url should have an expiry time

Non-Functional:

1. availability
2. scalability - the system should be able to handle large numbers of short urls and users requesting redirection
3. fault tolerence
4. durability
5. low latency
6. unpredictability - generated short urls should be random for security reasons
7. readability - short urls should be easily readable

Capacity estimation

genration to redirection ration is 1:100.

200 million new short url generation requests per month.

5 years retention.

each url is 500B of DB storage.

Storage

DB storage: 200*10^6 * 500 = 100GB a month -> 1.2TB a year -> 6TB for 5 years

Bandwidth

Ingress: (100GB/(30*24*60*60) )* 8 = 308Kbps

egress: (100GB/(30*24*60*60) )* 8 * 100 = 31Mbps

Cache memory: 20% * daliy requested url for redirection

100 * 100GB / 30 = 333GB requested urls a day -> 0.2*333GB = 66GB cache memory

API design

POST /api/v1/shortUrl

{

long_url: string,

custom_url: string, (optional)

auth_token: string,

expiry_time: timestamp, (optional)

}

GET /api/v1/redirect/{short_url}

returns 302 redirect to the original url

PUT /api/v1/shortUrl

{

short_url: string,

new_long_url: string,

auth_token: string,

}

DELETE /api/v1/shortUrl

{

short_url: string,

auth_token: string,

}

Database design

urls table NOSQL MongoDB

{

pk: short_url,

long_url,

expiry_time,

user_id,

}

I chose MongoDB because it provides good scalabillity with atomicity when writing or updating records since it uses main and secondary replica. DBs like Cassandra or Dynamodb have high write throughput, which is not necessary for this system, and this has cost when reading records because of read sync between replicas. Also, if there are multiple updates to a record, the last one will be saved which can cause some concurrency issues.

High-level design

Redirection service

This service looks for the long url mapping given a short url. It checks the url cache, and if it's not in cache then it will load it from the MongoDB database.

API Gateway

This service authentication and authorizes create, update, and delete requests based on auth token. The service also throttles requests if a user sending too many requests. Create, update, and delete requests can be rate limited based on user_id, and redirect requests will be rate limited based on ip since redirection doesn't require authentication.

Short URL service

This service will generate a short url by fetching a new random sequence id from the sequencer service. Then, the service will encode the id to a 58-base string and store it in the DB. The reason we use a 58-base encoding scheme is because we want the short url to be readable; therefore, we won't use characters like '0', 'o', 'l, or 'I'.

URL Cache

In order to imrpove the latency of redirection requests, we want to get the short url mapping from cache. This will improve the availability and fault tolerence of our service in case of issues with MongoDB servers.

Request flows

Short url request:

1. user sends a requests that is routed by the load balancer to one of the api gateways
2. the api gateway authentication, authorizes, and rate limits all requests based on user_id
3. api gateway routes the request to the short url service
4. short url service fetches a new random seqeunce id
5. the sequence id is encoded to a 10-character short url using base-58 encoding scheme
6. The short and long url mapping is stored in the MongoDB database

redirect request:

1. user sends a requests that is routed by the load balancer to one of the api gateways
2. the api gateway rate limits all requests based on ip
3. api gateway routes the request to the redirection service
4. redirection service fetches the long url mapping from the cache or it loads it to the cache from the MongoDB database if it's missing in the cache.

Detailed component design

Short url service

The sequencer id returns a number with 64 bits. 64/(log_2 58) = 11; therefore, the maximum numbers of characters in the encoded short url is 11. Since we're using a minimum of 10 characters, a user can request a custom short url with a shorter length.

In order to have a minimum of 10 chars, the sequencer id will need to return any number higher than 1*58^9. Therefore, we have (2^64-1) - 58^9 available numbers.

available numbers/yearly requests = [ (2^64-1) - 58^9]/200 million a month * 12 = 7.6 billion years.

Trade offs/Tech choices

Hash vs. random url generation

There are two ways to generate short urls:

1. use cryptographic hash like sha2 to generate a string from the long url and take the first 10 characters.
2. use a random number and encode it to a string.

Pro of using hash is that it's less complex, but at a cost of collisions since we only take 10 characters of the hash. Also, the length of the hash would have to be constant and hash is predictable so it could be a security threat.

With random id, if we get a collision, we'll just generate a new id. The cost is extra compute to generate random ids.

Failure scenarios/bottlenecks

Node failures: short url and redirection services are stateless; therefore, in case of failure, we can schedule a new pod and the load and api gateway will route the requests to healthy instances. These services will run multiple instances to provide redundancy in case of partial failures.

Cache failure

We'll have a replicated cache to provide redundancy and fault tolerence in case of partial instance crash or network outage. In case of the entire cache failure, we can serve redirection requests from the DB, and in case it gets overloaded, we'll use circuit breaker to throttle more requests.

Future improvements

cold data archiving: to reduce cost, we can move rare redirected urls to a cheaper data storage and serve them via a slower path.