Detailed Component Design

Requests to backend would be rooted by our API gateway, ethier by round-robin or by least connections principle.

Then i would introduce back-end server. It's responsible for handling both requests. When generating short URL, i would generate hashcode of it, and attempt to store first 6-7 characters. I would use sha256 for it. That would give me 3T of different combinations, so collisions would be rare. If it is there already, i would attempt to move sliding window of 6-7 characters along generated hashcode. Given that user is not generating urls often, target is <1s so we can afford retries. As it is not storing any data at runtime, it is stateless and we can have active-active configuration. If one instance goes down, other will take over the trafic. no prewarm needed - no downtime. As for split brain issue - when two instances consider themselves masters - we don't have modify endpoints - only create and read. For this reason collisions are not possible. for the same reason, we can scale those instances horizontaly when we have burst traffics. Retries could be handled by API gateway.

For disabled or edited links, we could have separate backend endpoint.

/api/disable/{shortUrl}. It would acess the cache and remove corresponding rows. First by taking long Id as a value from first table, then removing both rows in both tables by primary key. For editing. Customer cannot edit them as per functional requirements.

For this, we would have to lock the row before modifying it - in order to avoid concurrent interactions. I wouldn't purge the cash, only to invalidate single link, as restoring it is expensive process.

In order to decide, if cache can act like a persistent db, i will run calculations. Given that one entity contains following: shortUrl (250b), longUrl (1Kb), isEnabled(1b), we have 1.25kb per one entity. With 100M reads and read:write ration 100:1 we end up with 1M writes a day. With retention policy (TTL per entry) of 1 year, we will have 1.25kb x 1M x 365 = 456 gb of data. One single Redis instance can easily handle up to 100gb of data. Therefore, redis is not an enough solution.

As for the bandwith, we have for write, we have 500RPS x 1.250kb = 625kb/s

I would keep redis a a cache, having only 10% of the hottest trafic in the cache. This could be achieved by daily eviciton of the cache.

As a database, i would go for non-relational db - we have standard key-value pairs. MongoDb is the first idea candidate It would be responsible for storing both short and long urls. I would use two tables. First is would have key as a shortUrl and value as a LongUrl. It would be used for read request. Second would have key as LongUrl and value as Short Url. It would be used to check if we already have URL for create request. Keys in both cases represent the url. And url should always lead to the same place. This that in case we face collision - it simply means we already have the shortUrl generated, and should just return it

For a very hot IDs, we have in-memory cache: Redis. It can handle up to 1M request per second, which is sufficiend even for the celebrity problem - when one famous person creates a link and millions click on it within a minutes. In order to improve that, we could potentially add small in-memory cache like small hashmaps to account for the hottest IDs.

Submissions

Displaying Solutions with Scores Ranging from 1 to 10