Backup operations in a tree-based distributed file system

Patent metadata

Field	Value
Publication number	US-9720947-B2
Application number	US-201414450730-A
Country	US
Kind code	B2
Filing date	Aug 4, 2014
Priority date	Aug 4, 2014
Publication date	Aug 1, 2017
Grant date	Aug 1, 2017

Abstract

Techniques for cloning, writing to, and reading from file system metadata. Cloning involves identifying a first set of pointers included in a first root node in a file system metadata tree structure that stores file system metadata in leaf nodes of the tree structure, creating a first copy of the first root node that includes the first set of pointers, creating a second copy of the first root node that includes the first set of pointers, associating the first copy with a first view, and associating the second copy with a second view. Reading generally involves traversing the tree structure towards a target leaf node that contains data to be read. Writing generally involves traversing the tree structure in the same manner, but also creating copies of any nodes to be modified if those nodes are deemed to have a different treeID than a particular root node.

First claim

What is claimed is:

1. A method for creating a backup copy of a set of file system metadata, the method comprising:
identifying a first set of pointers included in a first root node in a file system metadata tree structure that stores file system metadata in leaf nodes of the tree structure;
creating a first copy of the first root node that includes the first set of pointers;
creating a second copy of the first root node that includes the first set of pointers;
associating the first copy with a first view, wherein the first view represents a current state of the file system metadata;
associating the second copy with a second view, wherein the second view represents a snapshot in time of the file system metadata; and
modifying metadata in one or more leaf nodes of the tree structure, wherein the modifying comprises:
establishing a read lock on the first root node and one or more second nodes on a path between the first root node and the one or more leaf nodes,
upon determining that establishing a read lock on a third node exceeds a threshold number of read locks, releasing the read lock on a second node closest to the first root node and establishing a read lock on the third node,
generating one or more new leaf nodes by copying the one or more leaf nodes,
associating the one or more leaf nodes of the tree structure with the second view, and
associating the one or more new leaf nodes with the first view.

2. The method of claim 1 , wherein identifying the first set of pointers comprises reading the first root node and acquiring a read-lock on the first root node prior to reading the first root node.

3. The method of claim 1 , wherein identifying the first set of pointers comprises reading the first root node by performing a node-lookup operation with a node key.

4. The method of claim 1 , further comprising deleting the first root node.

5. The method of claim 1 , wherein:
the first root node includes a first tree identifier (treeID), the first copy has a second treeID, and the second copy has a third treeID; and
the first root node, the first copy, and the second copy each have a distinct treeID.

6. The method of claim 1 , wherein each pointer in the first set of pointers includes an indication of which nodes are found by following that pointer.

7. The method of claim 1 , wherein each leaf node of the tree structure stores a metadata key-value pair.

8. A system comprising:
a processor; and
a memory storing a metadata management application, which, when executed on the processor, performs an operation, comprising:
identifying a first set of pointers included in a first root node in a file system metadata tree structure that stores file system metadata in leaf nodes of the tree structure,
creating a first copy of the first root node that includes the first set of pointers,
creating a second copy of the first root node that includes the first set of pointers,
associating the first copy with a first view, wherein the first view represents a current state of the file system metadata,
associating the second copy with a second view, wherein the second view represents a snapshot in time of the file system metadata, and
modifying metadata in one or more leaf nodes of the tree structure, wherein the modifying comprises establishing a read lock on the first root node and one or more second nodes on a path between the first root node and the one or more leaf nodes, upon determining that establishing a read lock on a third node exceeds a threshold number of read locks, releasing the read lock on a second node closest to the first root node and establishing a read lock on the third node, generating one or more new leaf nodes by copying the one or more leaf nodes, generating one or more new leaf nodes, associating the one or more leaf nodes of the tree structure with the second view, and associating the one or more new leaf nodes with the first view.

9. The system of claim 8 , wherein identifying the first set of pointers comprises reading the first root node and acquiring a read-lock on the first root node prior to reading the first root node.

10. The system of claim 8 , wherein identifying the first set of pointers comprises reading the first root node by performing a node-lookup operation with a node key.

11. The system of claim 8 , wherein the operation further comprises deleting the first root node.

12. The system of claim 8 , wherein:
the first root node includes a first tree identifier (treeID), the first copy has a second treeID, and the second copy has a third treeID; and
the first root node, the first copy, and the second copy each have a distinct treeID.

13. The system of claim 8 , wherein each pointer in the first set of pointers includes an indication of which nodes are found by following that pointer.

14. The system of claim 8 , wherein each leaf node of the tree structure stores a metadata key-value pair.

15. A non-transitory computer-readable medium storing instructions that, when executed by a processor, cause the processor to perform the steps of:
identifying a first set of pointers included in a first root node in a file system metadata tree structure that stores file system metadata in leaf nodes of the tree structure;
creating a first copy of the first root node that includes the first set of pointers;
creating a second copy of the first root node that includes the first set of pointers;
associating the first copy with a first view, wherein the first view represents a current state of the file system metadata;
associating the second copy with a second view, wherein the second view represents a snapshot in time of the file system metadata; and
modifying metadata in one or more leaf nodes of the tree structure, wherein the modifying comprises establishing a read lock on the first root node and one or more second nodes on a path between the first root node and the one or more leaf nodes, upon determining that establishing a read lock on a third node exceeds a threshold number of read locks, releasing the read lock on a second node closest to the first root node and establishing a read lock on the third node, generating one or more new leaf nodes by copying the one or more leaf nodes, generating one or more new leaf nodes, associating the one or more leaf nodes of the tree structure with the second view, and associating the one or more new leaf nodes with the first view.

16. The non-transitory computer-readable medium of claim 15 , wherein each leaf node of the tree structure stores a metadata key-value pair.

Assignees

• Cohesity Inc

Inventors

• Aron Mohit
• Shanmuganathan Ganesha

Classifications

• G06F16/128

  Details of file system snapshots on the file-level, e.g. snapshot creation, administration, deletion (error detection or correction of the data by redundancy in operations or in hardware G06F11/14, G06F11/16) · CPC title

• G06F16/2246 Primary

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

• G06F2201/84

  Using snapshots, i.e. a logical point-in-time copy of the data · CPC title

• G06F16/1873

  Versioning file systems, temporal file systems, e.g. file system supporting different historic versions of files · CPC title

• G06F11/1435 Primary

  using file system or storage system metadata · CPC title