Reconstruction of dense tree volume metadata state across crash recovery

• US 9,501,359 B2
• Filed: 09/10/2014
• Issued: 11/22/2016
• Est. Priority Date: 09/10/2014
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Pundir, Anshul, D'Sa, Janice, Krishnamachari, Srinath, Zheng, Ling
• Primary Examiner(s): NGUYEN, CAM LINH T
• Application Number:
  US14/482,618
• Publication Number:
  US 20160070618A1
• Time in Patent Office: 804 Days
• Field of Search: 707/802, 707/806, 707/822
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1088 Reconstruction on already foreseen single or plurality of spare disks
• CPC Class Codes: G06F 11/1438 Restarting or rejuvenating
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 11/2069 Management of state, configuration or failover
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 2201/80 Database-specific techniques
• CPC Class Codes: G06F 2201/805 Real-time
• CPC Class Codes: G06F 2201/82 Solving problems relating to consistency ensuring consistency in mirrored systems G06F11/2064
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: G06F 2211/104 Metadata, i.e. metadata associated with RAID systems with parity
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G06F 7/32 Merging, i.e. combining data contained in ordered sequence on at least two record carriers to produce a single carrier or set of carriers having all the original data in the ordered sequence merging methods in generalG06F7/36 takes precedence

Abstract

Embodiments herein are directed to efficient crash recovery of persistent metadata managed by a volume layer of a storage input/output (I/O) stack executing on one or more nodes of a cluster. Volume metadata managed by the volume layer is organized as a multi-level dense tree, wherein each level of the dense tree includes volume metadata entries for storing the volume metadata. When a level of the dense tree is full, the volume metadata entries of the level are merged with the next lower level of the dense tree. During a merge operation, two sets of generation IDs may be used in accordance with a double buffer arrangement: a first generation ID for the append buffer that is full (i.e., a merge staging buffer) and a second, incremented generation ID for the append buffer that accepts new volume metadata entries. Upon completion of the merge operation, the lower level (e.g., level 1) to which the merge is directed is assigned the generation ID of the merge staging buffer.

Claims

1. A method comprising:

receiving a write request directed towards a logical unit (LUN), the write request having data, a logical block address (LBA) and a first length representing a first address range of the LUN, the write request processed at a storage system having a memory;

associating a key with the data;

determining whether a first metadata structure exceeds an occupancy threshold to store a first data entry having the key, a first offset and the first length representing the first address range of the LUN, the first metadata structure assigned a first generation identifier (ID);

in response to determining that the first metadata structure exceeds the occupancy threshold, storing the first data entry in a second metadata structure, the second metadata structure assigned a second generation ID different from the first generation ID;

merging a second data entry of a first level 0 of the first metadata structure with a third data entry of a level 1 of the first metadata structure to form a fourth data entry, the second data entry having a second offset and a second length representing a second address range, the third data entry having a third offset and a third length representing a third address range, the fourth data entry representing a merge of the second address range with the third address range; and

storing the fourth data entry in a storage array of solid state drives (SSDs) attached to the storage system.

2. The method of claim 1 wherein the first data entry is stored in a second level 0 of the second metadata structure, wherein the level 1 of the first metadata structure is shared with the second metadata structure, wherein the first and second level 0s are stored in the memory, and wherein the level 1 is stored on the storage array.

3. The method of claim 2 further comprising:

storing the first generation ID and second generation ID on the storage array;

performing a merge operation of the first level 0 of the first metadata structure with the level 1 of the first metadata structure;

incrementing the first generation ID; and

storing the incremented first generation ID in the level 1 of the first metadata structure on the storage array.

4. The method of claim 1 further comprising:

logging the first data entry in a log entry of a persistent log, the log entry associated with the second generation ID.

5. The method of claim 2 further comprising:

recovering the first level 0 of the first metadata structure from the storage array;

disregarding the fourth data entry stored on the storage array; and

restarting the merging of the second data entry of the first level of the first metadata structure with the third data entry of the second level of the first metadata structure.

6. The method of claim 4 further comprising:

replaying the log entry of the persistent log; and

recovering the second level 0 of the second metadata structure from the storage array.

7. The method of claim 5 wherein the restart of the merge is in response to comparing first and second fields of the level 0 stored on storage array, and wherein the first field includes the first generation ID and the second field includes the second generation ID.

