QuestionDatastore with Consistent HashingIntroductionWe’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.Housekeeping pointsThis is a minimal example and may not follow some standard practicesThe focus is on the main flow, with minimal error handling.This has basic consistent hashing semantics. It might not follow all production practices rigorously.Please read the comments in the code, they explain the structure and the methodsProgram OrganizationAll the code is in the M01-P02-Source-Code.zip fileUser.py: This file implements UserInfo and UserData classes. UserInfo has a user id field and UserData data including email and password. These are mainly to create the data to be stored in the data storeInfoGenerator.py: InfoGenerator class implements utility methods for generating various random data including:generate_user_id – Creates monotonically increasing user id using a class methodgenerate_email and generate_password – Static methods for generating random but structured strings for email and password datagenerate_node_name – Static method for generating random node name including timestamp to further avoid any chance of name clashesVirtualNodeMap.py: VirtualNodeMap class implements and stores vnode-to-node name mapping. It’ll be composed inside of the Node class. It supports creation of random but balanced vnode-node mapping and provides fetching the node for a given vnode or a given key. Keys are mapped to virtual nodes by a simple modulo based mapping.Node.py: Node class implements the main logic in the data store. Multiple Node instances work together as an example distributed data store.get_data and set_data: These methods provide retrieval and insert/update in the data store. Ultimately, they are supposed to handle any key query and internally get the data from the appropriate node. A normal client should be able to interact with any node about any key, without the need to understand or know about key ownership.add_new_node: This method is called in each existing node when a new node is created. It’ll reassign a proportional quantity of virtual nodes from itself to the new node. It’ll then prepare for the transfer of the relevant keys and accomplish the actual transfer using transfer_keys methodremove_current_node: This method is called on the node selected for removal in a planned scenario while down-scaling. It’ll take all of its virtual nodes and proportionately reassign them to all other remaining nodes. It’ll then prepare for the transfer of the keys and accomplish the actual transfer using transfer_keys methodtransfer_keys: This function takes keys to be transferred, grouped by the virtual nodes. It goes through all of them, transferring each block and reassigning the virtual node to the new mapped node.data_store.py: This is the main driver program. In order, it:Creates a node first and creates a random VirtualNodeMap inside itCreates other initial set of nodes, with the same virtual node mapping and connects them with each otherTakes appropriate actions to add a new nodeTakes appropriate actions to remove an existing nodeDemonstrates the state of all available nodes and also shows data interaction on random user ids, after each major step.Problem StatementThe 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.(Hard) Implement gaps specified in add_new_node1a. 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 them1b. 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.==========================================================————————Including the Node.py code below—————————==========================================================import copyimport randomimport mathfrom VirtualNodeMap import VirtualNodeMapclass Node: def __init__(self, name, TOTAL_VIRTUAL_NODES, vnode_map=None): self._name = name self._node_dict = {} self._data_store = {} self._vnode_map = vnode_map self._TOTAL_VIRTUAL_NODES = TOTAL_VIRTUAL_NODES def __str__(self): return f’Node: {self.name}, Number of Stored Keys: {len(self._data_store)}’ @property def name(self): return self._name &..;@name.setter def name(self, name): self._name = name @property def node_names(self): return list(self._node_dict.keys()) # For a masterless data fetch, any key can be requested from any Node # The Node should return the value directly if it has the ownership # Otherwise it should find the Node with ownership and act as a proxy to get data from # that node and return to the client def get_data(self, key): # Problem statement 2.a # Update this function to return value from local store if exists (assuming it’s the owner) # Otherwise it should find the owner using get_assigned_node function in _vnode_map # and use get_data in that node to return the value return self._data_store[key] # For a masterless data save/update, any key update can be sent to any Node # This node should find the Node with ownership and act as a proxy to set data in # that node # Please note that ‘force’ flag overrides this behaviour # ‘force’ will be used during rebalancing in node addition/deletion # This is so that data can be saved first before vnode map update def set_data(self, key, value, force=False): if (force): self._data_store[key] = copy.deepcopy(value) else: # Problem statement 2.b # Update this else section to find the owner using get_assigned_node function in _vnode_map # and set the value in the correct node. Use direct assignment if its the current node # or call set_data in the remote note otherwise self._data_store[key] = copy.deepcopy(value) def remove_data(self, key): return self._data_store.pop(key, ‘Key not found’) def get_keys(self): return self._data_store.keys() # This updates the nodes information by doing a new copy # However actual node instances are retained to be the same def populate_nodes(self, new_node_dict): self._node_dict = {} for node_name in new_node_dict: self._node_dict[node_name] = new_node_dict[node_name] def add_node_to_mapping(self, new_node_name, new_node): self._node_dict[new_node_name] = new_node # This clones a complete instance copy for the VirtualNodeMap class to be used in other nodes def clone_vnode_map(self): return copy.deepcopy(self._vnode_map) # This is triggered in the initial node to actually create a randomized virtual node mapping def initialize_vnode_map(self, node_names): self._vnode_map = VirtualNodeMap(node_names, self._TOTAL_VIRTUAL_NODES) self._vnode_map.populate_map() # This changes the mapping of a particular vnode to a new node def set_vnode_map_entry(self, vnode, node_name): self._vnode_map.set_new_assigned_node(vnode, node_name) # Transfers the keys to the new target node, one vnode at a time # Each vnode key in the transfer_dict has a dictionary as value # which includes a list of keys to transfer, and the target node name # Each vnode’s mapping change is broadcasted to all the nodes to change # after all the relevant keys have been sent to the new owner def transfer_keys(self, transfer_dict): for vnode, transfer_data in transfer_dict.items(): target_node_name = transfer_data[‘target_node’] target_node = self._node_dict[target_node_name] # Transfer all keys for a vnode and remove them from the existing node for key in transfer_data[‘keys’]: target_node.set_data(key, self._data_store[key], True) entry = self.remove_data(key) # Update virtual node maps for everyone for node in self._node_dict.values(): node.set_vnode_map_entry(vnode, target_node_name) # Called on each node when a new node is added # It selects a part of its vnode set to assign to the new node # It then creates the transfer_dict for keys from the to-be transferred vnodes def add_new_node(self, new_node_name, new_node): local_vnode_list = [] self.add_node_to_mapping(new_node_name, new_node) # Problem statement 3.a # Finds all vnodes mapped to this node and shuffles them # Implement this logic and store in local_vnode_list # Prepares to select proportional vnodes and their corresponding keys to transfer transfer_slice = round(len(local_vnode_list) / len(self._node_dict)) local_vnode_slice = local_vnode_list[0:transfer_slice] transfer_dict = {} # Problem statement 3.b # Loop over all keys and create the transfer dict structure # Only the relevant keys from vnodes in the local_vnode_slice should be considered # An example of the structure will look like: # transfer_dict{ # 23: {‘target_node’:
