SHARED DENSE TREE REPAIR

• US 20170300248A1
• Filed: 04/15/2016
• Published: 10/19/2017
• Est. Priority Date: 04/15/2016
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Purohit, Prahlad, Venkitakrishnan, Vidhyalakshmi, Li, Anthony J.
• Granted Patent: US 10,191,674 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 11/0727 in a storage system, e.g. in a DASD or network based storage system drivers for digital recording or reproducing units G06F3/06; circuits for error detection or correction within digital recording or reproducing units G11B20/18; 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], H04L67/1097
• CPC Class Codes: G06F 11/0793 Remedial or corrective actions recovery from an exception in an instruction pipeline G06F9/3861; by retry G06F11/1402; for recovering from a failure of a protocol instance or entity H04L69/40
• CPC Class Codes: G06F 11/30 Monitoring
• CPC Class Codes: G06F 2201/82 Solving problems relating to consistency
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0623 in relation to content
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

A consistency checker is configured to perform repairs to one or more multi-level dense tree metadata structures shared between volumes managed by a volume layer of a storage input/output (I/O) stack executing on one or more nodes of a cluster. The volumes include a parent volume and a snapshot and/or clone, wherein the snapshot/clone may be represented as an independent volume, and embodied as a respective read-only copy (snapshot) or read-write copy (clone) of the parent volume. Illustratively, the consistency checker verifies and/or fixes (i.e., repairs) on-disk structures of the volume layer, e.g., the shared dense tree, according to a distributed repair procedure that maintains consistency properties across all volumes in a volume family and avoid cyclic repairs made in the context of different volumes sharing the dense tree.

Claims

1. A method comprising:

initiating a consistency checker to perform repairs to levels of dense trees shared among volumes of a volume family managed by a volume layer of a storage input/output (I/O) stack executing on a node, each level of each dense tree including volume metadata entries for storing metadata, the volume metadata entries organized as metadata pages according to address space regions for the volumes, each region represented by a dense tree; and

configuring the consistency checker to operate in parallel on the dense trees shared among the volumes to check and repair the dense trees using a workflow that minimizes use of locks when traversing the dense trees, the consistency checker further configured to render non-cyclic repairs to each dense tree that ensure that the repairs are rendered once to avoid traversing the respective dense tree multiple times for the volumes of the volume family.

2. The method of claim 1 wherein configuring the consistency checker further comprises:

maintaining a map in a memory of the node, the map organized as a key-value data structure wherein the key is a header key included in a level header of each level of the dense tree and the value is a reference counter maintained for the level of the dense tree; and

marking the map to indicate use of the header key to check and repair the level and the metadata pages of the level to avoid cyclic repairs to the dense tree.

3. The method of claim 1 wherein configuring the consistency checker further comprises:

processing check and repair operations directed to the volume metadata of the regions using a plurality of services;

distributing the check and repair operations among the regions;

mapping each region to a service; and

executing the check and repair operations on the volume metadata of the regions in parallel across the regions.

4. The method of claim 3 wherein the services are threads of execution on processors of the node.

5. The method of claim 1 further comprising:

using a generation number within a level header of each level of the dense tree to uniquely identify the level header within the volume family;

determining whether the generation number is corrupted; and

,

if the generation number is corrupted, assigning a new generation number to the level header that does not collide with other generation numbers in the volume family.

6. The method of claim 5 wherein the volumes of the volume family include a parent volume and one of a snapshot volume and a clone volume.

7. The method of claim 6 further comprising:

ensuring that the level header of the parent volume has a greatest generation number of the volume family.

8. The method of claim 1 further comprising:

recording a reference count within a level header of each level of the dense tree to track sharing of the levels between the volumes, the reference count indicating a number of pointers to a corresponding level of the dense tree;

gathering an actual number of the pointers to the level header;

determining whether the actual number matches the reference count recorded in the level header; and

in response to the actual number not matching the recorded reference count, repairing the reference count to reflect the actual number.

9. The method of claim 8 wherein gathering the actual number comprises:

discovering that one of the pointers is corrupted;

discarding the corrupted pointer; and

disregarding the corrupted pointer in the actual number used to repair the reference count.

10. A system comprising:

a central processing unit (CPU) of a node coupled to one or more storage devices; and

a memory coupled to the CPU and configured to store a storage input/output (I/O) stack executable by the CPU, the storage I/O stack having a volume layer configured to manage metadata of dense trees having multiple levels shared among volumes of a volume family, each level of each dense tree including volume metadata entries for storing the metadata, the volume metadata entries organized as metadata pages according to address space regions for the volumes, each region represented by a dense tree, the storage I/O stack when executed operable to;

initiate a consistency checker to perform repairs to the levels of the dense trees shared among the volumes; and

configure the consistency checker to operate in parallel on the dense trees shared among the volumes to check and repair the dense trees in a manner that minimizes use of locks when traversing the dense trees, the consistency checker further configured to render non-cyclic repairs to each dense tree that ensure that the repairs are rendered once to avoid traversing the dense tree multiple times for the volumes of the volume family.

11. The system of claim 10 wherein the storage I/O stack when executed to configure the consistency checker is further operable to:

maintain a map in a memory of the node, the map organized as a key-value data structure wherein the key is a header key included in a level header of each level of the dense tree and the value is a reference counter maintained for the level of the dense tree; and

mark the map to indicate use of the header key to check and repair the level and the metadata pages of the level to avoid cyclic repairs to the dense tree.

12. The system of claim 10 wherein the storage I/O stack when executed to configure the consistency checker is further operable to:

process check and repair operations directed to the volume metadata of the regions using a plurality of services;

distribute the check and repair operations among the regions;

map each region to a service; and

execute the check and repair operations on the volume metadata of the regions in parallel across the regions.

13. The system of claim 12 wherein the services are threads of execution on processors of the node.

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

use a generation number within a level header of each level of the dense tree to uniquely identify the level header within the volume family;

determine whether the generation number is corrupted; and

,

if the generation number is corrupted, assign a new generation number to the level header that does not collide with other generation numbers in the volume family.

15. The system of claim 14 wherein the volumes of the volume family include a parent volume and one of a snapshot volume and a clone volume.

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

ensure that the level header of the parent volume has a greatest generation number of the volume family.

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

record a reference count within a level header of each level of the dense tree to track sharing of the levels between the volumes, the reference count indicating a number of pointers to a corresponding level of the dense tree;

gather an actual number of the pointers to the level header;

determine whether the actual number matches the reference count recorded in the level header; and

in response to the actual number not matching the recorded reference count, repair the reference count to reflect the actual number.

18. The system of claim 17 wherein the storage I/O stack when executed to gather the actual number is operable to:

discover that one of the pointers is corrupted;

discard the corrupted pointer; and

disregard the corrupted pointer in the actual number used to repair the reference count.

19. A non-transitory computer readable medium including program instructions for execution on one or more processors, the program instructions when executed operable to:

initiate a consistency checker to perform repairs to levels of dense trees shared among volumes of a volume family managed by a volume layer of a storage input/output (I/O) stack executing on a node, each level of each dense tree including volume metadata entries for storing metadata, the volume metadata entries organized as metadata pages according to address space regions for the volumes, each region represented by a dense tree; and

configure the consistency checker to operate in parallel on the dense trees shared among the volumes to check and repair the dense trees in a manner that minimizes use of locks when traversing the dense trees, the consistency checker further configured to render non-cyclic repairs to each dense tree that ensure that the repairs are rendered once to avoid traversing the respective dense tree multiple times for the volumes of the volume family.

20. The non-transitory computer readable medium of claim 19 wherein the program instructions when executed are further operable to:

process check and repair operations directed to the volume metadata of the regions using a plurality of services;

distribute the check and repair operations among the regions;

map each region to a service; and

execute the check and repair operations on the volume metadata of the regions in parallel across the regions.