# US 10,310,752 B1 · Extent selection with mapped raid > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,310,752 B1 - Document ID: US10310752B1 - Status: Granted - Kind: B1 - Application number: 15/395,132 - Filed: 2016-12-30 - Granted: 2019-06-04 - Earliest claimed: 2016-12-30 - Assignees: EMC IP Holding Company LLC - Applicants: EMC IP Holding Company LLC - Inventors: Wayne Li; Geng Han; Jian Gao; Jibing Dong; Jianbin Kang; Lili Chen - Web page: https://patentgrep.com/patent/US10310752B1 ## CPC - G06F 3/061: {Improving I/O performance} - G06F 3/0619: {in relation to data integrity, e.g. data losses, bit errors} - G06F 3/0631: {by allocating resources to storage systems} - G06F 3/0665: {at area level, e.g. provisioning of virtual or logical volumes} - G06F 3/0689: {Disk arrays, e.g. RAID, JBOD} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## 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. ## Claims ### Claim 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. ### Claim 2 (depends on 1) 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. ### Claim 3 (depends on 1) 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. ### Claim 4 (depends on 1) 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. ### Claim 5 (depends on 4) 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. ### Claim 6 (depends on 5) 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. ### Claim 7 (depends on 6) 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. ### Claim 8 (depends on 6) 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. ### Claim 9 (depends on 8) The method of claim 8, wherein the selected subset covers all N physical storage devices of the pool. ### Claim 10 (depends on 1) 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. ### Claim 11 (depends on 1) 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. ### Claim 12 (depends on 11) 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. ### Claim 13 (depends on 11) 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. ### Claim 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. ### Claim 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. ### Claim 16 (depends on 15) 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. ### Claim 17 (depends on 16) 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. ### Claim 18 (depends on 17) 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.