Method, device, and system for data reconstruction

• US 9,904,599 B2
• Filed: 08/11/2014
• Issued: 02/27/2018
• Est. Priority Date: 02/09/2012
• Status: Active Grant

• Current Assignee: Xfusion Digital Technologies Company Limited
• Original Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Inventors: Yin, Yu, Wang, Daohui
• Primary Examiner(s): Bonzo, Bryce
• Assistant Examiner(s): GIBSON, JONATHAN D
• Application Number:
  US14/456,690
• Publication Number:
  US 20140351636A1
• Time in Patent Office: 1,296 Days
• CPC Class Codes: G06F 11/0727 in a storage system, e.g. in a DASD or network based storage system drivers for digital recording or reproducing units G06F3/06; circuits for error detection or correction within digital recording or reproducing units G11B20/18; for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS], H04L67/1097
• CPC Class Codes: G06F 11/0757 by exceeding a time limit, i.e. time-out, e.g. watchdogs
• CPC Class Codes: G06F 11/1446 Point-in-time backing up or restoration of persistent data
• CPC Class Codes: G06F 11/1464 for networked environments
• 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 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 16/214 Database migration support
• CPC Class Codes: G06F 16/90335 Query processing

Abstract

A method for data reconstruction includes: obtaining a data migration list, where the data migration list indicates a partition with data to be migrated on a storage node with data to be migrated; generating a data migration task according to the data migration list and routing table information, where the routing table information indicates correspondence between a storage node in a cluster and a partition; and concurrently executing data migration tasks of a storage node in the cluster to reconstruct data. In addition, a device for data reconstruction and a storage system are further provided accordingly.

Claims

1. A method for data reconstruction in a cluster having a plurality of storage nodes, wherein each storage node includes a plurality of partitions, the method comprising:

identifying, by a device, first partitions of a plurality of first storage nodes that store backup data of a first faulty storage node based on routing table information, wherein at least two partitions in the cluster store backup data for each partition of the first faulty storage node

and wherein each first partition stores backup data for a corresponding partition of the first faulty storage node;

generating, by the device, one or more first data migration tasks for migrating backup data from the first partitions of the plurality of first storage nodes to second partitions of a plurality of second storage nodes;

identifying, by the device, a second faulty storage node and that the second faulty storage node is one of the first or second storage nodes in the one or more first data migration tasks;

when the second faulty storage node is one of the first storage nodes in the one or more first data migration tasks, identifying a third partition of a third storage node which stores backup data for a first partition of the first faulty storage node, updating the one or more first data migration tasks by replacing a second partition of the second faulty storage node with the third partition of the third storage node;

when the second faulty storage node is one of the second storage nodes in the one or more first data migration tasks, identifying one or more fourth storage nodes to store backup data for one or more partitions of the first faulty storage node, updating the one or more first data migration tasks by replacing the second faulty storage node with the one or more fourth storage nodes; and

executing, by the device, the updated one or more first data migration tasks.

2. The method according to claim 1, further comprising:

obtaining status information of the storage nodes in the cluster;

adjusting a number of partitions according to the status information of the storage nodes in the cluster to obtain a partition adjustment result; and

updating original routing table information according to the partition adjustment result to obtain the routing table information.

3. The method according to claim 1, further comprising:

generating, by the device, one or more second data migration tasks for migrating backup data of the second faulty storage node from partitions of a plurality of fifth storage nodes to partitions of a plurality of sixth storage nodes, wherein the fifth storage nodes store the backup data of the second faulty storage node; and

combining the updated one or more first data migration tasks and the second data migration tasks.

4. The method according to claim 3, wherein the combining the updated one or more first data migration tasks and the second data migration tasks comprises:

adding the second data migration tasks to a migration task queue to which the updated one or more first data migration tasks belong; and

executing tasks in the migration task queue substantially in parallel.

5. The method according to claim 2, wherein when status information of the second storage node is not received within a predetermined time period, determining, by the device, that the second storage node is a faulty storage node.

6. The method of claim 1, further comprising:

executing, by the device, the updated one or more first data migration tasks substantially in parallel to reconstruct the first faulty storage node.

7. The method of claim 2, further comprising:

determining a data migration list based on the original routing table information and the routing table information; and

obtaining the second partitions of the plurality of second storage nodes based on the data migration list.

8. A device comprising:

a memory storage comprising instructions; and

one or more processors in communication with the memory,

wherein the one or more processors execute the instructions to;

