Technique for quantifying logical space trapped in an extent store

• US 9,524,103 B2
• Filed: 09/10/2014
• Issued: 12/20/2016
• 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:
  US14/482,863
• Publication Number:
  US 20160070480A1
• Time in Patent Office: 832 Days
• Field of Search: 707/661, 707/722, 707/758, 707/781, 707/790, 707/791
• US Class Current: 1/1
• 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 method comprising:

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

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

storing the first and second keys in respective first and second data entries of a metadata structure, the first data entry having a first offset and a first original length representing the first offset range of the LUN, the second data entry having a second offset and a second original length representing the second offset range of the LUN, wherein the first data entry includes a first length decreased from the first original length by an amount of overlap of the second offset range with the first offset range;

subtracting the first length from the first original length, thereby calculating an amount of trapped logical space associated with the first data entry; and

storing the first and second data in a storage array attached to the storage system.

2. The method of claim 1 wherein the second offset range has a first starting offset greater than a second starting offset of the second offset range, and wherein the first data entry includes a relative offset equal to the amount of overlap of the second offset range with the first offset range.

3. The method of claim 1 wherein the second offset range has a first starting offset greater than a second starting offset of the second offset range, the second offset range has a first end offset less than a second end offset of the first offset range, and a third data entry is generated storing the first key and having a third original length equal to the first original length and a third relative offset equal to a sum of the second offset and the second length, wherein the third relative offset references a portion of the first data.

4. The method of claim 3 further comprising:

calculating a third length included in the third data entry, wherein the third length is equal to first original length less the first length and less the second length; and

subtracting the third length from the calculated amount of trapped logical space associated with the first data entry, thereby correcting the amount of trapped logical space associated with the first data entry.

5. The method of claim 1 further comprising:

accumulating a total amount of trapped logical space in the metadata structure, wherein the total amount of trapped logical space includes the calculated amount of trapped logical space associated with the first data entry.

6. The method of claim 1 further comprising:

traversing the metadata structure;

for each entry traversed, calculating an amount of trapped logical space; and

adding the amount of trapped logical space for each entry traversed to a list.

7. The method of claim 6 further comprising:

removing the amounts of trapped logical space from the list; and

accumulating the removed amounts of trapped logical space in a counter, thereby determining a total amount of trapped logical space in the metadata structure.

8. The method of claim 6 wherein the metadata structure is traversed during a merge operation of entries of the metadata structure, and wherein the metadata structure is a dense tree.

9. The method of claim 6 wherein the list is implemented as a stack.

10. A method comprising:

receiving a plurality of write requests directed towards a logical unit (LUN), the write requests each having data associated with an offset range of the LUN, the write requests processed at a storage system;

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

storing each data of each write request in a storage array attached to the storage system;

storing each key in a respective data entry of a metadata structure, each respective data entry representing the offset range of the write request having the data associated with the respective key;

calculating an amount of overlapping offset range for each data entry that is overlapped; and

accumulating the calculated amount of overlapping offset range for each data entry, thereby determining an amount of trapped logical space in the LUN.

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;

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

receive first and second write requests directed to a logical unit (LUN), the first and second write requests having respective first and second data, the first and second write requests representing respective first and second offset ranges of the LUN, the second offset range overlapping a portion of the first offset range;

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

store the first and second keys in respective first and second data entries of a metadata structure, the first data entry having a first offset and a first original length representing the first offset range of the LUN, the second data entry having a second offset and a second original length representing the second offset range of the LUN, wherein the first data entry includes a first length decreased from the first original length by an amount of overlap of the second offset range with the first offset range;

subtract the first length from the first original length, thereby calculating an amount of trapped logical space associated with the first data entry; and

store the first and second data in the storage array.

12. The system of claim 11 wherein the second offset range has a first starting offset greater than a second starting offset of the second offset range, and wherein the first data entry includes a relative offset equal to the amount of overlap of the second offset range with the first offset range.

13. The system of claim 11 wherein the second offset range has a first starting offset greater than a second starting offset of the second offset range, the second offset range has a first end offset less than a second end offset of the first offset range, and a third data entry is generated storing the first key and having a third original length equal to the first original length and a third relative offset equal to a sum of the second offset and the second length, wherein the third relative offset references a portion of the first data.

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

calculate a third length included in the third data entry, wherein the third length is equal to first original length less the first length and less the second length; and

subtract from the calculated amount of trapped logical space associated with the first data entry the third length, thereby correcting the amount of trapped logical space associated with the first data entry.

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

accumulate a total amount of trapped logical space in the metadata structure, wherein the total amount of trapped logical space includes the calculated amount of trapped logical space associated with the first data entry, and wherein the second data is de-duplicated from the first data.

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

traverse the metadata structure;

for each entry traversed having an overlapping entry, calculate an amount of trapped logical space; and

add the amount of trapped logical space for each entry traversed to a list.

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

remove the amounts of trapped logical space from the list; and

accumulate the removed amounts of trapped logical space in a counter, thereby determining a total amount of trapped logical space in the metadata structure.

18. The system of claim 16 wherein the metadata structure is traversed during a merge operation of entries of the metadata structure, and wherein the metadata structure is a dense tree.

19. The system of claim 16 wherein the list is implemented as a stack.

20. The system of claim 11 wherein the storage array includes solid state drives.