Systems and methods for selecting a set of storage nodes for use in reconstructing data on a faulted node in an erasure-coded system

• US 10,275,312 B1
• Filed: 03/29/2017
• Issued: 04/30/2019
• Est. Priority Date: 03/29/2017
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Inventors: Barhate, Deodatta, Kolhe, Roshan, Bankar, Pritam
• Primary Examiner(s): Ko, Chae M
• Application Number:
  US15/472,393
• Time in Patent Office: 762 Days
• Field of Search: 714 624
• CPC Class Codes: G06F 11/1088 Reconstruction on already foreseen single or plurality of spare disks
• CPC Class Codes: G06F 11/1612 where the redundant component is persistent storage
• CPC Class Codes: G06F 11/3419 by assessing time
• CPC Class Codes: G06F 11/3485 for I/O devices

Abstract

The disclosed computer-implemented method for selecting a set of storage nodes from a plurality of storage nodes for use in reconstructing data on a faulted node in an erasure-coded system may include determining an average read access latency for a first set of storage nodes, detecting a storage failure a storage node, selecting a subset of the first set of storage nodes, such that the average read access latency for each of the storage nodes within the subset has a lower average read access latency than at least one other node (or as many as all the other nodes) of the available storage nodes, and reconstructing data that was stored on the failed storage node from the subset of the first set of storage nodes. During reconstruction, each of the nodes multiplies their data chunk by a coefficient and transmits the resulting product to an initiator node.

Claims

1. A computer-implemented method for selecting a set of storage nodes from a plurality of storage nodes for use in reconstructing data on a faulted node in an erasure-coded system, at least a portion of the method being performed by a computing device comprising at least one processor, the method comprising:

determining, over a first period of time, an average read access latency for a first set of the plurality of storage nodes in the erasure-coded system;

detecting a storage failure on one of the plurality of storage nodes;

selecting a subset of the first set of storage nodes, wherein the average read access latency for each of the storage nodes within the subset of the first set of storage nodes has a lower average read access latency than at least one other node in the plurality of storage nodes; and

reconstructing data that was stored on the failed storage node, from the subset of the first set of storage nodes.

2. The method according to claim 1, further comprising periodically determining the average read access latency for the first set of the plurality of storage nodes in the system.

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

detecting another storage failure on another of the plurality of storage nodes;

replacing at least one of the selected nodes from the subset of the first set of storage nodes with at least another node from the first set of the plurality of storage nodes to create another subset of storage nodes, wherein the at least another node from the first set of the plurality of storage nodes has a lower average read access latency than the at least one of the selected nodes from the subset of the first set of storage nodes that is replaced; and

reconstructing data that was stored on the another failed storage node from the another subset of storage nodes.

4. The method according to claim 1, wherein the first set of the plurality of storage nodes in the system comprises all of the plurality of storage nodes in the system.

5. The method according to claim 1:

wherein the first set of the plurality of storage nodes in the system comprises less than all of the plurality of storage nodes in the system;

further comprising determining an average read access latency for a second set of the plurality of storage nodes in the system;

wherein at least one node is not common to both the first set of the plurality of storage nodes and the second set of the plurality of storage nodes.

6. The method according to claim 1, wherein each of the nodes within the subset of the first set of storage nodes has a lower average read access latency than a remainder of the nodes in the plurality of storage nodes.

7. The method according to claim 1, wherein the data includes a plurality of chunks of data and reconstructing the data comprises each of the nodes within the subset of the first set of storage nodes respectively multiplying a chunk of data by a coefficient and transmitting the multiplied chunk of data to an initiator node.

8. The method according to claim 7, wherein the initiator node receives the multiplied chunks of data and reconstructs the data by applying an exclusive OR function to the received multiplied chunks of data.

9. A system for selecting a set of storage nodes from a plurality of storage nodes for use in reconstructing data on a faulted node in an erasure-coded system, the system comprising:

a determination module, stored in memory, that determines, over a first period of time, an average read access latency for a first set of the plurality of storage nodes in the erasure-coded system;

