System requirements

Functional:

• The system should be able to take a URL and return an alias: a hash string.
• The system should redirect to the mapped URL upon loading the hashed string in the browser.
• The system should allow to optionally name a URL with a custom alias.
• The system should allow to delete a URL.
• Authentication is out of scope (for now).

Non-Functional:

• The aliases must be unique
• The aliases must be alphanumeric
• We want to prevent bad actors from flooding the system programmatically, so we will rate limit the shortening to 5 URLs per user per hour.
• When deleting an alias:
  • The alias should be reusable
  • The system should return a 404 error.

Capacity estimation

Users will shorten a URL and then access it potentially multiple times a day.

Based on this we could say that a user in average will shorten 1-2 URLs per day and access them at least 8 times during the day (case considered is average works hours, accessing to the link once an hour).

With no user authentication we might have more "walk-ins" meaning that we can have traffic in the tens of millions in DAU if the system is somewhat popular.

This means that if we have ~10M DAU, we will have:

1. 1.5 writes/day x User * 10M DAU
   1. 15M writes/day
   2. 15M / 24 ~ 600k writes/hour
   3. 600k/3600 ~ 6000/36 = 1000/6 ~ 167 write/s
2. 8 reads/day x User * 10M DAU
   1. 80M reads/day
   2. 80M/24 ~ 3.2M reads/hour
   3. 3.2M/3600 ~ 890 reads/s

If we were to have a URL peaking, and say 50% of the DAU were to visit at least four times a day, we would have:

1. 5M DAU * 4 reads/day = 20M reads/day
   1. ~220 reads/s
2. Avg traffic + burst traffic ~ 1.1k reads/s

Finally, if we have 15M unique URLs shortened per day total, this means that in a period of a year we could potentially have 5.475 billion unique URLs shortened stored in the database. In a period of 10 years, we would have 54.75b unique URLs.

This means that if we were to set a hash length of 10 characters using base-62 encoding, we would be able to hold ~800q unique URLS. If we were to set 9 characters as the size, the unique URLs space gets shrunk to ~13q. It would take hundreds of years to even fill that space which reduces the possibilities of collisions.

Just storing 5.475b, 9 character strings will represent 54.75b Bytes (50.73 GB) per year stored in the database.

Thankfully, this is within the limits of what a DBRMS system can hold.

API design

POST /shorten/

DELETE /shorten/

GET /{hash}

Database design

URLS (285B)

• (Indexed) HASH: VARCHAR(9) (11 bytes for field + ~19B for index)
• URL: VARCHAR(255) (256B)

The table should hold ~100-200b records in typical DBRMS (like MySQL or Postgres) which give us ~20 years of storage.

High-level design

The system should be composed of

• A client
• The ShortenService backend with N servers
• A load balancer between the client and the shorten service
• A rate limiter at the middleware level in the shorten service
• A NoSQL database the backend consumes from
• A cache used to improve the read performance

Request flows

POST /shorten

• Client submits request
• Request gets deferred by the load balancer using round robin
• The rate limiter in the middleware responds with 429 if rate limit is reached, continues if not.
• The server checks if the hash or slug exists.
  • If it's a hash it automatically tries with 1 more character.
  • If it's a slug, then it returns a 400 Bad Request error that should be processed by the client and surfacing that the slug has already been taken.
• If the hash or slug is unique, then the server adds the record in both the Database and the Cache.
  • If the cache is full then we evict the least recently accessed URL.

DELETE /shorten/

• Client submits request
• Request gets deferred by the load balancer using round robin
• The rate limiter in the middleware responds with 429 if rate limit is reached, continues if not.
• The server deletes the item from the database and the cache if it exists.

GET /{HASH}

• Client submits request
• Request gets deferred by the load balancer using round robin
• The rate limiter in the middleware responds with 429 if rate limit is reached, continues if not.
• The server checks the cache.
  • If it's a miss, then the server checks the database.
    • If the record exists, then it returns a 303 Redirect Immediately and adds a background task to add the record to the cache.
    • If the record doesn't exist then it returns a 404 error.
  • If the record exists then return 302 and redirect to URL.

