Systems and methods for indexing backup file metadata

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.

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.