Mapped RAID (redundant array of independent disks) in a data storage system with drive extents allocated to individual RAID extents from individual sub-groups of storage made up of ranges of logical block addresses defined across a group of hard disk drives

• US 10,146,447 B1
• Filed: 07/28/2017
• Issued: 12/04/2018
• Est. Priority Date: 07/28/2017
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Dong, Jibing, Gao, Jian, Wahl, Michael, Han, Geng, Xu, Xinlei, Kang, Jamin
• Primary Examiner(s): YU, JAE UN
• Application Number:
  US15/662,720
• Time in Patent Office: 494 Days
• Field of Search: 711114
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 12/00 Accessing, addressing or allocating within memory systems or architectures digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/0665 at area level, e.g. provisioning of virtual or logical volumes
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

Technology is provided within a mapped RAID (Redundant Array of Independent Disks) system for creating multiple storage sub-groups in a group of disk drives. Each one of the storage sub-groups contains, in each one of the hard disk drives in the group of hard disk drives, a contiguous set of blocks of storage located within a unique range of logical block addresses corresponding to the storage sub-group. Based on the storage sub-groups created by the disclosed technology, a unique corresponding set of drive extents is allocated to each one of the RAID extents in the RAID mapping table, such that all drive extents contained in each one of the sets of drive extents are allocated from within a single one of the storage sub-groups. Drive extents may be allocated such that a low level of variance is maintained within values of a neighborhood matrix for the group of disk drives.

Claims

1. A method of providing RAID (Redundant Array of Independent Disks) data protection for a storage object in a data storage system, wherein the data storage system includes a storage processor and a group of hard disk drives communicably coupled to the storage processor, the method comprising:

generating a RAID mapping table, wherein the RAID mapping table contains a plurality of RAID extents, wherein each RAID extent contained in the RAID mapping table indicates a predetermined number of drive extents that are used to persistently store host data written to the storage object, and wherein each drive extent comprises a contiguous region of non-volatile data storage located on one of the hard disk drives, wherein each one of the RAID extents in the RAID mapping table indicates the same predetermined total number of drive extents;

creating, in the group of hard disk drives, a plurality of storage sub-groups, wherein each one of the storage sub-groups contains, in each one of the hard disk drives in the group of hard disk drives, a contiguous set of blocks of storage located within a unique range of logical block addresses corresponding to the storage sub-group; and

allocating, to each one of the RAID extents in the RAID mapping table, and based on the created storage sub-groups, a unique corresponding set of drive extents in which all drive extents contained in the set of drive extents are allocated from within a single one of the storage sub-groups, wherein allocating a unique corresponding set of drive extents to each one of the RAID extents in the RAID mapping table includes calculating a RAID mapping table sub-group size, and wherein the value of the RAID mapping table sub-group size has a value that is at least as large as the result of dividing i) a total number of hard disk drives contained in the group of hard disk drives, by ii) the number of drive extents indicated by each one of the RAID extents in the RAID mapping table.

2. The method of claim 1, wherein allocating a unique corresponding set of drive extents to each one of the RAID extents in the RAID mapping table further includes:

dividing the RAID mapping table into a plurality of RAID mapping table sub-groups, wherein each RAID mapping table sub-group is made up of a unique set of consecutively located RAID extents, wherein each set of consecutively located RAID extents comprises a total number of RAID extents equal to the RAID mapping table sub-group size; and

assigning each RAID mapping table sub-group in the RAID mapping table to a corresponding one of the storage sub-groups.

3. The method of claim 2, wherein creating the storage sub-groups includes calculating a storage sub-group size, wherein the storage sub-group size is equal to a multiple of a product of i) the RAID mapping table sub-group size, and ii) the predetermined number of drive extents indicated by each one of the RAID extents in the RAID mapping table;

and

wherein each storage sub-group contains a total number of drive extents that is equal to the storage sub-group size.

4. The method of claim 3, wherein allocating a unique corresponding set of drive extents to each one of the RAID extents in the RAID mapping table includes allocating higher performing drive extents from the group of hard disk drives before allocating lower performing drive extents from the group of hard disk drives by allocating drive extents from storage sub-groups having lower corresponding ranges of logical block addresses before allocating drive extents from storage sub-groups having higher corresponding ranges of logical block addresses.

