Distributed Systems -- 2

We’ll extend the simple consistent hashing based datastore shown in the notebooks. In this project, we’ll look at using virtual nodes, masterless data fetch, and addition and removal of nodes.

Problem Statement
The program structure is already set and there are specific methods that you are expected to implement. Please also read the comments in the code, especially in the methods to be implemented. Please leave data_store.py as it is. You can copy it to a different file and modify that for your testing and demonstration purposes as you see fit.

1. (Medium) Implement the populate_map method in VirtualNodeMap class.

You are supposed to create a random mapping (dictionary) of virtual node numbers (0 to (TOTAL_VIRTUAL_NODES - 1)) mapped to node names.

Each node should get equal distribution of virtual nodes. However, given the maths, it might not be always exactly possible so slight variations are fine, for example, distributing 200 virtual nodes among 6 nodes would mean that 2 nodes would get an extra virtual node. Please ensure that exactly TOTAL_VIRTUAL_NODES count of virtual nodes are there in the mapping.

2. (Medium) Implement get_data and set_data in the Node class


2a. get_data: As you can see, it currently just looks up in its local data store and tries to return the value. This would, of course, fail for keys owned by other nodes.
Enhance this method to fetch from local or sibling nodes based on node assignment of the key and return the data to the user. You can assume local ownership if the key exists in the local store.

2b. set_data: Firstly, as specified in the function, data will always be set in the current node if the force flag is True. Aside from that, the method is still setting the data in the local data store.

When the force flag is not True, enhance this method to find the node owner based on node assignment of the key. Then set the data locally or call a sibling set_data method accordingly.

3. (Hard) Implement gaps specified in add_new_node

3a. At the specified place (see comments in the method), find the list of all virtual nodes mapped to this node, store them in the specified variable and shuffle them

3b. At the specified place (see comments in the method), loop over all local keys and create the appropriate structure that can be ingested by transfer_keys. Please ensure to only consider keys mapped to virtual nodes in the local_vnode_slice as we’ll be transferring only a few virtual nodes to a new node.

4. (Hard) Implement gaps specified in remove_current_node

4a. At the specified place (see comments in method), find the list of all virtual nodes mapped to this node, store them in the specified variable and shuffle them

4b. At the specified place (see comments in the method), loop over all local keys and create the appropriate structure that can be ingested by transfer_keys. Please ensure to correctly mark the appropriate target node based on the new mapping created in transfer_node_mapping