Granted Patent B1

US 10,311,021 · App. 13/368,692 · Granted Jun 4, 2019

Inventors: Biju Pillai (Pune, IN); Gaurav Makin (Roseville, MN); Nilesh Telang (Pune, IN)

Assignee: Veritas Technologies LLC

G06F16/128G06F16/137

Abstract

Claims (122)

1. A computer-implemented method for ensuring single-instance storage of file metadata across multiple backups, at least a portion of the method being performed by a computing device comprising at least one processor, the method comprising:

in response to identifying a request to perform a full backup of a volume of data, identifying a file metadata index, wherein:

the file metadata index includes file metadata records for files included in a plurality of previous backups of the volume of data;

each of the file metadata records comprises:

a key-identifier pair comprising both (1) a key uniquely identifying a corresponding file within one of the previous backups and (2) an identifier of the previous backup; and

file metadata of the corresponding file at the time of the previous backup; and

the file metadata index comprises a plurality of subindices, each of which comprises a subset of the file metadata records; and

updating the file metadata index to include file metadata records for both the plurality of previous backups and the full backup such that, for each file within the volume of data, only a single instance of each version of metadata of the file is stored across the plurality of previous backups and the full backup, wherein updating the file metadata index comprises, for each file within the volume of data:

generating a current key for the file using a combination of at least two metadata attributes of the file capable of uniquely identifying the file in its current version;

adding a new key-identifier pair to the file metadata index, the new key-identifier pair comprising both (1) the current key and (2) an identifier of the full backup;

generating a hash of the current key and applying a mapping function to the hash to select, for the new key-identifier pair, a subindex from the plurality of subindices;

comparing the current key to the key-identifier pairs already included in the selected subindex to determine whether the current key is already represented in the file metadata index;

adding file metadata to the file metadata index for each file within the volume of data that is uniquely represented by the current key of the file within the selected subindex; and

not adding file metadata to the file metadata index for each file within the volume of data that is already represented by one of the keys within the key-identifier pairs already included in the selected subindex.

2. The computer-implemented method of claim 1 , wherein:

the previous backups comprise at least one previous full backup; and

the at least one previous full backup comprises a result of a procedure to duplicate data of an entirety of the volume of data.

3. The computer-implemented method of claim 2 , further comprising:

performing the full backup in response to the request to perform the full backup;

associating the full backup with the file metadata index;

receiving a restoration request to restore the volume of data from the full backup; and

in response to the restoration request:

restoring each file within the volume of data from the full backup; and

restoring file metadata for each file within the volume of data from the file metadata index.

4. The computer-implemented method of claim 1 , wherein the combination of metadata attributes comprises at least one of:

a file path of the file;

a modification time of the file; and

an owner name of the file.

5. The computer-implemented method of claim 1 , wherein:

the previous backups of the volume of data comprise a first previous backup and a second previous backup;

the first previous backup comprises an original file;

the second previous backup comprises a modified version of the original file that includes one or more changes to the original file;

the full backup comprises the modified version of the original file that has not been changed since the second previous backup was performed; and

the method further comprises:

at the time the first previous backup is performed, adding, to the file metadata index, a first key-identifier pair that comprises a first key uniquely identifying the original file;

at the time the second previous backup is performed, adding, to the file metadata index, a second key-identifier pair that comprises a second key uniquely identifying the modified version of the original file; and

in response to the request to perform the full backup:

adding, to the file metadata index, a new key-identifier pair comprising a current key uniquely identifying the modified version of the original file;

determining, by comparing the current key uniquely identifying the modified version of the original file to the key-identifier pairs already included in the file metadata index, that the current key uniquely identifying the modified version of the original file is already represented by the second key; and

not adding metadata to the file metadata index for the modified version of the original file in response to determining that the current key uniquely identifying the modified version of the original file is already represented by the second key.

6. The computer-implemented method of claim 5 , further comprising, at the time the second previous backup is performed:

determining, by comparing the second key to the key-identifier pairs added to the file metadata index at the time the first previous backup was performed, that the modified version of the original file is uniquely represented by the second key; and

adding metadata to the file metadata index for the modified version of the original file in response to determining that the modified version of the original file is uniquely represented by the second key.

7. The computer-implemented method of claim 1 , wherein each of the file metadata records comprises file metadata used to at least one of:

identify files within the volume of data; and

describe files within the volume of data.

8. The computer-implemented method of claim 7 , wherein the file metadata comprises at least one of:

a file name;

a document title;

a file creator identifier;

a file owner identifier;

a file creation time;

a file modification time;

a file access time;

a file permission;

a file size;

a tag;

a security attribute; and

a reparse point.

9. A system for ensuring single-instance storage of file metadata across multiple backups, the system comprising:

an identification module, stored in memory, programmed to:

identify a request to perform a full backup of a volume of data; and

in response to the request to perform the full backup, identify a file metadata index, wherein:

the file metadata index includes file metadata records for files included in a plurality of previous backups of the volume of data;

each of the file metadata records comprises:

