Extent selection with mapped raid

Patent metadata

Field	Value
Publication number	US-10310752-B1
Application number	US-201615395132-A
Country	US
Kind code	B1
Filing date	Dec 30, 2016
Priority date	Dec 30, 2016
Publication date	Jun 4, 2019
Grant date	Jun 4, 2019

Abstract

Techniques for allocating mapped RAID extents of a RAID group may include: determining a pool of N physical storage devices; selecting M physical storage portions, wherein each of the M physical storage portions is selected from a different one of the N physical storage devices of the pool; and allocating a first mapped RAID extent as the selected M physical storage portions. The first mapped RAID extent may denotes a stripe of the RAID group. Physical storage portions for each mapped RAID extent may be selected from the N physical storage devices with a goal of maintaining even distribution of the selected portions among the N physical storage devices. Such selection may use a neighborhood matrix and a subset of all possible combinations of M physical storage devices that may be selected from the N physical storage devices.

First claim

What is claimed is:

1. A method of allocating one or more mapped RAID extents comprising:
determining a pool of N physical storage devices;
selecting M physical storage portions, wherein each of the M physical storage portions is selected from a different one of the N physical storage devices of the pool, wherein said selecting is performed in accordance with a neighborhood matrix denoting a distribution of neighboring physical storage portions across the N physical storage devices of the pool; and
allocating a first mapped RAID extent as the selected M physical storage portions, wherein the first mapped RAID extent denotes a stripe of a RAID group.

2. The method of claim 1 , wherein a first portion of the M physical storage portions of the stripe store user data for the stripe and remaining ones of the M physical storage portions of the stripe, not included in the first portion, store parity information for the stripe.

3. The method of claim 1 , wherein N denotes a first integer value that is equal to or greater than a second integer value denoted by M.

4. The method of claim 1 , wherein the neighborhood matrix includes N rows and N columns and wherein each entry (I, J) of the neighborhood matrix located at row I, column J denotes a count of how many times physical storage device I of the pool has neighbored physical storage device J of the pool.

5. The method of claim 4 , wherein the two physical storage devices I and J of the pool are neighbors with each other each time a first physical storage portion from physical storage device I and a second physical storage portion from physical storage device J are included in a same mapped RAID extent that is allocated.

6. The method of claim 5 , wherein the M physical storage portions on M different ones of the N physical storage devices is a first combination, and wherein said selecting selects the first combination from a plurality of combinations using the neighborhood matrix.

7. The method of claim 6 , wherein said selecting uses the neighborhood matrix to evaluate whether the first combination results in a first variance that is a minimum variance with respect to other variances resulting from selection of any other combination of the plurality of combinations, wherein the first variance and the other variances are with respect to values stored in the entries of the neighborhood matrix.

8. The method of claim 6 , wherein the plurality of combinations is a selected subset of all possible combinations of selecting M physical storage devices from the N physical storage devices.

9. The method of claim 8 , wherein the selected subset covers all N physical storage devices of the pool.

10. The method of claim 1 , wherein a first physical storage device of the N physical storage devices fails and a group X of remaining ones of the N physical storage devices of the pool that have not failed, and the method includes:
determining a first set of one or more physical storage portions of the first mapped RAID extent stored on the first physical storage device that failed; and
relocating each physical storage portion of the first set to a physical storage device of the group X, wherein said relocating is performed in accordance with criteria, said criteria including each physical storage portion of the first mapped RAID extent is stored on a different physical storage device of the group X and said criteria including evenly distributing the first set of one or more physical storage portions among the physical storage devices of group X.

11. The method of claim 1 , wherein the one or more mapped RAID extents include a plurality of mapped RAID extents that are stripes of the RAID group and the plurality of mapped RAID extents include the first mapped RAID extent, and wherein each stripe of the RAID group includes M physical storage portions comprising X, one or more physical storage portions storing user data for said each stripe and Y, one or more physical storage portions storing parity information for said each stripe.

12. The method of claim 11 , wherein the RAID group has a RAID-5 configuration and wherein Y denotes a single physical storage portion storing parity information for said each stripe.

13. The method of claim 11 , wherein the RAID group has a RAID-6 configuration and wherein Y denotes two physical storage portions storing parity information for said each stripe.

14. A system comprising:
at least one processor; and
a memory comprising code stored thereon that, when executed, performs a method of allocating one or more mapped RAID extents comprising:
determining a pool of N physical storage devices;
selecting M physical storage portions, wherein each of the M physical storage portions is selected from a different one of the N physical storage devices of the pool, wherein said selecting is performed in accordance with a neighborhood matrix denoting a distribution of neighboring physical storage portions across the N physical storage devices of the pool; and
allocating a first mapped RAID extent as the selected M physical storage portions, wherein the first mapped RAID extent denotes a stripe of a RAID group.

15. A computer readable medium comprising code stored thereon that, when executed, performs a method of allocating one or more mapped RAID extents comprising:
determining a pool of N physical storage devices;
selecting M physical storage portions, wherein each of the M physical storage portions is selected from a different one of the N physical storage devices of the pool, wherein said selecting is performed in accordance with a neighborhood matrix denoting a distribution of neighboring physical storage portions across the N physical storage devices of the pool; and
allocating a first mapped RAID extent as the selected M physical storage portions, wherein the first mapped RAID extent denotes a stripe of a RAID group.

16. The computer readable medium of claim 15 , wherein the neighborhood matrix includes N rows and N columns and wherein each entry (I, J) of the neighborhood matrix located at row I, column J denotes a count of how many times physical storage device I of the pool has neighbored physical storage device J of the pool.

17. The computer readable medium of claim 16 , wherein the two physical storage devices I and J of the pool are neighbors with each other each time a first physical storage portion from physical storage device I and a second physical storage portion from physical storage device J are included in a same mapped RAID extent that is allocated.

18. The computer readable medium of claim 17 , wherein the M physical storage portions on M different ones of the N physical storage devices is a first combination, and wherein said selecting selects the first combination from a plurality of combinations using the neighborhood matrix, and wherein said selecting uses the neighborhood matrix to evaluate whether the first combination results in a first variance that is a minimum variance with respect to other variances resulting from selection of any other combination of the plurality of combinations, wherein the first variance and the other variances are with respect to values stored in the entries of the neighborhood matrix.

Assignees

• Emc Ip Holding Co Llc

Inventors

• Li Wayne
• Han Geng
• Gao Jian
• Dong Jibing
• Kang Jianbin
• Chen Lili

Classifications

• G06F3/0665

  at area level, e.g. provisioning of virtual or logical volumes · CPC title

• G06F3/061 Primary

  Improving I/O performance · CPC title

• G06F3/0631

  by allocating resources to storage systems · CPC title

• G06F3/0689

  Disk arrays, e.g. RAID, JBOD · CPC title

• G06F3/0619 Primary

  in relation to data integrity, e.g. data losses, bit errors · CPC title