Reconstruction of dense tree volume metadata state across crash recovery

• US 9,836,355 B2
• Filed: 09/22/2016
• Issued: 12/05/2017
• 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:
  US15/272,971
• Publication Number:
  US 20170010939A1
• Time in Patent Office: 439 Days
• Field of Search: 707822, 707802, 707806
• 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
• 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:

storing a first upper level of a multi-level dense tree structure and a second upper level of the multi-level dense tree structure in a memory of a storage system coupled to one or more solid state devices (SSDs), wherein each level of the multi-level dense tree structure includes volume metadata entries for storing volume metadata, the volume metadata entries of the first upper level associated with a first generation identifier (ID), the volume metadata entries of the second upper level associated with a second generation ID;

recording the volume metadata entries in an append log stored on the SSDs, each recorded volume metadata entry tagged with one of the first generation ID associated with the first upper level and the second generation ID associated with the second upper level;

triggering a merge operation to merge the volume metadata entries of the first upper level of the multi-level dense tree structure with the volume metadata entries of a next lower level of the multi-level dense tree structure when the first upper level is full, the volume metadata entries of the merged levels recorded to the SSDs; and

recovering from a crash of the storage system during the merge operation by reading merged metadata entries from the SSDs into the memory and replaying entries of the append log to recreate the first upper level and the second upper level of the multi-level dense tree structure, such that the first upper level and second upper level are consistent with restarting the merge operation.

2. The method of claim 1 further comprising loading the volume metadata entries in first and second append buffers stored in the memory, the volume metadata entries of the first append buffer associated the first upper level and the first generation ID, the volume metadata entries of the second append buffer associated with the second upper level and the second generation ID.

3. The method of claim 2 further comprising recording the first generation ID and the second generation ID in an upper level header on the SSDs.

4. The method of claim 3 wherein replaying further comprises replaying the recorded entries of the append log to recreate the first append buffer and the second append buffer in the memory.

5. The method of claim 4 wherein recovering further comprises restarting the merge operation with the first and second upper levels and the first and second append buffers having the first and second generation IDs, respectively, as recorded in the upper level header.

6. The method of claim 2 wherein the first upper level and the first append buffer are used for consistency of data during the merge operation between the levels of the multi-level dense tree structure, and wherein the second upper level and second append buffer are used for incoming data during the merge operation.

7. The method of claim 6 wherein the first generation ID is lower than the second generation ID.

8. The method of claim 7 further comprising storing most recent metadata in the second append buffer associated with the second generation ID.

9. The method of claim 7 wherein recovering further comprises restarting the merge operation with the first append buffer associated with the lower first generation ID at a time of the crash.

10. A system comprising:

a storage system having a memory connected to a processor;

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

a storage input/output (I/O) stack adapted for execution on the processor of the storage system, the storage I/O stack configured to;

store a first upper level of a multi-level dense tree structure and a second upper level of the multi-level dense tree structure in the memory, wherein each level of the multi-level dense tree structure includes volume metadata entries for storing volume metadata, the volume metadata entries of the first upper level associated with a first generation identifier (ID), the volume metadata entries of the second upper level associated with a second generation ID;

record the volume metadata entries in an append log stored on the SSDs, each recorded volume metadata entry tagged with one of the first generation ID associated with the first upper level and the second generation ID associated with the second upper level;

trigger a merge operation to merge the volume metadata entries of the first upper level of the multi-level dense tree structure with the volume metadata entries of a next lower level of the multi-level dense tree structure when the first upper level is full, the volume metadata entries of the merged levels recorded to the SSDs; and

recover from a crash of the storage system during the merge operation by reading merged metadata entries from the SSDs into the memory and replaying entries of the append log to recreate the first upper level and the second upper level of the multi-level dense tree structure, such that the first upper level and second upper level are consistent with restarting the merge operation.

11. The system of claim 10 wherein the storage I/O stack is further configured to load the volume metadata entries in first and second append buffers stored in the memory, the volume metadata entries of the first append buffer associated the first upper level and the first generation ID, the volume metadata entries of the second append buffer associated with the second upper level and the second generation ID.

12. The system of claim 11 wherein the storage I/O stack is further configured to record the first generation ID and the second generation ID in an upper level header on the SSDs.

13. The system of claim 12 wherein the storage I/O stack is further configured to replay the recorded entries of the append log to recreate the first append buffer and the second append buffer in the memory.

14. The system of claim 13 wherein the storage I/O stack is further configured to restart the merge operation with the first and second upper levels and the first and second append buffers having the first and second generation IDs, respectively, as recorded in the upper level header.

15. The system of claim 11 wherein the first upper level and the first append buffer are used for consistency of data during the merge operation between the levels of the multi-level dense tree structure, and wherein the second upper level and second append buffer are used for incoming data during the merge operation.

16. The system of claim 15 wherein the first generation ID is lower than the second generation ID.

17. The system of claim 16 wherein the storage I/O stack is further configured to store most recent metadata in the second append buffer associated with the second generation ID.

18. The system of claim 16 wherein the storage I/O stack is further configured to restart the merge operation with the first append buffer associated with the lower first generation ID at a time of the crash.

19. A non-transitory computer readable medium including program instructions for execution on a processor of a storage system, the program instructions configured to:

store a first upper level of a multi-level dense tree structure and a second upper level of the multi-level dense tree structure in a memory of the storage system coupled to one or more solid state devices (SSDs), wherein each level of the multi-level dense tree structure includes volume metadata entries for storing volume metadata, the volume metadata entries of the first upper level associated with a first generation identifier (ID), the volume metadata entries of the second upper level associated with a second generation ID;

record the volume metadata entries in an append log stored on the SSDs, each recorded volume metadata entry tagged with one of the first generation ID associated with the first upper level and the second generation ID associated with the second upper level;

is trigger a merge operation to merge the volume metadata entries of the first upper level of the multi-level dense tree structure with the volume metadata entries of a next lower level of the multi-level dense tree structure when the first upper level is full, the volume metadata entries of the merged levels recorded to the SSDs; and

recover from a crash of the storage system during the merge operation by reading merged metadata entries from the SSDs into the memory and replaying entries of the append log to recreate the first upper level and the second upper level of the multi-level dense tree structure, such that the first upper level and second upper level are consistent with restarting the merge operation.

20. The non-transitory computer readable medium of claim 19 wherein the first upper level is used for consistency of data during the merge operation between the levels of the multi-level dense tree structure, and wherein the second upper level is used for incoming data during the merge operation.