Redundant data assigment in a data storage system

• US 20080046779A1
• Filed: 07/13/2007
• Published: 02/21/2008
• Est. Priority Date: 05/16/2003
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Spence, Susan, Merchant, Arif, Veitch, Alistair, Frolund, Svend, Saito, Yasusuhi
• Granted Patent: US 8,775,763 B2
• Time in Patent Office: Days
• US Class Current: 714/6
• CPC Class Codes: G06F 11/2087 with a common controller
• CPC Class Codes: G06F 2206/1012 Load balancing
• CPC Class Codes: G06F 3/0605 by facilitating the interaction with a user or administrator
• CPC Class Codes: G06F 3/0607 by facilitating the process of upgrading existing storage systems, e.g. for improving compatibility between host and storage device
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0635 by changing the path, e.g. traffic rerouting, path reconfiguration
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

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.

Claims

1-17. -17. (canceled)

18. 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, the requirement including at least one of a reliability requirement, a capacity requirement and a performance requirement, and when a number of nodes identified by said identifying 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 and the method 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-25. -25. (canceled)

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. (canceled)

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-41. -41. (canceled)

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-53. -53. (canceled)