N-way merge technique for updating volume metadata in a storage I/O stack

• US 10,365,838 B2
• Filed: 11/21/2017
• Issued: 07/30/2019
• Est. Priority Date: 11/18/2014
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: D'Sa, Janice, Zheng, Ling, Lewis, Blake H.
• Primary Examiner(s): Song, Hua J
• Application Number:
  US15/820,004
• Publication Number:
  US 20180095685A1
• Time in Patent Office: 616 Days
• Field of Search: 711114
• CPC Class Codes: G06F 3/0607 by facilitating the process of upgrading existing storage systems, e.g. for improving compatibility between host and storage device
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0626 Reducing size or complexity of storage systems
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0665 at area level, e.g. provisioning of virtual or logical volumes
• 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/0689 Disk arrays, e.g. RAID, JBOD
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

A N-way merge technique efficiently updates metadata in accordance with a N-way merge operation managed by a volume layer of a storage input/output (I/O) stack executing on one or more nodes of a cluster. The metadata is embodied as mappings from logical block addresses (LBAs) of a logical unit (LUN) accessible by a host to durable extent keys, and is organized as a multi-level dense tree. The mappings are organized such that a higher level of the dense tree contains more recent mappings than a next lower level, i.e., the level immediately below. The N-way merge operation is an efficient (i.e., optimized) way of updating the volume metadata mappings of the dense tree by merging the mapping content of all three levels in a single iteration, as opposed to merging the content of the first level with the content of the second level in a first iteration of a two-way merge operation and then merging the results of the first iteration with the content of the third level in a second iteration of the operation.

Claims

1. A system comprising:

a central processing unit (CPU) adapted to execute a storage input/output (I/O) stack;

one or more solid state devices (SSDs) coupled to the CPU; and

a memory coupled to the CPU and configured to store the storage I/O stack, the memory further configured to store one or more dense tree metadata structures wherein each dense tree metadata structure has at least three adjacent levels, each level of each dense tree metadata structure including metadata entries for storing metadata embodied as mappings from offset ranges of a logical unit (LUN) to keys, the storage I/O stack configured to merge the mappings of the adjacent levels in a single merge iteration when at least one of the adjacent levels exceeds an amount of fullness.

2. The system of claim 1 wherein the storage I/O stack is further configured to:

apportion the LUN into one or more volumes; and

partition each volume into one or more regions, wherein each region is represented by a dense tree metadata structure.

3. The system of claim 2 wherein the storage I/O stack is further configured to receive a write request directed towards the LUN, the write request representing an offset range within an offset range space of a region of the LUN.

4. The system of claim 3 wherein the storage I/O stack is further configured to:

employ a sliding window to merge the mappings of the adjacent levels;

advance the sliding window across the offset range space; and

fill the sliding window with the mappings.

5. The system of claim 4 wherein the storage I/O stack is further configured to organize the offset range space as a matrix.

6. The system of claim 5 wherein the matrix has a top-down focus that extends from a highest adjacent level of the dense tree metadata structure to a lowest adjacent level of the dense tree metadata structure.

7. The system of claim 5 wherein the storage I/O stack is configured to advance the sliding window from a starting offset of the matrix to an ending offset of the matrix.

8. The system of claim 5 wherein the storage I/O stack is configured to:

advance the sliding window at defined offset and length intervals; and

examine the mappings of the levels that fill the sliding window at each interval.

9. The system of claim 1 wherein the storage I/O stack is configured to merge the mappings of the adjacent levels for a dense tree metadata structure having complete overlap of each mapping between the adjacent levels.

10. The system of claim 1 wherein the storage I/O stack is configured to merge the mappings of the adjacent levels for a dense tree metadata structure having partial overlap of the mappings between the adjacent levels.

11. The system of claim 10 wherein the partial overlap of the mappings comprises a three-way split overlap of the mappings between the adjacent levels.

12. A method comprising:

storing one or more dense tree metadata structures in a memory coupled to a processor of a storage system, wherein each dense tree metadata structure has at least three adjacent levels, each level of each dense tree metadata structure including metadata entries for storing metadata embodied as mappings from offset ranges of a logical unit (LUN) to keys; and

merging the mappings of the adjacent levels in a single merge iteration when at least one of the adjacent levels exceeds an amount of fullness.

13. The method of claim 12 further comprising:

apportioning the LUN into one or more volumes; and

partitioning each volume into one or more regions, wherein each region is represented by a dense tree metadata structure.

14. The method of claim 13 further comprising:

receiving a write request directed towards the LUN, the write request representing an offset range within an offset range space of a region of the LUN.

15. The method of claim 14 further comprising:

employing a sliding window to merge the mappings of the adjacent levels;

advancing the sliding window across the offset range space; and

filling the sliding window with the mappings.

16. The method of claim 15 further comprising:

organizing the offset range space as a matrix.

17. The method of claim 16 wherein the matrix has a top-down focus that extends from a highest adjacent level of the dense tree metadata structure to a lowest adjacent level of the dense tree metadata structure.

18. The method of claim 16 further comprising:

advancing the sliding window from a starting offset of the matrix to an ending offset of the matrix.

19. The method of claim 16 further comprising:

advancing the sliding window at defined offset and length intervals; and

examining the mappings of the levels that fill the sliding window at each interval.

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

store one or more dense tree metadata structures in a memory of the storage system, wherein each dense tree metadata structure has at least three adjacent levels, each level of each dense tree metadata structure including metadata entries for storing metadata embodied as mappings from offset ranges of a logical unit (LUN) to keys; and

merge the mappings of the adjacent levels in a single merge iteration when at least one of the adjacent levels exceeds an amount of fullness.