Mapped RAID (redundant array of independent disks) in a data storage system with RAID extent sub-groups that are used to perform drive extent allocation and data striping for sequential data accesses to a storage object

• US 10,140,041 B1
• Filed: 07/28/2017
• Issued: 11/27/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, Han, Geng, Wahl, Michael, Gao, Jian, Kang, Jamin, Xu, Xinlei
• Primary Examiner(s): Yu, Jae U
• Application Number:
  US15/662,731
• Time in Patent Office: 487 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 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• 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 system that creates multiple RAID extent sub-groups in a RAID mapping table. Each of the RAID extent sub-groups contains a unique set of consecutively located RAID extents within the RAID mapping table, and a unique corresponding set of drive extents is allocated to the RAID extents contained in each one of the RAID extent sub-groups. Drive extents are allocated to each RAID extent sub-group such that no drive extent is allocated to any RAID extent contained in the RAID extent sub-group that is located on the same hard disk drive as any other drive extent allocated to any other RAID extent contained in that RAID extent sub-group. Data striping may be performed based on the RAID extent sub-groups, such that host data is divided into data elements that are striped across the RAID extents contained in one or more individual RAID extent sub-groups.

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 by one or more hosts, and wherein each drive extent comprises a contiguous region of non-volatile data storage located on one of the hard disk drives in the group of hard disk drives;

creating, in the RAID mapping table, a plurality of RAID extent sub-groups, wherein each one of the RAID extent sub-groups contains a unique set of consecutively located RAID extents within the RAID mapping table;

allocating, to the RAID extents contained in each one of the created RAID extent sub-groups, a unique corresponding set of drive extents such that for each RAID extent sub-group no drive extent is allocated to any RAID extent contained in the RAID extent 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 extent sub-group;

receiving a set of sequential data directed to the storage object that spans a sequential range of logical block addresses within a logical address space of the storage object;

dividing the set of data into multiple fixed size data elements;

identifying, within the RAID mapping table, at least one RAID extent sub-group corresponding to the sequential range of logical block addresses within the logical address space of the storage object; and

striping the data elements across the RAID extents contained in the identified RAID extent sub-group by writing consecutive ones of the data elements to sets of drive extents indicated by consecutive ones of the RAID extents contained in the RAID extent sub-group corresponding to the sequential range of logical block addresses of the storage object until all of the data elements have been written.

2. The method of claim 1, wherein each one of the RAID extents in the RAID mapping table indicates the same predetermined total number of drive extents, and further comprising:

calculating a RAID extent sub-group size, wherein the value of the RAID extent sub-group size is at least as large as a result of dividing i) a total number of hard disk drives contained in the group of hard disk drives, by ii) the predetermined total number of drive extents indicated by each one of the RAID extents in the RAID mapping table; and

wherein creating the plurality of RAID extent sub-groups further comprises creating each one of the RAID extent sub-groups to contain a total number of consecutively located RAID extents that is equal to the RAID extent sub-group size.

3. The method of claim 2, wherein allocating drive extents to the RAID extent sub-groups includes allocating consecutive, contiguous drive extents from each hard disk drive, starting from drive extents that extend over lower ranges of logical block addresses of the hard disk drive, and continuing upwards through consecutive, contiguously located drive extents that extend over higher ranges of logical block addresses of the hard disk drive.

4. The method of claim 3, further comprising:

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 hard disk 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 hard disk drives in the pair of hard disk drives corresponding to the element, and ii) at least one drive extent located on a second one of the hard disk drives in the pair of hard disk drives corresponding to the element; and

wherein allocating each one of the drive extents in the unique set of drive extents corresponding to the RAID extents contained in each one of the RAID extent sub-groups includes;

i) generating a list of candidate drives contained in the group of hard disk drives, wherein each candidate drive in the list of candidate drives has located thereon at least one free drive extent and has no drive extent located thereon that was previously allocated to any RAID extent in the RAID extent sub-group,

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 a drive extent from the candidate drive having the lowest assigned variance weighting.

5. The method of claim 4, wherein allocating a unique corresponding set of drive extents to each one of the RAID extent sub-groups further includes:

determining whether any drive extent has previously been allocated to the RAID extent sub-group; and

in response to determining that no drive extent has previously been allocated to the RAID extent sub-group;

i) determining which one of the hard disk drives in the group of hard disk drives that has located thereon a number of free drive extents that is greater than the number of free drive extents located on any other hard disk drive in the group of hard disk drives, and

ii) allocating a drive extent to the RAID extent sub-group from the one of the hard disk drives that has located thereon the number of free drive extents that is greater than the number of free drive extents located on any other hard disk drive in the group of hard disk drives.

6. The method of claim 1, further comprising:

performing a flush operation on a cache located within the data storage system that stores host data received by the data storage system that is directed to the storage object; and

wherein the set of sequential data directed to the storage object that spans a sequential range of logical block addresses within a logical address space of the storage object is received from the cache during the flush operation.

7. 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 group 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, 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 by one or more hosts, and wherein each drive extent comprises a contiguous region of non-volatile data storage located on one of the hard disk drives in the group of hard disk drives,

