Cluster storage collection based data management

• US 20060271547A1
• Filed: 05/25/2005
• Published: 11/30/2006
• Est. Priority Date: 05/25/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhang, Zheng, Chen, Wei, Lian, Qiao
• Granted Patent: US 7,346,734 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1662 the resynchronized component or unit being a persistent storage device re-synchronization of failed mirror storage G06F11/2082; rebuild or reconstruction of parity RAID storage G06F11/1008
• CPC Class Codes: G06F 16/1844 Management specifically adapted to replicated file systems

Abstract

Cluster storage collection-based data management is described. In one aspect, and in a distributed system for storing data across a network to multiple data storage nodes, a bounded bandwidth available for data repair in the distributed system is determined. A specific number of stripes are then created on each data storage node of the multiple data storage nodes. The stripes are for placement and replication of data objects across respective ones of the data storage nodes. The specific number of stripes created on each data storage node is a function of the determined bounded data repair bandwidth.

Claims

1. In a distributed system for storing data across a network to multiple data storage nodes, a method comprising:

determining a bounded bandwidth available for data repair in the distributed system; and

creating a specific number of stripes on each data storage node of the multiple data storage nodes, the stripes for placement and replication of data objects across respective ones of the data storage nodes, the specific number of stripes on each data storage node being a function of the bounded bandwidth.

2. A method as recited in claim 1, wherein the bounded bandwidth is a function of bandwidth of a network and bandwidth of a data storage node of the data storage nodes.

3. A method as recited in claim 1, wherein creating the stripes further comprises:

calculating a target chunk size based on a replication degree such that data reliability of storing data across the multiple computing devices using a random data placement scheme is optimized; and

wherein creating further comprises allocating disk storage space on each node as a function of the target chunk size.

4. A method as recited in claim 3, wherein the target chunk size is based on bandwidth of a computer-readable medium for storing data on a data storage node of the data storage nodes, storage capacity of the computer-readable medium, and network bandwidth.

5. A method as recited in claim 3, wherein calculating the target chunk size further comprises analyzing data reliability of the distributed system in view of the bounded bandwidth, the analyzing comprising:

estimating a mean time to data loss (MTTDL) for an object (MTTDL_obj) of multiple objects as a function of a harmonic sum of MTTDL in each state i of multiple states i, the distributed system comprising the multiple objects, each state i representing a state of the distributed system when i data storage nodes fail and lost replicas on the i data storage nodes have not been repaired.

6. A method as recited in claim 3, wherein calculating the target chunk size further comprises analyzing data reliability of the distributed system in view of the bounded bandwidth, the analyzing comprising:

estimating a mean time to repair (MTTR) all failed replicas in a state i (MTTR(i)) of multiple states i, each state i representing a state of the distributed system when i data storage nodes fail and lost replicas on the i data storage nodes have not been repaired, the MTTR(i) being a function of an amount of data to be repaired in the state i and available bandwidth for repair in the state i.

7. A method as recited in claim 6, wherein the amount of data to be repaired in the state i is based on an amount of data in a last failed computing device of the i data storage nodes, and an amount of un-repaired data left on the last failed computing device from a previous state i.

8. A method as recited in claim 1, wherein the method further comprises randomly placing a single chunk of collected data objects on a randomly selected data storage node, the single chunk having been generated to correspond to the target chunk size, the single chunk being a unit for placement and repair.

9. A method as recited in claim 1, wherein the method further comprises:

grouping two or more data objects that are smaller than a target chunk size into a unit for placement and repair, the target chunk size being based on bounded network bandwidth and brick bandwidth such that reliability of storing data across the multiple data storage nodes using a random data placement scheme is optimized; and

randomly placing the unit for placement and repair on a randomly selected data storage node.

10. A method as recited in claim 1, further comprising:

collecting multiple data objects from data storage requests;

determining that collected ones of the multiple data objects meet a collective target chunk size criteria;

responsive to the determining, grouping the multiple data objects into a single chunk;

randomly selecting a data storage node and a corresponding stripe of the stripes for data placement; and

storing the single chunk of collected data objects onto the stripe using a replication data storage scheme.

11. In a distributed system for storing data across a network to multiple data storage nodes, a method comprising:

creating a specific number of stripes on each data storage node of the multiple data storage nodes, the specific number is a function of bandwidth of a network and bandwidth of a data storage node of the data storage nodes, the stripes for placement and replication of data objects across respective ones of the data storage nodes, the specific number being based on the bounded bandwidth; and

wherein each stripe is configured to store a data chunk and a replica of the data chunk, the data chunk representing collected data objects that have been grouped together into a single chunk that meets a criteria associated with a target chunk size, the target chunk size being a function of a determined data storage reliability of the distributed system.

12. A method as recited in claim 11, wherein the target chunk size is based on bandwidth of a computer-readable medium for storing data on a data storage node of multiple data storage nodes in the distributed system, storage capacity of the computer-readable medium, and distributed system network bandwidth.

13. A method as recited in claim 11, wherein the method further comprises estimating the data storage reliability in view of a mean time to data loss (MTTDL) for an object (MTTDL_obj) of multiple objects, the MTTDL being a function of a harmonic sum of MTTDL in each state i of multiple states i, the distributed system comprising the multiple objects, each state i representing a state of the distributed system when i data storage nodes fail and lost replicas on the i data storage nodes have not been repaired.

14. A method as recited in claim 11, wherein the method further comprises estimating the data storage reliability in view of a mean time to repair (MTTR) all failed replicas in a state i (MTTR(i)) of multiple states i, each state i representing a state of the distributed system when i data storage nodes fail and lost replicas on the i data storage nodes have not been repaired, the MTTR(i) being a function of an amount of data to be repaired in the state i and available bandwidth for repair in the state i.

15. A method as recited in claim 14, wherein the amount of data to be repaired in the state i is based on an amount of data in a last failed computing device of the i data storage nodes, and an amount of un-repaired data left on the last failed computing device from a previous state i.

16. A method as recited in claim 11, wherein the method further comprises randomly placing a single chunk of collected data objects on a randomly selected data storage node, the single chunk having been generated to correspond to the target chunk size, the single chunk being a unit for placement and repair.

17. A method as recited in claim 11, wherein the method further comprises:

grouping two or more data objects that are smaller than the target chunk size into a unit for placement and repair; and

randomly placing the unit for placement and repair on a randomly selected data storage node.

18. A method as recited in claim 11, further comprising restoring the data chunk on a data storage node with a replica of the data chunk stored on a different data storage node.

19. A method as recited in claim 11, further comprising:

collecting multiple data objects from data storage requests;

determining that collected ones of the multiple data objects approach a target chunk size; and

responsive to the determining, grouping the multiple data objects into a single data chunk for placement onto a stripe using a replication data storage scheme.

20. A method as recited in claim 19, further comprising:

randomly selecting a data storage node and a corresponding stripe of the stripes for data placement; and

storing the single and data chunk of collected onto the stripe.