US 2021/0064580 A1 · FAST ALGORITHM TO FIND FILE SYSTEM DIFFERENCE FOR DEDUPLICATION

Abstract

The disclosure provides techniques for deduplicating files. The techniques include, upon creating or modifying a file, placing a logical timestamp of the current logical time, within a queue associated with the directory of the file. The techniques further include placing the logical timestamp within a queue of each parent directory of the directory of the file. To determine a set of files for deduplication, the techniques disclosed herein identify files that have been modified within a logical time range. The set of files modified within a logical time is identified by traversing directories of a storage system, the directories being organized within a tree structure. If a directory's queue does not contain a timestamp that is within the logical time range, then all child directories can be skipped over for further processing, such that no files within the child directories end up being within the set of files for deduplication.

Claims20

Dependent claims

A method of deduplicating one or more files within a storage system, the one or more files organized within a tree of directories, the method comprising:

modifying or creating a first file, wherein the first file is located within a first directory and is a child of the first directory;
responsive to the modifying or creating the first file, (a) marking with a timestamp the first directory, and (b) marking with the timestamp each parent directory of the first directory that is not already marked with the timestamp;
determining a time range;
identifying directories of the tree of directories marked with a corresponding timestamp within the time range, wherein the identified directories comprise the first directory;
searching within the identified directories to identify files modified or created during the time range, wherein the identified files comprise the first file;
and
deduplicating the identified files.

4 more elements

A non-transitory computer readable medium comprising instructions to be executed in a processor of a computer system, the instructions when executed in the processor cause the computer system to carry out a method of deduplicating one or more files within a storage system, the one or more files organized within a tree of directories, the method comprising:

modifying or creating a first file, wherein the first file is located within a first directory and is a child of the first directory;
responsive to the modifying or creating the first file, (a) marking with a timestamp the first directory, and (b) marking with the timestamp each parent directory of the first directory that is not already marked with the timestamp;
determining a time range;
identifying directories of the tree of directories marked with a corresponding timestamp within the time range, wherein the identified directories comprise the first directory;
searching within the identified directories to identify files modified or created during the time range, wherein the identified files comprise the first file;
and
deduplicating the identified files.

4 more elements

A computer system comprising:

a storage system;
and
at least one processor, wherein the at least one processor is programmed to carry out a method of deduplicating one or more files within the storage system, the one or more files organized within a tree of directories, the method comprising:
modifying or creating a first file, wherein the first file is located within a first directory and is a child of the first directory;
responsive to the modifying or creating the first file, (a) marking with a timestamp the first directory, and (b) marking with the timestamp each parent directory of the first directory that is not already marked with the timestamp;
determining a time range;
identifying directories of the tree of directories marked with a corresponding timestamp within the time range, wherein the identified directories comprise the first directory;
searching within the identified directories to identify files modified or created during the time range, wherein the identified files comprise the first file;
and
deduplicating the identified files.

7 more elements

Dependencies are inferred from the claim text.

Fast algorithm to find file system difference for deduplication

Life of this patent

Fast algorithm to find file system difference for deduplication

Life of this patent

Abstract

Claims20