a detection module, stored in memory, that detects a storage failure on one of the plurality of storage nodes;

a selection module, stored in memory, that selects a subset of the first set of storage nodes, wherein the average read access latency for each of the storage nodes within the subset of the first set of storage nodes has a lower average read access latency than at least one other node in the plurality of storage nodes; and

a reconstruction module, stored in memory, that reconstructs, data that was stored on the failed storage node, from the subset of the first set of storage nodes; and

at least one physical processor that executes the determination module, the detection module, the selection module, and the reconstruction module.

10. The system according to claim 9, wherein the determination module periodically determines the average read access latency for the first set of the plurality of storage nodes in the system.

11. The system according to claim 10, wherein:

the detection module further detects another storage failure on another of the plurality of storage nodes;

the selection module replaces at least one of the selected nodes from the subset of the first set of storage nodes with at least another node from the first set of the plurality of storage nodes to create another subset of storage nodes, wherein the at least another node from the first set of the plurality of storage nodes has a lower average read access latency than the at least one of the selected nodes from the subset of the first set of storage nodes that is replaced; and

the reconstruction module reconstructs data that was stored on the another failed storage node from the another subset of storage nodes.

12. The system according to claim 10, wherein the first set of the plurality of storage nodes in the system comprises less than all of the plurality of storage nodes in the system;

the determination module determining an average read access latency for a second set of the plurality of storage nodes in the system; and

at least one node is not common to both the first set of the plurality of storage nodes and the second set of the plurality of storage nodes.

13. The system according to claim 10, wherein each of the nodes within the subset of the first set of storage nodes has a lower average read access latency than a remainder of the nodes in the plurality of storage nodes.

14. The system according to claim 10, wherein:

the data includes a plurality of chunks of data;

the reconstruction module causes each of the nodes within the subset of the first set of storage nodes respectively to multiply a chunk of data by a coefficient and transmit the multiplied chunk of data to an initiator node.

15. The system according to claim 14, wherein the reconstruction module causes the initiator node to reconstructs the data by applying an exclusive OR function to the multiplied chunks of data.

16. A non-transitory computer-readable medium comprising one or more computer-executable instructions that, when executed by at least one processor of a computing device, cause the computing device to:

determine, over a first period of time, an average read access latency for a first set of a plurality of storage nodes in an erasure-coded system;

detect a storage failure on one of the plurality of storage nodes;

select a subset of the first set of storage nodes, wherein the average read access latency for each of the storage nodes within the subset of the first set of storage nodes has a lower average read access latency than at least one other node in the plurality of storage nodes; and

reconstruct data that was stored on the failed storage node, from the subset of the first set of storage nodes.

17. The non-transitory computer-readable medium according to claim 16, wherein the one or more computer-executable instructions cause the computing device to periodically determining the average read access latency for the first set of the plurality of storage nodes.

18. The non-transitory computer-readable medium according to claim 17, wherein the one or more computer-executable instructions cause the computing device to:

detect another storage failure on another of the plurality of storage nodes;

replace at least one of the selected nodes from the subset of the first set of storage nodes with at least another node from the first set of the plurality of storage nodes to create another subset of storage nodes, wherein the at least another node from the first set of the plurality of storage nodes has a lower average read access latency than the at least one of the selected nodes from the subset of the first set of storage nodes that is replaced; and

reconstruct data that was stored on the another failed storage node, from the another subset of storage nodes.

19. The non-transitory computer-readable medium according to claim 17, wherein:

the first set of the plurality of storage nodes comprises less than all of the plurality of storage nodes;

the one or more computer-executable instructions cause the computing device to determine an average read access latency for a second set of the plurality of storage nodes; and

at least one node is not common to both the first set of the plurality of storage nodes and the second set of the plurality of storage nodes.

20. The non-transitory computer-readable medium according to claim 17, wherein the data includes a plurality of chunks of data and wherein the one or more computer-executable instructions cause the computing device to cause each of the nodes within the subset of the first set of storage nodes respectively to multiply a chunk of data by a coefficient and transmit the multiplied chunk of data to an initiator node.