5. The method of claim 4, wherein allocating a unique corresponding set of drive extents to each one of the RAID extents in the RAID mapping table includes allocating all drive extents such that for each RAID mapping table sub-group no drive extent is allocated to any RAID extent contained in the RAID mapping table sub-group that is located on the same hard disk drive as any other drive extent allocated to any other RAID extent contained in the RAID mapping table sub-group.

6. The method of claim 5, wherein allocating a unique corresponding set of drive extents to each one of the RAID extents in the RAID mapping table includes:

generating a neighborhood matrix for the group of hard disk drives, wherein each element in the neighborhood matrix for the group of hard disk drives corresponds to a pair of drives contained in the group of hard disk drives and stores a value equal to a total number of RAID extents in the RAID mapping table that indicate both i) at least one drive extent located on a first one of the drives in the pair of drives corresponding to the element, and ii) at least one drive extent located on a second one of the drives in the pair of drives corresponding to the element; and

,

allocating each drive extent contained in the set of drive extents by;

i) generating a list of candidate drives contained in the group of hard disk drives, wherein each one of the candidate drives has located thereon at least one free drive extent,

ii) assigning, to each one of the candidate drives, a variance weighting that is equal to a variance of the values of the elements in the neighborhood matrix for the group of hard disk drives resulting from modifying the neighborhood matrix to indicate that the drive extent was allocated from the candidate drive,

iii) selecting one of the candidate drives having a lowest assigned variance weighting, and

iv) allocating the drive extent from the candidate drive having the lowest assigned variance weighting.

7. The method of claim 6, wherein drive extents are allocated to RAID extents in the RAID mapping table such that no two drive extents indicated by any single RAID extent are located on the same hard disk drive.

8. A data storage system that provides RAID (Redundant Array of Independent Disks) data protection for a storage object, comprising:

at least one storage processor including processing circuitry and a memory;

a set of hard disk drives communicably coupled to the storage processor; and

wherein the memory has program code stored thereon, wherein the program code, when executed by the processing circuitry, causes the processing circuitry to;

generate a RAID mapping table in the memory, wherein the RAID mapping table contains a plurality of RAID extents, wherein each RAID extent contained in the RAID mapping table indicates a predetermined number of drive extents that are used to persistently store host data written to the storage object, wherein each drive extent comprises a contiguous region of non-volatile data storage located on one of the hard disk drives, and wherein each one of the RAID extents in the RAID mapping table indicates the same predetermined total number of drive extents,

create, in the group of hard disk drives, a plurality of storage sub-groups, wherein each one of the storage sub-groups contains, in each one of the hard disk drives in the group of hard disk drives, a contiguous set of blocks of storage located within a unique range of logical block addresses corresponding to the storage sub-group, and

allocate, to each one of the RAID extents in the RAID mapping table, and based on the created storage sub-groups, a unique corresponding set of drive extents in which all drive extents contained in the set of drive extents are allocated from within a single one of the storage sub-groups, at least in part by causing the processing circuitry to calculate a RAID mapping table sub-group size, wherein the value of the RAID mapping table sub-group size has a value that is at least as large as the result of dividing i) a total number of hard disk drives contained in the group of hard disk drives, by ii) the number of drive extents indicated by each one of the RAID extents in the RAID mapping table.

9. The data storage system of claim 8, wherein the program code, when executed by the processing circuitry, causes the processing circuitry to allocate a unique corresponding set of drive extents to each one of the RAID extents in the RAID mapping table at least in part by causing the processing circuitry to:

divide the RAID mapping table into a plurality of RAID mapping table sub-groups, wherein each RAID mapping table sub-group is made up of a unique set of consecutively located RAID extents, wherein each set of consecutively located RAID extents comprises a total number of RAID extents equal to the RAID mapping table sub-group size; and

assign each RAID mapping table sub-group in the RAID mapping table to a corresponding one of the storage sub-groups.

10. The data storage system of claim 9, wherein the program, when executed by the processing circuitry, causes the processing circuitry to create the storage sub-groups at least in part by causing the processing circuitry to calculate a storage sub-group size, wherein the storage sub-group size is equal to a multiple of a product of i) the RAID mapping table sub-group size, and ii) the predetermined number of drive extents indicated by each one of the RAID extents in the RAID mapping table;

