Spare selection in a declustered RAID system

Patent metadata

Field	Value
Publication number	US-9690660-B1
Application number	US-201514729714-A
Country	US
Kind code	B1
Filing date	Jun 3, 2015
Priority date	Jun 3, 2015
Publication date	Jun 27, 2017
Grant date	Jun 27, 2017

Abstract

Embodiments are directed to techniques for techniques for selecting a proper set of spare sections to use in a given failure scenario. These embodiments use a set of rules to define which spare sections are eligible to serve as spares for reconstruction of the RAID members on a disk that had failed. In addition, the set of rules may include weighted rules to allow optimization in the spare selection process.

First claim

What is claimed is:

1. A method, performed by a data storage device, of recovering from a failure of a disk within a declustered RAID arrangement, the declustered RAID arrangement including N disks, each disk having a plurality of splits, the declustered RAID arrangement having a plurality of RAID groups, each RAID group distributed over a plurality less than N of members on distinct splits on distinct disks of the N disks, N being an integer greater than one, the method comprising:
receiving an indication that the disk has failed, the failed disk storing a set of members of various RAID groups of the plurality of RAID groups;
identifying, with reference to a set of hard rules, a set of spare splits eligible to store reconstructed versions of the set of members, each spare split being a split which is currently not a member of any RAID group, resulting in a set of eligible members of the set of members being identified as eligible sources for each respective spare split of the set of spare splits;
searching for an assignment between each member of the set of members and a respective eligible spare split of the set of spare splits; and
upon finding an assignment, reconstructing each member of the various RAID groups stored on the failed disk onto its respective assigned spare split;
wherein searching for the assignment includes applying a set of weighted rules to generate a weighted score for each pair of one spare split and one of its respective eligible sources.

2. The method of claim 1 wherein searching for the assignment further includes:
for each member of the set of members, ranking, with reference to the weighted scores, all spare splits for which that member is an eligible source; and
recursively searching for the assignment by attempting to assign higher-ranking spare splits to each respective member of the set of members prior to attempting to assign lower-ranking spare splits to each respective member.

3. The method of claim 1 wherein searching for the assignment further includes:
converting the generated weighted scores to flow capacity scores;
generating a directed graph with nodes representing respective members of the set of members and the eligible spare splits, the directed graph including an edge from each node representing a member of the set of members to respective nodes representing eligible spare splits for which that member is an eligible source, each edge having a flow capacity defined by a respective converted flow capacity score; and
applying a flow maximization technique to the directed graph.

4. The method of claim 3 wherein:
converting the generated weighted scores to flow capacity scores includes:
inverting the generated weighted scores;
normalizing the inverted weighted scores to a lowest value of the inverted weighted scores; and
performing integer rounding on the normalized inverted weighted scores; and

applying the flow maximization technique includes applying the Edmonds-Karp technique.

5. The method of claim 3 wherein:
converting the generated weighted scores to flow capacity scores includes inverting the generated weighted scores; and
applying the flow maximization technique includes applying the Ford-Fulkerson technique.

6. The method of claim 1 wherein searching for the assignment further includes selecting between members of a set of search techniques based on available time and processing resources, the set of search techniques including:
a recursive search technique;
a flow maximization technique utilizing integer flow capacity values in a directed graph; and
a flow maximization technique utilizing non-integer flow capacity values in a directed graph.

7. A method, performed by a data storage device, of recovering from a failure of a disk within a declustered RAID arrangement, the declustered RAID arrangement including N disks, each disk having a plurality of splits, the declustered RAID arrangement having a plurality of RAID groups, each RAID group distributed over a plurality less than N of members on distinct splits on distinct disks of the N disks, N being an integer greater than one, the method comprising:
receiving an indication that the disk has failed, the failed disk storing a set of members of various RAID groups of the plurality of RAID groups;
identifying, with reference to a set of hard rules, a set of spare splits eligible to store reconstructed versions of the set of members, each spare split being a split which is currently not a member of any RAID group, resulting in a set of eligible members of the set of members being identified as eligible sources for each respective spare split of the set of spare splits;
searching for an assignment between each member of the set of members and a respective eligible spare split of the set of spare splits; and
upon finding an assignment, reconstructing each member of the various RAID groups stored on the failed disk onto its respective assigned spare split;
wherein searching for the assignment includes:
generating a directed graph with nodes representing respective members of the set of members and the eligible spare splits, the directed graph including an edge from each node representing a member of the set of members to respective nodes representing eligible spare splits for which that member is an eligible source, each edge having an equal integer flow capacity; and
applying the Edmonds-Karp technique to the directed graph.

8. A method, performed by a data storage device, of recovering from a failure of a disk within a declustered RAID arrangement, the declustered RAID arrangement including N disks, each disk having a plurality of splits, the declustered RAID arrangement having a plurality of RAID groups, each RAID group distributed over a plurality less than N of members on distinct splits on distinct disks of the N disks, N being an integer greater than one, the method comprising:
receiving an indication that the disk has failed, the failed disk storing a set of members of various RAID groups of the plurality of RAID groups;
identifying, with reference to a set of hard rules, a set of spare splits eligible to store reconstructed versions of the set of members, each spare split being a split which is currently not a member of any RAID group, resulting in a set of eligible members of the set of members being identified as eligible sources for each respective spare split of the set of spare splits;
searching for an assignment between each member of the set of members and a respective eligible spare split of the set of spare splits;
upon finding an assignment, reconstructing each member of the various RAID groups stored on the failed disk onto its respective assigned spare split; and
upon not finding an assignment:
softening one or more hard rules of the set of hard rules by removing a limit from each of the one or more hard rules, forming a softened set of hard rules;
re-identifying, with reference to the softened set of hard rules, a new set of spare splits eligible to store reconstructed versions of the set of members, each new spare split being a split which is currently not a member of any RAID group, resulting in a new set of eligible members of the set of members being identified as now eligible sources for each respective new spare split of the set of spare splits; and
re-searching for an assignment between each member of the set of members and a respective eligible spare split of the new set of spare splits.

9. The method of claim 8 wherein softening the one or more hard rules of the set of hard rules includes softening the one or more hard rules of the set of hard rules in order of a pre-defined hierarchy.

10. The method of claim 8 wherein re-searching for the

Assignees

• Emc Corp
• Emc Ip Holding Co Llc

Inventors

• Robins Edward S
• Malkevich Evgeny

Classifications

• G06F11/1076

  Parity data used in redundant arrays of independent storages, e.g. in RAID systems · CPC title

• G06F11/1088 Primary

  Reconstruction on already foreseen single or plurality of spare disks · CPC title

• G06F16/24578

  using ranking · CPC title

• G06F17/3053

  Physics · mapped topic