Redundant data assigment in a data storage system

Abstract

The present invention provides techniques for assignment and layout of redundant data in data storage system. In one aspect, the data storage system stores a number M of replicas of the data. Nodes that have sufficient resources available to accommodate a requirement of data to be assigned to the system are identified. When the number of nodes is greater than M, the data is assigned to M randomly selected nodes from among those identified. The data to be assigned may include a group of data segments and when the number of nodes is less than M, the group is divided to form a group of data segments having a reduced requirement. Nodes are then identified that have sufficient resources available to accommodate the reduced requirement. In other aspects, techniques are providing for adding a new storage device node to a data storage system having a plurality of existing storage device nodes and for removing data from a storage device node in such a data storage system.

What is claimed is:  
     
         1 . A method of assigning data to storage device nodes in a data storage system wherein the data storage system stores a number M of replicas of the data, the method comprising identifying nodes that have sufficient resources available to accommodate a requirement of the data and when the number of nodes is greater than M, assigning the data to M randomly selected nodes from among those identified.  
     
     
         2 . The method according to  claim 1 , wherein the data to be assigned includes a group of data segments and when the number of nodes is less than M, dividing the group of data segments thereby forming a group of data segments having a reduced requirement and identifying nodes that have sufficient resources available to accommodate the reduced requirement.  
     
     
         3 . The method according to  claim 2 , further comprising repeating said dividing the group of data segments and identifying nodes that have sufficient resources available until at least M nodes are identified.  
     
     
         4 . The method according to  claim 3 , wherein a node is identified as having sufficient resources for the data only when available capacity of the node is at least as great as a capacity requirement of the data.  
     
     
         5 . The method according to  claim 4 , wherein a node is identified as having sufficient resources for the data only when an available performance parameter of the node is at least as great as a corresponding performance requirement of the data.  
     
     
         6 . The method according to  claim 5 , wherein the corresponding performance requirement includes throughput.  
     
     
         7 . The method according to  claim 4 , wherein a node is identified as having sufficient resources for the data only when availability of the M nodes is at least as great as a corresponding availability requirement of the data.  
     
     
         8 . The method according to  claim 4 , wherein a node is identified as having sufficient resources for the data only when reliability of the M nodes is at least as great as a corresponding reliability requirement of the data.  
     
     
         9 . The method according to  claim 1 , further comprising adding an entry to a data locations table wherein the entry identifies the data and the M nodes to which the data is assigned.  
     
     
         10 . A method of assigning data to storage device nodes in a data storage system wherein the data storage system stores a number M of replicas of the data, the method comprising dividing the data into a plurality of groups of segments and for each group of segments, identifying nodes that have sufficient resources available to accommodate a requirement of the data and when the number of nodes is greater than M, assigning the data to M randomly selected nodes from among those identified and when the number of nodes is equal to M, assigning the data to the M identified nodes and when the number of nodes is less than M, dividing the group of data segments thereby forming a group of data segments having a reduced requirement and identifying nodes that have sufficient resources available to accommodate the reduced requirement.  
     
     
         11 . The method according to  claim 10 , wherein when the number of nodes is less than M, further comprising repeating said dividing the group of data segments and identifying nodes that have sufficient resources available until at least M nodes are identified and assigning the group of data segment to M of the nodes that have sufficient resources available.  
     
     
         12 . The method according to  claim 11 , further comprising selecting a next group of segments and repeating said steps of identifying nodes and assigning the next group of segments to M of the nodes until all of the groups of segments have been assigned to the data storage system.  
     
     
         13 . The method according to  claim 12 , wherein a node is identified as having sufficient resources for the data only when available capacity of the node is at least as great as a capacity requirement of the data.  
     
     
         14 . The method according to  claim 13 , wherein a node is identified as having sufficient resources for the data only when an available performance parameter of the node is at least as great as a corresponding performance requirement of the data.  
     
     
         15 . The method according to  claim 13 , wherein a node is identified as having sufficient resources for the data only when availability of the node is at least as great as a corresponding availability requirement of the data.  
     
     
         16 . The method according to  claim 13 , wherein a node is identified as having sufficient resources for the data only when reliability of the node is at least as great as a corresponding reliability requirement of the data.  
     
     
         17 . The method according to  claim 10 , further comprising adding an entry to a data locations table for each group of segments assigned to the storage system wherein the entry identifies the group of segments and the M nodes to which the group of segments is assigned.  
     
     
         18 . The method according to  claim 10 , further comprising adding a new storage device node to the data storage system including identifying an existing node that is heavily loaded in comparison to other ones of existing nodes; moving data stored at the identified existing node to the new node; and determining whether the new node is sufficiently loaded in comparison the existing nodes and when the new node is not sufficiently loaded, repeating said steps of identifying and moving until the new node is sufficiently loaded.  
     
     
         19 . A method of assigning data to storage device nodes in a data storage system wherein the data storage system stores a number M of replicas of the data, the method comprising randomly selecting a set of at least M nodes and determining whether M nodes of the set have sufficient resources available to accommodate a requirement of the data and, when M nodes of the set have sufficient resources, assigning the data to the M nodes.  
     
     
         20 . The method according to  claim 19 , wherein the data to be assigned includes a group of data segments and when said steps of selecting and determining have been performed a predetermined number of times, dividing the group of data segments thereby forming a group of data segments having a reduced requirement.  
     
     
         21 . The method according to  claim 19 , wherein a node is identified as having sufficient resources for the data only when available capacity of the node is at least as great as a capacity requirement of the data.  
     
     
         22 . The method according to  claim 21 , wherein a node is identified as having sufficient resources for the data only when an available performance parameter of the node is at least as great as a corresponding performance requirement of the data.  
     
     
         23 . The method according to  claim 21 , wherein a node is identified as having sufficient resources for the data only when availability of the M nodes is at least as great as a corresponding availability requirement of the data.  
     
     
         24 . The method according to  claim 21 , wherein a node is identified as having sufficient resources for the data only when reliability of the M nodes is at least as great as a corresponding reliability requirement of the data.  
     
     
         25 . The method according to  claim 19 , further comprising adding an entry to a data locations table wherein the entry identifies the data and the M nodes to which the data is assigned.  
     
     
         26 . A method for adding a new storage device node to a data storage system having a plurality of existing storage device nodes for storing redundant data, the method comprising steps of: 
 identifying an existing node that is heavily loaded in comparison to other ones of the existing nodes;    moving data stored at the identified existing node to the new node; and    determining whether the new node is sufficiently loaded in comparison the existing nodes and when the new node is not sufficiently loaded, repeating said steps of identifying and moving until the new node is sufficiently loaded.    
     
     
         27 . The method according to  claim 26 , wherein said determining comprises determining an average loading of the existing nodes and when the loading of the new node is at least as great as the average loading, then the newly-added node is sufficiently loaded.  
     
     
         28 . The method according to  claim 26 , wherein said determining comprises determining an average loading of the existing nodes and when the loading of the new node within a range bounded by the lowest and highest loading of the existing nodes, then the newly-added node is sufficiently loaded.  
     
     
         29 . The method according to  claim 28 , wherein the data stored at the existing node includes a group of data segments selected from among a plurality of groups of segments stored at the existing node.  
     
     
         30 . The method according to  claim 29 , wherein the group of data segments is selected according to its size.  
     
     
         31 . The method according to  claim 26 , wherein said identifying is performing by comparing utilization of the existing nodes.  
     
     
         32 . The method according to  claim 26 , further comprising updating a data locations table to indicate said moving the data.  
     
     
         33 . A method for removing data from a storage device node in a data storage system for storing redundant data, the data storage system having a plurality of storage device nodes, the method comprising steps of: 
 selecting data from the storage device node from which data is to be removed;    identifying other nodes of the data storage system having sufficient resources available to accommodate a requirement of the data;    moving the data to a randomly selected node from among those identified; and    repeating said steps of selecting, identifying and moving until the storage device node to be removed is empty.    
     
     
         34 . The method according to  claim 33 , further comprising removing the node from the data storage system.  
     
     
         35 . The method according to  claim 33 , wherein the data stored at the existing node includes a group of data segments selected from among a plurality of groups of segments stored at the existing node.  
     
     
         36 . The method according to  claim 33 , wherein when another node of the data storage system having sufficient resources available to accommodate a requirement of the data is not identified, dividing the group of data segments thereby forming a group of data segments having a reduced requirement.  
     
     
         37 . The method according to  claim 36 , wherein a node is identified as having sufficient resources for the data only when available capacity of the node is at least as great as a capacity requirement of the data.  
     
     
         38 . The method according to  claim 37 , wherein a node is identified as having sufficient resources for the data only when an available performance parameter of the node is at least as great as a corresponding performance requirement of the data.  
     
     
         39 . The method according to  claim 37 , wherein a node is identified as having sufficient resources for the data only when availability of the node and other nodes to which the data is assigned is at least as great as a corresponding availability requirement of the data.  
     
     
         40 . The method according to  claim 37 , wherein a node is identified as having sufficient resources for the data only when reliability of the node and other nodes to which the data is assigned is at least as great as a corresponding reliability requirement of the data.  
     
     
         41 . The method according to  claim 33 , further comprising updating a data locations table to indicate said moving the data.  
     
     
         42 . A method for removing data from a storage device node in a data storage system for storing redundant data, the data storage system having a plurality of storage device nodes, the method comprising steps of: 
 selecting data from the storage device node from which data is to be removed;    randomly selecting at least one other node in the data storage system;    determining whether the at least one other randomly selected node has sufficient resources available to accommodate a requirement of the data;    moving the data to one of the randomly selected nodes having sufficient resources available to accommodate a requirement of the data; and    repeating said steps of selecting data, randomly selecting, determining and moving until the storage device node to be removed is empty.    
     
     
         43 . The method according to  claim 42 , further comprising removing the node from the data storage system.  
     
     
         44 . The method according to  claim 42 , wherein the data stored at the existing node includes a group of data segments selected from among a plurality of groups of segments stored at the existing node.  
     
     
         45 . The method according to  claim 42 , wherein when another node of the data storage system having sufficient resources available to accommodate a requirement of the data is not identified, dividing the group of data segments thereby forming a group of data segments having a reduced requirement.  
     
     
         46 . The method according to  claim 45 , wherein a node is identified as having sufficient resources for the data only when available capacity of the node is at least as great as a capacity requirement of the data.  
     
     
         47 . The method according to  claim 46 , wherein a node is identified as having sufficient resources for the data only when an available performance parameter of the node is at least as great as a corresponding performance requirement of the data.  
     
     
         48 . The method according to  claim 46 , wherein a node is identified as having sufficient resources for the data only when availability of the node and other nodes to which the data is assigned is at least as great as a corresponding availability requirement of the data.  
     
     
         49 . The method according to  claim 46 , wherein a node is identified as having sufficient resources for the data only when reliability of the node and other nodes to which the data is assigned is at least as great as a corresponding reliability requirement of the data.  
     
     
         50 . The method according to  claim 42 , further comprising updating a data locations table to indicate said moving the data.  
     
     
         51 . A program storage medium readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for assigning data to storage device nodes in a data storage system wherein the data storage system stores a number M of replicas of the data, said method steps including: identifying nodes that have sufficient resources available to accommodate a requirement of the data and when the number of nodes is greater than M, assigning the data to M randomly selected nodes from among those identified.  
     
     
         52 . A program storage medium readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for adding a new storage device node to a data storage system having a plurality of existing storage device nodes for storing redundant data, said method steps including: 
 identifying an existing node that is heavily loaded in comparison to other ones of the existing nodes;    moving data stored at the identified existing node to the new node; and    determining whether the new node is sufficiently loaded in comparison the existing nodes and when the new node is not sufficiently loaded, repeating said steps of identifying and moving until the new node is sufficiently loaded.    
     
     
         53 . A program storage medium readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for removing data from a storage device node in a data storage system for storing redundant data, the data storage system having a plurality of storage device nodes, said method steps including: 
 selecting data from the storage device node from which data is to be removed;    randomly selecting at least one other node in the data storage system;    determining whether the at least one other randomly selected node has sufficient resources available to accommodate a requirement of the data;    moving the data to one of the randomly selected nodes having sufficient resources available to accommodate a requirement of the data; and    repeating said steps of selecting data, randomly selecting, determining and moving until the storage device node to be removed is empty.