8. The method of claim 2 further comprising:

assigning a default generation ID to the first level 0 of the first metadata structure, thereby indicating the first level 0 is empty.

9. The method of claim 1 wherein the fourth data entry is associated with level 1 of the first metadata structure.

10. A method comprising:

receiving a write request directed towards a logical unit (LUN), the write request having data, a logical block address (LBA) and a length representing a first address range of the LUN, the write request processed at a storage system having a memory;

associating a key with the data;

adding a first data entry to a level 0 of a first metadata structure stored in the memory, the first data entry representing the first address range of the LUN, the first metadata structure representing a second address range of the LUN overlapping the first address range, the first data entry having the key, wherein adding the first data entry renders the level 0 of the first metadata structure full, wherein the first metadata structure is assigned a first generation identifier (ID);

creating a second metadata structure assigned a second generation ID different from the first generation ID;

merging the level 0 of the first metadata structure with a level 1 of the first metadata structure stored in a storage array of solid state drives (SSDs) attached to the storage system, the level 1 of the first metadata structure shared with the second metadata structure; and

storing a result of the merging in the level 1 of the first metadata structure in a storage array of solid state drives (SSDs) attached to the storage system.

11. A system comprising:

a storage system having a memory connected to a processor via a bus;

a storage array coupled to the storage system and having one or more solid state drives (SSDs);

a storage I/O stack executing on the processor of the storage system, the storage I/O stack when executed operable to;

receive a write request directed towards a logical unit (LUN), the write request having data, a logical block address (LBA) and a first length representing a first address range of the LUN, the write request processed at a storage system having a memory;

associate a key with the data;

determine whether a first metadata structure exceeds an occupancy threshold to store a first data entry having the key, a first offset and the first length representing the first address range of the LUN, the first metadata structure assigned a first generation identifier (ID);

in response to determining that the first metadata structure exceeds the occupancy threshold, store the first data entry in a second metadata structure, the second metadata structure assigned a second generation ID different from the first generation ID;

merge a second data entry of a first level 0 of the first metadata structure with a third data entry of a level 1 of the first metadata structure to form a fourth data entry, the second data entry having a second offset and a second length representing a second address range, the third data entry having a third offset and a third length representing a third address range, the fourth data entry representing a merge of the second address range with the third address range; and

store the fourth data entry in a storage array of solid state drives (SSDs) attached to the storage system.

12. The system of claim 11 wherein the first data entry is stored in a second level 0 of the second metadata structure, wherein the level 1 of the first metadata structure is shared with the second metadata structure, wherein in the first and second level 0s are stored in the memory and wherein the level 1 is stored on the storage array.

13. The system of claim 12 wherein the storage I/O stack is further operable to:

store the first generation ID and second generation ID on the storage array;

perform a merge operation of the first level 0 of the first metadata structure with the level 1 of the first metadata structure;

increment the first generation ID; and

store the incremented first generation ID in the level 1 of the first metadata structure on the storage array.

14. The system of claim 11 wherein the storage I/O stack is further operable to:

log the first data entry in a log entry of a persistent log, the log entry associated with the second generation ID.

15. The system of claim 12 wherein the storage I/O stack is further operable to:

recover the first level 0 of the first metadata structure from the storage array;

disregard the fourth data entry stored on the storage array; and

restart the merge of the second data entry of the first level 0 of the first metadata structure with the third data entry of the level 1 of the first metadata structure.

16. The system of claim 14 wherein the storage I/O stack is further operable to:

replay the log entry of the persistent log; and

recover the second level 0 of the second metadata structure from the storage array.

17. The system of claim 15 wherein the restart of the merge is in response to comparing first and second fields of the level 0 stored on storage array, and wherein the first field includes the first generation ID and the second field includes the second generation ID.

18. The system of claim 16 wherein the storage I/O stack is further operable to:

assign a default generation ID to the first level 0 of the first metadata structure, thereby indicating the first level 0 is empty.

19. The system of claim 11 wherein the fourth data entry is associated with level 1 of the first metadata structure.

20. The system of claim 18 wherein level 0 includes a first plurality of data entries that are newer than a second plurality of data entries included in level 1.