and

wherein each storage sub-group contains a total number of drive extents that is equal to the storage sub-group size.

11. The data storage system of claim 10, wherein the program code, when executed by the processing circuitry, causes the processing circuitry to allocate a unique corresponding set of drive extents to each one of the RAID extents in the RAID mapping table at least in part by causing the processing circuitry to allocate higher performing drive extents from the group of hard disk drives before lower performing drive extents are allocated from the group of hard disk drives by causing the processing circuitry to allocate drive extents from storage sub-groups having lower corresponding ranges of logical block addresses before drive extents are allocated from storage sub-groups having higher corresponding ranges of logical block addresses.

12. The data storage system of claim 11, wherein the program code, when executed by the processing circuitry, causes the processing circuitry to allocate a unique corresponding set of drive extents to each one of the RAID extents in the RAID mapping table at least in part by causing the processing circuitry to allocate all drive extents such that for each RAID mapping table sub-group no drive extent is allocated to any RAID extent contained in the RAID mapping table sub-group that is located on the same hard disk drive as any other drive extent allocated to any other RAID extent contained in the RAID mapping table sub-group.

13. The data storage system of claim 12, wherein the program code, when executed by the processing circuitry, causes the processing circuitry to allocate a unique corresponding set of drive extents to each one of the RAID extents in the RAID mapping table at least in part by causing the processing circuitry to:

generate a neighborhood matrix for the group of hard disk drives, wherein each element in the neighborhood matrix for the group of hard disk drives corresponds to a pair of drives contained in the group of hard disk drives and stores a value equal to a total number of RAID extents in the RAID mapping table that indicate both i) at least one drive extent located on a first one of the drives in the pair of drives corresponding to the element, and ii) at least one drive extent located on a second one of the drives in the pair of drives corresponding to the element; and

,

allocate each drive extent contained in the set of drive extents by causing the processing circuitry to;

i) generate a list of candidate drives contained in the group of hard disk drives, wherein each one of the candidate drives has located thereon at least one free drive extent,

ii) assign, to each one of the candidate drives, a variance weighting that is equal to a variance of the values of the elements in the neighborhood matrix for the group of hard disk drives resulting from modifying the neighborhood matrix to indicate that the drive extent was allocated from the candidate drive,

iii) select one of the candidate drives having a lowest assigned variance weighting, and

iv) allocate the drive extent from the candidate drive having the lowest assigned variance weighting.

14. The data storage system of claim 13, wherein drive extents are allocated to RAID extents in the RAID mapping table such that no two drive extents indicated by any single RAID extent are located on the same hard disk drive.

15. A non-transitory computer readable medium for providing RAID (Redundant Array of Independent Disks) data protection for a storage object, comprising instructions stored thereon, that when executed on processing circuitry in a storage processor, perform the steps of:

generating a RAID mapping table, wherein the RAID mapping table contains a plurality of RAID extents, wherein each RAID extent contained in the RAID mapping table indicates a predetermined number of drive extents that are used to persistently store host data written to the storage object, and wherein each drive extent comprises a contiguous region of non-volatile data storage located on one of the hard disk drives, wherein each one of the RAID extents in the RAID mapping table indicates the same predetermined total number of drive extents;

creating, in the group of hard disk drives, a plurality of storage sub-groups, wherein each one of the storage sub-groups contains, in each one of the hard disk drives in the group of hard disk drives, a contiguous set of blocks of storage located within a unique range of logical block addresses corresponding to the storage sub-group; and

allocating, to each one of the RAID extents in the RAID mapping table, and based on the created storage sub-groups, a unique corresponding set of drive extents in which all drive extents contained in the set of drive extents are allocated from within a single one of the storage sub-groups, wherein allocating a unique corresponding set of drive extents to each one of the RAID extents in the RAID mapping table includes calculating a RAID mapping table sub-group size, and wherein the value of the RAID mapping table sub-group size has a value that is at least as large as the result of dividing i) a total number of hard disk drives contained in the group of hard disk drives, by ii) the number of drive extents indicated by each one of the RAID extents in the RAID mapping table.