Detailed component design

Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...

Trade offs/Tech choices

Collisions

Given the birthday paradox, even seemingly remote, there is still a chance of collision depending the amount of records we store, which becomes greater as the table gets populated.

For this length of a string we would expect to see collisions as the numbers get close to the limit (~13q). Considering that in 100 years we would probably reached 547.5b unique URLs, the chances of reaching 13q records are very low, but still possible. In order to deal with collisions I propose two solutions:

1) Recommended - To hash the URL using base-62 and truncate it to 9 characters. If there is collision, then we truncate the hash to 10 characters and if that collides, we truncate it to 11 characters, and so on. We will use a highly available / partition tolerant NoSQL database for storage:

• Pros:
  • We rely entirely on business logic for the hashing.
  • We don't need an extra ID field that takes 16 bytes.
    • (PK) ID: (BIGINT) AUTOINCREMENTAL (8 bytes for field + ~16B for index)
  • High availability for writes and reads.
• Cons:
  • We are giving away consistency meaning that for some deletions, customers might still have access to the deleted URL (or access to an unrelated URL that could have used the same hash before).

2) To hash the URL using base-62 and truncate it to 9 characters. If there is collision, then we truncate the hash to 10 characters and if that collides, we truncate it to 11 characters, and so on. We would store using DBRMS:

• Pros:
  • We rely entirely on business logic for the hashing.
  • We don't need an extra ID field that takes 16 bytes.
    • (PK) ID: (BIGINT) AUTOINCREMENTAL (8 bytes for field + ~16B for index)
  • We can benefit of strong consistency to be ACID-compliant for deletions.
• Cons:
  • We would have to manage the replication rather than delegating it to a managed solution.
  • If a user hits the wrong node they might get a failure, reducing the availability.

3) To generate an autoincremental ID and hash it using base-62. We would have to use a DBRMS to save time on the business logic.

• Pros:
  • No need to implement more complex hashing to prevent collisions as each ID will be unique.
  • It reuses already implemented capabilities by DBRMS to generate hashes.
  • We can benefit of strong consistency to be ACID-compliant for deletions.
• Cons:
  • We would have to manage the replication rather than delegating it to a managed solution.
  • If a user hits the wrong node they might get a failure, reducing the availability.
  • For highly concurrent scenarios the ID generation can fall into contention issues, which will cause performance issues.

Duplicate URLs

In order to deal with URLs that have already been hashed, we have to consider that we have to allow the system to also assign custom slugs to URLs, even if they are hashed.

We have some alternatives:

1) Recommended - Allow for duplicates for fast performance. Hash and slug can be stored under the same column, and it will be already indexed.

2) Create a slugs table, that contains a slug and a FK to the hash in the URLs table. We would create a unique index for the URL.

• We are just removing duplicates virtually as we are just normalizing, but in reality we are still consuming storage and decreasing performance.
• We could leverage a bloom filter stored in the cache that checks whether the URL exists in the set or not. If the doesn't exist, we create the entry; if not we try to load the entry the URL belongs to as part of the response.

3) To add a column "is_custom: BOOLEAN" to the URLs table, and add a unique index for (URL, is_custom), then we can implement our business logic in a way such that if there are duplicates, we catch them and return the original record instead.

• This approach is expensive and adds complexity to the solution at the expense of performance and storage.

Caching - Eviction Strategy

1) Recommended - LRU, mainly because people tend to access more to recently visited websites, which this eviction strategy uses as a leverage.

2) LFU - If we were to go with this one, it would be mostly useful on peak times, but as soon as that passes we will have old items that peaked lingering until there are newer items peaking in access, which doesn't help too much with the performance.

Failure scenarios/bottlenecks

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

Future improvements

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