# US 10,311,021 B1 · Systems and methods for indexing backup file metadata

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,311,021 B1
- Document ID: US10311021B1
- Status: Granted
- Kind: B1
- Application number: 13/368,692
- Filed: 2012-02-08
- Granted: 2019-06-04
- Earliest claimed: 2012-02-08
- Assignees: Veritas Technologies LLC
- Applicants: Biju Pillai; Gaurav Makin; Nilesh Telang
- Inventors: Biju Pillai; Gaurav Makin; Nilesh Telang
- Web page: https://patentgrep.com/patent/US10311021B1

## CPC

- G06F 16/128: {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)}
- G06F 16/137: {Hash-based (content-based indexing of textual data G06F16/31)}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A computer-implemented method for indexing backup file metadata may include 1) identifying a request to perform a full backup of a volume, 2) identifying a file metadata index for previous backups of the volume, 3) adding a current key uniquely identifying the file within the full backup and an identifier of the full backup to the file metadata index, 4) comparing the current key to the file metadata index to determine whether the current key is represented in the file metadata index, and 5) adding file metadata to the file metadata index for each file within the volume that is uniquely represented by the current key of the file within the file metadata index. Various other methods, systems, and computer-readable media are also disclosed.

## Claims

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 2)

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.

### Claim 4 (depends on 1)

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.

### Claim 5 (depends on 1)

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.

### Claim 6 (depends on 5)

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.

### Claim 7 (depends on 1)

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.

### Claim 8 (depends on 7)

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.

### Claim 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.

### Claim 10 (depends on 9)

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.

### Claim 11 (depends on 10)

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.

### Claim 12 (depends on 9)

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.

### Claim 13 (depends on 9)

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.

### Claim 14 (depends on 9)

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.

### Claim 15 (depends on 9)

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.

### Claim 16 (depends on 15)

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.

### Claim 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.

### Claim 18 (depends on 17)

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.

### Claim 19 (depends on 18)

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.

### Claim 20 (depends on 17)

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.