Bottom-up dense tree repair technique

Patent metadata

Field	Value
Publication number	US-2017212919-A1
Application number	US-201615005593-A
Country	US
Kind code	A1
Filing date	Jan 25, 2016
Priority date	Jan 25, 2016
Publication date	Jul 27, 2017
Grant date	—

Abstract

A bottom-up technique repairs a data structure, e.g., a multi-level dense tree, used to organize volume metadata as metadata entries managed by a volume layer of a storage input/output (I/O) stack executing on one or more nodes of a cluster. The bottom-up repair technique implements a progressive repair algorithm that initially involves traversing each level of the dense tree to determine consistency of metadata entries by ensuring that the entries, e.g., (i) monotonically increase, (ii) do not overlap and (iii), if appropriate, reference (point to) existing entries of a lower level. The technique detects and corrects inconsistencies by, e.g., deleting out-of-order and overlapping entries, and adjusting the range of an index entry to reference the corresponding lower level entry. The technique then examines whether metadata entries at a lower level of the tree are referenced (pointed to) by corresponding index entries in an upper (parent) level. If there is no index entry at the upper level pointing to a lower level entry (i.e., a gap in offset range), the upper level is fixed (repaired) by employing a gap analysis procedure.

First claim

What is claimed is:

1 . A system comprising:
a central processing unit (CPU) of a storage system coupled to one or more storage devices of a storage array; and a memory coupled to the CPU and configured to store a storage input/output (I/O) stack executable by the CPU, the memory further configured to store a dense tree structure organized as multiple levels of metadata entries that store metadata embodied as mappings from offsets of a logical unit (LUN) to extent keys associated with storage locations of extents on the one or more storage devices, the storage I/O stack configured to traverse each level of the dense tree structure to determine consistency of the metadata entries by ensuring that the metadata entries (i) monotonically increase, (ii) do not overlap and, (iii) if appropriate, reference existing metadata entries of a lower level of the dense tree structure, the storage I/O stack further configured to repair the dense tree structure by deleting out-of-order metadata entries and deleting overlapping metadata entries.

2 . The system of claim 1 wherein the metadata entries comprise a data entry configured to map an offset range of the LUN to an extent key for an extent and an index entry configured to link the levels of the dense tree structure.

3 . The system of claim 2 wherein the metadata entries are organized as one or more metadata pages and wherein the index entry is configured to map an offset range of the LUN to a page key of a metadata page at a next lower level of the dense tree structure.

4 . The system of claim 3 wherein the storage I/O stack is further configured to repair the dense tree structure by adjusting the offset range of an index entry to reference a corresponding lower level entry.

5 . The system of claim 4 wherein the storage I/O stack is further configured to examine whether the metadata entries at the lower level of the dense tree structure are referenced by corresponding index entries in an upper level of the dense tree structure.

6 . The system of claim 5 wherein, in response to detecting a gap between adjacent upper level metadata entries of the dense tree structure and detecting that a lower level metadata entry is unreferenced, the storage I/O stack is further configured to repair the dense tree structure by one of extending an offset range of the upper level metadata entry and inserting a new repair index entry in the upper level of the dense tree structure to cover the gap corresponding to the lower level metadata entry of the dense tree structure.

7 . The system of claim 6 wherein the storage I/O stack is further configured to repair the dense tree structure by one of inserting the new repair index entry on a new metadata page to cover the gap and moving one or more existing upper level metadata entries on to the new metadata page.

8 . The system of claim 7 wherein if there is available space for a new metadata entry on the upper level of the dense tree structure, the storage I/O stack is further configured to rebalance the upper level to move the available space to a metadata page and insert the new repair index entry on the metadata page to cover the gap.

9 . The system of claim 8 wherein the storage I/O stack is further configured to replace a data entry in the upper level with an index entry that covers the gap.

10 . The system of claim 1 wherein the storage I/O stack is further configured to take the LUN offline during repair of the dense tree structure.

11 . A method comprising:
receiving one or more write requests having data directed toward a logical unit (LUN) at a storage system coupled to one or more storage devices, storing a dense tree structure organized as multiple levels of metadata entries that store metadata embodied as mappings from offsets of the LUN to extent keys associated with storage locations of extents including the data on the one or more storage devices, traversing each level of the dense tree structure to determine consistency of the metadata entries by ensuring that the metadata entries (i) monotonically increase, (ii) do not overlap and, (iii) if appropriate, reference existing metadata entries of a lower level of the dense tree structure, and repairing the dense tree structure by deleting out-of-order metadata entries and deleting overlapping metadata entries.

12 . The method of claim 11 wherein the metadata entries comprise a data entry configured to map an offset range of the LUN to an extent key for an extent and an index entry configured to link the levels of the dense tree structure.

13 . The method of claim 12 wherein the metadata entries are organized as one or more metadata pages and wherein the index entry is configured to map an offset range of the LUN to a page key of a metadata page at a next lower level of the dense tree structure.

14 . The method of claim 13 further comprising:
repairing the dense tree structure by adjusting the offset range of the index entry to reference a corresponding lower level entry.

15 . The method of claim 14 further comprising:
examining whether the metadata entries at the lower level of the dense tree structure are referenced by corresponding index entries in an upper level of the dense tree structure.

16 . The method of claim 15 further comprising:
in response to detecting a gap between adjacent upper level metadata entries of the dense tree structure and detecting that a lower level metadata entry is unreferenced, repairing the dense tree structure by one of extending an offset range of the upper level metadata entry and inserting a new repair index entry in the upper level of the dense tree structure to cover the gap corresponding to the lower level metadata entry of the dense tree structure.

17 . The method of claim 16 further comprising:
repairing the dense tree structure by one of inserting the new repair index entry on a new metadata page to cover the gap and moving one or more existing upper level metadata entries on to the new metadata page.

18 . The method of claim 17 further comprising:
determining whether there is available space for a new metadata entry on the upper level of the dense tree structure, and
in response to determining that there is insufficient space available for the new metadata entry, rebalancing the upper level to move the available space to a metadata page and insert the new repair index entry on the metadata page to cover the gap.

19 . The method of claim 18 further comprising:
replacing a data entry in the upper level with an index entry that covers the gap.

20 . A non-transitory computer readable medium including program instructions for execution on one or more processors coupled to a plurality of storage devices, the program instructions when executed operable to:
receive one or more write requests having data directed toward a logical unit (LUN), store a dense tree structure organized as multiple levels of metadata entries that store metadata embodied as mappings from offsets of the LUN to extent keys associated with storage locations of extents including the data on the plurality of storage devices, traverse each level of the dense tree structure to determine consistency of the metadata entries by ensuring that the metadata entries (i) monotonically increase, (ii) do not overlap and, (iii) if appropriate, reference existing metadata entries of a lower level of the dense tree structure, and repair the dense tree structure by deleting out-of-order metadata entries and deleting overlapping metadata

Assignees

• Netapp Inc

Inventors

• Li Anthony J
• Krishnamachari Srinath
• Zheng Ling

Classifications

• G06F16/2379

  Updates performed during online database operations; commit processing · CPC title

• G06F13/4068

  Electrical coupling · CPC title

• G06F13/1668 Primary

  Details of memory controller · CPC title

• G06F16/2246 Primary

  Trees, e.g. B+trees · CPC title

• G06F17/30327 Primary

  Physics · mapped topic