Write operations in a tree-based distributed file system

Patent metadata

Field	Value
Publication number	US-9792309-B2
Application number	US-201414450848-A
Country	US
Kind code	B2
Filing date	Aug 4, 2014
Priority date	Aug 4, 2014
Publication date	Oct 17, 2017
Grant date	Oct 17, 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 write 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 a file system metadata tree structure that is associated with the view;
traversing the file system metadata tree structure from the first root node to arrive at 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,
upon determining that establishing a read lock on a third node exceeds 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
upon arriving at the first leaf node, establishing a write lock on the first leaf node; and

modifying the value in a leaf node associated with the metadata key,
wherein each leaf node in the file system metadata tree store 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 1 , wherein traversing the file system metadata tree comprises acquiring read locks on nodes encountered while following pointers towards the leaf node.

5. The method of claim 4 , wherein traversing the file system metadata tree further comprises acquiring a first write-lock on a first parent of a first node that has a tree identifier (treeID) that is different than a treeID of the first root node and that is encountered while following the pointers towards the leaf node.

6. The method of claim 5 , wherein traversing the file system metadata tree further comprises creating a copy of the first node that has the treeID that is different than the treeID of the first root node.

7. The method of claim 1 , wherein modifying the value comprises adding the leaf node to the file system metadata tree.

8. The method of claim 1 , wherein modifying the value comprises deleting the leaf node from the file system metadata tree.

9. The method of claim 1 , wherein modifying the value comprises changing the value in a metadata key-value pair stored in the leaf node.

10. 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.

11. 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 a file system metadata tree structure that is associated with the view,
traversing the file system metadata tree structure from the first root node to arrive at 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,
upon determining that establishing a read lock on a third node exceeds 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
upon arriving at the first leaf node, establishing a write lock on the first leaf node, and

modifying the value in a leaf node associated with the metadata key,

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

12. The system of claim 11 , 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.

13. The system of claim 12 , 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.

14. The system of claim 11 , wherein traversing the file system metadata tree comprises acquiring read locks on nodes encountered while following pointers towards the leaf node.

15. The system of claim 14 , wherein traversing the file system metadata tree further comprises acquiring a first write-lock on a first parent of a first node that has a tree identifier (treeID) that is different than a treeID of the first root node and that is encountered while following the pointers towards the leaf node.

16. The system of claim 15 , wherein traversing the file system metadata tree further comprises creating a copy of the first node that has the treeID that is different than the treeID of the first root node.

17. The system of claim 11 , wherein modifying the value comprises adding the leaf node to the file system metadata tree.

18. The system of claim 11 , wherein modifying the value comprises deleting the leaf node from the file system metadata tree.

19. The system of claim 11 , wherein modifying the value comprises changing the value in a metadata key-value pair stored in the leaf node.

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

21. 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;
identifying a first root node in a file system metadata tree structure that is associated with the view, wherein the view identifier identifies a version of the file system metadata tree to traverse;
traversing the file system metadata tree structure from the first root node to arrive at 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,
upon determining that establishing a read lock on a third node exceeds 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 root node, and
upon arriving at the first leaf node, establishing a w

Assignees

• Cohesity Inc

Inventors

• Aron Mohit
• Shanmuganathan Ganesha

Classifications

• G06F11/1448 Primary

  Management of the data involved in backup or backup restore · CPC title

• G06F16/219

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

• G06F16/2246 Primary

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

• G06F16/24562

  Pointer or reference processing operations · CPC title

• G06F16/907

  Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually · CPC title