Read operations in a tree-based distributed file system

Patent metadata

Field	Value
Publication number	US-9720926-B2
Application number	US-201414450798-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 performing a read operation on a set of file system metadata, the method comprising:
receiving a metadata key associated with a value stored in a file system metadata tree that stores file system metadata in leaf nodes, and a view identifier that identifies a view, wherein the view identifier identifies a version of the file system metadata tree to traverse;
identifying a first root node in the file system metadata tree associated with the view;
traversing the file system metadata tree from the first root node to a first leaf node associated with the metadata key, wherein traversing the file system metadata tree 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 first leaf node, and
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; and

reading the first leaf node to obtain the stored value,
wherein each leaf node in the file system metadata tree stores a single metadata key-value pair.

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

3. The method of claim 2 , wherein traversing the file system metadata tree comprises:
identifying a metadata key range that includes the metadata key and that is associated with a first pointer in the first set of pointers;
identifying a first node pointed to by the first pointer; and
traversing the file system metadata tree from the first node towards the leaf node.

4. The method of claim 3 , wherein traversing the file system metadata tree further comprises repeating the steps of identifying the metadata key range, identifying a node pointed to by a pointer, and following that node until arriving at the first leaf node.

5. The method of claim 3 , wherein traversing the file system metadata tree further comprises acquiring a first read-lock on the first node prior to reading the first node.

6. The method of claim 5 , wherein traversing the file system metadata tree further comprises acquiring a second read-lock on the root node prior to identifying the first root node, and releasing the second read-lock on the root node after acquiring the first read-lock on the first node.

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

8. The method of claim 1 , wherein the file system metadata tree includes a set of nodes that are stored in a distributed node key-value store.

9. The method of claim 8 , wherein the node key-value store comprises a distributed node key-value store.

10. A system comprising:
a processor; and
a memory storing a metadata management application, which, when executed on the processor, performs an operation, comprising:
receiving a metadata key associated with a value stored in a file system metadata tree that stores file system metadata in leaf nodes, and a view identifier that identifies a view, wherein the view identifier identifies a version of the file system metadata tree to traverse,
identifying a first root node in the file system metadata tree associated with the view,
traversing the file system metadata tree from the first root node to a first leaf node associated with the metadata key, wherein traversing the file system metadata tree 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 first leaf node, and
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, and

reading the first leaf node to obtain the stored value,

wherein each leaf node in the file system metadata tree stores a single metadata key-value pair.

11. The system of claim 10 , wherein the first root node includes a first set of pointers, and each pointer in the first set of pointers includes an indication of which nodes are found by following that pointer.

12. The system of claim 11 , wherein traversing the file system metadata tree comprises:
identifying a metadata key range that includes the metadata key and that is associated with a first pointer in the first set of pointers;
identifying a first node pointed to by the first pointer; and
traversing the file system metadata tree from the first node towards the leaf node.

13. The system of claim 12 , wherein traversing the file system metadata tree further comprises repeating the steps of identifying the metadata key range, identifying a node pointed to by a pointer, and following that node until arriving at the first leaf node.

14. The system of claim 12 , wherein traversing the file system metadata tree further comprises acquiring a first read-lock on the first node prior to reading the first node.

15. The system of claim 14 , wherein traversing the file system metadata tree further comprises acquiring a second read-lock on the root node prior to identifying the first root node, and releasing the second read-lock on the root node after acquiring the first read-lock on the first node.

16. The method of claim 10 , wherein the leaf nodes of the tree structure each include a metadata key-value pair.

17. The method of claim 10 , wherein the file system metadata tree includes a set of nodes that are stored in a distributed node key-value store.

18. The method of claim 17 , wherein the node key-value store comprises a distributed node key-value store.

19. A non-transitory computer-readable medium storing instructions that, when executed by a processor, cause the processor to perform the steps of:
receiving a metadata key associated with a value stored in a file system metadata tree that stores file system metadata in leaf nodes, and a view identifier that identifies a view, wherein the view identifier identifies a version of the file system metadata tree to traverse;
identifying a first root node in the file system metadata tree associated with the view;
traversing the file system metadata tree from the first root node to a first leaf node associated with the metadata key, wherein traversing the file system metadata tree 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 first leaf node, and
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; and

reading the first leaf node to obtain the stored value,
wherein each leaf node in the file system metadata tree stores a single metadata key-value pair.

20. The non-transitory computer-readable medium of claim 19 , wherein:
the file system metadata tree includes a set of nodes that are stored in a distributed node key-value store; and
the node key-value store comprises a distributed node key-value store.

Assignees

• Cohesity Inc

Inventors

• Aron Mohit
• Shanmuganathan Ganesha

Classifications

• G06F16/16 Primary

  File or folder operations, e.g. details of user interfaces specifically adapted to file systems · CPC title

• G06F16/219

  Managing data history or versioning (querying versioned data G06F16/2474; querying temporal data G06F16/2477) · CPC title

• G06F17/30309

  Physics · mapped topic

• G06F17/30115 Primary

  Physics · mapped topic