Detailed component design

First component: The KGS will be continuously generating keys, since we are expecting the key length to be 6 characters long, with base64 encoding, we can generate 64^6 ~ 68 billion keys. Thus, we would need 6 * 68 * 10 ^ 9 = 420 * 10 ^ 9 = 420 GB. The key DB would need 420 GB of storage. We can limit the size of the key to be 16 for custom aliases. To prevent collision, we move all keys to the used table and since the KGS is offline, it is very fast to fetch a new key.
Second component: Since we would be querying many keys, the database could be a bottle neck. We will perform horizontal partitioning of the data where each replica db will hold a set of the records. We would use consistent hashing here where we hash the object to an integer and in a circular fashion, store the object in the next db corresponding to the hash. We could also use virtual nodes to ensure that in the case of db failures, the records are not moved around too much since we have a much more even distribution using virtual nodes.
Third component: For the caches, we can use MemCached which can store long urls and their keys. We calculated above that caches would require around 30 GB of storage which is reasonable. We will also replicate the caches to distribute the load. Each cache will use the LRU eviction policy since we want to keep the hottest URLs in the cache and evict the cold ones. This could be done with a linked hashmap or some alternative.
Fourth component: To clean up expired links, we want to delete them from our system. It would be expensive to do this continuously so as a tradeoff, we will use lazy deletion. When a user queries for an expired link, we will then delete it and return an error. A lightweight async job will still run to clean up expired link but it no longer has to be a consistently running job, we could likely run it during off hours to reduce the load on the database. Optionally, we could move the keys back to the unused table, however this may be confusing to users if the same short link suddenly redirects to a different website, so we would not do that.
For data retention, we choose to keep all urls until they expire

Submissions

Displaying Solutions with Scores Ranging from 1 to 10

Submissions

Displaying Solutions with Scores Ranging from 1 to 10