identify first partitions of a plurality of first storage nodes that store backup data of a first faulty storage node based on routing table information, wherein at least two partitions in a cluster store backup data for each partition of the first faulty storage node

and wherein each first partition stores backup data for a corresponding partition of the first faulty storage node;

generate one or more first data migration tasks for migrating backup data from the first partitions of the plurality of first storage nodes to second partitions of a plurality of second storage nodes;

identify a second faulty storage node and that the second faulty storage node is one of the first or second storage nodes in the one or more first data migration tasks;

when the second faulty storage node is one of the first storage nodes in the one or more first data migration tasks, identify a third partition of a third storage node which stores backup data for a first partition of the first faulty storage node, update the one or more first data migration tasks by replacing a second partition of the second faulty storage node with the third partition of the third storage node;

when the second faulty storage node is one of the second storage nodes in the one or more first data migration tasks, identify one or more fourth storage nodes to store backup data for one or more partitions of the first faulty storage node, update the one or more first data migration tasks by replacing the second faulty storage node with the one or more fourth storage nodes; and

execute the updated one or more first data migration tasks.

9. The device according to claim 8, wherein the processors execute instructions to:

obtain status information of the storage nodes in the cluster;

adjust a number of partitions according to the status information of the storage nodes in the cluster to obtain a partition adjustment result; and

update original routing table information according to the partition adjustment result to obtain the routing table information.

10. The device according to claim 8, wherein the processors execute instructions to:

generate one or more second data migration tasks for migrating backup data of the second faulty storage node from partitions of a plurality of fifth storage nodes to partitions of a plurality of sixth storage nodes, wherein the fifth storage nodes store the backup data of the second faulty storage node; and

combine the updated one or more first data migration tasks and the second data migration tasks.

11. The device according to claim 10, wherein the processors execute instructions to:

add the second data migration tasks to a migration task queue to which the updated one or more first data migration tasks belong; and

execute tasks in the migration task queue substantially in parallel.

12. The device according to claim 9, wherein the processors execute instructions to:

determine a data migration list based on the original routing table information and the routing table information; and

obtain the second partitions of the plurality of second storage nodes based on the data migration list.

13. A non-transitory computer-readable storage medium storing instructions that, when executed by one or more processors, cause the one or more processors to perform operations including:

identifying first partitions of a plurality of first storage nodes that store backup data of a first faulty storage node based on routing table information, wherein at least two partitions in a cluster store backup data for each partition of the first faulty storage node

and wherein each first partition stores backup data for a corresponding partition of the first faulty storage node;

generating one or more first data migration tasks for migrating backup data from the first partitions of the plurality of first storage nodes to second partitions of a plurality of second storage nodes;

identifying a second faulty storage node and that the second faulty storage node is one of the first or second storage nodes in the one or more first data migration tasks;

when the second faulty storage node is one of the first storage nodes in the one or more first data migration tasks, identifying a third partition of a third storage node which stores backup data for a first partition of the first faulty storage node, updating the one or more first data migration tasks by replacing a second partition of the second faulty storage node with the third partition of the third storage node;

when the second faulty storage node is one of the second storage nodes in the one or more first data migration tasks, identifying one or more fourth storage nodes to store backup data for one or more partitions of the first faulty storage node, updating the one or more first data migration tasks by replacing the second faulty storage node with the one or more fourth storage nodes; and

executing, by the device, the updated one or more first data migration tasks.

14. The non-transitory computer-readable medium according to claim 13, wherein the operations include:

obtaining status information of storage nodes in the cluster;

adjusting a number of partitions according to the status information of the storage nodes in the cluster to obtain a partition adjustment result; and

updating original routing table information according to the partition adjustment result to obtain the routing table information.

15. The non-transitory computer-readable medium according to claim 13, wherein the operations include:

generating one or more second data migration tasks for migrating backup data of the second faulty storage node from partitions of a plurality of fifth storage nodes to partitions of a plurality of sixth storage nodes, wherein the third storage nodes store the backup data of the second faulty storage node; and

combining the updated one or more first data migration tasks and the second data migration tasks.

16. The non-transitory computer-readable medium according to claim 15, wherein the operations include:

adding the second data migration tasks to a migration task queue to which the updated one or more first data migration tasks belong; and

executing tasks in the migration task queue substantially in parallel.

17. The non-transitory computer-readable medium according to claim 14, wherein the processors execute instructions to:

determine a data migration list based on the original routing table information and the routing table information; and

obtain the second partitions of the plurality of second storage nodes based on the data migration list.