High-Level Design

the client will make a call, either get, set, etc. the call will reach load balancer which routes it to coordinator node. this one will be responsible to route it to the correct node within the has ring. we could you consistent hashing: we have a number of N nodes spread across a circle; whenever we want to add a new operation, we place it in the circle and map it to the closest node to the right. this will ensure that in case of removing one node, we will have to recompute only the ones to its left and not the entire entries.

replication manager will be the one handling scales up and the one actually computing the matching node for an entry using a hash function and applying it to the key. it will be using version vectors to handle concurrent operations and ensuring consistency: for example we will save data[{node,version}] where node is the node the operation will be routed to and version will keep getting incremented on each update of the same data. this will be an array where we keep adding the versions. when the memory is being restrained, we will remove the older entries giving priority to the new ones.

hash ring is the upper method i mentioned where we route the data to a specific node to its right, you can scale up this by simply adding multiple nodes, which are replicas of one main node. these communicate between them using gossip protocol, meaning that a node sends requests to a random set of other nodes and the next node forwards to some other nodes and so on. when multiple nodes start receiving no responses from let's say one specific node, it means that the node might be down, so it checks with a failure detector that afterwards pushes all the writes directed to that node to a message queue to assure consistency when the server is back up. once it's up it start updating it, until then, the node to its right will be taking its place.

for read repairs, we could use merkle trees: each node maintains a Merkle tree for its data partitions. The tree is built by hashing individual key-value pairs at the leaf level, then recursively hashing pairs of hashes up to the root.

during anti entropy (checking consistency between the values of different replicas) nodes exchange only the root level hashes. If roots match, data is consistent. If roots differ, they traverse down the tree level by level — comparing child hashes to identify exactly which data ranges have diverged. This minimizes data transfer since only the differing branches need comparison.

Once inconsistencies are found, read repair kicks in: the node with stale data fetches the correct values from a replica with newer data (determined by version vector timestamps). This happens asynchronously in the background, but can also be triggered during read operations — if a coordinator reads from multiple replicas and detects version mismatches, it repairs the stale replica inline."

ttl manager can be used to evict expired nodes and all their data in order not to consume too much memory useless.

each node will look like this internally: it has in memory stored results (these will be the most read results), and in case of missing results it will check the storage engine. we could use sorted strings tables to get a faster access by the key, by searching them lexicographically

for space reclamation, we use a compaction process. when keys are deleted, they are marked rather than immediately removed. During compaction, multiple sstables are merged together and it removes the keys marked for deletion that have exceeded the grace period

Submissions

Displaying Solutions with Scores Ranging from 1 to 10