Backup operations in a tree-based distributed file system

Patent metadata

Field	Value
Publication number	US-11892995-B2
Application number	US-202117475060-A
Country	US
Kind code	B2
Filing date	Sep 14, 2021
Priority date	Aug 4, 2014
Publication date	Feb 6, 2024
Grant date	Feb 6, 2024

Abstract

Techniques for cloning, writing to, and reading from file system metadata. Cloning involves identifying a first set of pointers included h a first root node in a file system metadata tree structure that stores file system metadata n 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, comprising:
receiving, at a first storage appliance of a distributed storage system that includes a plurality of storage appliances, a request to perform an operation associated with a key-value pair in a current view of a metadata tree structure, wherein the current view of the metadata tree structure is associated with a view identifier;
traversing, by the first storage appliance, the current view of the metadata tree structure from a root node to a target node of a plurality of encountered nodes, wherein traversing the metadata tree structure from the root node to the target node includes:
obtaining a corresponding lock for each of the plurality of encountered nodes;
comparing a view identifier associated with current view of the metadata tree structure to a view identifier associated with one or more encountered nodes of the plurality of encountered nodes;
releasing the corresponding lock for a previously encountered node of the one or more encountered nodes that is a threshold number of levels above a particular node of the one or more encountered nodes, wherein the corresponding lock for the root node is maintained throughout the traversal; and
creating a local copy of the particular node of the one or more encountered nodes in response to determining that the view identifier associated with current view of the metadata tree structure does not match the view identifier associated with the encountered node, wherein creating the local copy of the particular node of the one or more encountered nodes includes determining that a degree of the particular node meets a threshold degree and adding one or more additional nodes to the metadata tree structure in response to determining that the degree of the particular node meets the threshold degree; and

performing the operation associated with the key-value pair.

2. The method of claim 1 , wherein the operation is a modify-value operation.

3. The method of claim 2 , wherein the target node is a leaf node that stores the key-value pair.

4. The method of claim 3 , wherein the local copy of the particular node is a local copy of an intermediate node that points to the leaf node that stores the key-value pair.

5. The method of claim 4 , further comprising:
copying the leaf node that stores the key-value pair; and
modifying a pointer of the local copy of the intermediate node to reference the copied leaf node instead of the leaf node that stores the key-value pair.

6. The method of claim 1 , wherein the operation is an add-key operation.

7. The method of claim 6 , wherein the target node is an intermediate node.

8. The method of claim 7 , wherein performing the operation associated with the key-value pair includes creating a new leaf node to which the intermediate node points.

9. The method of claim 1 , further comprising obtaining read locks for the root node and the one or more encountered nodes.

10. The method of claim 1 , wherein the key-value pair stores file system metadata.

11. The method of claim 1 , wherein traversing the metadata tree structure from the root node to the target node further includes obtaining a write lock on a parent node of an encountered node of the one or more encountered nodes that has a view identifier that does not match the view identifier associated with the current view of the metadata tree structure.

12. The method of claim 1 , further comprising storing an encountered node of the one or more encountered in a cache of the first storage appliance.

13. A computer program product, the computer program product being embodied in a non-transitory computer readable storage medium and comprising computer instructions for:
receiving, at a first storage appliance of a distributed storage system that includes a plurality of storage appliances, a request to perform an operation associated with a key-value pair in a current view of a metadata tree structure, wherein the current view of the metadata tree structure is associated with a view identifier;
traversing, by the first storage appliance, the current view of the metadata tree structure from a root node to a target node of a plurality of encountered nodes, wherein traversing the metadata tree structure from the root node to the target node includes:
obtaining a corresponding lock for a plurality of encountered nodes;
comparing a view identifier associated with current view of the metadata tree structure to a view identifier associated with one or more encountered nodes of the plurality of encountered nodes;
releasing the corresponding lock for a previously encountered node of the one or more encountered nodes that is a threshold number of levels above a particular node of the one or more encountered nodes, wherein the corresponding lock for the root node is maintained throughout the traversal; and
creating a local copy of the particular node of the one or more encountered nodes in response to determining that the view identifier associated with current view of the metadata tree structure does not match the view identifier associated with the encountered node, wherein creating the local copy of the particular node of the one or more encountered nodes includes determining that a degree of the particular node meets a threshold degree and adding one or more additional nodes to the metadata tree structure in response to determining that the degree of the particular node meets the threshold degree; and

performing the operation associated with the key-value pair.

14. The computer program product of claim 13 , wherein the operation is a modify-value operation.

15. The computer program product of claim 13 , wherein the operation is an add-key operation.

16. A system, comprising:
a processor of a first storage appliance of a distributed storage system that includes a plurality of storage appliances, wherein the processor is configured to:
receive a request to perform an operation associated with a key-value pair in a current view of a metadata tree structure, wherein the current view of the metadata tree structure is associated with a view identifier;
traverse the current view of the metadata tree structure from a root node to a target node of a plurality of encountered nodes, wherein to traverse the metadata tree structure from the root node to the target node, the processor is further configured to:
obtaining a corresponding lock for each of the plurality of encountered nodes;
compare a view identifier associated with current view of the metadata tree structure to a view identifier associated with one or more encountered nodes of the plurality of encountered nodes;
release the corresponding lock for a previously encountered node of the one or more encountered nodes that is a threshold number of levels above a particular node of the one or more encountered nodes, wherein the corresponding lock for the root node is maintained throughout the traversal; and
create a local copy of the particular node of the one or more encountered nodes in response to determining that the view identifier associated with current view of the metadata tree structure does not match the view identifier associated with the encountered node, wherein to create the local copy of the particular node of the one or more encountered nodes, the processor is configured to determine that a degree of the particular node meets a threshold degree and adding one or more additional nodes to the metadata tree structure in response to determining that the degree of the particular node meets the threshold degree; and

perform the operation associated with the key-value pair; and

Assignees

• Cohesity Inc

Inventors

• Aron Mohit
• Shanmuganathan Ganesha

Classifications

• G06F16/2246 Primary

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

• G06F11/1435 Primary

  using file system or storage system metadata · CPC title

• 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/1873

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

• G06F2201/84

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