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

• US 9,836,229 B2
• Filed: 11/18/2014
• Issued: 12/05/2017
• 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 JASMINE
• Application Number:
  US14/546,214
• Publication Number:
  US 20160139838A1
• Time in Patent Office: 1,113 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 method comprising:

receiving first, second and third write requests directed towards a logical unit (LUN), the first, second and third write requests having respective first, second and third data, the first, second and third write requests representing respective first, second and third offset ranges of the LUN, the second and third offset ranges overlapping the first offset range, the write requests processed at a storage system having a memory;

associating first, second and third keys with the respective first, second and third data;

storing the first, second and third keys in respective first, second and third entries of a metadata structure;

merging the first, second and third entries to form a fourth entry, the fourth entry representing a merge of the first, second and third offset ranges, the second and third entries stored on an array of storage devices attached to the storage system; and

storing the fourth entry on the storage array.

2. The method of claim 1 wherein the metadata structure includes a plurality of levels, and wherein the first, second and third entries are each associated with a different level.

3. The method of claim 2 wherein a first level of the plurality of levels is associated with the first entry, wherein a second level of the plurality of levels is associated with the second entry, wherein a third level of the plurality of levels is associated with the third entry, wherein the first entry is more recent than the second entry, and wherein the second entry is more recent than the third entry.

4. The method of claim 3 wherein the fourth entry has an offset range that includes a portion of the first offset range that overlaps the second and third offset ranges.

5. The method of claim 2 wherein the plurality of levels form a dense tree structure.

6. The method of claim 3 wherein merging the first, second and third entries to form the fourth entry occurs when a first level of the plurality of levels exceeds a capacity threshold.

7. The method of claim 3 wherein the first level of the plurality of levels is emptied.

8. The method of claim 7 wherein the second level of the plurality of levels is emptied.

9. The method of claim 1 wherein the storage devices are solid state drives.

10. A method comprising:

receiving a number of write requests directed towards a logical unit (LUN),each write request having respective data and representing respective offset ranges of the LUN, wherein the number of write requests is greater than three, the write requests processed at a storage system having a memory;

associating the respective data of each write request with a respective key;

storing the respective key of the respective data in a respective entry of a metadata structure, wherein the metadata structure includes a plurality of levels, wherein each entry is associated with a different level of the plurality of levels;

merging the respective entries to form a merged entry, the merged entry representing a merge of all the respective offset ranges, the plurality of entries stored on an array of storage devices attached to the storage system; and

storing the merged entry on a lowest level of the plurality of levels of the metadata structure.

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

a storage I/O stack executing on the processor of the storage system, the storage I/O configured to;

receive first, second and third write requests directed towards a logical unit (LUN), the first, second and third write requests having respective first, second and third data, the first, second and third write requests representing respective first, second and third offset ranges of the LUN, the second and third offset ranges overlapping the first offset range, the write requests processed at a storage system having a memory;

associate first, second and third keys with the respective first, second and third data;

store the first, second and third keys in respective first, second and third entries of a metadata structure;

merge the first, second and third entries to form a fourth entry, the fourth entry representing a merge of the first, second and third offset ranges, the second and third entries stored on an array of storage devices attached to the storage system; and

store the fourth entry on the storage array.

12. The system of claim 11 wherein the metadata structure includes a plurality of levels, and wherein the first, second and third entries are each associated with a different level.

13. The system of claim 12 wherein a first level of the plurality of levels is associated with the first entry, wherein a second level of the plurality of levels is associated with the second entry, wherein a third level of the plurality of levels is associated with the third entry, wherein the first entry is more recent than the second entry, and wherein the second entry is more recent than the third entry.

14. The system of claim 13 wherein the fourth entry has an offset range that includes a portion of the first offset range that overlaps the second and third offset ranges.

15. The system of claim 12 wherein the plurality of levels form a dense tree structure.

16. The system of claim 13 wherein the merge of the first, second and third entries to form the fourth entry occurs when a first level of the plurality of levels exceeds a capacity threshold.

17. The system of claim 13 wherein the first level of the plurality of levels is emptied.

18. The system of claim 17 wherein the second level of the plurality of levels is emptied.

19. The system of claim 11 wherein the storage devices are solid state drives.

20. The system of claim 13 wherein the fourth entry is stored on the third level of the plurality of levels of the metadata structure.