Technique for quantifying logical space trapped in an extent store

• US 9,779,018 B2
• Filed: 10/27/2016
• Issued: 10/03/2017
• Est. Priority Date: 09/10/2014
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Babu, Sriranjani, D'Sa, Janice
• Primary Examiner(s): AL HASHEMI, SANA A
• Application Number:
  US15/336,096
• Publication Number:
  US 20170046257A1
• Time in Patent Office: 341 Days
• Field of Search: 707661, 707722, 707758, 707781, 707790, 707791
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 12/10 Address translation
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/65 Details of virtual memory and virtual address translation
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0638 Organizing or formatting or addressing of data
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/0665 at area level, e.g. provisioning of virtual or logical volumes
• CPC Class Codes: G06F 3/0683 Plurality of storage devices
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

A technique quantifies logical storage space trapped in an extent store due to overlapping write requests associated with volume metadata managed by the volume layer. The volume metadata is illustratively organized as a multi-level dense tree metadata structure, wherein each level of the dense tree metadata structure (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 a next lower level of the dense tree in accordance with a merge operation. Illustratively, the technique may be invoked during the merge operation to examine the volume metadata entries at each level of the dense tree involved in the merge and determine the LBA range overlap of the entries. To that end, the technique may include an algorithm configured to calculate the overlapping space per level and then aggregate the overlapping space of all levels involved in the merge operation to arrive at a result that quantifies the logical storage space trapped in the extent store.

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 drives (SSDs) coupled to the CPU; and

a memory coupled to the CPU and configured to store the storage I/O stack and a multi-level dense tree metadata structure, wherein each level of the dense tree metadata structure includes entries for storing metadata having mappings from offset ranges of a logical unit (LUN) to extent keys associated with storage locations for extents stored on an extent store of the SSDs, wherein the storage I/O stack is configured to;

receive overlapping write requests directed to the LUN, the overlapping write requests representing overlapping offset ranges of the LUN, the overlapping offset ranges stored as overlapping entries of the dense tree metadata structure;

process the mappings of the overlapping entries to determine an offset range overlap of the overlapping entries per level; and

aggregate the offset range overlap of the overlapping entries between adjacent levels of the multi-level dense tree metadata structure to quantify trapped logical storage space in overlapping extents of the extent store due to the overlapping write requests.

2. The system of claim 1 wherein the adjacent levels of the dense tree metadata structure include an upper level and a next lower level.

3. The system of claim 2 wherein the storage I/O stack is further configured to perform a merge operation to merge the entries of the upper level of the dense tree metadata structure with the entries of the next lower level of the dense tree metadata structure when the upper level is full.

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

calculate an amount of the trapped logical storage space of the overlapping extents; and

determine whether the amount of trapped logical storage space exceeds a threshold.

5. The system of claim 4 wherein, if the amount of trapped logical space exceeds the threshold, the storage I/O stack is further configured to:

perform read-modify-write operations on the overlapping extents to recapture the trapped logical storage space.

6. The system of claim 5 wherein the storage I/O stack when configured to perform the read-modify-write operations is further configured to:

purge the extents consuming the trapped logical storage space; and

write new non-overlapping extents.

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

implement a depth-first tree traversal of the entries of the dense tree metadata structure to compute the trapped logical storage space using predetermined rules and data structures.

8. The system of claim 7 wherein the data structures comprise a space lockup list and a space lockup counter.

9. The system of claim 8 wherein the space lockup list is embodied as a push-pop stack.

10. The system of claim 8 wherein the storage I/O stack when configured to implement the depth-first tree traversal is further configured to:

apply the predetermined rules to one of add and remove items from the space lockup list depending on a previous extend key in the list; and

accumulate amounts of the trapped logical storage space to the space lockup counter.

11. A method comprising:

storing a dense tree metadata structure in a memory coupled to a processor of a storage system, the dense tree metadata structure having multiple levels wherein each level of the dense tree metadata structure includes entries for storing metadata having mappings from offset ranges of a logical unit (LUN) to extent keys associated with storage locations for extents stored on an extent store of the storage system;

receiving overlapping write requests directed to the LUN at the storage system, the overlapping write requests representing overlapping offset ranges of the LUN, the overlapping offset ranges stored as overlapping entries of the dense tree metadata structure;

processing the mappings of the overlapping entries to determine an offset range overlap of the overlapping entries per level; and

aggregating the offset range overlap of the overlapping entries between adjacent levels of the multi-level dense tree metadata structure to quantify trapped logical storage space in overlapping extents of the extent store due to the overlapping write requests.

12. The method of claim 11 wherein the adjacent levels of the dense tree metadata structure include an upper level and a next lower level.

13. The method of claim 12 further comprising:

performing a merge operation to merge the entries of the upper level of the dense tree metadata structure with the entries of the next lower level of the dense tree metadata structure when the upper level is full.

14. The method of claim 11 further comprising:

calculating an amount of the trapped logical storage space of the overlapping extents; and

determining whether the amount of trapped logical storage space exceeds a threshold.

15. The method of claim 14 further comprising:

performing read-modify-write operations on the overlapping extents to recapture the trapped logical storage space if the amount of trapped logical space exceeds the threshold.

16. The method of claim 15 wherein performing the read-modify-write operations comprises:

purging the extents consuming the trapped logical storage space; and

writing new non-overlapping extents.

17. The method of claim 11 further comprising:

implementing a depth-first tree traversal of the entries of the dense tree metadata structure to compute the trapped logical storage space using predetermined rules and data structures.

18. The method of claim 17 wherein the data structures comprise a space lockup list and a space lockup counter.

19. The method of claim 18 wherein implementing the depth-first tree traversal comprises:

applying the predetermined rules to one of add and remove items from the space lockup list depending on a previous extent key in the list; and

accumulating amounts of the trapped logical storage space to the space lockup counter.

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

store a dense tree metadata structure in a memory coupled to the processor, the dense tree metadata structure having multiple levels wherein each level of the dense tree metadata structure includes entries for storing metadata having mappings from offset ranges of a logical unit (LUN) to extent keys associated with storage locations for extents stored on an extent store;

receive overlapping write requests directed to the LUN, the overlapping write requests representing overlapping offset ranges of the LUN, the overlapping offset ranges stored as overlapping entries of the dense tree metadata structure;

process the mappings of the overlapping entries to determine an offset range overlap of the overlapping entries per level; and

aggregate the offset range overlap of the overlapping entries between adjacent levels of the multi-level dense tree metadata structure to quantify trapped logical storage space in overlapping extents of the extent store due to the overlapping write requests.