Detailed Component Design

Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.

The main component of interest is the hash service as well as how to associate a hash value with an actual URL.

One thing we'll want to consider is how to associate a hash value with an actual 'url'. Assuming the url portion is made up of only alphanumeric characters in the range of A-Z, a-z and 0-9, then in total we have 26 + 26 + 10 characters, leading to 62 possible characters. The easiest way to convert from a hash value (an integer) value into characters is to do so in base 62. For example, let's assign A-Z as the values 0-25, a-z as the values 26-51, and 0-9 as 52-61. If we have a value like 63, then we'd have AB I believe. This would allow us to actually get the URL. In the database, we'd store the value of '63' as the key and the long url as the value.

One thing that we'll need to handle is collisions in terms of IDs. When multiple servers are generating hash values, there may be a chance of conflicts if there are multiple instances of the hash service. If there is only one, there is no conflict, but it becomes a bottleneck and Single point of failure. If we do have multiple instances of the hash service, we can make use of the Snowflake style ID generator. We allocate 64 bits for each hash value. Here we can allocate 41 bits for the time stamp, 10 bits for the hash server instance, and 12 bits for the actual sequence number. 12 bits allows for 2^11 different combinations per second, which should be sufficient for our use case.

The next challenge is security. Because the snowflake approach is monotonically increasing, any malicious actor can find out how we 'hash' our values and reverse engineer it. To prevent that, we may may also want to use a crypotgraphic hash to encode the generated hash value. This way, only the server knows the secret and has the key.

The other thing that's worth considering is whether or not we actually need to query the database every time. In most cases, there may be 'hotspot' shortened URLs and repeated queries to the database may overload the database. To lessen the load, we could introduce a cache in between the server and the database. Thus anytime we query the database, we'd query the cache to see if that key value pair is stored there. If yes, then we retrieve it from the cache. If not, then we retrieve from the database, and write through the cache as well. Of course, we want to ensure that the cache has a TTL for each entry to prevent stale entries.

For further caching, we can also store the redirect codes associated with a short code at the CDN level, preventing later requests from hammering our servers.

So for database partitioning, we could separate the database into different shards. The most straightforward is to assign a key via its hash value (consistent hashing). The node following the key in the hash ring will be the one assigned to 'store it'. If nodes are added and removed, then we can easily adjust a small subset of keys that will be assigned to a new node (if added) or reassigned to an existing node if removed.

For replication/availability, we can also assign read replicas for each of the nodes. In the case that the master fails, we can use a consensus algorithm to vote in a new leader and have it stand in.

Submissions

Displaying Solutions with Scores Ranging from 1 to 10

Submissions

Displaying Solutions with Scores Ranging from 1 to 10