System requirements

Functional:

Ability to take the url and return short version that could be map to the original one

Non-Functional:

1. High availability over consistency: we want this system to be available over consistency
2. Low latency: we want our service to respond as quickly as possible

Capacity estimation

1. we assume 1 writes per second
2. we assume 100 reads per second
3. Per write consumes 8Byte, the 8 Bytes * 10 ^ 5 s, that's means 800MB per day.

API design

We would have two api:

1. Get com.me/url-short:
   1. serving as the get request
   2. redirect the sender to the actual resource and on success return 302 (redirected), on fail get 404
2. The other API would let user encode their URL through UI portal

Database design

The most perfect database here is persist kv store.

Since kv stores are usually NoSql, so we choose NoSql to be our database and we don't need to worry about scaling too much.

High-level design

1. Client send request to LoadBalancer and then redirect to appropriate server based on Round Robin stateless algorithm.
2. The server will first check if the url present in our im-memory Cache (based on consitent hash to determine which cache server to check, the cache is LRU). If present in cache, return the record and redirect to the full url.
3. If not present in our cache, send request to NoSql DB to get full url, if exist, then return and redirect
4. If not present in our DB, let's return 404

Request flows

1. Client send request to LB
2. LB send reuqest to appropriate server based on RR stateless algorithm.
3. Application server check if exist in Cache, if exist return the full url
4. Application server check if exist in NoSql DB, if exist return the full url
5. Application server return the full url to redirect or 404 not found.

Detailed component design

I'd like the database to be replicating synchronously within the datacenter and async outside the datacenter. That could gurantee the strong consistence.

Version conflicts are not big issue for us as we won't have tons of duplicate records and two short-url can be mapped to a same url

Trade offs/Tech choices

There are 2 tradeoffs I made there:

1. read/write flows around cache. Choices when to write the cache, in write flow or read flow. In our senario, we are trading of write latency (which is ok to be slow) with read latency (which we care about).
2. Consistency for latency, we want the request to be served as quickly as possible and without waiting for all replicas to complete. The reason is again we care about read latency and mostly like link doesn't need to immediately available within second of creation.

Failure scenarios/bottlenecks

We do have few things which are SPOF - we can deploy many LB, servers and database nodes and cache nodes, but we should be very careful with the algorithm that generate short URL.

1. We do not keep tracks of used hash.
2. We are making lot of DB calls on create, lowering write latency.
3. The Hashes would ran out and the short url won't be short
4. If someone famous post a short URL would cause massive traffic

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?

Since our system is eventually consistency, in most cases it would be fine. But in special case there would be problems.

For example, if a famous person post a short link, and it's been requested by massive traffic before replicates to all nodes, it would cause two problem:

1. some nodes are able to get data;
2. too many request to DB that could crash DB or cost more money.

How to fix it?

For the specific user or famous user, we use push based approach in cache, that means we write cache during write request flow, that could leads the read requests to cache and lower the stress of DB