System requirements

Functional:

1. user can get the short URL with long URL
2. user can be redirected to the long URL with the short URL
3. distributed system to support large throughput

Non-Functional:

1. high availability: the availability of the system should be over consistency
2. low latency: user should get the response rapidly when request URL shortening and long URL redirecting.

Capacity estimation

Write:

• Assume 100M write every day.
• 100M / 86400 s = 1000 write / sec

Read:

• Read/write = 10:1, so we have 10k read/sec

Storage:

• Assume each URL is 100 bytes and they will be stored for 10 years, 100M * 10 * 100 byte * 365 = 365TB

API design

1. URL shortening:
2. POST api/v1/data/shorten
3. request parameter {url: longURL}
4. return shortURL
5. URL Redirecting:
6. GET api/v1/shortURL
7. return longURL with 301 redirect if the longURL exists.
8. otherwise, return 404 not found.

Database design

userID (PK)

shortURL

longURL

Description:

userID: unique ID can be generated by unique ID generator.

shortURL: 7 characters (a-z, A-Z, 0-9)

longURL: the long url is from the user

High-level design

URL Shortening:

1. Client sends request to tiny url server URL with longURL for shortening via API gateway and load balancer.
2. The app server first check if the long URL is in the cache and disk, if it exist, return the short URL to client with 200 ok code.
3. Otherwise, a new unique ID is generated which is used by the app server to create a short URL.
4. App server stores the userID, longURL and short URL to data store.

URL Redirection:

1. Client sends request to tiny url server URL with shortURL for redirecting via API gateway and load balancer.
2. Memory Cache: this system is read heavy. The server first checks if the long URL is in the cache, if it is not in cache, check if it is in data store. Return the short URL to the client with 301 redirecting.
3. If neither, return 404 not found code to client.

Request flows

Detailed component design

1. Short URL:
2. we can use Unique ID to generate shortURL
3. shortURL can be 7 chars from (a-z, A-Z, 0-9) which is base 62. We can convert the unique ID (base 10) to short URL (base 62)
4. the unique ID generators are also distributed and the details has been covered in unique ID generator chapter.

Trade offs/Tech choices

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

Read/Write: There are some trade-offs I am making when designing the read/write flows around the cache. Because this system is a read heavy system. We need the cache to make the read fast and write could be slow. In such case, the app server will send the response back to client first and then persist the change to data store.

Availability/Consistency: Another trade off I made is around the consistency. As the system is ready heavy and we would like the client receives the response as soon as possible, so the system must be a high available over consistency system. Eventually consistency to other replications is acceptable.

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

Failure Scenarios:

We do have a few things that could lower the system performance or even down.

1. The system could get DDoS attack or user abuse to exhaust the system resource
2. Mitigation: we can use Api gateway to apply the rate limiting and securities (authentication)
3. load balancer could be single point of failure.
4. Mitigation: we can use master-slave load balancer to resolve single point failure. When the master LB is down, the slave LB will be flipped over.

Bottlenecks:

1. a few famous short URL could be the hot spot and make the node which handles this URL be hot spot.

Future improvements

1. the longURL - short URL pair should be replicated to multiple data store to avoid data loss.