create, in the RAID mapping table, a plurality of RAID extent sub-groups, wherein each one of the RAID extent sub-groups contains a unique set of consecutively located RAID extents within the RAID mapping table,

allocate, to the RAID extents contained in each one of the created RAID extent sub-groups, a unique corresponding set of drive extents such that for each RAID extent sub-group no drive extent is allocated to any RAID extent contained in the RAID extent 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 extent sub-group,

receive a set of sequential data directed to the storage object that spans a sequential range of logical block addresses within a logical address space of the storage object,

divide the set of sequential data into multiple fixed size data elements,

identify, within the RAID mapping table, at least one RAID extent sub-group corresponding to the sequential range of logical block addresses within the logical address space of the storage object, and

stripe the data elements across the RAID extents contained in the identified RAID extent sub-group by writing consecutive ones of the data elements to sets of drive extents indicated by consecutive ones of the RAID extents contained in the RAID extent sub-group corresponding to the sequential range of logical block addresses of the storage object until all of the data elements have been written.

8. The data storage system of claim 7, wherein each one of the RAID extents in the RAID mapping table indicates the same predetermined total number of drive extents, and wherein the program code, when executed by the processing circuitry, further causes the processing circuitry to:

calculate a RAID extent sub-group size, wherein the value of the RAID extent sub-group size is at least as large as a result of dividing i) a total number of hard disk drives contained in the group of hard disk drives, by ii) the predetermined total number of drive extents indicated by each one of the RAID extents in the RAID mapping table; and

create the plurality of RAID extent sub-groups at least in part by creating each one of the RAID extent sub-groups to contain a total number of consecutively located RAID extents that is equal to the RAID extent sub-group size.

9. The data storage system of claim 8, wherein the program code, when executed by the processing circuitry, further causes the processing circuitry to allocate drive extents to the RAID extent sub-groups at least in part by allocating consecutive, contiguous drive extents from each hard disk drive, starting from drive extents that extend over lower ranges of logical block addresses of the hard disk drive, and continuing upwards through consecutive, contiguously located drive extents that extend over higher ranges of logical block addresses of the hard disk drive.

10. The data storage system of claim 9, wherein the program code, when executed, further causes 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 hard disk 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 hard disk drives in the pair of hard disk drives corresponding to the element, and ii) at least one drive extent located on a second one of the hard disk drives in the pair of hard disk drives corresponding to the element; and

wherein the program code, when executed, in order to cause the processing circuitry to allocate each one of the drive extents in the unique set of drive extents corresponding to the RAID extents contained in each one of the RAID extent sub-groups, further causes the processing circuitry to;

generate a list of candidate drives contained in the group of hard disk drives, wherein each candidate drive in the list of candidate drives has located thereon at least one free drive extent and has no drive extent located thereon that was previously allocated to any RAID extent in the RAID extent sub-group,

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,

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

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

11. The data storage system of claim 10, wherein the program code, when executed, in order to cause the processing circuitry to allocate a unique corresponding set of drive extents to each one of the RAID extent sub-groups, further causes the processing circuitry to:

determine whether any drive extent has previously been allocated to the RAID extent sub-group; and

in response to a determination that no drive extent has previously been allocated to the RAID extent sub-group;

i) determine which one of the hard disk drives in the group of hard disk drives that has located thereon a number of free drive extents that is greater than the number of free drive extents located on any other hard disk drive in the group of hard disk drives, and

ii) allocate a drive extent to the RAID extent sub-group from the one of the hard disk drives that has located thereon the number of free drive extents that is greater than the number of free drive extents located on any other hard disk drive in the group of hard disk drives.

12. The data storage system of claim 7, further comprising:

a cache located within the data storage system that stores host data received by the data storage system that is directed to the storage object; and

wherein the set of sequential host directed to the storage object that spans the sequential range of logical block addresses of the storage object is received from the cache during a flush operation.

13. 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 a storage object by one or more hosts, and wherein each drive extent comprises a contiguous region of non-volatile data storage located a hard disk in a group of hard disk drives;

creating, in the RAID mapping table, a plurality of RAID extent sub-groups, wherein each one of the RAID extent sub-groups contains a unique set of consecutively located RAID extents within the RAID mapping table;

allocating, to the RAID extents contained in each one of the created RAID extent sub-groups, a unique corresponding set of drive extents such that for each RAID extent sub-group no drive extent is allocated to any RAID extent contained in the RAID extent 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 extent sub-group;

receiving a set of sequential data directed to the storage object that spans a sequential range of logical block addresses within a logical address space of the storage object;

dividing the set of data into multiple fixed size data elements;

identifying, within the RAID mapping table, at least one RAID extent sub-group corresponding to the sequential range of logical block addresses within the logical address space of the storage object; and

striping the data elements across the RAID extents contained in the identified RAID extent sub-group by writing consecutive ones of the data elements to sets of drive extents indicated by consecutive ones of the RAID extents contained in the RAID extent sub-group corresponding to the sequential range of logical block addresses of the storage object until all of the data elements have been written.