a key-identifier pair comprising both (1) a key uniquely identifying a corresponding file within one of the previous backups and (2) an identifier of the previous backup; and

file metadata of the corresponding file at the time of the previous backup; and

the file metadata index comprises a plurality of subindices, each of which comprises a subset of the file metadata records;

a key module, a comparison module, and an addition module, stored in memory, programmed to update the file metadata index to include file metadata records for both the plurality of previous backups and the full backup such that, for each file within the volume of data, only a single instance of each version of metadata of the file is stored across the plurality of previous backups and the full backup, wherein updating the file metadata index comprises, for each file within the volume of data:

generating a current key for the file using a combination of at least two metadata attributes of the file capable of uniquely identifying the file in its current version;

adding a new key-identifier pair to the file metadata index, the new key-identifier pair comprising both (1) current key and (2) an identifier of the full backup;

generating a hash of the current key and applying a mapping function to the hash to select, for the new key-identifier pair, a subindex from the plurality of subindices;

comparing the current key to the key-identifier pairs already included in the selected subindex to determine whether the current key is already represented in the file metadata index;

adding file metadata to the file metadata index for each file within the volume of data that is uniquely represented by the current key of the file within the selected subindex; and

not adding file metadata to the file metadata index for each file within the volume of data that is already represented by one of the keys within the key-identifier pairs already included in the selected subindex; and

at least one physical processor configured to execute the identification module, the key module, the comparison module, and the addition module.

10. The system of claim 9 , further comprising a backup module programmed to:

perform the full backup in response to the request to perform the full backup; and

associate the full backup with the file metadata index.

11. The system of claim 10 , further comprising a restoration module programmed to:

receive a restoration request to restore the volume of data from the full backup; and

in response to the restoration request:

restore each file within the volume of data from the full backup; and

restore file metadata for each file within the volume of data from the file metadata index.

12. The system of claim 9 , wherein the combination of metadata attributes comprises at least one of:

a file path of the file;

a modification time of the file; and

an owner name of the file.

13. The system of claim 9 , wherein the addition module adds file metadata to the file metadata index by storing the file metadata within the file metadata index.

14. The system of claim 9 , wherein the addition module adds file metadata to the file metadata index by:

storing the file metadata in a separate repository; and

linking to the file metadata in the separate repository from the file metadata index.

15. The system of claim 9 , wherein applying the mapping function to the hash comprises applying a modulus to the hash equivalent to the number of subindices.

16. The system of claim 15 , wherein applying the mapping function to the hash comprises at least one of:

dividing a hash space associated with the hash into ranges; and

selecting a hash function that maps directly to the number of subindices.

17. A non-transitory computer-readable-storage medium comprising one or more computer-executable instructions that, when executed by at least one processor of a computing device, cause the computing device to:

in response to identifying a request to perform a full backup of a volume of data, identify a file metadata index, wherein:

the file metadata index includes file metadata records for files included in a plurality of previous backups of the volume of data;

each of the file metadata records comprises:

a key-identifier pair comprising both (1) a key uniquely identifying a corresponding file within one of the previous backups and (2) an identifier of the previous backup; and

file metadata of the corresponding file at the time of the previous backup; and

the file metadata index comprises a plurality of subindices, each of which comprises a subset of the file metadata records; and

update the file metadata index to include file metadata records for both the plurality of previous backups and the full backup such that, for each file within the volume of data, only a single instance of each version of metadata of the file is stored across the plurality of previous backups and the full backup, wherein updating the file metadata index comprises, for each file within the volume of data:

generating a current key for the file using a combination of at least or more metadata attributes of the file capable of uniquely identifying the file in its current version;

adding a new key-identifier pair to the file metadata index, the new key-identifier pair comprising both (1) the current key and (2) an identifier of the full backup;

generating a hash of the current key and applying a mapping function to the hash to select, for the new key-identifier pair, a subindex from the plurality of subindices;

comparing the current key to the key-identifier pairs already included in the selected subindex to determine whether the current key is already represented in the file metadata index;

adding file metadata to the file metadata index for each file within the volume of data that is uniquely represented by the current key of the file within the selected subindex; and

not adding file metadata to the file metadata index for each file within the volume of data that is already represented by one of the keys within the key-identifier pairs already included in the selected subindex.

18. The non-transitory computer-readable-storage medium of claim 17 , wherein the one or more computer-executable instructions further cause the computing device to:

perform the full backup in response to the request; and

associate the full backup with the file metadata index.

19. The non-transitory computer-readable-storage medium of claim 18 , wherein the one or more computer-executable instructions further cause the computing device to:

receive a restoration request to restore the volume of data from the full backup; and

in response to the restoration request:

restore each file within the volume of data from the full backup; and

restore file metadata for each file within the volume of data from the file metadata index.

20. The non-transitory computer-readable-storage medium of claim 17 , wherein the combination of metadata attributes comprises at least one of:

a file path of the file;

a modification time of the file; and

an owner name of the file.

Assignments (14)