Granted Patent B1

US 11,137,945 · App. 16/844,076 · Granted Oct 5, 2021

Inventors: Vamsi K. Vankamamidi (Hopkinton, MA); Philippe Armangau (Acton, MA); Ashok Tamilarasan (Shrewsbury, MA); Geng Han (Beijing, CN)

Assignee: EMC IP Holding Company LLC

G06F3/0659G06F3/0604G06F3/0631G06F3/0689G06F12/10G06F2212/1044

Abstract

Claims (44)

1. A method comprising:

providing a logical unit of non-volatile data storage for persistently storing metadata by allocating RAID (Redundant Array of Independent Disks) extents to the logical unit and allocating logical block addresses for the logical unit from within a logical address space of the logical unit to store blocks of metadata written to the logical unit; and

in response to detecting that a stored indication of a last allocated logical block address for the logical unit has been lost:

determining two RAID extents that were last allocated to the logical unit, and

performing a binary search across logical block addresses within the two RAID extents that were last allocated to the logical unit to locate the last allocated logical block address for the logical unit within the logical address space of the logical unit.

2. The method of claim 1 , wherein the two RAID extents that were last allocated to the logical unit comprise a second to last RAID extent allocated to the logical unit and a last RAID extent allocated to the logical unit, and wherein performing the binary search across the logical block addresses within the two RAID extents that were last allocated to the logical unit comprises:

initially setting a lower bound to a lowest logical block address within the second to last RAID extent allocated to the logical unit;

initially setting an upper bound to a highest logical block address within the last RAID extent allocated to the logical unit; and

performing the binary search on logical block addresses across a range of logical block addresses extending from the lower bound to the upper bound.

3. The method of claim 2 , wherein performing the binary search on the logical block addresses across the range of logical block addresses extending from the lower bound to the upper bound includes detecting whether individual logical block addresses in the range of logical block addresses extending from the lower bound to the upper bound have been used to persistently store metadata.

4. The method of claim 3 , wherein detecting whether individual logical block addresses in the range of logical block addresses extending from the lower bound to the upper bound have previously been used to store metadata includes performing read operations directed to individual logical block addresses in the range of logical block addresses to determine whether data returned in response to the read operations includes an indication of valid previously stored metadata.

5. The method of claim 4 , wherein the logical unit is used to store metadata generated by at least one process executing in a storage processor of a data storage system;

wherein the process executing in the data storage system stores an identifier corresponding to the process in each block of metadata that is stored by the process into the logical unit; and

wherein detecting whether individual logical block addresses in the range of logical block addresses extending from the lower bound to the upper bound have previously been used to store metadata includes performing read operations directed to individual logical block addresses in the range of logical block addresses to determine whether data returned in response to the read operations includes the identifier corresponding to the process executing in the data storage system.

6. The method of claim 1 , wherein determining the two RAID extents that were last allocated to the logical unit comprises:

determining a total capacity of RAID extents previously allocated to the logical unit;

determining a total number of RAID extents allocated to the logical unit by dividing the total capacity of RAID extents previously allocated to the logical unit by a RAID extent size; and

determining the two RAID extents that were last allocated to the logical unit based on the total number of RAID extents allocated to the logical unit.

7. A data storage system comprising:

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

a plurality of non-volatile data storage 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:

provide a logical unit of non-volatile data storage for persistently storing metadata by allocating RAID (Redundant Array of Independent Disks) extents to the logical unit and allocating logical block addresses for the logical unit from within a logical address space of the logical unit to store blocks of metadata written to the logical unit; and

in response to detecting that a stored indication of a last allocated logical block address for the logical unit has been lost:

determine two RAID extents that were last allocated to the logical unit, and

perform a binary search across logical block addresses within the two RAID extents that were last allocated to the logical unit to locate the last allocated logical block address for the logical unit within the logical address space of the logical unit.

8. The data storage system of claim 7 , wherein the two RAID extents that were last allocated to the logical unit comprise a second to last RAID extent allocated to the logical unit and a last RAID extent allocated to the logical unit, and wherein the program code, when executed by the processing circuitry, causes the processing circuitry to perform the binary search across the logical block addresses within the two RAID extents that were last allocated to the logical unit at least in part by causing the processing circuitry to:

initially set a lower bound to a lowest logical block address within the second to last RAID extent allocated to the logical unit;

initially set an upper bound to a highest logical block address within the last RAID extent allocated to the logical unit; and

perform the binary search on logical block addresses across a range of logical block addresses extending from the lower bound to the upper bound.

9. The data storage system of claim 8 , wherein the program code, when executed by the processing circuitry, causes the processing circuitry to perform the binary search on the logical block addresses across the range of logical block addresses extending from the lower bound to the upper bound at least in part by causing the processing circuitry to detect whether individual logical block addresses in the range of logical block addresses extending from the lower bound to the upper bound have been used to persistently store metadata.

10. The data storage system of claim 9 , wherein the program code, when executed by the processing circuitry, causes the processing circuitry to detect whether individual logical block addresses in the range of logical block addresses extending from the lower bound to the upper bound have previously been used to store metadata at least in part by causing the processing circuitry to perform read operations directed to individual logical block addresses in the range of logical block addresses to determine whether data returned in response to the read operations includes an indication of valid previously stored metadata.

11. The data storage system of claim 10 , wherein the logical unit is used to store metadata generated by at least one process executing in a storage processor of a data storage system;

wherein the process executing in the data storage system stores an identifier corresponding to the process in each block of metadata that is stored by the process into the logical unit; and

wherein the program code, when executed by the processing circuitry, causes the processing circuitry to detect whether individual logical block addresses in the range of logical block addresses extending from the lower bound to the upper bound have previously been used to store metadata at least in part by causing the processing circuitry to perform read operations directed to individual logical block addresses in the range of logical block addresses to determine whether data returned in response to the read operations includes the identifier corresponding to the process executing in the data storage system.

12. The data storage system of claim 7 , wherein the program code, when executed by the processing circuitry, causes the processing circuitry to determine the two RAID extents that were last allocated to the logical unit at least in part by causing the processing circuitry to:

determine a total capacity of RAID extents previously allocated to the logical unit;

determine a total number of RAID extents allocated to the logical unit by dividing the total capacity of RAID extents previously allocated to the logical unit by a RAID extent size; and

determine the two RAID extents that were last allocated to the logical unit based on the total number of RAID extents allocated to the logical unit.

13. A computer program product including a non-transitory computer readable medium having instructions stored thereon, wherein the instructions, when executed on processing circuitry, cause the processing circuitry to perform the steps of:

providing a logical unit of non-volatile data storage for persistently storing metadata by allocating RAID (Redundant Array of Independent Disks) extents to the logical unit and allocating logical block addresses for the logical unit from within a logical address space of the logical unit to store blocks of metadata written to the logical unit; and

in response to detecting that a stored indication of a last allocated logical block address for the logical unit has been lost:

determining two RAID extents that were last allocated to the logical unit, and

performing a binary search across logical block addresses within the two RAID extents that were last allocated to the logical unit to locate the last allocated logical block address for the logical unit within the logical address space of the logical unit.

Assignments (9)