Determining differences between two versions of a file directory tree structure

Patent metadata

Field	Value
Publication number	US-11556501-B2
Application number	US-202016818547-A
Country	US
Kind code	B2
Filing date	Mar 13, 2020
Priority date	Mar 20, 2019
Publication date	Jan 17, 2023
Grant date	Jan 17, 2023

Abstract

A file directory tree structure of a selected storage snapshot is dynamically divided into different portions. A plurality of the different file directory tree structure portions are analyzed in parallel to identify any changes of the selected storage snapshot from a previous storage snapshot. To analyze each of the plurality of the different file directory tree structure portions, a processor is further configured to traverse and compare a corresponding file directory tree structure portion of the selected storage snapshot with a corresponding portion of a file directory tree structure of the previous storage snapshot while at least another one of the plurality of the different file directory tree structure portions of the selected storage snapshot is being analyzed in parallel.

First claim

What is claimed is:

1. A method, comprising:
remotely accessing a selected storage snapshot that is stored on a primary system;
dynamically dividing, by a storage system, a file directory tree structure of the selected storage snapshot into different portions, wherein a corresponding walker is assigned to each of the different portions;
analyzing, by the storage system, a plurality of the different file directory tree structure portions in parallel to identify any changes of the selected storage snapshot from a previous storage snapshot, wherein analyzing each of the plurality of the different file directory tree structure portions includes traversing and comparing a corresponding file directory tree structure portion of the selected storage snapshot with a corresponding portion of a file directory tree structure of the previous storage snapshot while at least another one of the plurality of the different file directory tree structure portions of the selected storage snapshot is being analyzed in parallel, wherein traversing and comparing the corresponding file directory tree structure portion of the selected storage snapshot with the corresponding portion of the file directory tree structure of the previous storage snapshot at least includes:
a first directory walker associated with the selected storage snapshot traversing a corresponding assigned portion of the file directory tree structure associated with the selected storage snapshot based on a directory tuple of the first directory walker associated with the selected storage snapshot,
a second directory walker associated with the previous storage snapshot traversing a corresponding assigned portion of the file directory tree structure associated with the previous storage snapshot based on the directory tuple associated with the second directory walker associated with the selected storage snapshot, wherein the directory tuple of the first directory walker associated with the selected storage snapshot is the same as the directory tuple of the second directory walker associated with the previous storage snapshot, and
a differ identifying one or more changes that includes one or more additions and/or one or more removals of file directory tree structure nodes between the corresponding assigned portion of the file directory tree structure associated with the selected storage snapshot and the corresponding assigned portion of the file directory structure associated with the previous storage snapshot based on a comparison of a traversal of the first directory walker with a traversal of the second directory walker; and

performing an incremental backup of the file directory tree structure of the primary system in part by:
requesting, by the storage system, data associated with the identified changes,
receiving from the primary system and storing by the storage system the requested data associated with the identified changes, and
generating, by the storage system, a backup version of the file directory tree structure of the selected storage snapshot based on the requested data.

2. The method of claim 1 , further comprising traversing at least a portion of the file directory tree structure of the selected storage snapshot in a determined order.

3. The method of claim 2 , wherein the determined order is a preorder traversal with a lexicographical order of children nodes.

4. The method of claim 1 , wherein dynamically dividing the file directory tree structure of the selected storage snapshot into the different portions further comprises assigning a corresponding directory differ to each of the different portions.

5. The method of claim 4 , wherein the corresponding directory differ is associated with a first corresponding directory walker and a second corresponding directory walker.

6. The method of claim 5 , wherein the first corresponding directory walker is configured to traverse the corresponding portion of the file directory tree structure of the selected storage snapshot and the second corresponding directory walker is configured to traverse the corresponding portion of the file directory tree structure of the previous storage snapshot.

7. The method of claim 1 , wherein the directory tuple at least indicates a root node associated with the first directory walker and the second directory walker, a starting node associated with the first directory walker and the second directory walker, and an ending node associated with the first directory walker and the second directory walker.

8. The method of claim 4 , wherein the corresponding directory differ is configured to maintain a data structure that associates the first directory walker and the second directory walker with the directory tuple.

9. The method of claim 5 , wherein the first corresponding directory walker and the second corresponding directory walker are configured to provide checkpoint information to the corresponding directory differ and the corresponding directory differ is configured to update a checkpoint data store based on the checkpoint information.

10. The method of claim 9 , wherein the corresponding directory differ is configured to identify one or more differences associated with the corresponding portion of the file directory tree structure of the selected storage snapshot and the corresponding portion of the file directory tree structure of the previous storage snapshot based on the checkpoint information included in the checkpoint data store.

11. The method of claim 9 , wherein a traversal of the corresponding portion of the file directory tree structure of the selected storage snapshot and the corresponding portion of the file directory tree structure of the previous storage snapshot is resumed from a location based on the checkpoint data store.

12. The method of claim 9 , wherein a primary directory differ is configured to generate one or more consolidated checkpoint data stores based on corresponding checkpoint data stores received from the plurality of directory differs, wherein the one or more consolidated checkpoint data stores are used to perform a subsequent incremental backup of the file directory tree structure.

13. The method of claim 12 , wherein the subsequent incremental backup of the file directory tree structure is divided based on the one or more consolidated checkpoint data stores.

14. The method of claim 12 , wherein performing the subsequent incremental backup of the file directory tree structure includes comparing node information included in the one or more consolidated checkpoint data stores to node information determined from a traversal of a subsequent version of the file directory tree structure.

15. The method of claim 1 , wherein dynamically dividing the file directory tree structure of the selected storage snapshot into the different portions at least includes:
determining a root node of the file directory tree structure of the selected storage snapshot;
determining a level of the file directory tree structure of the selected storage snapshot below the root node of the file directory tree structure of the selected storage snapshot; and
determining a plurality of nodes associated with the level of the file directory tree structure of the selected storage snapshot.

16. A non-transitory computer readable storage medium and comprising computer instructions for:
remotely accessing a selected storage snapshot that is stored on a primary system;
dynamically dividing, by a storage system, a file directory tree structure of the selected storage snapshot into different portions, wherein a corresponding walker is assigned to each of the different portions

Assignees

• Cohesity Inc

Inventors

• Pogde Prashant
• Gupta Apurv
• Cai Zheng
• Murugesan Sureshbabu
• Thomas Markose

Classifications

• G06F16/128 Primary

  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

• G06F11/1464

  for networked environments · CPC title

• G06F11/1451

  by selection of backup contents · CPC title

• G06F16/278

  Data partitioning, e.g. horizontal or vertical partitioning · CPC title

• G06F16/1858

  Parallel file systems, i.e. file systems supporting multiple processors · CPC title